Теория массового обслуживания

Введение

 

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

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

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

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

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

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

 

 

 

 

1. Теория массового обслуживания. Основные положения

 

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

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

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

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

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

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

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

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

Простейший поток обладает такими важными свойствами:

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

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

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

При простейшем потоке требований распределение  требований, поступающих в систему  подчиняются закону распределения  Пуассона:

вероятность того, что в обслуживающую  систему за время t поступит именно k требований:

где, – среднее число требований, поступивших на обслуживание в единицу времени.

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

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

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

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

 

 

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

1. Классификация СМО и их основные элементы

массовый обслуживание уравнение  ожидание

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

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

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

1) с неограниченным временем  ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

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

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

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

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

 

 

 

 

 

2. Обслуживание с ожиданием

 

1. Постановка задачи

 

СМО с ожиданием распространены наиболее широко. Их можно разбить на 2 большие группы:

• разомкнутые
• замкнутые.

Эти системы определяют так же, как системы с ограниченным входящим потоком.

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

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

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

Мы рассмотрим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена К. Эрлангом. на n одинаковых приборов поступает простейший поток требований интенсивности . Если в момент поступления имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь прибывшее требование становится в очередь за всеми теми требованиями, которые поступили раньше и ещё не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживанию очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент времени не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей Предполагается, что при .

 

где – постоянная.

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

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

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

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

 

      Требуемое доказано.

Несомненно, что в реальной обстановке показательное время обслуживания является, как правило, лишь грубым приближением к действительности. Так, нередко время обслуживания не может быть меньше, чем некоторая определенная величина. Предположение же (1) приводит к тому, что значительная доля требований нуждается лишь в кратковременной операции, близкой к 0. Позднее перед нами возникает задача освобождения от излишнего ограничения, накладываемого предположением (1). Необходимость этого была ясна уже самому Эрлангу, и он в ряде работ делал усилия найти иные удачные распределения для длительности обслуживания. В частности, им было предложено так называемое распределение Эрланга, плотность распределения которого дается формулой

 

         где >0, a k – целое положительное число.

Распределение Эрланга представляет собой распределение суммы k – независимых слагаемых, каждое из которых имеет распределение (1).

Обозначим для случая распределения (1) через время обслуживания требования. Тогда средняя длительность обслуживания равна

 

 

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

 

 

2. Процесс обслуживания как марковский случайный процесс