Механики
 Скачать 4.29 Mb.
|
λ Н (О) b Рис.4.1. Одноканальная система массового обслуживания (СМО) Раздел 4. АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ «Всякое уравнение длиной более двух дюймов, скорее всего, неверно!» (Автор неизвестен ) 4.1. Одноканальные СМО с однородным потоком заявок Рассмотрим одноканальную СМО с однородным потоком заявок при следующих предположениях (рис.4.1): 1) СМО содержит один обслуживающий прибор, в котором в каждый момент времени может обслуживаться только одна заявка; 2) перед прибором имеется накопитель Н неограниченной ёмко- сти, что означает отсутствие отказов поступающим заявкам при их поста- новке в очередь О, то есть любая поступающая заявка всегда найдет в накопителе место для ожидания не зависимо от того, сколько заявок уже находится в очереди; 3) заявки поступают в СМО с интенсивностью λ ; 4) средняя длительность обслуживания одной заявки в приборе равна b, причем длительности обслуживания разных заявок не зависят друг от друга; 5) обслуживающий прибор не простаивает, если в системе (накопителе) имеется хотя бы одна заявка, причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка; 6) заявки из накопителя выбираются в соответствии с бесприори- тетной дисциплиной обслуживания в порядке поступления (ОПП) по правилу «первым пришел – первым обслужен» (FIFO – First In First Out). 7) в системе существует стационарный режим, предполагающий отсутствие перегрузок, то есть нагрузка и, следовательно, загрузка системы меньше 1: 1 < = = b y λ ρ В качестве расчётной характеристики обслуживания заявок в СМО будем использовать среднее время ожидания заявок Значения остальных характеристик функционирования СМО легко могут быть рассчитаны с использованием приведенных в разделе 3 фундаментальных соотношений (3.13) – (3.15). Рассмотрим четыре модели СМО с однородным потоком заявок : экспоненциальную СМО М / М /1 и три неэкспоненциальные СМО типа M/G/1, G/M/1, G/G/1. Раздел 3. Аналитическое моделирование 121 4.1.1. Характеристики экспоненциальной СМО M/M/1 Пусть заявки , поступающие в одноканальную СМО , образуют простейший поток с интенсивностью λ , а длительность b τ обслуживания заявок распределена по экспоненциальному закону со средним значением b , причём 1 < = b λ ρ , то есть система работает в установившемся режиме Такая СМО с однородным потоком заявок называется экспоненциальной С использованием метода средних значений [2] или марковской модели ( см п .5.4.4) можно получить следующие выражения для расчета средних значений : • времени ожидания заявок ρ ρ − = 1 b w ; (4.1) • времени пребывания заявок ρ − = + = 1 b b w u ; (4.2) • длины очереди заявок ρ ρ λ − = = 1 2 w l ; • числа заявок в системе ( в очереди и на обслуживании ) ρ ρ λ − = = 1 u m Из последнего выражения вытекает , что среднее число заявок в системе ρ + = l m , где второе слагаемое ρ определяет среднее число заявок , находящихся на обслуживании в приборе Кроме того , сравнивая выражения (4.1) и (4.2) получим , что w u ρ = 4.1.2. Характеристики неэкспоненциальной СМО M/G/1 Пусть заявки , поступающие в одноканальную СМО , образуют простейший поток с интенсивностью λ , а длительность b τ обслуживания заявок распределена по произвольному закону ) ( τ B со средним значением b и коэффициентом вариации b ν С использованием метода средних значений можно показать , что среднее время ожидания заявок определяется по формуле Поллачека - Хинчина [2]: ) 1 ( 2 ) 1 ( 2 2 ρ ν λ − + = b b w , (4.3) где 1 < = b λ ρ – загрузка системы. Среднее время пребывания заявок в системе: 122 Раздел 3. Аналитическое моделирование b b b w u b + − + = + = ) 1 ( 2 ) 1 ( 2 2 ρ ν λ Следует отметить интересную особенность представленных выраже - ний , а именно : средние значения характеристик обслуживания заявок зави - сят только от двух первых моментов длительности обслуживания заявок и не зависят от моментов более высокого порядка Другими словами , для того чтобы рассчитать средние характеристики обслуживания , не обяза - тельно знать закон распределения длительности обслуживания заявок – достаточно знать только два первых момента распределения Можно пока - зать , что для расчета вторых моментов характеристик обслуживания зая - вок достаточно задать три первых момента длительности обслуживания и т д Резюмируя , можно утверждать , что для СМО с простейшим потоком заявок для расчёта первых k моментов характеристик обслуживания необходимо задать ) 1 ( + k моментов длительности обслуживания заявок 4.1.3. Характеристики неэкспоненциальной СМО G/M/1 Пусть в одноканальную СМО с интенсивностью λ поступает случайный поток заявок произвольного вида , задаваемый функцией распределения интервалов между заявками ) ( τ A , а длительность b τ обслуживания заявок распределена по экспоненциальному закону ) ( τ B со средним значением b ( интенсивностью b / 1 = µ ). СМО G/M/1 является симметричной по отношению к СМО M/G/1, рассмотренной в предыдущем пункте Однако получение конечного результата в виде аналитического выражения для расчёта среднего времени ожидания , по аналогии с предыдущей моделью , в общем случае , оказывается невозможным Это обусловлено тем , что среднее время ожидания , впрочем , как и другие числовые моменты , зависит не только от двух первых моментов интервалов между поступающими заявками , но и от моментов более высокого порядка , т е от закона распределения интервалов между заявками Среднее время ожидания заявок в очереди может быть рассчитано следующим образом [9]: ) 1 /( ς ς − = b w , (4.4) где ς – единственный в области 1 0 < < ς корень уравнения ) ( * µς µ ς − = A . (4.5) Здесь ) ( * s A – преобразование Лапласа плотности распределения ) ( τ a интервалов между поступающими в систему заявками : ∫ ∞ − ≥ = 0 * ). 0 ( ) ( ) ( s d a e s A s τ τ τ Раздел 3. Аналитическое моделирование 123 Основная сложность при исследовании СМО G/M/1 заключается в том, что уравнение (4.5) для нахождения ς , в общем случае, является трансцендентным, и невозможно получить выражение для ς в явном виде. Однако в каждом конкретном случае корень уравнения (4.5) может быть найден с использованием численных методов. Как сказано выше, средние значения характеристик обслуживания заявок зависят не только от двух первых моментов интервалов между поступающими заявками, но и от моментов более высокого порядка, причем степень влияния соответствующих моментов убывает с увеличением порядка моментов. Другими словами, влияние моментов 4-го порядка менее существенно, чем моментов 3-го порядка и т.д. Пример 4.1. Проиллюстрируем применение описанного метода расчета к рассмотренной выше СМО M/M/1 с простейшим потоком заявок. В простейшем потоке интервалы времени между последовательными заявками распределены по экспоненциальному закону, преобразование Лапласа которого имеет вид: s s A + = λ λ ) ( Тогда уравнение (4.5) примет вид: ς µ µ λ λ ς − + = После некоторых преобразований получим квадратное уравнение: 0 ) ( 2 = + + − λ ς µ λ ς µ Разделив левую и правую часть этого уравнения на µ , получим: 0 ) 1 ( 2 = + + − ρ ς ρ ς Из двух корней 1 1 = ς и ρ ς = 2 последнего уравнения условию 1 0 < < ς удовлетворяет только второй корень Подставляя его в выражение (4.4) окончательно получим выражение для среднего времени ожидания , совпадающее с известным для СМО M/M/1 выражением (4.1). 4.1.4. Характеристики СМО общего вида G/G/1 Наиболее общим случаем одноканальных систем массового обслуживания являются СМО типа G/G/1, в которую поступает произвольный поток заявок общего вида с функцией распределения интервалов между заявками ) ( τ A Длительность обслуживания заявок в приборе распределена по произвольному закону ) ( τ B Расчет таких систем требует задания конкретных законов распределений , что не позволяет получить аналитическое решение в общем виде Аналитическое решение возможно только для некоторых частных распределений , связанных , например , с экспоненциальным распределением Для большинства законов распределений интервалов между поступающими в систему заявками и длительностей их 124 Раздел 3. Аналитическое моделирование обслуживания в приборе невозможно получить точное решение в аналитической форме В то же время , на практике при исследовании реальных систем редко бывают известны законы распределений указанных величин Обычно при описании процессов поступления заявок в систему и их обслуживания в приборе ограничиваются несколькими моментами соответствующих распределений , чаще всего – двумя первыми моментами , задаваемыми в виде математического ожидания и среднеквадратического отклонения или коэффициента вариации искомой случайной величины Однако при этом оказывается невозможным получение точного результата Это обусловлено тем , что в случае произвольного ( отличного от простейшего ) потока заявок , поступающих в систему , характеристики функционирования СМО , в частности среднее время ожидания , зависят не только от двух первых моментов , но и от моментов более высокого порядка – третьего , четвёр - того и т д Причём эта зависимость тем меньше , чем выше порядок число - вого момента Таким образом , все результаты , полученные в аналитичес - кой форме при задании интервалов между поступающими в систему заявками и длительностей их обслуживания в приборе двумя первыми моментами – средними значениями λ / 1 = a и µ / 1 = b и коэффициентами вариации a ν и b ν , представляют собой приближённые зависимости Как показал анализ многочисленных опубликованных результатов , одним из наиболее удачных приближений для расчета среднего времени ожидания в СМО G/G/1 является следующая формула [17]: ) ( ) 1 ( 2 ) ( 2 2 a b a f b w ν ρ ν ν ρ − + ≈ , (4.6) где 1 < = b λ ρ – загрузка системы; λ , a ν – интенсивность потока заявок и коэффициент вариации интервалов между поступающими в систему заявками; b , b ν – среднее значение и коэффициент вариации длительности обслуживания заявок; ) ( a f ν – корректирующая функция, рассчитываемая в зависимости от значения коэффициента вариации a ν : ≥ + − − − < + − − − = 1 , 4 1 ) 1 ( exp 1 , ) ( 3 ) 1 )( 1 ( 2 exp ) ( 2 2 2 2 2 2 2 a b a a a b a a a f ν ν ν ν ρ ν ν ν ρ ν ρ ν При решении многих практических задач выходящий поток заявок из одной СМО является входящим потоком в другую СМО. В этом случае для расчёта характеристик функционирования второй СМО необходимо знать характер входящего потока, наиболее полно описываемый законом распределения интервалов между последовательными заявками. В то же время, для проведения оценочных расчётов во многих случаях достаточно Раздел 3. Аналитическое моделирование 125 знание первых двух моментов этих интервалов: математического ожидания и коэффициента вариации. Очевидно, что в СМО с накопителем неограниченной ёмкости, работающей без перегрузок, интенсивность выходящего потока заявок равна интенсивности входящего потока, то есть математические ожидания интервалов между последовательными заявками на выходе и входе СМО совпадают. Можно показать, что для экспоненциальной СМО М/М/1 коэффициент вариации выходящего потока равен единице. В общем случае для СМО G/G/1 коэффициент вариации выходящего потока заявок может быть рассчитан по следующей приближённой формуле [17]: b w b a c ) 1 ( 2 2 2 2 2 ρ ρ ρν ν ν − − + ≈ . (4.7) 4.1.5. Анализ свойств одноканальной СМО «Если факты не подтверждают теорию, от них надо избавиться» (Закон Майерса) Анализ свойств одноканальной СМО с однородным потоком заявок будем проводить с использованием представленных выше математических моделей в виде формул (4.1 – 4.3), определяющих зависимости характери- стик обслуживания заявок от параметров поступления и обслуживания заявок для установившегося (стационарного) режима работы системы. 1. Среднее время ожидания заявок в очереди минимально при постоянной (детерминированной) длительности обслуживания заявок, когда коэффициент вариации длительности обслуживания 0 = b ν , и увеличивается с ростом коэффициента вариации (дисперсии) длительности обслуживания. Заметим, что зависимость среднего времени ожидания от коэффициента вариации b ν носит нелинейный характер. Так, например, при экспоненциально распределенной длительности обслуживания, когда 1 = b ν , среднее время ожидания заявок увеличивается в 2 раза, а при 2 = b ν – в 5 раз, по сравнению с детерминированным обслуживанием. 2. Среднее время ожидания заявок существенно зависит от нагрузки y (загрузки ρ )системы (рис.4.2). При ) 1 ( 1 → ≥ ρ y время ожидания заявок возрастает неограниченно: ∞ → w , т.е. заявки могут ожидать обслуживания сколь угодно долго. Отметим, что увеличение нагрузки может быть обусловлено двумя факторами: увеличением интенсивности поступления заявок в систему или увеличением длительности обслужи- вания заявок (например, в результате уменьшения скорости работы обслуживающего прибора). 126 Раздел 3. Аналитическое моделирование 3. Можно показать, что для бесприоритетных дисцип- лин обслуживания в обратном порядке (ООП) и обслужива- ния в случайном порядке (ОСП) средние времена ожида- ния заявок будут такими же, как и при обслуживании в порядке поступления, но дисперсии времени ожидания будут больше. Это обусловле- но, в частности для дисципли- ны ООП, тем, что часть заявок, поступивших последними, будут ожидать незначительное время, в то время как заявки, попавшие в начало очереди, могут ожидать обслуживания достаточно долго, то есть увеличивается разброс значений времени ожидания относительно среднего значения. 4.2. Многоканальные СМО с однородным потоком заявок «Работая над решением задачи, всегда полезно знать ответ» (Правило точности) Рассмотрим многоканальную СМО с K идентичными обслуживаю- щими приборами и накопителем неограниченной ёмкости, в которую поступают заявки, образующие простейший поток с интенсивностью λ (рис.4.3). Длительность b τ обслуживания заявок распределена по экспо- ненциальному закону со средним значе- нием b . Выбор заявок из очереди на обслуживание осуществляется в соот- ветствии с бесприоритетной дисципли- ной обслуживания в порядке поступле- ния (ОПП) по правилу «первым пришёл – первым обслужен» (FIFO – First In First Out). 4.2.1. |