Мы рассмотрим те же самые два случая потоков нагрузки, о которых говорили в Лекциях 7 и 8.
Пуассоновский поток вызовов (бесконечное число источников) и экспоненциально распределенное время обслуживания (
С этими параметрами мы будем иметь дело в секции 12.2. В секции12.3 будет показано, как для оптимизации системы может быть применен Принцип Мо. В секции 12.4. вычисляется распределение времени ожидания для основной дисциплины обслуживания - Первый Прибыл Первый обслужен (
PCT -IIРассмотрим систему с ожиданием $$M/M/n$$. Она обслуживает Пуассоновский поток вызовов ( $$M$$ ), имеет экспоненциальное время обслуживания ( $$M$$ ) и n обслуживающих приборов при бесконечном числе мест ожидания. Состояние системы определяется как общее количество пользователей в системе (или в обслуживании, или ожидающих в очереди).
(рис 12.1) Диаграмма переходов состояний M/M/n системы с ожиданием, имеющей n серверов и неограниченное число мест ожидания.Нас интересуют вероятности устойчивых состояний системы. В секции 7.4 дана диаграмма переходов между состояниями (рис.12.1). Принимая, что диаграмма находится в статистическом равновесии, получаем:
$$\lambda *p(0)=\mu *p(1),\\ \lambda *p(1)=2 \mu *p(2),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda * p(i)=(i+1) \mu * p(i+1),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda *p(n-1)=n \mu *p(n),\\ \lambda*p(n)=n \mu*p(n+1),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda*p(n+j)=n \mu*p(n+j+1).$$Если $$A = \lambda / \mu$$ - это предложенная нагрузка, то мы имеем:
$$p(i)=\begin{cases} p(0)*\frac{A^i}{i!}, 0 \le i \le n,\\ p(n)*\left ( \frac An \right )^{i-n}=p(0)*\frac{A^i}{n!*n^{i-n}}, i \ge n. \end{cases}$$С помощью нормировки вероятностей состояний получаем:
$$1=\sum_{i=0}^{\infty}p(i),\\ 1=p(0)*\left \{ 1+\frac A1+\frac{A^2}{2!}+ \dots + \frac{A^n}{n!} \left (1+\frac A1+ \frac{A^2}{n^2}+\dots \right ) \right \}.$$Внутренние фигурные скобки содержат геометрическую прогрессию с коэффициентом прогрессии $$A/n$$. Условие нормализации может быть выполнено только для:
$$A < n$$Статистическое равновесие получено лишь для $$A/n$$. Иначе очередь будет увеличиваться до бесконечности. Мы получаем значение $$p_0$$:
$$p(0)=\frac{1}{\sum_{i=0}^{n-1} \frac{A^i}{i!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n.$$Уравнения (12.2) и (12.4) показывают вероятности устойчивых состояний.
Для оценки производительности и рабочих характеристик системы нужно рассмотреть несколько характеристик. Они отражают вероятности устойчивых состояний.
Когда Пуассоновский поток вызовов не зависит от состояния системы, вероятность того, что произвольный вызов должен будет ждать обслуживания в очереди, равна пропорции времени, когда заняты все обслуживающие приборы ( свойство PASTA ). Время ожидания - случайная величина, которая обозначается $$W$$. Для произвольного поступления вызовов имеем:
$$E_{2,n}(A)=\frac{\frac{A^n}{n!} \frac{n}{n-A}}{1+\frac A1+\frac{A^2}{2!}+\dots+\frac{A^{n-1}}{(n-1)!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n.$$Эта вероятность ожидания зависит только от $$A$$, т.е.произведения $$\lambda$$ и $$s$$. Формула имеет несколько названий: C-формула Эрланга, вторая формула Эрланга или формула Эрланга для систем с ожиданием. Она имеет различные обозначения в литературе:
$$E_{2,n}(A)=D=D_n(A)=p\{W > 0\}.$$Клиенты либо обслуживаются немедленно, либо помещаются в очередь. Вероятность, что клиент обслуживается немедленно, равна:
$$S_n=1-E_{2,n}(A).$$Обслуженная нагрузка $$Y$$ равняется предложенной нагрузке $$A$$, так как ни одному вызову не отказывается в обслуживании, а процесс поступления вызовов - Пуассоновский процесс:
$$Y=\sum_{i=1}^n ip(i)+\sum_{i=n+1}^{\infty}np(i)\\ =\sum_{i=1}^n \frac{\lambda}{\mu}p(i-1)+\sum_{i=n+1}^{\infty} \frac{\lambda}{\mu}p(i-1)\\ =\frac{\lambda}{\mu}=A,$$Здесь применено уравнение равновесия.
Длина очереди - случайная величина $$L$$. Вероятность наличия клиентов в очереди в случайной точке времени:
$$p\{L > 0\}=\sum_{i=n+1}^{\infty}=\frac{\frac An}{1-\frac An}*p(n),\\ p\{L > 0\}=\frac{A}{n-A}p(n)=\frac AnE_{2,n}(A).$$Здесь использовалось (12.5).
Формула подобна B-формуле (7.10) Эрланга, за исключением коэффициента $$n/(n-A) $$ в последнем элементе. Поскольку существует очень точная рекурсивная формула для числовой оценки B-формулы Эрланга (7.29), можно использовать следующие отношения для того, чтобы получить числовые значения для C-формулы:
$$E_{2,n}(A)=\frac{n*E_{1,n}(A)}{n-A(1-E_{1,n}(A))}\\ =\frac{E_{1,n}(A)}{1-A\{1-E_{1,n}(A)\}/n}, \quad A < n.$$где элемент $$A\{1-E_{1,n} (A)\}/n$$ - средняя обслуженная нагрузка на канал в соответствующей
где $$I$$ - инверсия вероятности (7.30).
$$I_{n,2}(A)=\frac{1}{E_{2,n}(A)}.$$C-формула Эрланга была сведена в таблицу в Принципе Мо (Jensen, 1950 [50] ) и показана на рис.12.2.
(рис 12.2) C-формула Эрланга для системы с ожиданием M/M/n. Вероятность $$E_{2,n} (A) $$ для положительного времени ожидания показана как
Мы должны отличать длину очереди в произвольный момент времени и длину очереди, когда есть клиенты, стоящие в очереди.
Средняя длина очереди в произвольный момент времени
Длина очереди $$L$$ в произвольной момент времени называется виртуальной длиной очереди. Для произвольного клиента длина очереди определяется как свойство PASTA, т.е. Пуассоновский поток вызовов (математическое ожидание по времени = математическое ожидание по вызовам). Мы получаем среднюю длину очереди:
$$L_n = E \{L\}$$ в произвольный момент времени:
$$L_n=0*\sum_{i=0}p(i)+\sum_{i=n+1}^{\infty}(i-n)p(i)\\ =\sum_{i=n+1}^{\infty}i-n)p(n) \left (\frac An \right )^{i-n}\\ =p(n)*\sum_{i=1}^{\infty}i (\frac{A}{n})^{i-n}\\ =p(n)*\frac An \sum_{i=1}^{\infty} \frac{\partial}{\partial (A/n)} \left \{ \left (\frac An \right)^i \right \}.$$Поскольку $$A/n \le c \le 1$$, ряд является равномерно сходящимся, оператор дифференцирования может быть вынесен за сумму:
$$L_n=p(n) \frac An \frac{\partial}{\partial (\frac An)} \left \{ \frac{\frac An}{1-(\frac An)} \right \}=p(n)*\frac{\frac An}{\{1-(\frac An)\}^2}\\ =p(n)*\frac{n}{n-A}*\frac{A}{n-A},\\ L_n=E_{2,n}(A)*\frac{A}{n-A}.$$Средняя длина очереди, со временем ожидания больше нуля
Математическое ожидание времени и в этом случае равно математическому ожиданию вызова. Условная
Применяя (12.8) и (12.12), получаем:
$$L_{nq}=\frac{L_n}{p\{L > 0\}},$$где $$L$$ - случайная переменная, обозначающая длину очереди.
Здесь представляют интерес две характеристики:
Первая является индикатором уровня обслуживания целой системы, тогда как вторая относится к задержанным вызовам.
Математические ожидания времени будут равны математическим ожиданиям по вызовам из-за свойства PASTA.
Среднее время ожидания для всех вызовов
Формула Литла говорит, что
где $$L_n=L_n(A)$$ и $$W_n=W_n(A)$$. Рассматривая процесс поступления вызовов, из (12.12) мы имеем:
$$W_n=\frac{L_n}{\lambda}=\frac {1}{\lambda}*E_{2,n}(A)*\frac{A}{n-A}.$$Поскольку $$A = \lambda s$$, где $$s$$ - среднее время обслуживания, мы имеем:
$$W_n=E_{2,n}(A)*\frac{s}{n-A}.$$Среднее время ожидания для задержанных вызовов
Полное время ожидания является постоянным и может быть вычислено либо в среднем по всем клиентам ( $$W_n$$ ), либо только по вызовам, для которых времена ожидания ( $$w_n$$ ) имеют положительные значения (3.20):
$$W_n=w_n*E_{2,n}(A),$$ $$w_n=\frac{s}{n-A}$$Эта система наиболее часто упоминается в литературе. Вероятности состояния (12.2) определяются рядом геометрической прогрессии:
$$p(i)=(1-A)*A^i, i=0,1,2, \dots,$$поскольку $$p (0) = 1- A$$. Вероятность задержки равна:
$$Е_{2,1}(A)=А.$$С помощью уравнений 12.12, 12.14, 12.17 мы можем установить, что увеличение нагрузки из-за большего количества вызовов лучше, чем увеличение нагрузки из-за более длинного времени обслуживания, поскольку увеличение времени обслуживания увеличивает величину всех показателей. Поэтому важно, чтобы времена обслуживания системы не увеличивались в момент перегрузки.
Заметьте, что если $$A \to 0$$, мы получаем $$w_n = s/n$$ (12.17). Если клиент ожидает (что редко случается, когда $$A \to 0$$ ), то этот клиент будет единственным в очереди. Клиент должен ждать, пока сервер освободится. Это случается в конце экспоненциально распределенного временного интервала со средней величиной $$s/n$$. Поэтому $$w_n$$ никогда не может быть меньше, чем $$s/n$$.
Предельное увеличение нагрузки, которую может обслуживать система, когда мы дополняем число обслуживающих приборов, может быть выражено несколькими способами. Уменьшение отношения нагрузки канала к полной нагрузке (пропорционально числу всех вызовов от клиентов) определяется как:
$$F_{2,n}(A)=A\{E_{2,n}(A)-E_{2,n+1}(A)\}$$Уменьшение средней длины очереди (пропорционально нагрузке, которую обслуживают места ожидания) определяется формулой Литла (12.14):
$$F_{L,n}(A)=L_n(A)-L_{n+1}(A)\\ \qquad = \lambda \{W_n(A)-W_{n+1}(A)\},$$где $$W_n(A) $$ - среднее время ожидания для всех вызовов, когда предложенная нагрузка и число обслуживающих приборов - $$n$$ (12.15). Равенства (12.21) и (12.22) сведены в таблицу в Принципе Мо (Jensen, 1950 [50] ) и могут быть легко рассчитаны с помощью калькулятора или компьютера.
Mo сначала предложил свой принцип для систем организации очереди. Он изучил времена ожидания абонентов для оператора на ручных станциях Копенгагенской Телефонной Компании.
Рассмотрим $$k$$ независимости систем организации очереди. Вызов, обслуживаемый во всех $$k$$ системах, имеет полное среднее времени ожидания
$$\sum_i W_i,$$где $$W_i$$ - среднее время ожидания $$i$$ -той системы, которая имеет $$n_i$$ обслуживающих приборов и предложенную нагрузку $$A_i.$$ Стоимость канала равна переменной стоимости $$c_i$$ плюс постоянная стоимость, выраженная константой $$C_0.$$ Таким образом, общая стоимость каналов равна:
$$C=C_0+\sum_{i=1}^kn_ic_i.$$Если время ожидания также рассматривать как стоимость, то общая стоимость будет равна $$f=f (n_1, n_2 , \dots, n_k ) $$. Она должна быть свернута как функция числа $$n_i$$ каналов в отдельные системы. Если полное среднее время ожидания - $$W$$, то распределение каналов по отдельным системам определяется:
$$min\{f(n_1, n_2, \dots, n_k)\}=min \{C_0+\sum_in_ic_i+ \vartheta *\left(\sum_iW_i-W \right) \}$$где $$\vartheta$$ (тета) -
Величина $$n_i$$ является неотъемлемой частью необходимого условия для определения минимума, и можно показать, что в этом случае достаточным условием для минимума являются следующие неравенства :
$$0 < f(n_1, n_2, \dots, n_i-1, \dots, n_k)-f(n_1, n_2, \dots, n_i, \dots, n_k),\\ 0 \ge f(n_1, n_2, \dots, n_i, \dots, n_k)-f(n_1, n_2, \dots, n_i+1, \dots, n_k),$$что соответствует:
$$W_{n_i-1}(A_i)-W_{n_i}(A_i) > \frac{c_i}{\vartheta},\\ W_{n_i}(A_i)-W_{n_i+1}(A_i) \le \frac{c_i}{\vartheta},$$где $$W_{ni} (A_i ) $$ показано в (12.15).
Выраженное с помощью функции увеличения времени ожидания $$F_{W,n} (A) $$ (12.22) оптимальное решение равно:
$$F_{W,n_i-!}(A) > \frac{c_i}{\vartheta} \ge F_{W, n_i}(A), i=1,2,\dots, k$$Функция $$F_{W, n} (A) $$ сведена в таблицу в Принципе Мо (Jensen, 1950 [50] ). Подобная оптимизация может быть проведена для других функций увеличения.
Мы рассматриваем две различных $$M/M/n$$ системы организации очереди. Первая имеет среднее время обслуживания 100 с и предложенную нагрузку 20 Эрл. Отношение стоимости $$c_1/ \vartheta$$ равно 0,01. Вторая система имеет среднее время обслуживания, равное 10 с, и предложенную нагрузку 2 Эрл. Отношение стоимости равняется $$c_2 /\vartheta = 0,1$$. Таблица функции увеличения $$F_W,n (A) $$ дает:
$$n_1 = 32$$ канала и
$$n_2 = 5$$ каналов.
Средние времена ожидания:
$$W_1 = 0,075 с$$ $$W_2 = 0,199 с.$$Это показывает, что вызов, который обслуживается в обеих системах, имеет полное среднее время ожидания 0,274 с и что система с меньшим количеством каналов вносит больший вклад в среднее время ожидания.
Стоимость ожидания связана с отношением стоимости. Инвестируя больше в вышеупомянутую систему, мы уменьшаем затраты независимо от системы организации очереди. Необходимо идти на вложения, пока получаем прибыль. Исследования Мо в течение 1920-ых годов показали, что среднее время ожидания для абонентов маленьких станций с немногими операторами должно быть большим, чем среднее время ожидания при больших станциях со многими операторами.
Системы организации очереди, где дисциплина обслуживания зависит от времени поступления вызовов, все имеют одни и те же средние времена ожидания. В этом случае стратегия влияет только на распределение времен ожидания для каждого отдельного клиента. Исследование распределения времени ожидания упрощается в случае дисциплины FIFO (First In First Out). Она также называется дисциплина обслуживания в порядке поступлении. Но если обслуживающих приборов много, заявка может не обязательно покинуть обслуживающий прибор первой. Тогда дисциплина в порядке поступления рассматривается в соответствии с принципом, чтобы время выхода из очереди и начало освобождения обслуживающего прибора была началом обслуживания другой заявки.
Рассмотрим произвольный вызов. По прибытию в систему вызов или обслуживается немедленно, или должен ждать в очереди (12.6).
Предположим, что вызов, который мы рассматриваем, должен ждать в очереди, то есть система может быть в состоянии $$[n + k], (k = 0, 1, 2, \dots) $$, где $$k$$ - число занятых мест ожидания как раз перед поступлением вызова.
Наш вызов должен ждать, пока будет завершено обслуживание $$k + 1$$ вызовов, прежде чем станет доступным свободный обслуживающий прибор. Когда все $$n$$ обслуживающих приборов работают, система завершает обслуживание вызовов с постоянной скоростью $$n \mu$$, то есть процесс выхода вызовов из обслуживания является Пуассоновским процессом с данной интенсивностью. Мы используем отношения между числовым представлением и представлением с помощью интервала (5.4). Вероятность $$p(W \le t) = F(t) $$, что положительное время ожидания $$t$$ превосходит заданную величину, равна вероятности того, что в Пуассоновском потоке вызовов с интенсивностью $$n \mu$$, по крайней мере, $$(k+1) $$ вызовов поступят в течение интервала $$t$$ (6.1):
$$F(t|k \quad waiting)=\sum_{i=n+1}^{\infty} \frac{(n \mu t)^i}{i!}*e^{-n \mu t}.$$Вышеупомянутое равенство справедливо при условии, что наш вызов должен ждать в очереди. Условная вероятность, что наш вызов поступит, когда все $$n$$ обслуживающих приборов заняты и имеется $$k$$ обслуживаемых вызовов $$(k=1,2, \dots) $$, такова:
$$p_w(k)=\frac{\lambda p(n+k)}{\lambda \sum_{i=0}^{\infty}p(n+i)}=\frac{p(n)*(\frac An)^k}{p(n)*\sum_{i=0}^{\infty}(\frac An)^i}\\ =(1- \frac An)(\frac An)^k, k=0,1, \dots.$$Это геометрическое распределение, включая нулевой класс (табл. 6.1). Безусловное распределение времени ожидания тогда равно:
$$F(t)=\sum_{k=0}^{\infty}p_w(k)*F(t|k),$$ $$F(t)=\sum_{k=0}^{\infty} \left \{(1-\frac An)(\frac An)^k*\sum_{i=k+1}^{\infty} \frac{(n \mu t)^i}{i!}e^{-n \mu t} \right \}\\ =e^{-n \mu t}\sum_{i=1}^{\infty} \left \{ \frac{(n \mu t)^i}{i!}*\sum_{k=0}^{i-1}(1-\frac An)(\frac An)^k \right \},$$Когда все элементы - положительные вероятности, мы можем поменять порядок суммирования. Внутренняя сумма является геометрической прогрессией:
$$\sum_{k=0}^{i-1}(1-\frac An)(\frac An)^k=(1-\frac An)*\sum_{k=0}^{i-1}(\frac An)^k\\ =(1-\frac An)*1*\frac{1-(A/n)^i}{1-(A/n)}\\ =1-(\frac An)^i.$$Подставляя результат этой суммы, мы получаем:
$$F(t)=e^{-n \mu t}* \sum_{i=1}^{\infty} \frac{(n \mu t)^i}{i!} \left \{1-(\frac An)^i \right \}\\ =e^{-n \mu t} \left \{ \sum_{i=0}^{\infty} \frac{(n \mu t)^i}{i!}-\sum_{i=0}^{\infty} \frac{(n \mu t)^i}{i!} (\frac An)^i \right \}\\ =e^{n \mu t}\{e^{n \mu t}-e^{n \mu t*A/n}\},$$ $$F(t)=1-e^{-(n-A)\mu t},\\ F(t)=1-e^{-(n \mu - \lambda)t}, n > A, t > 0.$$то есть экспоненциальное распределение. Очевидно, существует парадокс - при поступлении вызова в систему со всеми ранее занятыми обслуживающими приборами можно:
Интерпретация этого факта - то, что взвешенная сумма распределений Эрланга с геометрически распределенными коэффициентами веса эквивалентна экспоненциальному распределению. На рис.12.3 показана диаграмма состояний для (12.30), и мы можем заметить, что она может быть сведена к единственному экспоненциальному распределению (секция 4.4.2 и рис.4.9). Формула (12.31) подтверждает, что среднее время ожидания $$w_n$$ для клиентов, которые должны ждать в очереди, определяется выражением, показанным в (12.17).
(рис 12.3)
Распределение общее время ожидания (для произвольного вызова) равно (3.19):
$$F_s(t)=1-E_{2,n}(A)*e^{-(n-A)\mu t}, A < n, t \ge 0,$$и средняя величина этого распределения - $$W_n,$$ в соответствии с (12.15).
Когда имеется только один обслуживающий прибор, вероятности состояния (12.2) представляются рядом геометрической прогрессии $$p(i)=(1 -A)^i \times Ai$$ (12.18) для всех $$i \ge 0$$. Каждый вызов занимает экспоненциально распределенный временной интервал с интенсивностью $$\lambda$$ в каждом состоянии. Вызов, который поступает в систему в состоянии $$[i] $$, должен остаться в системе, интервал времени распределен по закону Эрланга - $$(i+1) $$. Поэтому время пребывания в системе (время ожидания + время обслуживания), которое также называется временем реакции, является экспоненциально распределенным с интенсивностью $$(\mu - \lambda) $$. (см. рис. 4.9):
$$F(t)=1-e^{-(\mu - \lambda)t}, \mu > \lambda, t \ge 0.$$Это идентично распределению времени ожидания задержанных вызовов. Среднее время пребывания может быть получено непосредственно, используя $$W_1$$ из(12.20) и среднее время обслуживания $$s$$:
$$m=W_1+s=\frac{As}{1-A}+s,\\ m=\frac{s}{1-A}=\frac{1}{\mu - \lambda},$$где $$\mu = 1/s$$ - скорость обслуживания. Заметим, что среднее время пребывания в системе равно среднему времени ожидания для задержанных клиентов (12.17).
Эта модель принадлежит классу циклических систем организации очереди и соответствует чистой
Первым в 1933 г. эту модель рассмотрел Гнеденко и в 1934 г. опубликовал статью. Метод стал широко известен, когда в 1947 г. C. Пальм издал статью [80] с теоретическим анализом распределения трудовых ресурсов,
(рис 12.4) Плотность распределения для распределения времени ожидания при дисциплинах организации очереди FCFS, LCFS1 и SIRO (случайная). Во всех трех случаях среднее время ожидания для задержанных вызовов - 5 единиц времени. Коэффициент формы - 2 для FCFS, 3.33 - для LCFS и 10 - для SIRO. Число обслуживающих приборов - 10, и предложенная нагрузка - 8 Эрл. Среднее время обслуживания s = 10 единиц времени.обслуживающих автоматы. Множество $$S$$ машин, которые обычно работают автоматически, обслуживается n ремонтниками. Машины могут сломаться, и тогда понадобится ремонтник, чтобы запустить их в работу снова. Проблема состоит в том, чтобы определить число ремонтников в зависимости от числа машин так, чтобы общие стоимости были минимизированы (по-другому это называется "оптимизированная прибыль"). Машины могут быть, например, текстильными машинами, которые останавливаются, когда заканчивается нить; ремонтники тогда должны заменить пустую бобину машины полной.
Эту модель восстановления машин, или модель взаимного влияния машин, рассматривал Feller (1950 [27] ). Модель соответствует организации очереди в простой закрытой сети и успешно применяется, чтобы решить технические проблемы нагрузки в компьютерных системах. В системе обозначений Кендалла (Лекция 13) система организации очереди обозначается $$M/M/n/S$$, где $$S$$ - число клиентов и $$n$$ - число обслуживающих приборов.
Модель широко применяется на практике. В сети машины соответствуют вызовам, тогда как "ремонтники" предстают обслуживающими приборами, а "ремонтник" представляется компьютером, управляющим терминалами. В компьютерной си стеме машина может соответствовать программам, хранящимся на диске, а ремонтники представляют каналы ввода-вывода ( ввод-вывод ). Далее мы рассмотрим систему компьютерных терминалов, как основу для развития теории.
Режим разделения времени - лучшее решение для оптимального обслуживания большой группы источников нагрузки использующих, например, терминалы, подключенные к универсальному компьютеру. Отдельный пользователь должен чувствовать себя так, как будто он - единственный пользователь компьютера (рис.12.5).
(рис 12.5) Модель восстановления машин Пальма. Компьютерная система с S терминалами (диалоговая система) соответствует системе с ожиданием и с ограниченным числом источников (см. случай Энгсета для систем с потерями).
Отдельный терминал находится все время в одном из двух состояний (диалоговый режим) (рис.12.6):
(рис 12.6) Отдельный терминал может быть в трех различных состояниях. Любой пользователь может работать активно на терминале (или думать), или он ждет ответа от компьютера. Последний временной интервал (время реакции) разделен на две фазы: фаза ожидания и фаза обслуживания.
Временной интервал, когда пользователь думает, является случайной переменная $$T_t$$ со средней величиной $$m_t.$$ Временной интервал, когда пользователь ждет ответа от компьютера, называется временем реакции R. Он включает в себя временной интервал $$T_w$$ (средняя величина $$m_w$$ ), в котором работа ждет получения доступа к компьютеру, и непосредственно время обслуживания $$T_s$$ (средняя величина $$m_s$$ ).
$$T_t +R$$ называются временем обращения (рис.12.6). В конце этого временного интервала терминал возвращается к тому же самому состоянию, т.е. к левой стороне в начале интервала (текущее событие). Далее нас интересуют, главным образом, средние величины и характеристики, которые справедливы для всех дисциплин организации очереди, не нарушающих нормальную работу (секция 13.4.2).
Рассмотрим теперь систему с $$S$$ терминалами, которые связаны с одним компьютером. Предполагается, что времена размышления абонента для каждого терминала экспоненциально распределены с интенсивностью $$\gamma = 1/m_t$$ и время обслуживания (выполнение компьютером работы) распределено экспоненциально с интенсивностью $$\mu = 1/m_s$$. Когда есть очередь в компьютере, терминалы должны ждать обслуживания. Обслуживаемые терминалы или ждущие в очереди имеют нулевую интенсивность поступления.
Состояние $$[i] $$ определено как состояние, где в системе организации очереди (рис.12.5) есть $$i$$ терминалов, то есть компьютер либо свободен ( $$i = 0$$ ), либо работает ( $$i > 0$$ ), и ( $$i - 1$$ ) терминалов ждут все время, пока ( $$i > 0$$ ).
Система организации очереди может быть смоделирована процессом "гибели и размножения" и диаграммой перехода состояний, показанной на рис.12.7. Существует статистическое равновесие (эргодическая система). Интенсивности поступления заявок уменьшается, по мере того как длина очереди увеличивается, и интенсивность становится нулевой, когда все терминалы стоят в очереди.
(рис 12.7) Диаграмма переходов для системы организации очереди, показанной в 12.5. Состояние [ i ] обозначает число терминалов, которые либо обслуживаются, либо ожидают обслуживания, то есть S- i обозначает число терминалов, где пользователь либо размышляет, либо работает непосредственно с компьютером.
Устойчивые вероятности состояния могут быть найдены, по рис.12.7, с помощью уравнения сечения и выражены с помощью числа состояний $$S$$:
$$(S-i) \gamma *p(i)= \mu *p(i+1), i=0,1, \dots, S.$$Согласно дополнительным ограничением нормировки, подставляя $$\varrho = \mu / \gamma$$, находим сумму всех вероятностей, которая равна:
$$p(S-i)=\frac{\varrho^i}{i!}p(S)\\ =\frac{\frac{\varrho^i}{i!}}{\sum_{j=0}^S \frac{\varrho^j}{j!}}, i=0,1,\dots, S,$$ $$p(0)=E_{1,S}(\varrho).$$Это - усеченное
Мы можем интерпретировать систему следующим образом. Группе с $$S$$ пучками каналов (терминалами) поступают вызовы от компьютера с экспоненциально распределенными интервалами поступления (интенсивность) $$\mu$$.
Когда все $$S$$ пучков каналов заняты (пауза на размышление или ввод), компьютер свободен, и интенсивность поступления нулевая, но мы могли бы предположить, что все пучки еще генерируют вызовы с интенсивностью $$\mu$$, которые потеряны в этой или другой группе пучков каналов (экспоненциальное распределение не имеет памяти). Компьютер, таким образом, предлагает нагрузку $$\varrho =\mu / \gamma S$$ пучкам каналов, и мы имеем формулу (12.37). B-формула Эрланга справедлива для произвольных времен пребывания в системе (секция 7.3.3), и поэтому можно утверждать, что:
Теорема 12.1. Вероятности состояния модели восстановления машин (12.36) и (12.37) с одним компьютером и $$S$$ терминалами справедливы в течение произвольных времен пауз (размышления и работа с компьютером), когда времена обслуживания компьютером являются экспоненциально распределенными.
Отношение $$\varrho=\mu / \gamma:$$ это отношение среднего времени, когда пользователь терминала думает $$1/ \gamma$$, и среднего времени, когда компьютер обслуживает терминал $$1/ \mu$$. Это отношение называется сервисным отношением. В B-формуле Эрланга сервисное отношение соответствует предложенной нагрузке. Вероятности состояния определяются числом терминалов $$S$$ и сервисного отношения. Вычисление по формулам (12.36) и (12.37) проводится, как и в B-формуле (7.29) Эрланга.
Мы рассматриваем информационную систему, которая организована следующим образом. Вся информация хранится на 6 дисках, которые связаны с одним и тем же терминалом мультиплексорным каналом ввода-вывода данных. Среднее время поиска (определение месторасположения производится вручную) - 3 мс. Среднее время задержки, чтобы определить местонахождение файла - 1 мс, соответствующее время вращения - 2 мс, время считывания файла - экспоненциально распределенное со средней величиной 0,8 мс, дисковое хранение основано на определении месторасположения путем считывания при вращении диска так, чтобы канал был занят только в период чтения. Мы хотим найти максимальную производительность системы (число запросов в секунду). Время паузы на раздумье и работу с терминалом 4 мс, и время обслуживания - 0,8 мс, сервисное отношение, таким образом, равно 5.
B-формула Эрланга дает значение:
$$1-p(0)=1-E_{1,6}(5)=0.8082.$$Это соответствует $$\gamma_{Maкc.}=0.8082/0.0008=1010$$ запросов в секунду.
Характеристики качества работы легко могут быть получены на основе аналогии с классической
Среднее число ожидающих терминалов равно:
$$n_w=S-n_s-n_t=S-\{1-E_{1,S}(\varrho)- \varrho *\{1-E_{1,S}(\varrho)\}\\ \quad = S-\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}.$$Если мы рассматриваем случайный терминал в случайный момент времени, то получаем:
$$p(\mbox{обслуживающий терминал})p_s=\frac{n_s}{S}=\frac{1-E_{1,S}(\varrho}{S},$$ $$p(\mbox{терминал в паузе})p_t=\frac{n_t}{S}=\frac{\varrho(1-E_{1,S}(\varrho)}{S},$$ $$p(\mbox{ожидающий терминал})=p_w=\frac{n_w}{S}=1-\frac{\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}}{S}$$Мы также интересуемся временем реакции $$R$$, которая имеет среднюю величину $$m_r = m_w + m_s.$$ Применяя формулу Литла $$L = \lambda W$$ к терминалам, установленным на ожидание, и к компьютеру, мы, соответственно, получаем (обозначая скорость обращения заявок $$\lambda$$ ):
$$\frac{1}{\lambda}=\frac{m_t}{n_t}=\frac{m_w}{n_w}=\frac{m_s}{n_s}=\frac{m_r}{n_w+n_s},$$или
$$m_r=\frac{n_w+n_s}{n_s}*m_s=\frac{S_n_t}{n_s}*m_s.$$Используя (12.38) и (12.44) $$\frac{n_t}{n_s}=\frac{m_t}{m_s}$$, мы получим:
$$m_r=\frac{S}{n_s}*m_s-m_t\\ m_r=\frac{S}{1-E_{1,S}(\varrho)}*m_s-m_t.$$Таким образом, среднее время ответа не зависит от типа распределения времени, поскольку оно базируется на формуле Литла (12.38) и (12.44). Однако, $$E_{1, S} (varrho) $$ будет зависеть от типов распределений, так же, как это было в B-формуле Эрланга. Если время обслуживания компьютера является экспоненциально распределенным (средняя величина $$ms = 1/ \mu$$ ), то $$E_{1,S}(\varrho)$$ будет определяться формулой (12.37). Pис.12.8 в этом случае показывает время реакции как функцию числа терминалов.
Если все временные интервалы являются постоянными, то компьютер может работать без пауз, обслуживая $$K$$ терминалов без всякой задержки, когда:
$$K=\frac{m_t+m_s}{m_s}\\ = \varrho+1$$$$K$$ - подходящий параметр для описания точки насыщения системы. Среднее время ожидания для произвольного терминала может быть получено из (12.45):
$$m_w = m_r- m_s$$
(рис 12.8) Фактическое среднее время реакции, определяется как функция числа терминалов Сервисный коэффициент - $$\varrho$$ = 30. Среднее время реакции переходит в прямую линию, пересекающую ось $$x$$ при $$S = 30$$ терминалов. Среднее виртуальное время реакции для системы с S терминалами равно фактическому среднему времени реакции для системы с $$S +1$$ терминалами (теорема моментов поступления, теорема 8.1).
В системе, обслуживающей терминалы, компьютер иногда свободен (ждет заявок от терминалов), а иногда терминалы ждут компьютер. Если терминалов мало, результатом будет низкое использование компьютера, тогда как если подключено много терминалов, то пользователи будут тратить время впустую на ожидание.
Pис.12.9 показывает нагрузку времени ожидания в Эрл для компьютера и для одного терминала. Соответствующая надбавка затрат и сумма времен ожидания для компьютера и для всех терминалов дает стоимость ожидания.
(рис 12.9) Нагрузка времени ожидания (соотношение времени, потраченного на ожидание), измеренная в Эрл для компьютера и соответственно для терминалов при интерактивной системе организации очереди (коэффициент обслуживания - $$\varrho$$ = 30).
Например, на рис.12.9 мы получаем минимальные полные затраты ожидания приблизительно для 45 терминалов. Стоимость ожидания компьютера - в сотню раз больше стоимости времени одного терминала. При 31 терминале и одном компьютере каждый терминал тратит 11,4 % времени для ожидания. Если отношение стоимости - 31, то 31 - оптимальное число терминалов. Однако должны быть учтены несколько других факторов.
Мы можем определить потери по нагрузке обычным способом (секция 2.3). Предложенная нагрузка - это нагрузка, которая будет при отсутствии очереди.
Удельная нагрузка будет (8.8):
$$a=\frac{\beta}{1+\beta}=\frac{m_s}{m_t+m_s}$$На один источник обслуженная нагрузка:
$$y=\frac{m_s}{m_t+m_w+m_s}$$Потери по нагрузке равны:
$$C=\frac{a-y}{a}\\ =1-\frac{m_t-m_s}{m_t+m_w+m_s}=\frac{m_w}{m_t+m_w+m_s},\\ C=p_w$$Потери по нагрузке становятся равными соотношению времени, потраченного на ожидание. Для системы Эрланга с ожиданием потери по нагрузке являются нулевыми, потому что вся предложенная нагрузка обслуживается.
Вышеупомянутая модель легко может быть обобщена на $$п$$ компьютеров.
Диаграмма переходов показана на рис.12.10 Вероятности устойчивых состояний равны:
$$p(i)={S\choose i}(\frac{\gamma}{\mu})^ip(0), 0 \le i \le n,\\ p(i)=\frac{(S-n)!}{(S-i)!}(\frac{\gamma}{n \mu})^{i-n}*p(n), n \le i \le S.$$где мы имеем нормировочное ограничение:
$$\sum_{i=0}^Sp(i)=1$$
(рис 12.10) Диаграмма переходов состояний для модели восстановления машин с S терминалами и n компьютерами Можно показать, что вероятности состояния не зависят от распределения времени паузы (размышление или работа с терминалом), как и в случае с одним компьютером. (Мы получаем Пуассоновский поток вызовов, зависимый от состояния).
Произвольный терминал - в случайный момент времени может находиться в одном из трех возможных состояний:
$$p_s = p\{\mbox{ терминал, обслуживаемый компьютером}\};$$ $$p_s = p\{ \mbox{терминал, ожидающий обслуживания}\}; $$ $$p_w = p\{ \mbox{терминал в паузе}\}.$$Мы имеем:
$$p_s=\frac 1S\left \{\sum_{i=0}^ni*p(i)+\sum_{i=n+1}^Sn*p(i) \right \},$$ $$p_t=p_s*\frac{\mu}{\gamma},$$ $$p_w=1-p_s-p_t.$$Среднее использование компьютеров равно:
$$\alpha=\frac{p_s}{n}*S=\frac{n_s}{n}.$$Среднее время ожидания для терминала равно:
$$W=\frac{p_w}{p_s}*\frac{1}{\mu}.$$Иногда $$p_w$$ называют коэффициентом потерь терминалов, и аналогично $$(1 - \alpha) $$ называют коэффициентом потерь компьютеров (рис.12.9).
Следующие числовые примеры иллюстрируют то, что мы получаем самое высокое использование для больших значений $$n$$ (и $$S$$ ). Рассмотрим систему с $$S/n = 30$$ и $$\mu / \gamma = 30$$ для большого числа компьютеров (в этом случае $$p_t = \alpha$$ ).
| $$n$$ | 1 | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
| $$p_s$$ | 0.0289 | 0.0300 | 0.0307 | 0.0313 | 0.0316 |
| $$p_w$$ | 0.1036 | 0.0712 | 0.0477 | 0.0311 | 0.0195 |
| $$p_t$$ | 0.8675 | 0.8989 | 0.9215 | 0.9377 | 0.9489 |
| $$a$$ | 0.8675 | 0.8989 | 0.9215 | 0.9377 | 0.9489 |
| $$W[\mu^1]$$ | 3.5805 | 2.3754 | 1.5542 | 0.9945 | 0.6155 |
В этой секции мы оптимизируем модель восстановления машин тем же способом, как сделал это Пальм в 1947 г. Заметим, что модель для единственного ремонтника (одного обслуживающего прибора) похожа на систему с потерями Эрланга, которую мы оптимизировали в Лекции 7. Мы можем видеть, что одна и та же модель может быть оптимизирована несколькими способами.
Рассмотрим терминальную систему с одним компьютером и $$S$$ терминалами и найдем оптимальное значение $$S$$. Примем следующую структуру затрат:
$$c_t$$ - стоимость на терминал в единицу времени при паузе (размышление или работа только с терминалом);
$$c_w$$ - стоимость на один терминал в единицу времени при ожидании;
$$c_s$$ - стоимость на один терминал в единицу времени при обслуживании;
$$c_a$$ - стоимость на компьютер в единицу времени.
Предполагается, что стоимость компьютера не зависит от использования и разбита однородно по числу всех терминалов. Результат (конечный продукт) процесса - это некоторое время паузы (размышления и подготовки информации в терминалах) во время производства продукта.
Общая стоимость $$c_0$$ в единицу времени, когда терминал в паузе:
$$p_t*c_0=p_t*c_t+p_s*c_s+p_w*c_w+\frac 1S*c_a$$
(рис 12.11) Модель восстановления машины. Общие стоимости, данные в (12.57), показывают общую стоимость как функцию числа терминалов для сервисного отношения $$\varrho = 25$$ и отношения стоимости $$r = 1/25$$ (см. рис. 7.6)
Мы хотим минимизировать $$с_0$$. Сервисное отношение $$\varrho = m_t /m_s$$ равно $$p_t /p_s$$. Вводя отношение стоимости $$r = с_w /с_a,$$ получаем:
$$c_0=c_t+\frac{p_s}{p_t}*c_s+\frac{p_w*c_w+\frac 1S*c_a}{p_t}\\ =c_t+\frac{1}{\varrho}*c_s+c_a*\frac{r*p_w+(1/S)}{p_t},$$Это выражение должно быть свернуто как функция S. Учитывая, что только последний член зависит от числа терминалов, получаем:
$$min_S\{c_0\}=min_S \left \{\frac{r*p_w+(1/S)}{p_t} \right \}\\ =min_S \left \{\frac{r*(n_w/S)+(1/S)}{n_t/S} \right \}\\ =min_S \left \{ \frac{r*n_w+1}{n_t} \right \}$$ $$=min_S \left \{ \frac{r[S-\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}]+1}{\{1-E_{1,S}(\varrho)\}*\varrho}\right \}\\ =min_s \left \{ \frac{r*S+1}{\{1-E_{1,S}(\varrho)\}* \varrho}+1+\frac{1}{\varrho} \right \},$$Мы замечаем, что минимум не зависит от $$c_t$$ и $$c_s$$ и что только отношение $$r = c_w /c_a$$ содержит характеристики стоимости. Числитель соответствует (7.31), тогда как знаменатель соответствует обслуженной нагрузке в соответствующей
PCT -IPCT -IIВероятность, что система c ожиданием находится в состоянии $$i$$, равна
$$p(i)=\begin{cases} p(o)* \frac{A^i}{i!}, 0 \le i \le n\\ p(n)*(\frac An)^{i-n}=p(0)*\frac{A^i}{n!*n^{i-n}} i \ge n \end{cases}.$$где
$$p(0)=\frac{1}{\sum_{i=0}^{n-1} \frac{A^i}{i!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n$$.Вероятность ожидания $$p\{W > 0\} = E_{2,n} ( A ) $$ в
( формула Эрланга для систем с ожиданием ).
Поскольку мы имеем очень точную рекурсивную формулу для числовой оценки B-формулы (7.29) Эрланга, можно использовать следующие отношения для того, чтобы получить числовые значения для C-формулы:
$$E_{2,n}(A)=\frac{E_{1,n}(A)}{1-A\{1-E_{1,n}(A)\}/n}$$Длина очереди $$L$$ в произвольной момент времени называется виртуальной длиной очереди. Эта длина очереди определяется для произвольного клиента:
$$L_n=E_{2,n}(A)*\frac{A}{n-A} \qquad A < n$$где $$L$$ - случайная переменная, обозначающая длину очереди.
Среднее время обслуживания для системы равно:
$$W_n=E_{2,n}(A)*\frac{s}{n-A}$$.Среднее время ожидания $$w$$ для задержанных вызовов:
$$W_n=\frac{s}{n-A}$$.Mo предложил свой принцип для систем организации очереди. Согласно этому принципу оптимальное решение равно:
$$F_{W,n_i-1}(A) > \frac{c_i}{\vartheta} \ge F_{W, n_i}(A), \quad i=1,2, \dots, k$$где $$c_i$$ - переменная стоимость канала;
$$F_{W,n}(A)$$ - функция увеличения времени ожидания;
$$\vartheta$$ (тета) -
FIFO (First In First Out). Эта дисциплина также называется дисциплина обслуживания в порядке поступления.При поступлении вызова в систему с ожиданием и дисциплиной обслуживания
Среднее время пребывания заявки в системе в случае одного обслуживающего прибора:
$$m=\frac{1}{\mu - \lambda}$$Мы рассмотрим те же самые два случая потоков нагрузки, о которых говорили в Лекциях 7 и 8.
Пуассоновский поток вызовов (бесконечное число источников) и экспоненциально распределенное время обслуживания (
С этими параметрами мы будем иметь дело в секции 12.2. В секции12.3 будет показано, как для оптимизации системы может быть применен Принцип Мо. В секции 12.4. вычисляется распределение времени ожидания для основной дисциплины обслуживания - Первый Прибыл Первый обслужен (
PCT -IIРассмотрим систему с ожиданием $$M/M/n$$. Она обслуживает Пуассоновский поток вызовов ( $$M$$ ), имеет экспоненциальное время обслуживания ( $$M$$ ) и n обслуживающих приборов при бесконечном числе мест ожидания. Состояние системы определяется как общее количество пользователей в системе (или в обслуживании, или ожидающих в очереди).
(рис 12.1) Диаграмма переходов состояний M/M/n системы с ожиданием, имеющей n серверов и неограниченное число мест ожидания.Нас интересуют вероятности устойчивых состояний системы. В секции 7.4 дана диаграмма переходов между состояниями (рис.12.1). Принимая, что диаграмма находится в статистическом равновесии, получаем:
$$\lambda *p(0)=\mu *p(1),\\ \lambda *p(1)=2 \mu *p(2),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda * p(i)=(i+1) \mu * p(i+1),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda *p(n-1)=n \mu *p(n),\\ \lambda*p(n)=n \mu*p(n+1),\\ \qquad \qquad \vdots \qquad \vdots \qquad \vdots\\ \lambda*p(n+j)=n \mu*p(n+j+1).$$Если $$A = \lambda / \mu$$ - это предложенная нагрузка, то мы имеем:
$$p(i)=\begin{cases} p(0)*\frac{A^i}{i!}, 0 \le i \le n,\\ p(n)*\left ( \frac An \right )^{i-n}=p(0)*\frac{A^i}{n!*n^{i-n}}, i \ge n. \end{cases}$$С помощью нормировки вероятностей состояний получаем:
$$1=\sum_{i=0}^{\infty}p(i),\\ 1=p(0)*\left \{ 1+\frac A1+\frac{A^2}{2!}+ \dots + \frac{A^n}{n!} \left (1+\frac A1+ \frac{A^2}{n^2}+\dots \right ) \right \}.$$Внутренние фигурные скобки содержат геометрическую прогрессию с коэффициентом прогрессии $$A/n$$. Условие нормализации может быть выполнено только для:
$$A < n$$Статистическое равновесие получено лишь для $$A/n$$. Иначе очередь будет увеличиваться до бесконечности. Мы получаем значение $$p_0$$:
$$p(0)=\frac{1}{\sum_{i=0}^{n-1} \frac{A^i}{i!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n.$$Уравнения (12.2) и (12.4) показывают вероятности устойчивых состояний.
Для оценки производительности и рабочих характеристик системы нужно рассмотреть несколько характеристик. Они отражают вероятности устойчивых состояний.
Когда Пуассоновский поток вызовов не зависит от состояния системы, вероятность того, что произвольный вызов должен будет ждать обслуживания в очереди, равна пропорции времени, когда заняты все обслуживающие приборы ( свойство PASTA ). Время ожидания - случайная величина, которая обозначается $$W$$. Для произвольного поступления вызовов имеем:
$$E_{2,n}(A)=\frac{\frac{A^n}{n!} \frac{n}{n-A}}{1+\frac A1+\frac{A^2}{2!}+\dots+\frac{A^{n-1}}{(n-1)!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n.$$Эта вероятность ожидания зависит только от $$A$$, т.е.произведения $$\lambda$$ и $$s$$. Формула имеет несколько названий: C-формула Эрланга, вторая формула Эрланга или формула Эрланга для систем с ожиданием. Она имеет различные обозначения в литературе:
$$E_{2,n}(A)=D=D_n(A)=p\{W > 0\}.$$Клиенты либо обслуживаются немедленно, либо помещаются в очередь. Вероятность, что клиент обслуживается немедленно, равна:
$$S_n=1-E_{2,n}(A).$$Обслуженная нагрузка $$Y$$ равняется предложенной нагрузке $$A$$, так как ни одному вызову не отказывается в обслуживании, а процесс поступления вызовов - Пуассоновский процесс:
$$Y=\sum_{i=1}^n ip(i)+\sum_{i=n+1}^{\infty}np(i)\\ =\sum_{i=1}^n \frac{\lambda}{\mu}p(i-1)+\sum_{i=n+1}^{\infty} \frac{\lambda}{\mu}p(i-1)\\ =\frac{\lambda}{\mu}=A,$$Здесь применено уравнение равновесия.
Длина очереди - случайная величина $$L$$. Вероятность наличия клиентов в очереди в случайной точке времени:
$$p\{L > 0\}=\sum_{i=n+1}^{\infty}=\frac{\frac An}{1-\frac An}*p(n),\\ p\{L > 0\}=\frac{A}{n-A}p(n)=\frac AnE_{2,n}(A).$$Здесь использовалось (12.5).
Формула подобна B-формуле (7.10) Эрланга, за исключением коэффициента $$n/(n-A) $$ в последнем элементе. Поскольку существует очень точная рекурсивная формула для числовой оценки B-формулы Эрланга (7.29), можно использовать следующие отношения для того, чтобы получить числовые значения для C-формулы:
$$E_{2,n}(A)=\frac{n*E_{1,n}(A)}{n-A(1-E_{1,n}(A))}\\ =\frac{E_{1,n}(A)}{1-A\{1-E_{1,n}(A)\}/n}, \quad A < n.$$где элемент $$A\{1-E_{1,n} (A)\}/n$$ - средняя обслуженная нагрузка на канал в соответствующей
где $$I$$ - инверсия вероятности (7.30).
$$I_{n,2}(A)=\frac{1}{E_{2,n}(A)}.$$C-формула Эрланга была сведена в таблицу в Принципе Мо (Jensen, 1950 [50] ) и показана на рис.12.2.
(рис 12.2) C-формула Эрланга для системы с ожиданием M/M/n. Вероятность $$E_{2,n} (A) $$ для положительного времени ожидания показана как
Мы должны отличать длину очереди в произвольный момент времени и длину очереди, когда есть клиенты, стоящие в очереди.
Средняя длина очереди в произвольный момент времени
Длина очереди $$L$$ в произвольной момент времени называется виртуальной длиной очереди. Для произвольного клиента длина очереди определяется как свойство PASTA, т.е. Пуассоновский поток вызовов (математическое ожидание по времени = математическое ожидание по вызовам). Мы получаем среднюю длину очереди:
$$L_n = E \{L\}$$ в произвольный момент времени:
$$L_n=0*\sum_{i=0}p(i)+\sum_{i=n+1}^{\infty}(i-n)p(i)\\ =\sum_{i=n+1}^{\infty}i-n)p(n) \left (\frac An \right )^{i-n}\\ =p(n)*\sum_{i=1}^{\infty}i (\frac{A}{n})^{i-n}\\ =p(n)*\frac An \sum_{i=1}^{\infty} \frac{\partial}{\partial (A/n)} \left \{ \left (\frac An \right)^i \right \}.$$Поскольку $$A/n \le c \le 1$$, ряд является равномерно сходящимся, оператор дифференцирования может быть вынесен за сумму:
$$L_n=p(n) \frac An \frac{\partial}{\partial (\frac An)} \left \{ \frac{\frac An}{1-(\frac An)} \right \}=p(n)*\frac{\frac An}{\{1-(\frac An)\}^2}\\ =p(n)*\frac{n}{n-A}*\frac{A}{n-A},\\ L_n=E_{2,n}(A)*\frac{A}{n-A}.$$Средняя длина очереди, со временем ожидания больше нуля
Математическое ожидание времени и в этом случае равно математическому ожиданию вызова. Условная
Применяя (12.8) и (12.12), получаем:
$$L_{nq}=\frac{L_n}{p\{L > 0\}},$$где $$L$$ - случайная переменная, обозначающая длину очереди.
Здесь представляют интерес две характеристики:
Первая является индикатором уровня обслуживания целой системы, тогда как вторая относится к задержанным вызовам.
Математические ожидания времени будут равны математическим ожиданиям по вызовам из-за свойства PASTA.
Среднее время ожидания для всех вызовов
Формула Литла говорит, что
где $$L_n=L_n(A)$$ и $$W_n=W_n(A)$$. Рассматривая процесс поступления вызовов, из (12.12) мы имеем:
$$W_n=\frac{L_n}{\lambda}=\frac {1}{\lambda}*E_{2,n}(A)*\frac{A}{n-A}.$$Поскольку $$A = \lambda s$$, где $$s$$ - среднее время обслуживания, мы имеем:
$$W_n=E_{2,n}(A)*\frac{s}{n-A}.$$Среднее время ожидания для задержанных вызовов
Полное время ожидания является постоянным и может быть вычислено либо в среднем по всем клиентам ( $$W_n$$ ), либо только по вызовам, для которых времена ожидания ( $$w_n$$ ) имеют положительные значения (3.20):
$$W_n=w_n*E_{2,n}(A),$$ $$w_n=\frac{s}{n-A}$$Эта система наиболее часто упоминается в литературе. Вероятности состояния (12.2) определяются рядом геометрической прогрессии:
$$p(i)=(1-A)*A^i, i=0,1,2, \dots,$$поскольку $$p (0) = 1- A$$. Вероятность задержки равна:
$$Е_{2,1}(A)=А.$$С помощью уравнений 12.12, 12.14, 12.17 мы можем установить, что увеличение нагрузки из-за большего количества вызовов лучше, чем увеличение нагрузки из-за более длинного времени обслуживания, поскольку увеличение времени обслуживания увеличивает величину всех показателей. Поэтому важно, чтобы времена обслуживания системы не увеличивались в момент перегрузки.
Заметьте, что если $$A \to 0$$, мы получаем $$w_n = s/n$$ (12.17). Если клиент ожидает (что редко случается, когда $$A \to 0$$ ), то этот клиент будет единственным в очереди. Клиент должен ждать, пока сервер освободится. Это случается в конце экспоненциально распределенного временного интервала со средней величиной $$s/n$$. Поэтому $$w_n$$ никогда не может быть меньше, чем $$s/n$$.
Предельное увеличение нагрузки, которую может обслуживать система, когда мы дополняем число обслуживающих приборов, может быть выражено несколькими способами. Уменьшение отношения нагрузки канала к полной нагрузке (пропорционально числу всех вызовов от клиентов) определяется как:
$$F_{2,n}(A)=A\{E_{2,n}(A)-E_{2,n+1}(A)\}$$Уменьшение средней длины очереди (пропорционально нагрузке, которую обслуживают места ожидания) определяется формулой Литла (12.14):
$$F_{L,n}(A)=L_n(A)-L_{n+1}(A)\\ \qquad = \lambda \{W_n(A)-W_{n+1}(A)\},$$где $$W_n(A) $$ - среднее время ожидания для всех вызовов, когда предложенная нагрузка и число обслуживающих приборов - $$n$$ (12.15). Равенства (12.21) и (12.22) сведены в таблицу в Принципе Мо (Jensen, 1950 [50] ) и могут быть легко рассчитаны с помощью калькулятора или компьютера.
Mo сначала предложил свой принцип для систем организации очереди. Он изучил времена ожидания абонентов для оператора на ручных станциях Копенгагенской Телефонной Компании.
Рассмотрим $$k$$ независимости систем организации очереди. Вызов, обслуживаемый во всех $$k$$ системах, имеет полное среднее времени ожидания
$$\sum_i W_i,$$где $$W_i$$ - среднее время ожидания $$i$$ -той системы, которая имеет $$n_i$$ обслуживающих приборов и предложенную нагрузку $$A_i.$$ Стоимость канала равна переменной стоимости $$c_i$$ плюс постоянная стоимость, выраженная константой $$C_0.$$ Таким образом, общая стоимость каналов равна:
$$C=C_0+\sum_{i=1}^kn_ic_i.$$Если время ожидания также рассматривать как стоимость, то общая стоимость будет равна $$f=f (n_1, n_2 , \dots, n_k ) $$. Она должна быть свернута как функция числа $$n_i$$ каналов в отдельные системы. Если полное среднее время ожидания - $$W$$, то распределение каналов по отдельным системам определяется:
$$min\{f(n_1, n_2, \dots, n_k)\}=min \{C_0+\sum_in_ic_i+ \vartheta *\left(\sum_iW_i-W \right) \}$$где $$\vartheta$$ (тета) -
Величина $$n_i$$ является неотъемлемой частью необходимого условия для определения минимума, и можно показать, что в этом случае достаточным условием для минимума являются следующие неравенства :
$$0 < f(n_1, n_2, \dots, n_i-1, \dots, n_k)-f(n_1, n_2, \dots, n_i, \dots, n_k),\\ 0 \ge f(n_1, n_2, \dots, n_i, \dots, n_k)-f(n_1, n_2, \dots, n_i+1, \dots, n_k),$$что соответствует:
$$W_{n_i-1}(A_i)-W_{n_i}(A_i) > \frac{c_i}{\vartheta},\\ W_{n_i}(A_i)-W_{n_i+1}(A_i) \le \frac{c_i}{\vartheta},$$где $$W_{ni} (A_i ) $$ показано в (12.15).
Выраженное с помощью функции увеличения времени ожидания $$F_{W,n} (A) $$ (12.22) оптимальное решение равно:
$$F_{W,n_i-!}(A) > \frac{c_i}{\vartheta} \ge F_{W, n_i}(A), i=1,2,\dots, k$$Функция $$F_{W, n} (A) $$ сведена в таблицу в Принципе Мо (Jensen, 1950 [50] ). Подобная оптимизация может быть проведена для других функций увеличения.
Мы рассматриваем две различных $$M/M/n$$ системы организации очереди. Первая имеет среднее время обслуживания 100 с и предложенную нагрузку 20 Эрл. Отношение стоимости $$c_1/ \vartheta$$ равно 0,01. Вторая система имеет среднее время обслуживания, равное 10 с, и предложенную нагрузку 2 Эрл. Отношение стоимости равняется $$c_2 /\vartheta = 0,1$$. Таблица функции увеличения $$F_W,n (A) $$ дает:
$$n_1 = 32$$ канала и
$$n_2 = 5$$ каналов.
Средние времена ожидания:
$$W_1 = 0,075 с$$ $$W_2 = 0,199 с.$$Это показывает, что вызов, который обслуживается в обеих системах, имеет полное среднее время ожидания 0,274 с и что система с меньшим количеством каналов вносит больший вклад в среднее время ожидания.
Стоимость ожидания связана с отношением стоимости. Инвестируя больше в вышеупомянутую систему, мы уменьшаем затраты независимо от системы организации очереди. Необходимо идти на вложения, пока получаем прибыль. Исследования Мо в течение 1920-ых годов показали, что среднее время ожидания для абонентов маленьких станций с немногими операторами должно быть большим, чем среднее время ожидания при больших станциях со многими операторами.
Системы организации очереди, где дисциплина обслуживания зависит от времени поступления вызовов, все имеют одни и те же средние времена ожидания. В этом случае стратегия влияет только на распределение времен ожидания для каждого отдельного клиента. Исследование распределения времени ожидания упрощается в случае дисциплины FIFO (First In First Out). Она также называется дисциплина обслуживания в порядке поступлении. Но если обслуживающих приборов много, заявка может не обязательно покинуть обслуживающий прибор первой. Тогда дисциплина в порядке поступления рассматривается в соответствии с принципом, чтобы время выхода из очереди и начало освобождения обслуживающего прибора была началом обслуживания другой заявки.
Рассмотрим произвольный вызов. По прибытию в систему вызов или обслуживается немедленно, или должен ждать в очереди (12.6).
Предположим, что вызов, который мы рассматриваем, должен ждать в очереди, то есть система может быть в состоянии $$[n + k], (k = 0, 1, 2, \dots) $$, где $$k$$ - число занятых мест ожидания как раз перед поступлением вызова.
Наш вызов должен ждать, пока будет завершено обслуживание $$k + 1$$ вызовов, прежде чем станет доступным свободный обслуживающий прибор. Когда все $$n$$ обслуживающих приборов работают, система завершает обслуживание вызовов с постоянной скоростью $$n \mu$$, то есть процесс выхода вызовов из обслуживания является Пуассоновским процессом с данной интенсивностью. Мы используем отношения между числовым представлением и представлением с помощью интервала (5.4). Вероятность $$p(W \le t) = F(t) $$, что положительное время ожидания $$t$$ превосходит заданную величину, равна вероятности того, что в Пуассоновском потоке вызовов с интенсивностью $$n \mu$$, по крайней мере, $$(k+1) $$ вызовов поступят в течение интервала $$t$$ (6.1):
$$F(t|k \quad waiting)=\sum_{i=n+1}^{\infty} \frac{(n \mu t)^i}{i!}*e^{-n \mu t}.$$Вышеупомянутое равенство справедливо при условии, что наш вызов должен ждать в очереди. Условная вероятность, что наш вызов поступит, когда все $$n$$ обслуживающих приборов заняты и имеется $$k$$ обслуживаемых вызовов $$(k=1,2, \dots) $$, такова:
$$p_w(k)=\frac{\lambda p(n+k)}{\lambda \sum_{i=0}^{\infty}p(n+i)}=\frac{p(n)*(\frac An)^k}{p(n)*\sum_{i=0}^{\infty}(\frac An)^i}\\ =(1- \frac An)(\frac An)^k, k=0,1, \dots.$$Это геометрическое распределение, включая нулевой класс (табл. 6.1). Безусловное распределение времени ожидания тогда равно:
$$F(t)=\sum_{k=0}^{\infty}p_w(k)*F(t|k),$$ $$F(t)=\sum_{k=0}^{\infty} \left \{(1-\frac An)(\frac An)^k*\sum_{i=k+1}^{\infty} \frac{(n \mu t)^i}{i!}e^{-n \mu t} \right \}\\ =e^{-n \mu t}\sum_{i=1}^{\infty} \left \{ \frac{(n \mu t)^i}{i!}*\sum_{k=0}^{i-1}(1-\frac An)(\frac An)^k \right \},$$Когда все элементы - положительные вероятности, мы можем поменять порядок суммирования. Внутренняя сумма является геометрической прогрессией:
$$\sum_{k=0}^{i-1}(1-\frac An)(\frac An)^k=(1-\frac An)*\sum_{k=0}^{i-1}(\frac An)^k\\ =(1-\frac An)*1*\frac{1-(A/n)^i}{1-(A/n)}\\ =1-(\frac An)^i.$$Подставляя результат этой суммы, мы получаем:
$$F(t)=e^{-n \mu t}* \sum_{i=1}^{\infty} \frac{(n \mu t)^i}{i!} \left \{1-(\frac An)^i \right \}\\ =e^{-n \mu t} \left \{ \sum_{i=0}^{\infty} \frac{(n \mu t)^i}{i!}-\sum_{i=0}^{\infty} \frac{(n \mu t)^i}{i!} (\frac An)^i \right \}\\ =e^{n \mu t}\{e^{n \mu t}-e^{n \mu t*A/n}\},$$ $$F(t)=1-e^{-(n-A)\mu t},\\ F(t)=1-e^{-(n \mu - \lambda)t}, n > A, t > 0.$$то есть экспоненциальное распределение. Очевидно, существует парадокс - при поступлении вызова в систему со всеми ранее занятыми обслуживающими приборами можно:
Интерпретация этого факта - то, что взвешенная сумма распределений Эрланга с геометрически распределенными коэффициентами веса эквивалентна экспоненциальному распределению. На рис.12.3 показана диаграмма состояний для (12.30), и мы можем заметить, что она может быть сведена к единственному экспоненциальному распределению (секция 4.4.2 и рис.4.9). Формула (12.31) подтверждает, что среднее время ожидания $$w_n$$ для клиентов, которые должны ждать в очереди, определяется выражением, показанным в (12.17).
(рис 12.3)
Распределение общее время ожидания (для произвольного вызова) равно (3.19):
$$F_s(t)=1-E_{2,n}(A)*e^{-(n-A)\mu t}, A < n, t \ge 0,$$и средняя величина этого распределения - $$W_n,$$ в соответствии с (12.15).
Когда имеется только один обслуживающий прибор, вероятности состояния (12.2) представляются рядом геометрической прогрессии $$p(i)=(1 -A)^i \times Ai$$ (12.18) для всех $$i \ge 0$$. Каждый вызов занимает экспоненциально распределенный временной интервал с интенсивностью $$\lambda$$ в каждом состоянии. Вызов, который поступает в систему в состоянии $$[i] $$, должен остаться в системе, интервал времени распределен по закону Эрланга - $$(i+1) $$. Поэтому время пребывания в системе (время ожидания + время обслуживания), которое также называется временем реакции, является экспоненциально распределенным с интенсивностью $$(\mu - \lambda) $$. (см. рис. 4.9):
$$F(t)=1-e^{-(\mu - \lambda)t}, \mu > \lambda, t \ge 0.$$Это идентично распределению времени ожидания задержанных вызовов. Среднее время пребывания может быть получено непосредственно, используя $$W_1$$ из(12.20) и среднее время обслуживания $$s$$:
$$m=W_1+s=\frac{As}{1-A}+s,\\ m=\frac{s}{1-A}=\frac{1}{\mu - \lambda},$$где $$\mu = 1/s$$ - скорость обслуживания. Заметим, что среднее время пребывания в системе равно среднему времени ожидания для задержанных клиентов (12.17).
Эта модель принадлежит классу циклических систем организации очереди и соответствует чистой
Первым в 1933 г. эту модель рассмотрел Гнеденко и в 1934 г. опубликовал статью. Метод стал широко известен, когда в 1947 г. C. Пальм издал статью [80] с теоретическим анализом распределения трудовых ресурсов,
(рис 12.4) Плотность распределения для распределения времени ожидания при дисциплинах организации очереди FCFS, LCFS1 и SIRO (случайная). Во всех трех случаях среднее время ожидания для задержанных вызовов - 5 единиц времени. Коэффициент формы - 2 для FCFS, 3.33 - для LCFS и 10 - для SIRO. Число обслуживающих приборов - 10, и предложенная нагрузка - 8 Эрл. Среднее время обслуживания s = 10 единиц времени.обслуживающих автоматы. Множество $$S$$ машин, которые обычно работают автоматически, обслуживается n ремонтниками. Машины могут сломаться, и тогда понадобится ремонтник, чтобы запустить их в работу снова. Проблема состоит в том, чтобы определить число ремонтников в зависимости от числа машин так, чтобы общие стоимости были минимизированы (по-другому это называется "оптимизированная прибыль"). Машины могут быть, например, текстильными машинами, которые останавливаются, когда заканчивается нить; ремонтники тогда должны заменить пустую бобину машины полной.
Эту модель восстановления машин, или модель взаимного влияния машин, рассматривал Feller (1950 [27] ). Модель соответствует организации очереди в простой закрытой сети и успешно применяется, чтобы решить технические проблемы нагрузки в компьютерных системах. В системе обозначений Кендалла (Лекция 13) система организации очереди обозначается $$M/M/n/S$$, где $$S$$ - число клиентов и $$n$$ - число обслуживающих приборов.
Модель широко применяется на практике. В сети машины соответствуют вызовам, тогда как "ремонтники" предстают обслуживающими приборами, а "ремонтник" представляется компьютером, управляющим терминалами. В компьютерной си стеме машина может соответствовать программам, хранящимся на диске, а ремонтники представляют каналы ввода-вывода ( ввод-вывод ). Далее мы рассмотрим систему компьютерных терминалов, как основу для развития теории.
Режим разделения времени - лучшее решение для оптимального обслуживания большой группы источников нагрузки использующих, например, терминалы, подключенные к универсальному компьютеру. Отдельный пользователь должен чувствовать себя так, как будто он - единственный пользователь компьютера (рис.12.5).
(рис 12.5) Модель восстановления машин Пальма. Компьютерная система с S терминалами (диалоговая система) соответствует системе с ожиданием и с ограниченным числом источников (см. случай Энгсета для систем с потерями).
Отдельный терминал находится все время в одном из двух состояний (диалоговый режим) (рис.12.6):
(рис 12.6) Отдельный терминал может быть в трех различных состояниях. Любой пользователь может работать активно на терминале (или думать), или он ждет ответа от компьютера. Последний временной интервал (время реакции) разделен на две фазы: фаза ожидания и фаза обслуживания.
Временной интервал, когда пользователь думает, является случайной переменная $$T_t$$ со средней величиной $$m_t.$$ Временной интервал, когда пользователь ждет ответа от компьютера, называется временем реакции R. Он включает в себя временной интервал $$T_w$$ (средняя величина $$m_w$$ ), в котором работа ждет получения доступа к компьютеру, и непосредственно время обслуживания $$T_s$$ (средняя величина $$m_s$$ ).
$$T_t +R$$ называются временем обращения (рис.12.6). В конце этого временного интервала терминал возвращается к тому же самому состоянию, т.е. к левой стороне в начале интервала (текущее событие). Далее нас интересуют, главным образом, средние величины и характеристики, которые справедливы для всех дисциплин организации очереди, не нарушающих нормальную работу (секция 13.4.2).
Рассмотрим теперь систему с $$S$$ терминалами, которые связаны с одним компьютером. Предполагается, что времена размышления абонента для каждого терминала экспоненциально распределены с интенсивностью $$\gamma = 1/m_t$$ и время обслуживания (выполнение компьютером работы) распределено экспоненциально с интенсивностью $$\mu = 1/m_s$$. Когда есть очередь в компьютере, терминалы должны ждать обслуживания. Обслуживаемые терминалы или ждущие в очереди имеют нулевую интенсивность поступления.
Состояние $$[i] $$ определено как состояние, где в системе организации очереди (рис.12.5) есть $$i$$ терминалов, то есть компьютер либо свободен ( $$i = 0$$ ), либо работает ( $$i > 0$$ ), и ( $$i - 1$$ ) терминалов ждут все время, пока ( $$i > 0$$ ).
Система организации очереди может быть смоделирована процессом "гибели и размножения" и диаграммой перехода состояний, показанной на рис.12.7. Существует статистическое равновесие (эргодическая система). Интенсивности поступления заявок уменьшается, по мере того как длина очереди увеличивается, и интенсивность становится нулевой, когда все терминалы стоят в очереди.
(рис 12.7) Диаграмма переходов для системы организации очереди, показанной в 12.5. Состояние [ i ] обозначает число терминалов, которые либо обслуживаются, либо ожидают обслуживания, то есть S- i обозначает число терминалов, где пользователь либо размышляет, либо работает непосредственно с компьютером.
Устойчивые вероятности состояния могут быть найдены, по рис.12.7, с помощью уравнения сечения и выражены с помощью числа состояний $$S$$:
$$(S-i) \gamma *p(i)= \mu *p(i+1), i=0,1, \dots, S.$$Согласно дополнительным ограничением нормировки, подставляя $$\varrho = \mu / \gamma$$, находим сумму всех вероятностей, которая равна:
$$p(S-i)=\frac{\varrho^i}{i!}p(S)\\ =\frac{\frac{\varrho^i}{i!}}{\sum_{j=0}^S \frac{\varrho^j}{j!}}, i=0,1,\dots, S,$$ $$p(0)=E_{1,S}(\varrho).$$Это - усеченное
Мы можем интерпретировать систему следующим образом. Группе с $$S$$ пучками каналов (терминалами) поступают вызовы от компьютера с экспоненциально распределенными интервалами поступления (интенсивность) $$\mu$$.
Когда все $$S$$ пучков каналов заняты (пауза на размышление или ввод), компьютер свободен, и интенсивность поступления нулевая, но мы могли бы предположить, что все пучки еще генерируют вызовы с интенсивностью $$\mu$$, которые потеряны в этой или другой группе пучков каналов (экспоненциальное распределение не имеет памяти). Компьютер, таким образом, предлагает нагрузку $$\varrho =\mu / \gamma S$$ пучкам каналов, и мы имеем формулу (12.37). B-формула Эрланга справедлива для произвольных времен пребывания в системе (секция 7.3.3), и поэтому можно утверждать, что:
Теорема 12.1. Вероятности состояния модели восстановления машин (12.36) и (12.37) с одним компьютером и $$S$$ терминалами справедливы в течение произвольных времен пауз (размышления и работа с компьютером), когда времена обслуживания компьютером являются экспоненциально распределенными.
Отношение $$\varrho=\mu / \gamma:$$ это отношение среднего времени, когда пользователь терминала думает $$1/ \gamma$$, и среднего времени, когда компьютер обслуживает терминал $$1/ \mu$$. Это отношение называется сервисным отношением. В B-формуле Эрланга сервисное отношение соответствует предложенной нагрузке. Вероятности состояния определяются числом терминалов $$S$$ и сервисного отношения. Вычисление по формулам (12.36) и (12.37) проводится, как и в B-формуле (7.29) Эрланга.
Мы рассматриваем информационную систему, которая организована следующим образом. Вся информация хранится на 6 дисках, которые связаны с одним и тем же терминалом мультиплексорным каналом ввода-вывода данных. Среднее время поиска (определение месторасположения производится вручную) - 3 мс. Среднее время задержки, чтобы определить местонахождение файла - 1 мс, соответствующее время вращения - 2 мс, время считывания файла - экспоненциально распределенное со средней величиной 0,8 мс, дисковое хранение основано на определении месторасположения путем считывания при вращении диска так, чтобы канал был занят только в период чтения. Мы хотим найти максимальную производительность системы (число запросов в секунду). Время паузы на раздумье и работу с терминалом 4 мс, и время обслуживания - 0,8 мс, сервисное отношение, таким образом, равно 5.
B-формула Эрланга дает значение:
$$1-p(0)=1-E_{1,6}(5)=0.8082.$$Это соответствует $$\gamma_{Maкc.}=0.8082/0.0008=1010$$ запросов в секунду.
Характеристики качества работы легко могут быть получены на основе аналогии с классической
Среднее число ожидающих терминалов равно:
$$n_w=S-n_s-n_t=S-\{1-E_{1,S}(\varrho)- \varrho *\{1-E_{1,S}(\varrho)\}\\ \quad = S-\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}.$$Если мы рассматриваем случайный терминал в случайный момент времени, то получаем:
$$p(\mbox{обслуживающий терминал})p_s=\frac{n_s}{S}=\frac{1-E_{1,S}(\varrho}{S},$$ $$p(\mbox{терминал в паузе})p_t=\frac{n_t}{S}=\frac{\varrho(1-E_{1,S}(\varrho)}{S},$$ $$p(\mbox{ожидающий терминал})=p_w=\frac{n_w}{S}=1-\frac{\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}}{S}$$Мы также интересуемся временем реакции $$R$$, которая имеет среднюю величину $$m_r = m_w + m_s.$$ Применяя формулу Литла $$L = \lambda W$$ к терминалам, установленным на ожидание, и к компьютеру, мы, соответственно, получаем (обозначая скорость обращения заявок $$\lambda$$ ):
$$\frac{1}{\lambda}=\frac{m_t}{n_t}=\frac{m_w}{n_w}=\frac{m_s}{n_s}=\frac{m_r}{n_w+n_s},$$или
$$m_r=\frac{n_w+n_s}{n_s}*m_s=\frac{S_n_t}{n_s}*m_s.$$Используя (12.38) и (12.44) $$\frac{n_t}{n_s}=\frac{m_t}{m_s}$$, мы получим:
$$m_r=\frac{S}{n_s}*m_s-m_t\\ m_r=\frac{S}{1-E_{1,S}(\varrho)}*m_s-m_t.$$Таким образом, среднее время ответа не зависит от типа распределения времени, поскольку оно базируется на формуле Литла (12.38) и (12.44). Однако, $$E_{1, S} (varrho) $$ будет зависеть от типов распределений, так же, как это было в B-формуле Эрланга. Если время обслуживания компьютера является экспоненциально распределенным (средняя величина $$ms = 1/ \mu$$ ), то $$E_{1,S}(\varrho)$$ будет определяться формулой (12.37). Pис.12.8 в этом случае показывает время реакции как функцию числа терминалов.
Если все временные интервалы являются постоянными, то компьютер может работать без пауз, обслуживая $$K$$ терминалов без всякой задержки, когда:
$$K=\frac{m_t+m_s}{m_s}\\ = \varrho+1$$$$K$$ - подходящий параметр для описания точки насыщения системы. Среднее время ожидания для произвольного терминала может быть получено из (12.45):
$$m_w = m_r- m_s$$(рис 12.8) Фактическое среднее время реакции, определяется как функция числа терминалов Сервисный коэффициент - $$\varrho$$ = 30. Среднее время реакции переходит в прямую линию, пересекающую ось $$x$$ при $$S = 30$$ терминалов. Среднее виртуальное время реакции для системы с S терминалами равно фактическому среднему времени реакции для системы с $$S +1$$ терминалами (теорема моментов поступления, теорема 8.1).
В системе, обслуживающей терминалы, компьютер иногда свободен (ждет заявок от терминалов), а иногда терминалы ждут компьютер. Если терминалов мало, результатом будет низкое использование компьютера, тогда как если подключено много терминалов, то пользователи будут тратить время впустую на ожидание.
Pис.12.9 показывает нагрузку времени ожидания в Эрл для компьютера и для одного терминала. Соответствующая надбавка затрат и сумма времен ожидания для компьютера и для всех терминалов дает стоимость ожидания.
(рис 12.9) Нагрузка времени ожидания (соотношение времени, потраченного на ожидание), измеренная в Эрл для компьютера и соответственно для терминалов при интерактивной системе организации очереди (коэффициент обслуживания - $$\varrho$$ = 30).
Например, на рис.12.9 мы получаем минимальные полные затраты ожидания приблизительно для 45 терминалов. Стоимость ожидания компьютера - в сотню раз больше стоимости времени одного терминала. При 31 терминале и одном компьютере каждый терминал тратит 11,4 % времени для ожидания. Если отношение стоимости - 31, то 31 - оптимальное число терминалов. Однако должны быть учтены несколько других факторов.
Мы можем определить потери по нагрузке обычным способом (секция 2.3). Предложенная нагрузка - это нагрузка, которая будет при отсутствии очереди.
Удельная нагрузка будет (8.8):
$$a=\frac{\beta}{1+\beta}=\frac{m_s}{m_t+m_s}$$На один источник обслуженная нагрузка:
$$y=\frac{m_s}{m_t+m_w+m_s}$$Потери по нагрузке равны:
$$C=\frac{a-y}{a}\\ =1-\frac{m_t-m_s}{m_t+m_w+m_s}=\frac{m_w}{m_t+m_w+m_s},\\ C=p_w$$Потери по нагрузке становятся равными соотношению времени, потраченного на ожидание. Для системы Эрланга с ожиданием потери по нагрузке являются нулевыми, потому что вся предложенная нагрузка обслуживается.
Вышеупомянутая модель легко может быть обобщена на $$п$$ компьютеров.
Диаграмма переходов показана на рис.12.10 Вероятности устойчивых состояний равны:
$$p(i)={S\choose i}(\frac{\gamma}{\mu})^ip(0), 0 \le i \le n,\\ p(i)=\frac{(S-n)!}{(S-i)!}(\frac{\gamma}{n \mu})^{i-n}*p(n), n \le i \le S.$$где мы имеем нормировочное ограничение:
$$\sum_{i=0}^Sp(i)=1$$(рис 12.10) Диаграмма переходов состояний для модели восстановления машин с S терминалами и n компьютерами Можно показать, что вероятности состояния не зависят от распределения времени паузы (размышление или работа с терминалом), как и в случае с одним компьютером. (Мы получаем Пуассоновский поток вызовов, зависимый от состояния).
Произвольный терминал - в случайный момент времени может находиться в одном из трех возможных состояний:
$$p_s = p\{\mbox{ терминал, обслуживаемый компьютером}\};$$ $$p_s = p\{ \mbox{терминал, ожидающий обслуживания}\}; $$ $$p_w = p\{ \mbox{терминал в паузе}\}.$$Мы имеем:
$$p_s=\frac 1S\left \{\sum_{i=0}^ni*p(i)+\sum_{i=n+1}^Sn*p(i) \right \},$$ $$p_t=p_s*\frac{\mu}{\gamma},$$ $$p_w=1-p_s-p_t.$$Среднее использование компьютеров равно:
$$\alpha=\frac{p_s}{n}*S=\frac{n_s}{n}.$$Среднее время ожидания для терминала равно:
$$W=\frac{p_w}{p_s}*\frac{1}{\mu}.$$Иногда $$p_w$$ называют коэффициентом потерь терминалов, и аналогично $$(1 - \alpha) $$ называют коэффициентом потерь компьютеров (рис.12.9).
Следующие числовые примеры иллюстрируют то, что мы получаем самое высокое использование для больших значений $$n$$ (и $$S$$ ). Рассмотрим систему с $$S/n = 30$$ и $$\mu / \gamma = 30$$ для большого числа компьютеров (в этом случае $$p_t = \alpha$$ ).
| $$n$$ | 1 | 2 | 4 | 8 | 16 |
|---|---|---|---|---|---|
| $$p_s$$ | 0.0289 | 0.0300 | 0.0307 | 0.0313 | 0.0316 |
| $$p_w$$ | 0.1036 | 0.0712 | 0.0477 | 0.0311 | 0.0195 |
| $$p_t$$ | 0.8675 | 0.8989 | 0.9215 | 0.9377 | 0.9489 |
| $$a$$ | 0.8675 | 0.8989 | 0.9215 | 0.9377 | 0.9489 |
| $$W[\mu^1]$$ | 3.5805 | 2.3754 | 1.5542 | 0.9945 | 0.6155 |
В этой секции мы оптимизируем модель восстановления машин тем же способом, как сделал это Пальм в 1947 г. Заметим, что модель для единственного ремонтника (одного обслуживающего прибора) похожа на систему с потерями Эрланга, которую мы оптимизировали в Лекции 7. Мы можем видеть, что одна и та же модель может быть оптимизирована несколькими способами.
Рассмотрим терминальную систему с одним компьютером и $$S$$ терминалами и найдем оптимальное значение $$S$$. Примем следующую структуру затрат:
$$c_t$$ - стоимость на терминал в единицу времени при паузе (размышление или работа только с терминалом);
$$c_w$$ - стоимость на один терминал в единицу времени при ожидании;
$$c_s$$ - стоимость на один терминал в единицу времени при обслуживании;
$$c_a$$ - стоимость на компьютер в единицу времени.
Предполагается, что стоимость компьютера не зависит от использования и разбита однородно по числу всех терминалов. Результат (конечный продукт) процесса - это некоторое время паузы (размышления и подготовки информации в терминалах) во время производства продукта.
Общая стоимость $$c_0$$ в единицу времени, когда терминал в паузе:
$$p_t*c_0=p_t*c_t+p_s*c_s+p_w*c_w+\frac 1S*c_a$$(рис 12.11) Модель восстановления машины. Общие стоимости, данные в (12.57), показывают общую стоимость как функцию числа терминалов для сервисного отношения $$\varrho = 25$$ и отношения стоимости $$r = 1/25$$ (см. рис. 7.6)
Мы хотим минимизировать $$с_0$$. Сервисное отношение $$\varrho = m_t /m_s$$ равно $$p_t /p_s$$. Вводя отношение стоимости $$r = с_w /с_a,$$ получаем:
$$c_0=c_t+\frac{p_s}{p_t}*c_s+\frac{p_w*c_w+\frac 1S*c_a}{p_t}\\ =c_t+\frac{1}{\varrho}*c_s+c_a*\frac{r*p_w+(1/S)}{p_t},$$Это выражение должно быть свернуто как функция S. Учитывая, что только последний член зависит от числа терминалов, получаем:
$$min_S\{c_0\}=min_S \left \{\frac{r*p_w+(1/S)}{p_t} \right \}\\ =min_S \left \{\frac{r*(n_w/S)+(1/S)}{n_t/S} \right \}\\ =min_S \left \{ \frac{r*n_w+1}{n_t} \right \}$$ $$=min_S \left \{ \frac{r[S-\{1-E_{1,S}(\varrho)\}\{1+ \varrho\}]+1}{\{1-E_{1,S}(\varrho)\}*\varrho}\right \}\\ =min_s \left \{ \frac{r*S+1}{\{1-E_{1,S}(\varrho)\}* \varrho}+1+\frac{1}{\varrho} \right \},$$Мы замечаем, что минимум не зависит от $$c_t$$ и $$c_s$$ и что только отношение $$r = c_w /c_a$$ содержит характеристики стоимости. Числитель соответствует (7.31), тогда как знаменатель соответствует обслуженной нагрузке в соответствующей
PCT -IPCT -IIВероятность, что система c ожиданием находится в состоянии $$i$$, равна
$$p(i)=\begin{cases} p(o)* \frac{A^i}{i!}, 0 \le i \le n\\ p(n)*(\frac An)^{i-n}=p(0)*\frac{A^i}{n!*n^{i-n}} i \ge n \end{cases}.$$где
$$p(0)=\frac{1}{\sum_{i=0}^{n-1} \frac{A^i}{i!}+\frac{A^n}{n!} \frac{n}{n-A}}, A < n$$.Вероятность ожидания $$p\{W > 0\} = E_{2,n} ( A ) $$ в
( формула Эрланга для систем с ожиданием ).
Поскольку мы имеем очень точную рекурсивную формулу для числовой оценки B-формулы (7.29) Эрланга, можно использовать следующие отношения для того, чтобы получить числовые значения для C-формулы:
$$E_{2,n}(A)=\frac{E_{1,n}(A)}{1-A\{1-E_{1,n}(A)\}/n}$$Длина очереди $$L$$ в произвольной момент времени называется виртуальной длиной очереди. Эта длина очереди определяется для произвольного клиента:
$$L_n=E_{2,n}(A)*\frac{A}{n-A} \qquad A < n$$где $$L$$ - случайная переменная, обозначающая длину очереди.
Среднее время обслуживания для системы равно:
$$W_n=E_{2,n}(A)*\frac{s}{n-A}$$.Среднее время ожидания $$w$$ для задержанных вызовов:
$$W_n=\frac{s}{n-A}$$.Mo предложил свой принцип для систем организации очереди. Согласно этому принципу оптимальное решение равно:
$$F_{W,n_i-1}(A) > \frac{c_i}{\vartheta} \ge F_{W, n_i}(A), \quad i=1,2, \dots, k$$где $$c_i$$ - переменная стоимость канала;
$$F_{W,n}(A)$$ - функция увеличения времени ожидания;
$$\vartheta$$ (тета) -
FIFO (First In First Out). Эта дисциплина также называется дисциплина обслуживания в порядке поступления.При поступлении вызова в систему с ожиданием и дисциплиной обслуживания
Среднее время пребывания заявки в системе в случае одного обслуживающего прибора:
$$m=\frac{1}{\mu - \lambda}$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.