2.3.3. Моделирование системы массового обслуживания

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

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

Применение метода статистических испытаний для моделирова­ния процесса функционирования системы массового обслуживания рассмотрим на конкретном примере системы с отказами.

Система, в которую в отдельные случайные моменты времени поступают заявки, состоит из каналов (пунктов обслуживания). Поток заявок представляет собой простейший поток, интервал вре­мени между двумя последовательными событиями есть случай­ная величина, распределенная по экспоненциальному закону, и вычисляется по формуле (2.3.18):

,

где – интенсивность потока заявок (среднее число заявок в единицу времени);

– случайная величина, равномерно распределенная в ин­тервале .

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

.

Если в момент поступления заявки все каналы заняты, система выдает отказ.

-

- тый канал

Рис. 2.7. Показатели эффективности системы время функционирования

Требуется определить показатели эффективности системы время функционирования .

Введем следующие обозначения (рис. 2.7):

– момент поступления -той заявки;

– -тый интервал между двумя последовательными заявками (между -той и заявками);

– момент освобождения -того канала:

За начальный примем момент поступления первой заявки .

В этот момент все каналы свободны .

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

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

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

Оператор 3 определяет, принадлежит ли -тая заявка заданному интервалу времени функционирования системы. Если условие выполняется, заявка поступает на обслуживание управление передается оператору 4. В противном случае испытание заканчивается и управление передается на счетчик числа испытаний.

Оператор 4 сравнивает между собой моменты освобождения каналов системы и выбирает канал, освободившийся раньше всех. Если есть каналы, освободившиеся одновременно, выбирается канал с меньшим номером. Пусть номер выбранного канала равен . Заявка поступает для обслуживания в этот канал. Очевидно, в каждом испытании первая заявка поступает в первый канал, вторая заявка – во второй канал, третья – в третий, так как в начальный момент .

Рис. 2.8. Логическая схема алгоритма процесса обслуживания заявок

Оператор 5 сравнивает момент освобождения выбранного канала с моментом поступления -той заявки Если условие не выполняется, это означает, что все каналы к моменту заняты, система выдает отказ и управление передается оператору 6. Если же указанное условие выполняется, канал с номером свободен и управление передается оператору 10.

Оператор 6 представляет собой счетчик числа отказов, после каждого отказа показание счетчика увеличивается на единицу.

После отказа -той заявке необходимо формировать следующую заявку. Для этой цели предназначены операторы 7, 8 и 9.

Оператор 7 формирует поток заявок, то есть по формуле

определяет интервал времени между двумя последовательными заявками (между -той и ). Из формулы видно, что для определения оператор также формирует значения .

Оператор 8 формирует момент поступления следующей заявки

.

Оператор 9 формирует номер очередной заявки (за новым номером сохраняется прежнее обозначение ). С оператора 9 управление передается на оператор 3, где момент поступления новой заявки (за ним сохраняется прежнее обозначение ) сравнивается с временем , и начинается новый цикл.

Если условие проверку которого осуществляет оператор 5, выполняется, то выбранный оператором 4 канал с номером свободен и заявка передается в этот канал для обслуживания. Дальше необходимо определить время обслуживания -той заявки, найти время освобождения канала, зафиксировать обслуженную заявку и формировать следующую заявку. Эту задачу выполняют операторы 10, 11 и 12.

Оператор 10 определяет время обслуживания -той заявки согласно формуле

.

Оператор 11 вычисляет время освобождения канала с номером по формуле

.

Оператор 12 представляет собой счетчик числа обслуженных заявок, после каждой обслуженной заявки показание счетчика увеличивается на единицу.

С оператора 12 управление передается на оператор 7 и дальше формируется следующая заявка так же, как и в рассмотрением случае отказа в обслуживании.

