Тест теория очередей и ее элементы. Теория очередей. Средняя длительность ожидания

4. Классические теории, теории человеческих отношений, гуманистические теории Исследователи проблемы выделяют следующие этапы развития науки управления персоналом:1) классические теории (Ф. Тейлор, А. Файоль, Г. Эмерсон, Л. Урвик, М. Вебер, Г. Форд, А. Гастев, П. Керженцев) –

3. Теория очередей

Дать определение характеристикам прибытия линейных систем ожидания

Основные знания о линиях обслуживания называются теорией очередей.

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

Рис. 1. Соотношение между затратами ожидания и сервисными затратами

Обзор трех частей линейных систем ожидания, или очередей:

1) прибытия, или входы системы;

2) дисциплина очереди, или собственно система ожидания;

3) сервисное оборудование.

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

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

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

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

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

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

для х=0, 1, 2, 3, 4...

где Р (х) - вероятность х прибытии;

х - число прибытии в единицу времени;

а - среднее количество прибытии;

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

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

Дать определение характеристике очереди линейных систем ожидания

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

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

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

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

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

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

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

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

Этот метод, предложенный Данцигом, Кестеном и Ранненбергом (метод коллективных меток - method of collective marks) и развитый затем Г.П. Климовым (метод «катастроф»), позволяет легко получить аналитические результаты в ситуациях, когда другие известные методы приводят к трудоемким выкладкам. Особенно эффективен он оказался при анализе ненадежных и приоритетных систем массового обслуживания.

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

Проиллюстрируем этот метод, применив его для нахождения вероятностных характеристик системы M\G\1. Важной характеристикой производительности многих реальных систем является распределение периода занятости системы. Период занятости есть интервал времени с момента поступления запроса в пустую систему до момента, когда система впервые вновь окажется пустой. Знание периода занятости позволяет решать задачи, связанные, например, с планированием проведения в системе профилактических работ, исследованием возможности дополнительной загрузки прибора выполнением некоторой второстепенной «фоновой» работы и т.д.

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

Считаем, что выполняется условие:

гарантирующее существование стационарного распределения длины периода занятости рассматриваемой СМО.

Утверждение 13.

Преобразование Лапласа - Стилтьеса распределения длины периода занятости рассматриваемой СМО удовлетворяет следующему функциональному уравнению:

Доказательство. Легко видеть, что распределение длины периода занятости системы не зависит от того, в каком порядке обслуживаются запросы. Для облегчения анализа структуры периода занятости предположим, что запросы обслуживаются в инверсионном порядке, то есть на обслуживание всегда выбирается запрос, пришедший в систему последним. Такая дисциплина выбора из очереди кодируется как LIFO (Last In - First Out) или LCFS (Last Came - First Served). При такой дисциплине выбора из очереди каждый запрос как бы порождает период занятости системы запросами, пришедшими в систему после него. Причем структура и, следовательно, распределение длины периода занятости, порожденного некоторым запросом, такие же, как структура и распределение длины периода занятости системы. Используя эти рассуждения, мы приходим к пониманию того, что период занятости системы состоит из времени обслуживания первого запроса, с которого начался период занятости, и случайного числа периодов занятости, порожденных запросами, пришедшими в систему за время обслуживания первого запроса.

Теперь предположим, что независимо от функционирования данной системы поступает простейший поток катастроф интенсивности s. Введем в рассмотрение (дополнительное) событие А, состоящее в том, что за данный период занятости не поступили катастрофы.

Напомним, что согласно вероятностной трактовке преобразования Лапласа - Стилтьеса, величина есть вероятность того, что не произойдет ни одной катастрофы за случайное время, имеющее функцию распределения H(t). Поэтому легко понять, что вероятность события А определяется следующим образом:

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

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

Таким образом, используя еще раз вероятностную трактовку преобразования Лапласа - Стилтьеса мы получаем следующую формулу для вероятности события :

Сравнивая выражения (1.83) и (1.84), мы убеждаемся в справедливости формулы (1.82). Утверждение 13 доказано.

Уравнение (1.82), полученное Дж. Кендаллом в 1951 году, имеет единственное решение в области Res > 0, такое, что

