Введение в компьютерное моделирование. Л. В. Горчаков в в в в е е д д е е н н и и е е в в к к о о м м п п ь ь ю ю т т е е р р н н о о е е м м о о д д е е л л и и р р о о в в а а н н и и е е учебное пособие
 Скачать 1.03 Mb.
|
|
7.1. Элементарные сведения из теории массового обслуживания Рассмотрим пример построения модели для системы массового обслуживания. Общим для таких моделей является необходимость пребывать в состоянии ожидания обслуживания. Феномен ожида- ния является следствием вероятностного характера возникновения потребностей в обслуживании и разброса показателей соответ- ствующих обслуживающих систем. Ни время возникновения по- требности в обслуживании, ни продолжительности обслуживания поступившего в обслуживающую систему клиента заранее не из- вестно. Цель изучения режима функционирования обслуживающей системы при существенном факторе случайности состоит в том, 69 чтобы взять под контроль количественные показатели функциони- рования системы массового обслуживания, например, среднего времени пребывания в очереди, времени простоя системы обслу- живания из-за отсутствия заявок на обслуживание. Чем дольше ожидание, тем меньше простой и наоборот. Варьируя их, можно достигнуть компромисса. Рассматриваемые модели основаны на теории вероятности и теории случайных процессов. Взаимодей- ствие заявки с обслуживающей системой рассматривается только с точки зрения регистрации продолжительности интервала времени, требуемого для полного обслуживания заявки с момента ее по- ступления в обслуживающую систему. Т.е. интерес представляют отрезки времени, разделяющие последовательные поступления за- явок на обслуживание. При описании потока входящих требований используется распределение вероятностей моментов поступления требований и распределение времени обслуживания требований. При фиксированных параметрах потока требований, заявок, клиен- тов и заданном объеме обслуживающего оборудования длина оче- реди является функцией времени. Поэтому процесс образования очереди будет стохастическим, так как он состоит из случайных событий. При построении функции распределения вероятностей для длины очереди нужно учесть особенности, присущие процессу образования очередей: 1) порядок, в соответствии с которым заказы поступают и за- нимают свое место в очереди; 2) количество обслуживающих единиц, исполняющих заказы и стратегию обслуживания, т.е. ограничения, наложенные на воз- можности и потребности обслуживания; 3) последовательность обслуживания – порядок очереди; 4) характер обслуживания и его длительность. Cистемы массового обслуживания классифицируются с исполь- зованием обозначений Кендалла-Ли вида / / : / / a b c d e f , где символы a, b, c, d, e, f связаны с существенными элементами модельного представления процессов массового обслуживания. а – распределение моментов поступления заявок на обслуживание, b – распределение времени обслуживания (или выбытий обслуженных клиентов), с – число параллельных узлов обслуживания, d – дисци- 70 плина очереди, e – максимальное число допускаемых в систему требований (число требований в очереди + число требований, при- нятых на обслуживание), f – емкость источника, генерирующего заявки на обслуживание. Для a и b приняты следующие обозначе- ния: М – пуассоновское распределение моментов поступлений заявок на обслуживание или выбытий из системы обслуженных клиентов (или экспоненциальное распределение интервалов времени между моментами последовательных поступлений или продолжительно- стей обслуживания клиентов), D – фиксированный (детерминированный) интервал времени между моментами последовательных поступлений в систему за- явок на обслуживание или детерминированная (фиксированная) продолжительность обслуживания, E k – распределение Эрланга или гамма-распределение интерва- лов времени между моментами последовательных поступлений требований в обслуживающую систему или продолжительностей обслуживания (при этом k –параметр распределения), GI – распределение произвольного вида моментов поступления в систему заявок на обслуживание (или интервалов времени между последовательными поступлениями требований), G – распределение произвольного вида моментов выбытия из системы обслуженных клиентов (или продолжительностей обслу- живания). Например, / /10 : / / M D GD N означает систему массо- вого обслуживания с пуассоновским входным потоком, фиксиро- ванным временем обслуживания и 10 параллельными узлами, дис- циплина очереди не регламентирована, независимо от числа посту- пающих требований данная система (очередь + обслуживаемые клиенты) не может вместить более N требований, т.е. остальные не принимаются, источник емкости. При решении такого сорта задач возможны две ситуации: 1) число заказов слишком велико, что приводит к большому времени ожидания в очереди и говорит о недостаточном количе- стве станций обслуживания; 2) недостаточное число заказов, что приводит к большому вре- мени простоя оборудования и говорит об избытке оборудования. 71 Поскольку оба требования являются взаимоисключающими, то целью решения задачи являются установление оптимального соот- ношения между потерями, вызванными простоем оборудования и потерями из-за ожидания в очереди. Примером, который часто приводится в литературе, служит мо- делирование системы массового обслуживания с одной станцией обслуживания, обслуживание в порядке поступления, время об- служивания и время между поступлениями распределены по экс- поненциальному закону. Если мы возьмем некоторый интервал времени между поступлениями i-го и (I + 1) требований и обозна- чим его ATi, а время обслуживания i-го требования –STi, то время ожидания (WTi) и простой станции (IT) можно изобразить графиче- ски, как это сделано на рис. 20. время ST1 ST2 ST3 WT2 IT WT4 AT1 AT2 AT3 AT4 Рис. 20. Одноканальная система массового обслуживания Рассмотрим самый простой вид потока заявок – стационарный пуассоновский поток, который имеет свойства стационарности, ординарности и отсутствия последействия. Поток является стацио- нарным, если его вероятностные характеристики не зависят от сдвига во времени, т.е. вероятность, что на интервале t происходит некоторое количество событий, зависит от длины интервала и не зависит от его положения на оси t. Поток является ординарным, если в каждый момент времени может поступать только одна заяв- ка. Отсутствие последействия означает независимость событий друг от друга, т.е. длина интервала времени до момента поступле- ния следующей заявки не зависит от того, поступила ли в начале этого интервала заявка или нет. Рассмотрим процесс образования очереди на единственной станции – найдем среднюю длину очереди и вероятность появле- ния очереди заданной длины при случайных потоках заказов. Пусть скорость обслуживания не зависит от числа заказов в очере- 72 ди и заказы обслуживаются по очереди. Используем следующие обозначения: n P t – вероятность образования очереди из n заказов к момен- ту t; t – вероятность появления в очереди нового заказа в проме- жутке времени от t до t+ t, где – средняя скорость появления заказов; t – вероятность того, что в интервале времени от t до t+ t за- вершается исполнение заказа, находящегося на обслуживании, где – средняя скорость обслуживания; s L – среднее число находящихся в системе клиентов (заявок); L q – среднее число клиентов в очереди на обслуживание; W s – средняя продолжительность пребывания клиента в системе; W q – средняя продолжительность пребывания клиентов в очере- ди. По определению [11] 0 , s q n n n c L np L n c p , где с – число узлов обслуживания. Между L s и W s (L q и W q ) существует строгая взаимосвязь. В частности, если частота поступлений в систему заявок равна , то L s = W s , L q = W q Если не все заявки могут попасть в блок ожидания, то вводят эфф , учитывающее действительно допускаемые в систему требова- ния, т.е. эффективная частота поступлений. Тогда L s = эфф W s , L q = эфф W q В общем случае эфф , 0 1 . В любом случае можно установить зависимость от L s и Lq для эфф . По определению средняя продолжительность пребывания в системе равна средней продолжительности пребывания требований в очереди плюс сред- нее время обслуживания. Если средняя скорость обслуживания – и средняя продолжительность обслуживания 1/ , то W s = W q + 1/ Умножая на , получаем L s = L q + . Это справедливо и для эфф . При этом эфф s q L L . Далее основное внимание 73 будет направлено на формулы для n P , так как из них можно полу- чить все остальные в следующей очередности 0 1 n s n s s q s q q n P L np W L W W L W Рассмотрим пример, пусть с = 1 и среднее количество поступлений – 3 в час, а скорость обслуживания – 8 в час. Вероятность того, что в системе окажется n требований – n P определяется на основе наблюдений и данные помещены в табл. 11. Таблица 11 n 0 1 2 3 4 5 6 7 8 n P 0,615 0,234 0,088 0,033 0,012 0,005 0,002 0,001 0 Вычислим L s , W s , W q , L q 0 0 0, 625 1 0, 234 2 0, 088 3 0, 033 4 0, 012 5 0, 005 6 0, 002 7 0, 001 0, 6. s n n L np Так как = 3, то 0, 6 3 0, 2 s s W L часа. Учитывая, что = 8, имеем 1 0, 2 1 8 0, 075 q s W W часа, т.е. среднее количество находящихся в очереди клиентов равно 3 0, 075 0, 225 q q L W Вычислите среднее количество находящихся в очереди требова- ний, используя n P – ответ 2 1 0, 225 q n n L n p Вычислите среднее количество клиентов, которое обслуживает- ся системой – ответ 0,375 s q L L В теории массового обслуживания показано, что поведение ве- роятности P n (t) будет описываться дифференциальными уравнени- ями 1 1 , 0 n n n n dP t dt P t P t P t n , 0 0 1 dP t dt P t P t (51) Они в неявном виде отражают связь между временем ожидания и временем обслуживания и являются исходным пунктом для реше- 74 ния задач теории очередей. В частном случае n n P t P const решение имеет простой вид 0 1 , 1 n n P P , (52) где n P – вероятность появления очереди длины n. Отношение / называется интенсивностью нагрузки – средний объем обслужива- ния в единицу времени. Для среднего числа находящихся в системе клиентов получается формула 0 1 , 1 s n n L np . (53) Пусть число поступающих заказов в день равно = 10, а скорость обслуживания = 20 заказов в день. Тогда / = 1/2. Подставляя это значение в формулы, получим 1 2 1 1 2 и 1 2 1 1 2 1 n n s P L (54) Тогда вероятность появления очереди из 0,1,2… заказов в любой момент времени будет иметь вид табл. 12 Таблица 12 N 0 1 2 3 Pn 1/2 1/4 1/8 1/16 С увеличением интенсивности нагрузки / средняя длина очереди быстро возрастает и при / ->1 становится бесконечной. Уравне- ние для n перестает быть справедливым при / =1. Подставляя не- сколько значений / в формулу, можно найти как изменяется средняя длина очереди в зависимости от / (табл. 13). Таблица 13 Интенсивность нагрузки 1/2 3/4 7/8 15/16 Средняя длина очереди 1 3 7 15 Обозначим , тогда 2 1 1 , 1 , 1 s q q W L W Рассмотрим пример, пусть на мойку автомобили поступают по за- кону Пуассона со средней интенсивностью 5 автомобилей в час. 75 Продолжительность обслуживания подчиняется экспоненциально- му закону со средним значением 10 автомобилей в час. Узел об- служивания один. Таким образом, = 5, = 60/10 = 6 автомобилей в час, таким образом, = = 5/6<1 и достигается стационарный режим. Вычислим, какое количество стоянок нужно оборудовать на мойке. 2 5 6 1 5 6 4,14 4 q L автомобиля. Но L q – это математическое ожидание, т.е. может быть больше или меньше этого количества. Допустим, цель обеспечить одновремен- но 80% клиентов стоянкой. Это эквивалентно выполнению условия 0 1 0,8 s p p p . Используя формулу для n p , можно запи- сать 1 1 1 0,8 s Учитывая, что 1 1 1 1 1 1 1 1 1 1 1 , s s s s получаем 1 0, 2 s . Логарифмируя при = 5/6, имеем 1 log 5 6 log 0,8 s Так как log(5/6)<0, то деление на log(5/6) меняет знак неравенства, т.е. для s получаем log 0, 2 log 5 6 1 7,8 8 s площадок. Можно вычислить долю времени бездействия мойки – вероятность того, что на мойке не окажется ни одного автомобиля 0 1 0,17 p , т.е. 17% времени простаивает. Для оценки каче- ства обслуживания полезно знать среднее время пребывания авто- мобиля на станции (от момента прибытия до момента завершения мойки). 1 1 1 6 1 5 6 1 час s W Вычислите вероятность то, что прибывший автомобиль будет ждать обслуживания – ответ 0.8333. 76 Вычислите вероятность того, что при наличии 6 мест для стоянки для прибывающего автомобиля не найдется места – ответ 7 7 0, 279 n p Для системы массового обслуживания вида (M/M/1):(GD/N/ ) для вероятностей были получены следующие формулы 1 1 1 , для 1 и 0,1,... N n n P n N , 1 1 для 1 n P N 1 1 1 1 1 1 для 1 N N N s L N N , 2 s L N для = 1. Рассмотрим пример, пусть мойка имеет 5 площадок для стоян- ки. Службу интересует количество клиентов, которое она теряет из-за ограниченности числа площадок. Это эквивалентно нахожде- нию разности между и эфф эфф 1 N p , откуда эфф N p . Здесь 5 1 9, 5 6 N и 7 6 1 5 6 1 5 6 5 6 0, 07774, 6 N p N , т.е. частота возникновения ситуаций, когда все пять стоянок заня- ты, равна 5 0,07774 = 0,387 автомобилей в час, при 8-часовом рабо- чем дне – это означает потерю трех клиентов в среднем. Опреде- лим среднее время пребывания на мойке, вычислив L s и W s 6 7 7 5 6 1 7 5 6 6 5 6 1 5 6 1 5 6 2, 29 s L Так как вероятность того, что требования не имеют возможности присоединиться к очереди равна N p (т.е. вероятности, что в систе- ме уже N требований) доля требований, которым разрешено войти в блок ожидания равно 1 N P n N p Отсюда эфф 1 N p , эфф 1 q q q N W L L p , эфф 1 s q q N L L L p , 1 1 s q s N W W L p 77 Таким образом, эфф 1 s q N L L p С учетом эфф 6 1 5 1 0, 07774 4, 613 p , получаем эфф 2, 29 4, 613 0, 496 s s W L часа. Таким образом, при введении ограничения на количество мест для стоянки (N = 6) среднее время ожидания сократилось на полча- са по сравнению с очередью. Это достигнуто за счет «потери» в среднем трех автомобилей в день из-за недостаточности мест для стоянки. |