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

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

Содержание

Введение

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Схема СМО

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

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

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

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

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

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

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

|  | n |

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

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

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

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

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

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

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

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

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

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

 =  

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

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

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

=  +

 =

|  | n1 |  и |  | n - n1 |