Если неравенство не выполняется (следовательно , это означает, что -тая заявка уже не принадлежит задан ному интервалу, и реализация на этом заканчивается.

Оператор 13 представляет собой счетчик числа испытаний.

Оператор 14 проверяет, получено ли уже заданное число испытаний . Если неравенство выполняется, управление передается оператору 15.

Оператор 15 осуществляет подготовку к следующему испытанию. При этом очищаются рабочие ячейки, хранящие значения и , а содержимое ячеек, хранящих число отказов и обслуженных заявок, пересылаются в специальный массив для последующей статистической обработки. Дальше управление передается на оператор 3, и начинается очередное испытание.

Если неравенство не выполняется, управление передается оператору 16.

Оператор 16 осуществляет статистическую обработку полученных результатов и вычисляет требуемые показатели эффективности функционирования системы за время .

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

Пример. Рассмотрим, как можно моделировать одно­фазные системы обслуживания с помощью ручных вычислений. Этот пример должен пояснить основные идеи, описанные выше.

Пусть мы хотим моделировать систему массового обслуживания, поступление требований в которой подчинено пуассоновскому рас­пределению со средним 3 клиента в час, а время обслуживания рав­но 0,2 ч с вероятностью 0,5 или 0,6 ч с вероятностью 0,5. Клиенты обслуживаются согласно дисциплине «первым пришел – первым обслуживаешься»; длина очереди, а также источник поступления клиентов не ограничены. Предположим, что в начальный момент мо­делирования клиентов нет.

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

.

Поскольку время обслуживания равно либо 0,2, либо 0,6 ч с рав­ными

вероятностями, время обслуживания определяется как

Как указывалось выше, в однофазной системе обслуживания возможны события только двух типов: поступление клиентов и их уход (окончание обслуживания). Действия, вызываемые этими со­бытиями, можно охарактеризовать следующим образом.

Событие, связанное с поступлением клиента

1. Генерация момента времени, в который поступает следующее требование на обслуживание, путем вычисления промежутка вре­мени между требованиями и добавления его к текущему времени моделирования. (Это действие необходимо для обеспечения непрерывности процесса моделирования.)

2. Проверка состояния системы (простой или работа).

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

б) Если система работает, поставить поступившего клиен­та в очередь и увеличить ее длину на единицу.

Событие, связанное с окончанием обслуживания

1. Проверка состояния очереди (пустая или непустая).

а) Если очередь пуста, объявить простой системы.

б) Если, непуста, то начать обслуживание первого по очереди клиента, уменьшить длину очереди на единицу и скорректировать протокол времени ожидания; получить время обслуживания клиента и вычислить время окончания обслуживания (текущее время ). Поскольку в этом примере система начинает работу при пустой очереди, она начинает функционировать с состояния простоя. Пер­вая заявка на обслуживание поступает через

ч.

Последовательность случайных чисел, используемая в данном при­мере, из следующего ряда

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

.

П оступление Поступление Конец обслуживания

Рис. 2.9. События, связанные с окончанием обслуживания

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

.

Система объявляется работающей, а время простоя корректируется следующим образом:

Время простоя ч.

Осуществившиеся до настоящего момента события показаны на рис. 2.9.

Следующее по времени событие – поступление требования в мо­мент . Поскольку система продолжает работать, требование ставится в очередь, а длина очереди корректируется:

(в момент ).

Следующее требование поступает в момент времени

.

(В рассматриваемом примере полезно наносить новые события на рис. 2.9 по мере их получения.)

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

Следующее событие состоит в поступлении требования на об­служивание в момент . Поскольку система все еще находится в рабочем состоянии, длина очереди должна быть скорректирована

(в момент ),

а следующее требование поступит в момент

.

Следующее событие, происходящее в момент , представляет собой окончание обслуживания. Поскольку очередь непуста, начи­нается обслуживание первого по очереди клиента. Длина очереди изменяется

(в момент ),

а суммарное время ожидания становится равным

ч.

Используя , получаем время завершения обслуживания данного клиента:

.

Теперь становится понятным, как получаются данные в ходе эксплуатации имитационной модели. Процедура повторяется до тех пор, пока не будет промоделирован весь интервал . После можно определить различные операционные характеристики, исходя из периода моделирования:

Доля времени простоя системы, %	=	Суммарное время простоя П ериод моделирования	100
С реднее время ожидания клиентом обслуживания	=	Суммарное время ожидания Ч исло поступающих клиентов

Вычисление средней длины очереди осуществляется несколько ина­че. Из рис. 2.10 видно, каким образом обычно меняется длина оче­реди в зависимости от за моделируемый период времени продол­жительности . Например, в рассматриваемой здесь обслуживаю­щей системе длина очереди в период между и , между и и между и . Эта информация необходима для получения графика на рис.17.7. Средняя длина очереди представляет собой среднее значение, изобра­женное пунктирной линией, то есть

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

Площадь Моделируемый период

Заметим, что для получения необязательно ждать истечения пе­риода поскольку можно вычислять через приращения каждый раз, когда меняется . Так, в данном примере между и и ; между и и, следовательно, ; между и и . Этот процесс приращений продол­жается до тех пор, пока не станет равным .

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

Средняя длина очереди = A/t

Площадь A