Математические модели простейших систем массового обслуживания. Курсовая работа: Моделирование систем массового обслуживания

Цели

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

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

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

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

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

Система массового обслуживания;

Очередь;

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

Темп обслуживания;

Среднее время, которое заявка проводит в очереди;

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

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

Среднее число клиентов в системе обслуживания;

Издержки функционирования системы обслуживания;

Издержки ожидания.

Модели

Классификационные признаки систем массового обслуживания.

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

1) появление заявки на входе в систему;

2) прохождение очереди;

3) процесс обслуживания, после которого заявка покидает систему.

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

Характеристики входа:

1) число заявок на входе (размер популяции);

2) режим поступления заявок в систему обслуживания;

3) поведение клиентов.

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

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

Режим поступления заявок, в систему обслуживания. Заявки могут поступать в систему обслуживания в соответствии с опреде­ленным графиком (например, один пациент на прием к стомато­логу каждые 15 мин, один автомобиль на конвейере каждые 20 мин) или случайным образом. Появления клиентов считаются Случай­ными, если они независимы друг от друга и точно непредсказу­емы. Часто в задачах массового обслуживания число появлений в единицу времени может быть оценено с помощью пуассоновского распределения вероятностей. При заданном темпе поступления (например, два клиента в час или четыре грузовика в минуту) дискретное распределение Пуассона описывается следующей фор­мулой:

Где Р (х) - вероятность поступления Х заявок в единицу вре­мени;

Х - число заявок в единицу времени;

L - среднее число заявок в единицу времени (темп по­ступления заявок);

Соответствующие значения вероятностей Р(х) нетрудно опре­делить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок - два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки - около 0,27, двух - также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре - с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или бо­лее, близка нулю.

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

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

Жизнь значительно сложнее. На практике клиенты могут по­кинуть очередь потому, что она оказалась слишком длинной. Может возникнуть и другая ситуация: клиенты дожидаются сво­ей очереди, но по каким-то причинам уходят необслуженными. Эти случаи также являются предметом теории массового обслу­живания, однако здесь не рассматриваются.

Характеристики очереди:

2) правило обслуживания.

Длина очереди. Длина может быть ограничена либо не ограни­чена. Длина очереди (очередь) Ограничена, если она по каким-либо причинам (например, из-за физических ограничений) не может увеличиваться до бесконечности. Если очередь достигает своего максимального размера, то следующая заявка в систему не допускается и происходит отказ. Длина очереди Не ограничена, Если в очереди может находиться любое число заявок. Например, очередь автомобилей на бензозаправке.

Правило обслуживания. Большинство реальных систем исполь­зует правило «первым пришел - первым ушел» (FIFO - first in, first out). В некоторых случаях, например в приемном покое боль­ницы, в дополнение к этому правилу могут устанавливаться раз­личные Приоритеты. Пациент с инфарктом в критическом со­стоянии, по-видимому, будет иметь приоритет в обслуживании по сравнению с пациентом, сломавшим палец. Порядок запуска компьютерных программ - другой пример установления приорите­тов в обслуживании.

Характеристики процесса обслуживания:

1) конфигурация системы обслуживания (число каналов и чис­ло фаз обслуживания);

2) режим обслуживания.

Конфигурация системы обслуживания. Системы обслуживания различаются по Числу каналов обслуживания. Обычно количество каналов можно определить как число клиентов, обслуживание которых может быть начато одновременно, например: число мас­теров в парикмахерской. Примеры Одноканальной системы об­служивания: банк, в котором открыто единственное окошко для обслуживания клиентов, или ресторан, обслуживающий клиентов в автомобилях. Если же в банке открыто несколько окошек для обслуживания, клиент ожидает в общей очереди и подходит к пер­вому освободившемуся окну, то мы имеем дело с Многоканаль­ной однофазовой системой обслуживания. Большинство банков, также, как почтовые отделения и авиакассы, являются многока­нальными системами обслуживания.

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

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

