Элементы теории массового обслуживания и принятия решений

,      (2)

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

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

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

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

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

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

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

    (2)

 

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

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

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

   (3)

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

    (4)

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

Найдём сначала вероятность того, что и момент t+h все приборы свободны. Это может произойти следующими способами:

• в момент t все приборы были свободны и за время h новых требований не поступало;
• в момент t один прибор был занят обслуживанием требования, все остальные приборы свободны; за время h обслуживание требования было завершено и новых требований не поступило /6, 264 с./.

Остальные возможности, как-то: были заняты два или три прибора и за время h работа на них была закончена – имеют вероятность о(h), как легко в этом убедится.

Вероятность первого из указанных событий равна

,    (5)

вероятность второго события

,   (6)

Таким образом

,   (7)

Отсюда очевидным образом приходим к уравнению.

Перейдём теперь к составлению уравнений для при 1. Рассмотрим отдельно два различных случая: 1 и . Пусть в начале 1 . Перечислим только существенные состояния, из которых можно прийти в состояние в момент t+h. Эти состояния таковы:

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

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

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

Все остальные мыслимые возможности перехода в состояние за промежуток времени h имеют вероятность, равную о(h).

Собрав воедино найденные вероятности, получаем следующее равенство:

Несложные преобразования приводят от этого равенства к такому уравнению для 1 ;

   (8)

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

 (9)

Для определения вероятностей получили бесконечную систему дифференциальных уравнений (4) – (10). Её решение представляет несомненные технические трудности.

 

 

2. Определение основных параметров

 

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

Сказанное позволяет заключить, что уравнения (5), (6), (7) для стационарных вероятностей принимают следующий вид:

     (10)

при 1

   (11)

при

   (12)

К этим уравнениям добавляется нормирующее условие

Для решения полученной бесконечной алгебраической системы введём обозначения: при 1

    (13)

при

    (14)

Система уравнений (10) – (12) в этих обозначениях принимает такой вид:

  при     (15)

Отсюда заключаем, что при всех т.е. при 1

,      (16)

и при

,      (17)

Введём для удобства записи обозначение:

.,     (18)

 Уравнение (17) позволяет заключить, что при 1

      (19)

При из (18) находим, что

     (20)

 

и, следовательно, при

     (21)

 

Остаётся найти . Для этого в (9) подставляем выражения из (19) и (21). В результате

,    (22)

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

 ,   (23)

Если условие не выполнено, т.е. если , то ряд, стоящий в квадратной скобке уравнения для определения , расходится и, значит, должно быть равно 0. Но при этом, как следует из (2) и (24), при всех оказывается /7, 45 с./.

Методы теории цепей Маркова позволяют заключить, что при с течением времени очередь стремится к ∞ по вероятности.

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

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

,    (24)

Прежде чем преобразовать эту формулу к виду, удобному для использования, приготовим некоторые необходимые для дальнейшего сведения. Прежде всего для случаев m=1 и m=2 найдем простые формулы для . Несложные преобразования приводят к таким равенствам: при m=1

=1- ,       (25)

а при m=2

,      (26)

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

 , (27)

Эта формула для m=1 принимает особенно простой вид:

      (28)

при m=2

 ,    (29)

В формуле (25) может принимать любое значение от 0 до m (исключительно). Так что в формуле (23) < 1, а в (21) <2.

Если в момент поступления требования в очереди уже находились k-m требований, то, поскольку обслуживание происходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены k-m+1 требований. Пусть означает вероятность того, что за промежуток времени длительности t после поступления интересующего требования закончилось обслуживание ровно s требований. Ясно, что при имеет место равенство

,    (30)

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

,      (31)

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

,    (32)

Итак,

,     (33)

и, следовательно,

,  (34)

 

Но вероятности известны:

,     (34)

поэтому

,  (35)

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

=

.(36)

 

Из формул (25) и (26) следует, что поэтому при m>0

    (37)

 

Само собой разумеется, что при t<0 /8, 156 с./.

Функция имеет в точке t=1 разрыв непрерывности, равный вероятности застать все приборы занятыми.

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

,   (38)

Несложные вычисления приводят к формуле

,      (39)

Дисперсия величины равна

,    (40)

Формула (40) даёт среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшими в систему обслуживания в течение промежутка времени T. За время T в систему поступает требований и среднем; общая потеря ими времени па ожидание в среднем равна

     (41)

Приведем небольшие арифметические подсчеты, которые продемонстрируют нам, как быстро возрастают суммарные потери времени па ожидание с изменением величины . При этом мы ограничиваемся случаем Т=1 и рассматриваем лишь самые малые значения т: т=1 и т=2.

При т=1 в силу (28)

,     (42)

При р=0,1; 0,4; 0,6; 0,9 значение а приблизительно равно 0,011; 0,267; 0,9; 8,100.

При m=2 в силу (41)

,     (43)

При =0,1; 0,9; 1,3; 1,8 значение а приблизительно равно 0,00025; 0,229; 0,951; 7,674.

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

 

 

 

 

 

 

 

 

 

 

 

 

3 Решение задачи «Бери и кати»

 

Условие:

В полуавтоматическом бистро для автомобилистов «Бери и кати» робот-кёльнер выдает подогретый бутерброд и чашку горячего кофе  за 5 минут. Оценки показывают, что поток клиентов – 20 машин/ в час. Компания хочет оценить длину очередей автомобилей к автомату, для обеспечения необходимого пространства для них.

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

a. Долю времени, когда  робот загружен;

b. Долю времени, когда  он бездействует;

c. Среднее число машин  у робота-кёльнера;

d. Среднее число машин  в очереди у робота-кёльнера;

e. Среднее время, затрачиваемое  клиентом для получения бутерброда  и чашки чая;

f. Среднее время, которое  клиент проводит в очереди;