Моделирование систем массового обслуживания и метод Монте-Карло

    

  Абсолютная  пропускная способность (среднее число  заявок, обслуживаемых в единицу  времени) определяется величиной  
 

  Средняя длина очереди

  

 
 
 

  Cреднее число заявок, находящихся в системе, складывается из средних значений занятости каналов и длины очереди

    

  Среднее время пребывания заявки в очереди  равно 

    

  Общее время  пребывания заявки в очереди будет  складываться из T_очер и среднего времени обслуживания

    

  Полученные  характеристики дают возможность анализа  замкнутых и разомкнутых систем с отказами (=0), с очередью или с ожиданием при простейшем входном потоке и однотипных параллельных каналах обслуживания с показательным законом длительности обслуживания (в частности, с фиксированной длительностью).  

  4. Примеры систем  с ограниченной  очередью 

  Пример 1. Пусть на аэродром самолеты прибывают  с интенсивностью 27 самолетов в  час, время приземления составляет 2 минуты, допускается нахождение над  аэродромом не более  = 10 самолетов. Нужно определить число N посадочных полос, гарантирующее вероятность отказа, не превышающую 0.05, и среднее время ожидания, не превышающее 5 минут.  

  Здесь =27, = 30, R= / = 0.9.  

  Отыскиваем  вероятность простоя диспетчеров  службы посадки (19):

  

  Вероятность отказа в посадке равна 

  

 

  Среднее время ожидания в воздухе согласно (28) и (26)

  

   где 

  

   Выполняя  арифметические действия при  N=1, обнаруживаем, что 

  

   и что  одной посадочной полосы при  указанных условиях вполне достаточно.  

  Пример 2. Пусть имеются станки, которые  могут выходить из строя с частотой в среднем 2 раза за смену. Продолжительность  ремонта одним оператором составляет около трех часов (оператор одновременно может ремонтировать лишь один станок и не переходит к другому, не отремонтировав предыдущий). Хотелось бы определить число  операторов, при котором потери от простоя станков и оплаты лишнего  числа операторов были бы минимальны.  

  Такую замкнутую  систему можно представить системой с N каналами (операторами) и очередью с m местами ожидания (совпадает с  числом станков). Если известны потери С_п от простоя станка в течение часа и оплата Ср часа работы оператора, то при семичасовой смене задача сводится к нахождению значения N , которое минимизировало бы значение

  

   где  T_очер определяется (26) и (28) при =2/7, =1/3, R= / =6/7.  

  Можно привести множество подобных задач для  определения числа кассиров в  универмаге, наилучшего с позиций  минимума потерянных покупателей, для  определения числа бригад грузчиков  на железнодорожной станции, минимизирующего штраф за простой вагонов, для определения числа полос движения на проектируемой автомагистрали и т.п.  
 
 
 
 
 
 
 

  5. Дисциплина ожидания  и приоритеты 

  Выше мы рассматривали простейший поток  однотипных заявок с дисциплиной  выборки на обслуживание в порядке  поступления.  

  Можно показать, что и в случае случайного выбора на обслуживание полученные выше оценки не претерпят изменения, но их дисперсия (разброс относительно ожидаемой величины) возрастет. Очевидно, что среднее время сидения в очереди не изменится от того, что кто-то пройдет без очереди, но для отдельных клиентов время ожидания увеличится. Так отношение дисперсий времени ожидания в неупорядоченной и упорядоченной очереди имеет порядок (2+R)/(2-R), где R= / (мы обычно предпочитаем систему с жесткой дисциплиной обслуживания из-за предсказуемости ее поведения и всякое "возмущение" в ее работе отрицательно действует на нашу психику).  

  Существует  множество систем, в которых присутствует N>1 входных потоков с различной  интенсивностью _i(i = 1,..,N), время обслуживания заявок которых распределено по показательному закону с параметрами _i. Здесь при условии пуассоновости входных потоков можно считать, что суммарный поток будет пуассоновским с интенсивностью  функция распределения времени обслуживания заявок суммарного потока в одноканальной системе

  

   

  среднее время ожидания определяется формулой Полачека-Хинчина:

  

   которая для данного случая дает и в случае стационарности режима (R_{N < 1})

  

 

  Определенный  интерес представляют системы, где  каждому входному потоку сопоставлено целое число k - показатель приоритета потока (наивысший приоритет определяется k=1).  

  Если обслуживание заявки не прерывается ни при каких  условиях и выбор на обслуживание происходит с учетом приоритета (при  одинаковом приоритете выбирается первый пришедший в систему), то такая система называется системой с относительными приоритетами.  

  Можно показать, что поскольку время ожидания заявки с приоритетом k складывается из времени завершения обработки требования, вошедшего в канал, времени обслуживания ранее поступивших требований приоритета от 1 до k-1 и ранее поступивших требований с приоритетом k, то его среднее значение равно

  

 

  На этой основе можно определить среднюю  длину очереди заявок k -го приоритета L_k = _kW_k и среднее число таких заявок в системе L_k+R_k. Показано, что введение приоритетов улучшает функционирование системы, если более высокое преимущество присваивается заявкам с меньшей длительностью обслуживания. Если учитывать стоимостные характеристики, то более высокое преимущество предоставляется заявкам с большим значением С_{k k}, где С_k - средняя стоимость ожидания.

  

 

  Существуют  системы с абсолютными приоритетами, где появление заявки более высокого уровня прерывает обслуживание текущей  заявки, которая вернется в очередь  и потом снова поступит на обслуживание с места прерывания (или с начала). Здесь среднее время ожидания заявки с приоритетом k

  

 

  Рекомендуется для минимизации затрат на пребывание заявок в очереди в системах с относительными и абсолютными приоритетами, равных  
 
 

  где - издержки на ожидание заявки k -го приоритета в единицу времени, более высокий приоритет давать заявкам с наибольшим значением . 

  Исключительно сложно установить разумные приоритеты в случае многофазных систем, где  заявка проходит обслуживание в нескольких последовательных подсистемах. Здесь относительно простые выводы удается сделать лишь для случая двух подсистем, и для получения выводов для более сложных систем приходится прибегать к моделированию.  

  6. Моделирование систем массового обслуживания и метод Монте-Карло 

  До сих  пор мы рассматривали системы, для  которых удавалось описать результаты обследования в аналитическом виде. Однако, многие реальные системы (многофазные, c оригинальными приоритетами, с  признаками не стационарности, c не пуассоновскими входными потоками, с непоказательным распределением длительности обслуживания и т.д.) не поддаются такому решению.  

  Суть математического моделирования системы заключается в следующем.  

  Время функционирования системы разделяется на достаточно большое количество подинтервалов (единиц времени, в течение которых не может возникнуть более одной заявки или завершиться выполнение более одной заявки). Для каждого такого подинтервала последовательно моделируется факт появления новой заявки (да/нет), проверяется наличие свободного канала (закончено ли обслуживание какой-то заявки) и загрузка его заявкой из очереди, проверяется наличие мест в очереди с последующим выводом (принять в очередь/отказать в обслуживании) и т.д. При этом фиксируется число отказов, время ожидания заявок в очереди и в системе вообще, число заявок в очереди в каждый момент и другие значения, которые позволяют найти вероятность отказа, распределение времени ожидания и среднее время, вероятность простоя каналов и т.п. Для надежности выводов такое разовое моделирование повторяется достаточно много раз.  

  Очевидно, что ни о каком ручном моделировании  не может быть речи (объем работы здесь слишком велик для нормального  индивида). Здесь приходится использовать компьютер с встроенным или программным  датчиком псевдослучайных чисел  с равномерным законом распределения  в интервале от 0 до 1. Псевдослучайные  числа получаются по какому-то алгоритму, но в совокупности подчиняются всем законам проверки на случайность (мы не останавливаемся на методах их получения, так как есть отличные программные датчики во всех системах программирования).  

  В процессе моделирования возникает необходимость  генерации случайных чисел с  законом распределения, отличным от вышеуказанного.  

  Пусть R - случайные числа с равномерным  законом распределения в [0,1] и X - создаваемые случайные числа  с плотностью распределения p(X). Между  ними можно установить соотношение  
 

  Для равномерного распределения в [a,b] c очевидностью X=a+(b-a)R. Получение дискретных случайных чисел сводится к поиску наименьшего значения X, при котором

  

 

  Если взятие интеграла и представление X через R составит затруднение, можно воспользоваться  методом Неймана. Здесь при неограниченности области значений X усекаем ее до некоторого интервала [a,b]; например, для нормального распределения концы интервала берем отстоящими от среднего на 3-4 стандартных отклонения. Затем генерируется пара случайных чисел R₁ и R₂; если то берем X=a+(b-a)R₂ и в противном случае берем следующую пару случайных чисел.  

  Таким путем  мы можем моделировать интервалы  времени между заявками входного потока, продолжительность обслуживания заявки, вероятность выхода канала из строя и т.п.  

  Вопрос  о числе N отдельных реализаций системы  решается на основе закона больших чисел и вывода о том, что погрешность оценок имеет порядок

  

 

  Существуют многочисленные примеры успешного моделирования вполне реальных. 

  Описанный подход к поиску характеристик сложной  системы называют методом статистических испытаний (методом Монте-Карло), который  обычно используют там, где другие методы терпят фиаско (моделирование сложных  систем, вычисление интегралов кратности 10 и выше, поиск экстремумов функций  с очень большим числом переменных и др.).  
 
 
 
 
 
 
 
 

  Заключение 

  В последние  десятилетия существенно расширились  возможности исследования операций не столько за счет создания новых  методов, сколько за счет фантастического  увеличения возможностей компьютера. Так задача целочисленного линейного  программирования, требовавшая для  своего решения до трех часов машинного  времени сейчас решается в считанные  минуты.  

  Соответственно, появилось достаточно много компьютерных разработок, позволяющих пользователю, не слишком искушенному в области  математики и не умеющему писать программы  даже на уровне обычных алгоритмических  языков, успешно решать задачи исследования операций. Например, в популярной среде  электронных таблиц Excel предусмотрена стандартная процедура "Поиск решения", позволяющая достаточно просто записать ограничения на значения переменных (ячеек) и потребовать найти сочетание этих значений так, чтобы содержимое т.н. целевой ячейки приняло максимальное, минимальное или конкретное значение. Для реализации такого поиска можно выбрать итерационный подход (модифицированный метод Ньютона или метод сопряженных градиентов) и задать начальные приближения для искомых переменных.