Режим обслуживания. Как и режим поступления заявок, режим обслуживания может характеризоваться либо постоянным, либо случайным временем обслуживания. При Постоянном времени на обслуживание любого клиента затрачивается одинаковое вре­мя. Такая ситуация может наблюдаться на автоматической мойке автомобилей. Однако более часто встречаются ситуации, когда время обслуживания имеет Случайное распределение. Во многих случаях можно предположить, что время обслуживания подчиня­ется экспоненциальному распределению с функцией распреде­ления

F(T) = P(T< t) =1 – е–tm, где Р (T < t) - вероятность того, что фактическое время T обслу­живания заявки не превысит заданной величи­ны t;

M - среднее число заявок, обслуживаемых в едини­цу времени;

Е = 2,7182 - основание натурального логарифма.

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

Наиболее часто используются следующие Технические характери­стики:

1) среднее время, которое клиент проводит в очереди;

2) средняя длина очереди;

3) среднее время, которое клиент проводит в системе обслужи­вания (время ожидания плюс время обслуживания);

4) среднее число клиентов в системе обслуживания;

5) вероятность того, что система обслуживания окажется незанятой;

6) вероятность определенного числа клиентов в системе.

Среди Экономических характеристик наибольший интерес пред­ставляют следующие:

1) издержки ожидания в очереди;

2) издержки ожидания в системе;

3) издержки обслуживания.

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

Здесь мы ознакомимся с несколькими наиболее известными моделями. Все они имеют следующие общие характеристики:

А) пуассоновское распределение вероятностей поступления заявок;

Б) стандартное поведение клиентов;

В) правило обслуживания FIFO (первым пришел - первым об­служен);

Г) единственная фаза обслуживания.

I. Модель А - модель одноканальной системы массового об­служивания М/М/ 1 с Пуассоновским входным потоком заявок и Экспоненциальным временем обслуживания.

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

1. Заявки обслуживаются по принципу «первым пришел - пер­вым обслужен» (FIFO), причем каждый клиент ожидает своей очереди до конца независимо от длины очереди.

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

3. Процесс поступления заявок описывается пуассоновским распределением, причем заявки поступают из неограниченного множества.

4. Время обслуживания описывается экспоненциальным рас­пределением вероятностей.

5. Темп обслуживания выше темпа поступления заявок.

Пусть l - число заявок в единицу времени;

M - число клиентов, обслуживаемых в единицу времени;

П - число заявок в системе.

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

Формулы для описания системы М/М/ 1:

- среднее число клиентов в системе;

Среднее время обслуживания одного клиента в системе (время ожидания плюс время обслуживания);

Среднее число клиентов в очереди;

Среднее время ожидания клиента в очереди;

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

Вероятность отсутствия заявок в системе;

Вероятность того, что в системе находится бо­лее чем K заявок.

II. Модель В - многоканальная система обслуживания M/ M/ S. В многоканальной системе для обслуживания открыты два ка­нала или более. Предполагается, что клиенты ожидают в общей очереди и обращаются в первый освободившийся канал обслужи­вания.

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

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

Время нахождения заявки в очереди;

Время нахождения заявки в системе.

III. Модель С- модель с постоянным временем обслуживания M/ D/ 1.

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

Формулы, описывающие модель С:

- средняя длина очереди;

- среднее время ожидания в очереди;

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

Среднее время ожидания в системе.

IV. Модель D - модель с ограниченной популяцией.

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

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

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

Как частный случай модели с ограниченной очередью можно рассматривать Модель с отказами, если количество мест в очере­ди сократить до нуля.

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

ТЕОРИЯ МАССОВОГО ОБСЛУЖИВАНИЯ

Введение

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

Идеи и методы теории массового обслуживания (ТМО) получают всё большее распространение. Многие задачи техники, экономики, военного дела, естествознания могут быть поставлены и решены в терминах ТМО.

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

