Главная » Статьи » Студентам » Имитационное моделирование

5.2 Элементы и классификация систем массового обслуживания

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

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

Определение 6. Система, в которой, с одной стороны, возникает массовые требования на выполнения каких-либо видов услуг, а с другой стороны, происходит удовлетворение этих требований (обслуживание), называется системой массового обслуживания (СМО).

Примерами процессов массового обслуживания являются:

-   обслуживание покупателей в сфере мелкооптовой и розничной торговли;

-     транспортное обслуживание;

-     работа телекоммуникационных сетей;

-     медицинское обслуживание;

-     гостиничный бизнес;

-     обслуживание в бистро, кафе, ресторанах;

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

-     туристический бизнес и многие др.

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

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

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

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

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

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

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

Однако круг проблем, которые могут решаться с помощью данной теории, ограничен.

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

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

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

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

Определение 7. Требованием называется каждый отдельный запрос на выполнение какой-либо услуги (или операции, функции). Однако в литературе термин «требование» не является уникальным, и он равнозначен терминам «заявка» или «клиент», однако последний почти не используется в теории, чаще – в рассмотрении примеров реальных систем с осуществлением операций непосредственно над клиентами.

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

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

Определение 9. Обслуживание – это осуществление определенной операции или комплекса операций (функций) для удовлетворения поступившего в систему запроса.

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

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

Определение 10. Выходным потоком является поток обслуженных и необслуженных требований, покидающих систему.

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

На рис. 5.5 дана общая схема СМО, состоящей из входного потока требований, операционной системы и выходного потока требования.

 

Рис. 5.5. Общая схема СМО

 

Исходя из характера входного потока, выделяются следующие два типа СМО: система с отказами и система с ожиданием.

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

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

На рис. 5.6 представлено схематическое изображение СМО с ожиданием, состоящей из трех блоков: источника поступления требований, очереди и канала обслуживания, который содержит один и более (не исключая возможность наличия бесконечного числа) идентичных параллельно расположенных серверов.


 

Рис. 5.6. Схематическое изображение СМО с ожиданием

 

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

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

Сеть массового обслуживания представляет собой множество взаимосвязанных систем массового обслуживания (рис. 5.7).

 

Рис. 5.7. Пример сети массового обслуживания

 

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

Потоковые процессы обладают определенным набором свойств, имеющих специальные обозначения, предложенные Кендаллом. Свойства записываются в виде кода, имеющего форму A|B|m|R, где А и В – это буквенные символы, а m – целочисленная константа. С помощью А и В указывается вид закона распределения вероятностей случайных величин – интервала между поступлением двух последовательных заявок и времени обслуживания, соответственно. Константа m показывает, сколько в СМО насчитывается параллельно расположенных идентичных серверов (), или, проще говоря, – число каналов. R – предельное число заявок в очереди или в системе. Если R-->infinity, то четвертую позицию принято опускать. Возможно наличие пятого символа обозначающего порядок отбора (приоритета) требований.

Ниже приведены стандартные обозначения, используемые на позициях АВ: и

M – пуассоновский закон распределения (то есть отрицательная экспоненциальная функция распределения указанных выше случайных величин). Такое обозначение произошло путем выделения первой буквы из термина "memoryless", характеризующего процессы без памяти;

D – интервалы времени между последовательным событиями детерминированы («deterministic»). Распределение регулярного потока, когда плотность вероятностей интервалов вырождается в дельта-функцию:

,;

Errазное распределение Эрланга:

;

Kr – гамма-распределение;

Hk – гиперэкспоненциальное распределение с k составляющими:

;

G – закон распределения неизвестен или может быть любым ("general").

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

В качестве вывода приведем пример записи одного из видов СМО: M|G|1|infinity. Такая запись означает, что рассматривается одноканальная СМО с простейшим входным потоком, произвольным распределением времени обслуживания и неограниченной очередью.

Определение 13. Длина очереди – количество требований, ожидающих сигнал на обслуживание, или число мест.

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

Когда заявки порождаются ограниченным числом источников, при этом каждый источник порождает только одну заявку, и не генерирует новые заявки при условии нахождения заявки в СМО, используется обозначение  A|B|m|R|N. N – количество источников, A – закон, порождающий заявки входного потока СМО, B – распределение времени обслуживания, m – число серверов (приборов) обслуживания, R – допустимая длина очереди.

Определение 14. Поток называется рекуррентным, если он может быть задан функциями распределения , и Fi(t)=F(t) "i³1, где , (t0=0) – интервал между двумя последовательными заявками, при этом ti>=ti–1, i>=1.

Замечание 1. Вообще говоря, поток считается заданным, если для каждого индекса n задано совместное распределение интервалов .

Если длины этих интервалов статистически независимы, то в потоке с ограниченным последействием, где существует зависимость появления события ti (поступления очередной заявки) от предыстории процесса, необходимо фиксировать ti–1.

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

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

-       FIFO или FCFS – «the first-in, first-out» и «first come, first served» соответственно – соответствует ситуации, когда заявки обслуживаются по мере их поступления, и большая приоритетность отводится ранее поступившей заявке;

-       LIFO («last in, first out») или LCFS («last come, first served») – указывает на ситуацию, в которой последняя заявка в очереди автоматически переходит в категорию самой приоритетной заявки, и первой поступает на сервер;

-       аббревиатура SIRO («service in random order») соответствует ситуации, когда происходит случайный отбор заявок для обслуживания сервером.

-       RR (Round Robin) – если обслуживание заявки незавершенно к концу заданного временного периода, заявка отзывается и возвращается обратно в очередь. В дальнейшем она поступает в сервер по принципу FIFO. Процедура повторяется до тех, пока заявка не будет окончательно выполнена;

-       PS (Processor Sharing) – все требования обслуживаются одновременно,  и, как следствие, период обслуживания увеличивается;

-       IS (Infinite Server) – существует достаточное количество серверов, которое исключает возможность образования очереди.

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

-       с ограниченным временем пребывания заявки в очереди;

-       с приоритетами – некоторые из находящихся в очереди заявок имеют право первоочередного обслуживания.

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

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

Определение 15. Чтобы акцентировать внимание на том, что система состоит из элементов, которые географически отдалены друг от друга на большом расстоянии, используется понятие пространственно распределенные СМО.

Такие СМО особый интерес представляют в исследовании и моделировании инфраструктуры населенных пунктов.

Категория: Имитационное моделирование | Добавил: kvn2us (27.01.2009) | Автор: Кравченко Владимир Николаевич
Просмотров: 9901
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]