В случае, если распределение времени обслуживания показательное, рассматриваемая система есть М|М|1 и преобразование Лапласа - Стилтьеса распределения времени обслуживания имеет вид: При этом функциональное уравнение (1.82) переходит в квадратное уравнение для неизвестного преобразования Лапласа - Стилтьеса

Решая уравнение (1.85), получаем:

В этой формуле выбираем только знак чтобы полученное решение удовлетворяло условию Обращая теперь преобразование Лапласа - Стилтьеса получаем следующее выражение для производной функции распределения длины периода занятости системы М|М|1:

где функция есть модифицированная функция Бесселя первого рода.

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

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

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

Рассмотрим теперь другую характеристику функционирования системы M\G\1 - число запросов, обслуженных за период занятости. Обозначим

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

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

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

Так как поток запросов - простейший с параметром , а произвольный запрос является темно-красным с вероятностью , то поток нетемно-красных вызовов (как это следует из Утверждения 6) является простейшим с параметром Вспоминая вероятностную интерпретацию преобразования Лапласа - Стилтьеса, из приведенных рассуждений выводим следующую альтернативную формулу для вероятности события

Сравнивая формулы (1.90) и (1.91), убеждаемся в справедливости (1.89). Утверждение 14 доказано.

Уравнение (1.89) определяет единственную аналитическую в области функцию, такую, что

Следствие. Среднее число запросов, обслуженных в системе M\G\1 за один период занятости, задается формулой:

Приведем еще одно доказательство формулы Поллячека-Хинчина для производящей функции распределения вероятностей числа запросов в системе M\G\1 в моменты окончания обслуживания. Каждый из запросов, приходящих в систему, независимо от других назовем красным с вероятностью 2 и синим с дополнительной вероятностью. Введем событие А, состоящее в том что запрос, уходящий в данный момент окончания обслуживания из системы, сам красный и все запросы, остающиеся в системе в этот момент, тоже красные.

Из вероятностной интерпретации производящей функции очевидно следует, что:

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

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

Из этих рассуждений следует, что:

Из соотношений этого соотношения и (1.92) очевидным образом следует формула Поллячека - Хинчина:

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

В заключение подраздела найдем характеристики системы M\G\1 с дисциплиной LIFO.

Выше отмечалось, что распределение периода занятости системы M|G|1 не зависит от дисциплины обслуживания. Поэтому уравнение (1.82) определяет преобразование Лапласа - Стилтьеса распределения периода занятости для всех дисциплин. Кроме того, несложно видеть, что и распределения числа запросов в системе M\G\1 при дисциплинах FIFO и LIFO совпадают и задаются формулой (1.81).

Распределение времени ожидания запроса при дисциплинах FIFO и LIFO различно. При дисциплине FIFO преобразование Лапласа - Стилтьеса стационарного распределения времени ожидания задается формулой (1.52).

Утверждение 15. При дисциплине LIFO преобразование Лапласа - Стилтьеса имеет следующий вид:

где функция является решением уравнения (1.82).

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

Учитывая сущность дисциплины LIFO и рассуждения, использованные при доказательстве Утверждения 13, получаем формулу:

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

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

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

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

Число инспекторов 1 2 3 4 5 6 7

Среднее время ожидания 80.2 50.3 34.9 24.8 14.912.9 9.4

______(минуты) _______________________________________

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

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

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

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

Класс моделей, пригодных для решения подобных задач, называют еще теорией очередей.

Эта теория представляет особый раздел теории случайных процессов и использует, в основном, аппарат теории вероятностей. Первые публикации в этой области относятся к 20-м гг. XX в. и принадлежат датчанину А. Эрлангу, занимавшемуся исследованиями функционирования телефонных станций – типичных СМО, где случайны моменты вызова, факт занятости абонента или всех каналов, продолжительность разговора. В дальнейшем теория очередей нашла развитие в работах К.Пальма, Ф.Поллачека, А.Я.Хинчина, Б.В.Гнеденко, А.Кофмана, Р.Крюона, Т. Cаати и других отечественных и зарубежных математиков.

При решении задач, связанных с очередями, возможны две ситуации:

а) число заказов слишком велико; имеет место большое время ожидания (недостаточный объем обслуживающего оборудования );

б) поступает недостаточное число заказов; имеет место простой оборудования (избыток оборудования ).

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

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

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

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

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