Впервые на это обратил внимание и провёл исследования датчанин А.К. Эрланг. Основные его работы в данной области относятся к 1908 - 1921 годам. С этого времени, интерес к проблемам, выдвинутым Эрлангом, необычайно возрос. В 1927 - 1928 годах появляются работы Молина и Фрайя, позже в 1930 - 1932 годах - интересные работы Поллачека, А.Н. Колмогорова, А.Я. Хинчина.

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

23. Системы массового обслуживания

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

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

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

23.1. Понятие смо

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

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

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

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

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

Входящий поток. Требования, поступающие из источника на обслуживание, образуют входящий поток. Само требование можно рассматривать как запрос на удовлетворение какой-то потребности. Примеров входящих потоков можно привести множество. Это - поток информации, поступающей на обработку в ЭВМ; поток заявок на АТС; поток клиентов, приходящих в ателье, и больных в поликлинику, поток прибывающих в порт судов; налетающие на объект удара самолеты и ракеты противника и т. д.

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

Выходящий поток. Выходящий поток - это поток требований, покидающих систему после обслуживания. Сюда могут входить и требования, которые покинули систему, не пройдя обслуживания.

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

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

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

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

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

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

Системы массового обслуживания или теория массового обслуживания - предмет, берущий начало в теории вероятностей . Но изучение таких систем в приложении к реальному миру (а их множество: магазин или вокзал с кассами, склад с операторами, парикмахерские и больницы, вычислительные сети, станки и наладчики, системы АТС и т.п.), обычно проходит в рамках предметов "Исследование операций" и "Математические методы в экономике", поэтому мы помещаем примеры решений по СМО в данный раздел.

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

Вы можете заказать решение своих задач и контрольных работ по разным темам теории систем массового обслуживания в МатБюро: (Решение задач по экономико-математическим методам на заказ). Стоимость выполнения от 200 рублей, срок от 2 дней, оформление подробное в Word с графиками и выводами.

Бесплатные примеры решений по СМО (системы массового обслуживания)

Задача 1. Интенсивность потока телефонных звонков в агентство по заказу железнодорожных билетов, имеющему один телефон, составляет 16 вызовов в час. Продолжительность оформления заказа на билет равна 2.4 минуты. Определить относительную и абсолютную пропускную способность этой СМО и вероятность отказа (занятости телефона). Сколько телефонов должно быть в агентстве, чтобы относительная пропускная способность была не менее 0,75.

Задача 2. Система массового обслуживания - билетная касса с одним окошком и неограниченной очередью. Касса продает билеты в пункты А и В. Пассажиров, желающих купить билет в пункт А, приходит в среднем трое за 20 мин, в пункт В - двое за 20 мин. Поток пассажиров простейший. Кассир в среднем обслуживает трех пассажиров за 10 мин. Время обслуживания - показательное. Вычислить финальные вероятности Р0, P2, P3, среднее число заявок в системе и в очереди, среднее время пребывания заявки в системе, среднее время пребывания заявки в очереди.

Задача 3. Междугородный переговорный пункт имеет четыре телефонных аппарата. В среднем за сутки поступает 320 заявок на переговоры. Средняя длительность переговоров составляет 5 мин. Длина очереди не должна превышать 6 абонентов. Потоки заявок и обслуживаний простейшие. Определить характеристики обслуживания переговорного пункта в стационарном режиме (вероятность простоя каналов, вероятность отказа, вероятность обслуживания, среднее число занятых каналов, среднее число заявок в очереди, среднее число заявок в системе, абсолютную пропускную способность, относительную пропускную способность, среднее время заявки в очереди, среднее время заявки в системе, среднее время заявки под обслуживанием).

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

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

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

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

	Узлы	Требования
Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

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

Рис. 1

1. Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
2. Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

1. Очередь – накопитель заявок. Очередь может отсутствовать.
2. Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
3. Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

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

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

• СМО с отказами;
• СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

• СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
• СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.

Типы ограничения очереди могут быть комбинированными.

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

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

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

По количеству каналов СМО делятся на:

• одноканальные;
• многоканальные.

Характеристики системы массового обслуживания

Основными характеристиками системы массового обслуживания любого вида являются:

• входной поток поступающих требований или заявок на обслуживание;
• дисциплина очереди;
• механизм обслуживания.

Входной поток требований

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

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

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

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

Очередь имеет имя.

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

• первым пришел – первый обслуживаешься;

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

Вы как программисты должны уметь делать списки двусторонние, односторонние.

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

• случайный отбор заявок;
• отбор заявок по критерию приоритетности.

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

Характеристики очереди

• ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
• длина очереди.

Механизм обслуживания

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

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

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

Основные критерии эффективности функционирования СМО

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

• вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
• вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

• абсолютная пропускная способность системы – А=Р обсл *λ;
• относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

.

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

Математический (абстрактный) объект, элементами которого являются (рис. 2.1):

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

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

Рис. 2.1.

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

Обслуживание - задержка заявки в обслуживающем приборе на некоторое время.

Длительность обслуживания - время задержки (обслуживания) заявки в приборе.

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

Заявка, поступившая в СМО, может находиться в двух состояниях:

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

Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок в накопителе, ожидающих обслуживания, - длина очереди.

Дисциплина буферизации (дисциплина постановки в очередь) - правило занесения поступающих заявок в накопитель (буфер).

Дисциплина обслуживания - правило выбора заявок из очереди для обслуживания в приборе.

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

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

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

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

В системах ИМ при реализации СМО принимаются следующие ограничения и допущения:

• поступившая в систему заявка мгновенно попадает на обслуживание, если в очереди нет заявок и прибор свободен;
• в приборе на обслуживании в каждый момент времени может находиться только одна заявка;
• после окончания обслуживания какой-либо заявки в приборе очередная заявка выбирается из очереди на обслуживание мгновенно, т.е., прибор не простаивает, если в очереди есть хотя бы одна заявка;
• поступление заявок в СМО и длительности их обслуживания не зависят от числа заявок, уже находящихся в системе, или от каких- либо других факторов;
• длительность обслуживания заявок не зависит от интенсивности поступления заявок в систему.

Остановимся на некоторых элементах СМО более подробно.

Входной (входящий) поток заявок. Потоком событий называется последовательность однородных событий, следующих одно за другим и происходящих в какие-то, вообще говоря, случайные моменты времени. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок в общем случае необходимо задать интервалы времени т = t k - t k-1 между соседними моментами t k _ k и t k поступления заявок с порядковыми номерами к - 1 и к соответственно (к - 1, 2, ...; t 0 - 0 - начальный момент времени).

Основной характеристикой потока заявок является его интенсивность X - среднее число заявок, поступающих на вход СМО за единицу времени. Величина т = 1/Х определяет средний интервал времени между двумя последовательными заявками.

Поток называется детерминированным, если интервалы времени т к между соседними заявками принимают определенные заранее известные значения. Если при этом интервалы одинаковы (х к = т для всех к = 1, 2, ...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока X или значение интервала т = 1/Х.

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

Случайный поток, в котором все интервалы времени х ь х 2 , ... между соседними последовательными заявками представляют собой независимые случайные величины, описываемые функциями распределений FjCij), F 2 (x 2), ... соответственно, называется потоком с ограниченным последействием.

Случайный поток называется рекуррентным, если все интервалы времени х ь т 2 , ... между заявками распределены по одному и тому же закону F(t). Рекуррентных потоков много. Каждый закон распределения порождает свой рекуррентный поток. Рекуррентные потоки иначе называют потоками Пальма.

Если интенсивность X и закон распределения F(t) интервалов между последовательными заявками не меняются со временем, то поток заявок называется стационарнъш. В противном случае поток заявок является нестационарным.

