Основы теории очередей

Стохастическое моделирование

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

Стохастическое моделирование – это один из видов имитационного моделирования, базирующийся на теории Монте-Карло. Его определение можно представить так:

& Стохастическое моделирование (англ. stochastic modeling) – разновидность имитационного моделирования, в котором моделируемый объект представляется в виде совокупности параметров, описывающих внешнюю работу системы (внутренняя особенность объекта неизвестна) и имеющих случайную природу.

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

С внедрением автоматизации на предприятиях длительность изготовления продукции существенно сократилась за счёт ускорения выполнения роботами операций и внедрения конвейера. Производственный/обслуживающий процесс в основном стал сводиться к последовательности чётко разделённых технологических циклов, следующих друг за другом последовательно. Увеличился объём выпускаемой продукции, а следовательно, и нагрузки на обслуживающие элементы системы, что привело к возникновению задачи эффективной статистической оценки работы как системы в целом, так и её отдельных частей. Так появился подход, называемый теорией массового обслуживания или теорией очередей.

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

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

Стохастическое моделирование можно охарактеризовать следующими признаками:

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

– отсутствием информации о внутренней логике работы подсистем (всё задано случайными процессами во времени);

– наличием чёткой последовательности технологических операций в моделируемом процессе;

– рассмотрением однотипных объектов на каждом этапе процесса обслуживания;

– выделением законов движения транзакта путём наблюдения за моделируемой системой и обработки полученной статистики;

– просчётом, который позволяет визуализировать эволюцию модели на каждом шаге моделирования;

– представлением экспериментальных данных в виде таблицы-отчёта и графиков.

Условно в теории очередей рассматривается последовательность изменения состояния обслуживаемой заявки (транзакта) между этапами «поступление», «ожидание в очереди», «обслуживание», «покидание системы». При этом процесс внутренней работы подсистем (обслуживание) не детализируется, как в других моделях, а лишь характеризуется обобщенными временными характеристиками (высокая стохастичность). По этой причине подобные модели получили ещё одно название – системы массового обслуживания.

& Система массового обслуживания (англ. queue(ing) system, СМО) – система, описывающая движение транзактов в исследуемом сложном объекте, характеризуемом траекторией обслуживания транзактов в виде временных интервалов.

Целью исследования в модели будут этапы обслуживания – наиболее трудно формализуемые элементы в системе.

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

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

& Транзакт (англ. transact) – элементарный элемент обслуживания в модели (заявка), траектория обработки которого описывается на всём этапе его присутствия в системе в соответствии с особенностями технологического процесса.

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

По типу:

1) человеческие (например, клиенты торговой точки);

2) финансовые (например, заявка на денежный перевод в отделение банка);

3) информационные (например, вызов на междугороднюю АТС);

4) прочие (например, техническое устройство, требующее ремонта или обслуживания).

По времени жизни[12]:

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

2) с бесконечным временем жизни (например, заявка в отдел заказов книжного магазина на доставку литературы).

По способу обслуживания:

1) с привилегиями, или приоритетами (например, обслуживание в кассе ветеранов Великой Отечественной войны без очереди);

2) без приоритетов (например, очередь в кассу кинотеатра).

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

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

По положению:

1) внешняя (например, ожидание принтером ремонта в сервисном центре);

2) внутренняя (например, ожидание очередного этапа обработки изделия в середине технологического цикла (очередь внутри системы).

По длине:

1) с отказами (например, если на автостоянке нет свободных мест для парковки, то автомобиль уезжает, не дожидаясь освобождения места);

2) фиксированной длины (например, очередь запросов на соединение абонентов на АТС).

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

По интенсивности поступления новых запросов:

1) стационарные (регулярное поступление транзактов) (например, скорость движения конвейера задаёт интенсивность поступление товара в очередь для транспортировки на склад);

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

По направлению обслуживания транзактов:

1) правило FIFO: First Input – First Output, то есть ′первым пришел – первым вышел′ (например, очередь к парикмахерскую);

2) правило FILO: First Input – Last Output, то есть ′первым пришел – последним вышел′ (например, последовательность вынимания из постоянно пополняющегося контейнера деталей для последующей обработки: внизу находятся те детали, которые прибыли в контейнер первыми, поэтому они будут обработаны в последнюю очередь).

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

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

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

Дата добавления: 2014-12-26