Оптимизация систем массового обслуживания

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

Введение

Обзор литературы

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

Построение математической модели

Постановка задачи оптимизации среднего времени ожидания

Исследование зависимости критерия эффективности от распределения заявок по обслуживающим приборам

Анализ полученных результатов

Решение задачи оптимизации. Разработка программного кода для оптимизации системы

Численные примеры

Заключение

Список литературы

Введение

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

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

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

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

Обзор литературы

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

Один из подходов, используемый на пути решения проблемы оптимизации СМО с точки зрения уменьшения среднего времени ожидания в очереди, предполагает использование резервных приборов [1], [3]. Одна из таких работ принадлежит Самочерновой Л.И. и Петрову Е.С [3]. В своей работе Самочернова и Петров отмечают, что, изучение проблемы анализа управляемых систем массового обслуживания(УСМО) представляет большой интерес, так как моделями УСМО можно описать функционирование разных технические систем в реальной жизни. Если работы их предшественников были направлены на исследование оптимального времени включения/выключения резервного прибора в зависимости от числа заявок в системе или же длины очереди, то в данной работе представлена стратегия управления резервным прибором, которая основывается на времени ожидания заявки, находящейся первой в очереди, в текущий момент времени.

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

Как уже было сказано выше, теория массового обслуживания может быть применена во многих областях нашей жизни. Это могут быть такие места, как билетные кассы, автозаправочные станции, банки, поликлиники, супермаркеты и многие другие [4]. В частности, Монтеро и Сукар в своей работе [5] акцентируют внимание на том, что при условии аналогичных цен и качестве товаров, преимущество будет у того предприятия, в котором выше качество обслуживания. В супермаркете большее количество кассиров означает большие инвестиции, однако недостаточное количество кассиров может привести к высокому времени ожидания, и как следствие потери клиентов. Для эффективной работы бизнеса очень важно, чтобы принимались оптимальные решения по распределению ресурсов, но менеджеры не всегда способны справиться с данной задачей. В связи с этим, для организации лучшего управления, предлагается внедрить автоматические системы, которые сами анализируют очереди в супермаркете, и для каждого конкретного интервала времени определяют необходимое количество кассиров.

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

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

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

Схема СМО

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

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

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

Схема соответствующей СМО

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

Построение математической модели

Рассмотрим оба способа функционирования СМО более детально:

| | n |

 - входящий поток требований

- определяется интенсивностью обслуживания на одном приборе (процесс обслуживания)

n - количество обслуживающих приборов

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

- интенсивность входящего потока заявок первого типа

- интенсивность входящего потока заявок второго типа

- интенсивность обслуживания заявок первого типа

- интенсивность обслуживания заявок второго типа

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

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

Интенсивность суммарного входящего потока

=

- вероятность того, что заявка первого типа поступит на обслуживание

- вероятность того, что заявка второго типа поступит на обслуживание

Тогда среднее время обслуживания одной заявки:

T = +

=

| | n1 | и | | n - n1 |

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

Постановка задачи оптимизации среднего времени ожидания

1) Необходимо выяснить, какой из способов организации СМО эффективнее с точки зрения оптимизации среднего времени ожидания.

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

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

2) Найти условие, при котором разделение системы будет выгодно.

Исследование зависимости критерия эффективности от распределения заявок по обслуживающим приборам

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

т(t) - число заявок в СМО в момент времени t

- предельное распределение

=

EX = = =

= =

= =

= = {j-n = k} = =

= =

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

б = - среднее число занятых каналов

=



= при 1 ? j ? n

=

=

=

= = =

=

= = =

Таким образом получаем:

EX =

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

б1 = б2 =

EX1 =

EX2 =

где

Не забудем поставить ограничение:

< 1

< 1

< 1

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

Анализ полученных результатов

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

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

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

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

- по специальной базе оператор проверяет `надежность' клиента (оформлялись ли кредиты ранее, возникали ли какие-то проблемы с выплатами и т.д.)

- если было решено, что клиент `надежный', оформляется договор в нескольких экземплярах

- данные по клиенту вносятся в базу

- клиенту выдают необходимую сумму денег

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

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

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

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

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

Рассмотри график зависимости EXnew от для следующего входящего потока:

= 2

= 3

= 3

= 2

n1 = 1

n = 4

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

Решение задачи оптимизации. Разработка программного кода для оптимизации системы

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

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

*Данные о входящем потоке вводятся вручную

# M|M|n|?

l1 = 2 #интенсивность 1-го входящего потока

l2 = 3 #интенсивность 2-го входящего потока

mu1 = 3 #интенсивность обслуживания заявок первого типа

mu2 = 2 #интенсивность обслуживания заявок второго типа

n=4 #число обслуживающих приборов в случае, когда у нас общая очередь для всех типов заявок

n1=1 #число обслуживающих приборов для заявок 1-го типа

n2=n-n1 #число обслуживающих приборов для заявок 2-го типа

l = l1 + l2

T = l1 / ((l1+l2) * mu1) + l2 / ((l1+l2) * mu2)

mu = 1 / T

alpha1 = l1 / mu1

alpha2 = l2 / mu2

alpha = l / mu

print 'Input data:'

print 'l1: '

l1

print 'l2: '

l2

print 'mu1: '

mu1

print 'mu2: '

mu2

print 'n: '

n

print 'n1: '

n1

#проверка на допустимость значений

if (l1 / (n1*mu1)) >= 1:

print "Error(1), these values are not available"

if (l2 / (n2*mu2)) >= 1:

print "Error(2), these values are not available"