Если в каждый момент времени t k на входе СМО может появиться только одна заявка, то поток заявок называется ординарным. Если в какой-либо момент времени может появиться более одной заявки, то поток заявок - неординарный, или групповой.

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

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

Интервалы времени т между заявками в простейшем потоке распределены по экспоненциальному (показательному ) закону: с функцией распределения F(t) = 1 - е~ м; плотностью распределения/(f) = Хе~" л, где X > 0 - параметр распределения - интенсивность потока заявок.

Простейший поток часто называют пуассоновским. Название происходит от того, что для этого потока вероятность P fc (At) появления ровно к заявок за некоторый интервал времени At определяется законом Пуассона:

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

• стационарным, если интенсивность X не меняется со временем;
• нестационарным, если интенсивность потока зависит от времени: X = >.(t).

В то же время простейший поток, по определению, всегда является стационарным.

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

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

Сумма N независимых стационарных ординарных потоков с интенсивностями Х ь Х 2 ,..., X N образует простейший поток с интенсивностью

X=Y,^i при условии, что складываемые потоки оказывают более или

менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при N > 5. Значит, при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении N.

• 2. Вероятностное разрежение потока. Вероятностное (но не детерминированное ) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью X* = рХ, где X - интенсивность исходного потока. Поток исключенных заявок с интенсивностью X** = (1 - р)Х - тоже простейший поток.
• 3. Эффективность. Если обслуживающие каналы (приборы) рассчитаны на простейший поток заявок с интенсивностью X, то обслуживание других типов потоков (с той же интенсивностью) будет обеспечено с не меньшей эффективностью.
• 4. Простота. Предположение о простейшем потоке заявок позволяет для многих математических моделей получить в явном виде зависимости показателей СМО от параметров. Наибольшее число аналитических результатов получено для простейшего потока заявок.

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

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

Важной характеристикой входного потока является коэффициент вариации

где т инт - математическое ожидание длины интервала; о - среднее квадратическое отклонение длины интервала х инт (случайной величины) .

Для простейшего потока (а =-, т = -) имеем v = 1. Для большинства

реальных потоков 0

Каналы (приборы) обслуживания. Основная характеристика канала - длительность обслуживания.

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

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

где ц - интенсивность обслуживания, здесь р = _--; т 0 бсл - матема-

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

Кроме экспоненциального распределения встречаются /с-распре- деление Эрланга, гиперэкспоненциальное, треугольное и некоторые другие. Это нас не должно смущать, так как показано, что значение критериев эффективности СМО мало зависит от вида закона распределения времени обслуживания.

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

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

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

Способы управления потоками заявок определяются дисциплинами:

• буферизации;
• обслуживания.

Дисциплины буферизации и обслуживания могут быть классифицированы по следующим признакам:

• наличие приоритетов между заявками разных классов;
• способ вытеснения заявок из очереди (для дисциплин буферизации) и назначения заявок на обслуживание (для дисциплин обслуживания);
• правило вытеснения или выбора заявок на обслуживание;
• возможность изменения приоритетов.

Вариант классификации дисциплин буферизации (постановки в очередь) в соответствии с перечисленными признаками представлен на рис. 2.2.

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

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

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

Рис. 2.2.

Дисциплины буферизации могут использовать следующие правила вытеснения заявок из накопителя:

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

На рис. 2.3 представлена классификация дисциплин обслуживания заявок в соответствии с теми же признаками, что и для дисциплин буферизации.

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

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

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

• одиночного режима;
• группового режима;
• комбинированного режима.

Рис. 2.3.

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

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

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

Дисциплины обслуживания могут использовать следующие правила выбора заявок на обслуживание.

Бесприоритетные (заявки не имеют привилегий на досрочное обслуживание - захват ресурсов):