if (l / (n*mu)) >= 1:

print "Error, these values are not available"

#Функция для вычисления факториала

def fac(n):

if n == 0:

return 1

return fac(n-1) * n

sumpk1 = (n1 ** n1) / fac(n1) * ((alpha1 / n1) ** (n1 + 1)) / (1 - (alpha1 / n1))

b1 = 0

for j in range(0, n1+1):

b1 += (alpha1 ** j) / fac(j)

p10 = 1 / (b1 + sumpk1)

EX1 = (1 / (n1 * mu1)) * ((p10 / fac(n1-1)) * (alpha1 ** (n1+1)) * (1 / ((n1 - alpha1) ** 2)) + sumpk1)

sumpk2 = (n2 ** n2) / fac(n2) * ((alpha2 / n2) ** (n2 + 1)) / (1 - (alpha2 / n2))

b2 = 0

for j in range(0, n2+1):

b2 += (alpha2 ** j) / fac(j)

p20 = 1 / (b2 + sumpk2)

EX2 = (1 / (n2 * mu2)) * ((p20 / fac(n2-1)) * (alpha2 ** (n2+1)) * (1 / ((n2 - alpha2) ** 2)) + sumpk2)

sumpk = (n ** n) / fac(n) * ((alpha / n) ** (n + 1)) / (1 - (alpha / n))

b = 0

for j in range(0, n+1):

b += (alpha ** j) / fac(j)

p0 = 1 / (b + sumpk)

EX = (1 / (n * mu)) * ((p0 / fac(n-1)) * (alpha ** (n+1)) * (1 / ((n - alpha) ** 2)) + sumpk)

EXnew = EX1 * (l1 / (l1 +l2)) + EX2 * (l2 / (l1 +l2))

print 'EX1:'

EX1

print 'EX2:'

EX2

print 'EX:'

EX

print 'EXnew:'

EXnew

#Каким должно стать mu1, чтобы разбиение стало актуальным?

mu1new = mu1

EXnew1 = EXnew

while EXnew1 > EX:

mu1new += 0.05

alpha1 = l1 / mu1new

sumpk1 = (n1 ** n1) / fac(n1) * ((alpha1 / n1) ** (n1 + 1)) / (1 - (alpha1 / n1))

b1 = 0

for j in range(0, n1+1):

b1 += (alpha1 ** j) / fac(j)

p10 = 1 / (b1 + sumpk1)

EX1 = (1 / (n1 * mu1new)) * ((p10 / fac(n1-1)) * (alpha1 ** (n1+1)) * (1 / ((n1 - alpha1) ** 2)) + sumpk1)

EXnew1 = EX1 * (l1 / (l1 +l2)) + EX2 * (l2 / (l1 +l2))

print 'Initial mu1: '

mu1

print 'Optimized mu1:'

mu1new

print 'Optimized EX'

EXnew1

Численные примеры

Пример1:

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

Полученные результаты:

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

Пример 2:

Полученные результаты:

Вывод: При данном входящем потоке, среднее время ожидания в очереди начнет уменьшаться, если интенсивность обслуживания заявок первого типа будет ? 3.5

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

В примере 3 рассмотрим случай, когда из 7 обслуживающих приборов, 2 задействованы для обработки заявок первого типа. Далее, в примере 3.1. берем тот же входящий поток, но на этот раз на обслуживание заявок первого типа выделим уже 3 прибора.

Пример 3:

Полученные результаты:

Пример 3.1:

Полученные результаты:

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

Пример 3.2

Полученные результаты:

Вспомним, что находится по следующей формуле:

Тогда:

= = 0.004

EX = 0.001… Следовательно оптимизация системы за счет уменьшения среднего времени ожидания заявок первого типа по определению не возможна. Та же ситуация произойдет при n1=5, поэтому будет логично эти разбиения из рассмотрения исключить.

Вывод:

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

До оптимизации: среднее время ожидания в очереди было равно 0,00168396…, а равнялось 5.

Для того, чтобы среднее время ожидания стало уменьшаться, в примере 3 значение должно принять значение 14.2 или выше, тогда как в примере 3.1 достаточно, чтобы стало равным 8.78.

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

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

Итог:

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

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

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

3) *проверить все возможные разбиения

Заключение

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

Список литературы

массовый обслуживание математический модель

1) Вывод уравнений для систем массового обслуживания с бесконечным накопителем и скачкообразной интенсивностью входного потока. / О. В. Бондрова, Д. С. Крылова, Н. И. Головко, Т. А. Жук - Дальневосточный Федеральный Университет, 2014

2) Исследование операций: задачи, принципы, методология. / Вентцель Е.С. - Москва: Издательство «Советское радио», 1972. - стр153-155

3) Оптимизация системы массового обслуживания с однотипным резервным прибором. / Самочернова Л.И., Петров Е.С. - Томск: Известия Томского Политехнического Университета, выпуск № 5 / том 317, 2010

4) Теория массового обслуживания. / Ивченко Г.И., Каштанов В.А., Коваленко И.Н. - Москва: Издательство «Высшая школа», 1982

5) Controlling the supermarket service/ Jose Antonio Montero, L. Enrique Sucar - Mexico: National Institute of Astrophysics, Computer Science Department, Reporte Tйcnico, 2010

6) The art of elevatoring/ Kai Ryssdal//[Электронный ресурс]-USA: American Public Media, 2012, режим доступа: http://www.marketplace.org/topics/business/art-elevatoring, свободный (дата обращения 19.04.2017)

Размещено на Allbest.ru