• обслуживание в порядке поступления FIFO (first in -first out, первый вошел - первый вышел);
• обслуживание в обратном порядке - заявка выбирается из очереди в режиме LIFO (last in - first out, последний вошел - первый вышел);
• обслуживание в случайном порядке - заявка выбирается из очереди в режиме RAND (random - случайным образом);
• обслуживание в циклическом порядке - заявки выбираются в процессе циклического опроса накопителей в последовательности 1, 2,Н СН - количество накопителей), после чего указанная последовательность повторяется;

Приоритетные (заявки имеют привилегии на досрочное обслуживание - захват ресурсов):

• с относительными приоритетами - если в процессе текущего обслуживания заявки в систему поступают заявки с более высокими приоритетами, то обслуживание текущей даже бесприоритетной заявки не прерывается, а поступившие заявки направляются в очередь; относительные приоритеты играют роль только в момент окончания текущего обслуживания заявки при выборе из очереди новой заявки на обслуживание.
• с абсолютными приоритетами - при поступлении заявки с высоким приоритетом обслуживание заявки с низким приоритетом прерывается и на обслуживание направляется поступившая заявка; прерванная заявка может быть возвращена в очередь или удалена из системы; если заявка возвращена в очередь, то ее дальнейшее обслуживание может быть выполнено с прерванного места или заново;
• со смешанными приоритетами - строгие ограничения на время ожидания в очереди на обслуживание отдельных заявок требуют присвоения им абсолютных приоритетов; вследствие этого время ожидания заявок с низкими приоритетами может оказаться недопустимо большим, хотя отдельные заявки имеют запас по времени ожидания; для выполнения ограничений по всем видам заявок можно наряду с абсолютными приоритетами некоторым заявкам присвоить относительные приоритеты, а остальные обслуживать в бесприоритетном режиме;
• с чередующимися приоритетами - аналогом относительных приоритетов, приоритет учитывается только в моменты завершения текущего обслуживания группы заявок одной очереди и назначения новой группы на обслуживание;
• обслуживание по расписанию - заявки разных классов (находящиеся в разных накопителях) выбираются на обслуживание согласно некоторому расписанию, задающему последовательность опроса очередей заявок, например в случае трех классов заявок (накопителей) расписание может иметь вид {2, 1, 3, 3, 1, 2} или {1, 2, 3, 3, 2, 1}.

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

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

• длительностью обслуживания;
• приоритетами.

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

Для математического описания дисциплин обслуживания со смешанными приоритетами используется матрица приоритетов, представляющая собой квадратную матрицу Q = (q, ;), i,j - 1,..., Я, Я - число классов заявок, поступающих в систему.

Элемент q (j матрицы задает приоритет заявок класса i по отношению к заявкам класса; и может принимать следующие значения:

• 0 - нет приоритета;
• 1 - приоритет относительный;
• 2 - приоритет абсолютный.

Элементы матрицы приоритетов должны удовлетворять следующим требованиям:

• q n = 0, так как между заявками одного и того же класса не могут быть установлены приоритеты;
• если q (j = 1 или 2, то q ^ = 0, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i (i,j = 1, ..., Я).

В зависимости от возможности изменения приоритетов в процессе функционирования системы приоритетные дисциплины буферизации и обслуживания делятся на два класса:

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

В компьютерных системах ИМ обязательно имеется единственный элемент (объект), через который, и только через него, вводятся заявки в модель. По умолчанию все вводимые заявки бесприоритетные. Но есть возможности присвоения приоритетов в последовательности 1, 2, ..., в том числе и в ходе выполнения модели, т.е. в динамике.

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

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

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

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

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

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

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

Рис. 2.4.

СеМО называют также многофазными СМО.

Пример построения ИМ СеМО мы рассмотрим позже.

Основными элементами СеМО являются узлы (У) и источники (генераторы) заявок (Г).

Узел сети - это система массового обслуживания.

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

Для упрощенного изображения СеМО используется граф.

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

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

Для лучшего восприятия этого творческого потенциала в первом приближении остановимся на классификации моделей СМО.