Очереди - это аспект современной жизни, с которым мы постоянно сталкиваемся в нашей повседневной деятельности. В супермаркетах, при доступе к метро, в банках и т. Д. Явление очередей возникает, когда необходимо получить доступ к общим ресурсам для обслуживания большого количества рабочих мест или клиентов.
Изучение очередей важно, потому что оно обеспечивает как теоретическую основу для типа услуги, которую мы можем ожидать от данного ресурса, так и того, как этот ресурс может быть спроектирован для предоставления определенного уровня обслуживания своим клиентам.
В связи с вышеизложенным, разработка инструмента, способного дать ответ о характеристиках определенной модели очереди, считается очень полезной.
Исходные определения
Теория массового обслуживания - это математическое исследование поведения очередей. Это происходит, когда «клиенты» прибывают в «место», требуя обслуживания от «сервера», которому уделяется определенное внимание. Если сервер недоступен сразу и клиент решает подождать, формируется очередь ожидания.
Очередь это ждет линии и теории массового обслуживания представляет собой совокупность математических моделей, описывающих конкретные системы ожидания линий или систем массового обслуживания. Эти модели используются для нахождения хорошего компромисса между стоимостью системы и средним временем ожидания в очереди для данной системы.
Системы массового обслуживания - это модели систем, предоставляющих услуги. В качестве модели они могут представлять любую систему, в которую вакансии или клиенты приходят в поисках какой-либо услуги и уходят после того, как эта услуга была посещена. Мы можем моделировать системы этого типа как простые очереди или как систему взаимосвязанных очередей, образующих сеть очередей. На следующем рисунке мы можем увидеть пример простой модели очереди. Эту модель можно использовать для представления типичной ситуации, в которой клиенты прибывают, ждут, если серверы заняты, обслуживаются доступным сервером, и уходят, когда будет получена требуемая услуга.
Проблема состоит в том, чтобы определить, какая емкость или скорость обслуживания обеспечивают правильный баланс. Это непросто, поскольку клиент прибывает не по фиксированному графику, то есть точно неизвестно, когда они прибудут. Также время обслуживания не имеет фиксированного графика.
Проблемы «очередей» постоянно присутствуют в повседневной жизни: исследование, проведенное в США, показало, что в среднем средний гражданин тратит пять лет своей жизни в ожидании в разных очередях, из них почти шесть месяцев, стоя на светофоре.
Введение в теорию массового обслуживания
Во многих случаях в реальной жизни очень распространенным явлением является образование очередей или очередей. Обычно это происходит, когда фактический спрос на услугу превышает возможности, существующие для предоставления этой услуги. Реальными примерами такой ситуации являются: пересечение двух маршрутов движения, светофор, плата за проезд, банкоматы, обслуживание клиентов в коммерческом учреждении, поломка электроприборов или других типов устройств, которые необходимо отремонтировать. технической службой и др.
Еще более частыми, если возможно, являются ситуации ожидания в контексте информационных технологий, телекоммуникаций и, в целом, новых технологий. Таким образом, например, процессы, отправленные на сервер для выполнения, образуют очереди ожидания, пока они не обслуживаются, информация, запрошенная через Интернет, от веб-сервера, может быть получена с задержкой из-за перегрузки в сети или на самом сервере. Другими словами, мы можем получить сигнал от занятых линий, если в этот момент рухнет блок управления, от которого зависит наш мобильный телефон, и т. Д.
Происхождение:
Теория массового обслуживания возникла в результате попытки Агнера Краупа Эрланга (Дания, 1878–1929) в 1909 году проанализировать перегрузку телефонного трафика с целью удовлетворения неопределенного спроса на услуги в телефонной системе Копенгагена. Его исследования привели к новой теории, получившей название теории очередей или очередей. Эта теория сейчас является ценным бизнес-инструментом, потому что большое количество проблем можно охарактеризовать как проблемы с заторами при прибытии-отправлении.
Модель массового обслуживания.
При возникновении проблем с очередями часто говорят о клиентах, например о людях, ожидающих освобождения телефонных линий, ожидании ремонта машин, а также о самолетах, ожидающих приземления, и станциях обслуживания, например, столиках в ресторане., операторы в ремонтной мастерской, взлетно-посадочные полосы в аэропорту и т. д. Проблемы с очередями часто включают переменную скорость прибытия клиентов, нуждающихся в определенном типе услуг, и переменную скорость доставки услуг на станции обслуживания.
Говоря об очередях ожидания, они имеют в виду те, которые созданы клиентами или станциями обслуживания. Клиенты могут стоять в очереди просто потому, что существующие помещения не соответствуют требованиям для обслуживания; в этом случае очередь имеет тенденцию быть взрывоопасной, то есть становиться все длиннее и длиннее с течением времени. Станции обслуживания могут ждать, потому что существующие мощности чрезмерны по сравнению с потребностями клиентов; в этом случае станции обслуживания большую часть времени могут бездействовать. Клиенты могут временно подождать, даже если услуги обслуживаются надлежащим образом, поскольку обслуживаются ранее прибывшие клиенты. Заправочные станции могут найти временные, когда,Несмотря на то, что в долгосрочной перспективе помещения находятся в надлежащем состоянии, время от времени наблюдается нехватка спроса из-за временного события. Эти последние два случая типичны для сбалансированной ситуации, постоянно стремящейся к равновесию, или стабильной ситуации.
В теории массового обслуживания группа физических единиц, объединенных таким образом, что они могут работать в унисон с рядом организованных операций, обычно называется системой. Теория массового обслуживания ищет решение проблемы ожидания, сначала предсказывая поведение системы. Но решение проблемы ожидания - это не только минимизировать время, которое клиенты проводят в системе, но и минимизировать общие затраты тех, кто запрашивает услугу, и тех, кто ее предоставляет.
Теория очередей включает математическое исследование очередей или очередей ожидания и предлагает большое количество математических моделей для их описания.
Необходимо достичь экономического баланса между стоимостью услуги и стоимостью, связанной с ожиданием этой услуги.
Сама теория массового обслуживания не решает эту проблему, она лишь предоставляет информацию для принятия решений.
Цели теории массового обслуживания
В задачи теории массового обслуживания входят:
- Определите оптимальный уровень пропускной способности системы, который минимизирует общую стоимость системы. Оцените влияние, которое возможные альтернативы изменения пропускной способности системы могут оказать на общую стоимость системы. Установите сбалансированный («оптимальный») баланс между соображениями количественные затраты и качественные услуги. Мы должны обращать внимание на время, проведенное в системе или в очереди: «терпение» клиентов зависит от типа конкретной рассматриваемой услуги, которая может заставить клиента «отказаться» от система.
Существующие элементы в модели очереди
Источник поступления или потенциальное население: это группа лиц (не обязательно живые существа), которые могут запросить данную услугу. Мы можем считать его конечным или бесконечным. Хотя случай бесконечности нереален, он позволяет (как ни странно) легче решать многие ситуации, в которых, в действительности, популяция конечна, но очень велика. Это предположение о бесконечности не является ограничивающим, когда, даже если потенциальная популяция конечна, ее количество элементов настолько велико, что количество людей, которые уже запрашивают вышеупомянутую услугу, практически не влияет на частоту, с которой потенциальная популяция генерирует новые запросы. услуги.
Клиент: Это каждый человек из потенциального населения, обращающийся за услугами. Предполагая, что время прибытия последовательных заявок составляет 0 <t 1 <t 2 <…, важно знать вероятностный паттерн, согласно которому источник входа генерирует заявки. Наиболее распространенным является использование в качестве эталона времени между поступлением двух последовательных клиентов: последовательные: последовательные клиенты: T {k} = tk - t k-1, задав их распределение вероятностей. Обычно, когда потенциальная популяция бесконечна, предполагается, что распределение вероятностей T k (которое будет так называемым распределением времени между прибытием) не зависит от количества клиентов, ожидающих завершения своего обслуживания, в то время как в если входной источник конечен,Распределение T k будет варьироваться в зависимости от количества клиентов в процессе обслуживания.
Емкость очереди: это максимальное количество клиентов, которые могут стоять в очереди (перед началом обслуживания). Опять же, его можно считать конечным или бесконечным. Самое простое, ради простоты расчетов, - принять его бесконечным. Хотя очевидно, что в большинстве реальных случаев емкость очереди конечна, не является большим ограничением предполагать, что она бесконечна, если крайне маловероятно, что клиенты не могут войти в очередь из-за того, что это предельное число было достигнуто в очереди., Дисциплина очереди: это способ, которым выбираются клиенты для обслуживания. Наиболее распространенные дисциплины:
Дисциплина FIFO (первым пришел - первым обслужен), также называемая FCFS (первым пришел - первым обслужен): в соответствии с которой первым обслуживается клиент, который прибыл первым.
Дисциплина LIFO (последний пришел - первый ушел), также известная как LCFS (последний пришел - первый обслуженный) или стек: который состоит в обслуживании первым клиента, который прибыл последним.
RSS (случайный выбор услуги) или SIRO (услуга в случайном порядке), который выбирает клиентов случайным образом.
Механизм обслуживания: это процедура, с помощью которой услуга предоставляется клиентам, которые ее запрашивают. Чтобы полностью определить механизм обслуживания, мы должны знать количество серверов указанного механизма (если указанное число было случайным, его распределение вероятностей) и распределение вероятностей времени, которое требуется каждому серверу для предоставления услуги. В случае, если серверы имеют разные навыки для предоставления услуги, распределение времени обслуживания должно быть указано для каждого из них.
Очередь, собственно говоря, - это набор ожидающих клиентов, то есть клиентов, которые уже запросили услугу, но еще не перешли в механизм обслуживания.
Система очереди: это набор, состоящий из очереди и механизма обслуживания, вместе с дисциплиной очереди, которая указывает критерии того, какой клиент из очереди выбрать для перехода к механизму обслуживания. Эти элементы более отчетливо видны на следующем рисунке:
Модель системы массового обслуживания должна определять распределение вероятностей времени обслуживания для каждого сервера.
Наиболее часто используемым распределением для времени обслуживания является экспоненциальное l, хотя обычно находят вырожденное или детерминированное распределение (постоянное время обслуживания) или распределение Эрланга (гамма).
Обозначения Кендалла
Условно модели, используемые в теории массового обслуживания, помечены как
Используемые дистрибутивы:
- M: экспоненциальное распределение (марковское) D: вырожденное распределение (постоянные времена) E k: распределение Эрланга G: общее распределение
M / M / s : Модель, в которой время между прибытием и временем обслуживания экспоненциально и имеется s серверов.
M / G / 1: экспоненциальное время между прибытием, общее время обслуживания и только 1 сервер
терминология
Обычно всегда используется следующая стандартная терминология:
- Статус системы: количество клиентов в системе. Длина очереди: количество клиентов, ожидающих обслуживания. N (t): количество клиентов в системе массового обслуживания в момент времени t (t ³0). P n (t): вероятность того, что в системе будет ровно n клиентов в момент времени t, учитывая их количество в нулевой момент времени. s: Количество серверов в системе очередей. ln: Средняя скорость поступления (ожидаемое количество приходов в единицу времени) новых клиентов, когда в системе n клиентов. m n: Средняя скорость обслуживания для всей системы (ожидаемое количество клиентов, завершающих обслуживание в единицу времени), когда в системе n клиентов.
Примечание: mn представляет собой совокупную скорость, с которой все занятые серверы успевают прекратить свои услуги.
ln : Когда ln постоянна для всех n
m n : Когда mn постоянна для всех n ³ 1
Его также можно интерпретировать как среднее количество людей, о которых заботятся
Примечание: для систем массового обслуживания, которые мы будем анализировать, мы будем делать предположение, что система находится в состоянии устойчивого состояния.
демонстрация
Для s = 1
r: ожидаемая доля времени, в течение которого отдельные серверы заняты).
l = 12 / час ® 1 / l = 5 минут
m = 15 / час ® 1 / m = 4 минуты
Сервер работает 4 раза из 5 минут, то есть работает 80% времени
r : Среднее количество обслуживаемых людей
Среднее число = 0 * P0 + 1 * P1
Среднее число = P1
Среднее количество = 1 / м / 1 / л
Среднее число = r
Следующие обозначения предполагают установившееся состояние:
- P n: вероятность того, что в системе ровно n клиентов. L: ожидаемое количество клиентов в системе. L q: ожидаемая длина очереди (исключая обслуживаемых клиентов). W : Время ожидания в системе для каждого клиента W: E (W) W q : Время ожидания в очереди для каждого клиента. W q : E (Вт q)
Соотношения между L, W, Lq и Wq
Предположим, что l n - постоянная l для всех n:
L = l Вт Lq = l Вт
Предположим, что среднее время обслуживания является постоянной величиной 1 / м для всех n ³ 1.
W = Wq + 1 / м L = Lq + r
Эти соотношения являются фундаментальными, поскольку они позволяют нам определить четыре фундаментальные величины L, W, Lq, Wq, как только значение одной из них будет найдено аналитически.
Ключевая особенность.
Между прибытием существует два основных типа времени:
Детерминированный, при котором последовательные клиенты приходят в один и тот же временной интервал, фиксированный и известный. Классическим примером является сборочная линия, где элементы прибывают на станцию через неизменные промежутки времени (известные как временные циклы).
Вероятностный, при котором время между последовательными поступлениями неопределенно и переменно. Вероятностное время между прибытием описывается распределением вероятностей.
В вероятностном случае определение реального распределения часто бывает затруднительным. Однако одно распределение, экспоненциальное распределение, оказалось надежным для решения многих практических задач. Функция плотности для экспоненциального распределения зависит от параметра, скажем l (греческая буква лямбда), и задается следующим образом:
f (t) = (1 / l) e- l t
где l (лямбда) - среднее количество прибытий в единицу времени.
При количестве времени T функцию плотности можно использовать для вычисления вероятности того, что следующий покупатель прибудет в пределах следующих T единиц времени от предыдущего прибытия, как показано ниже:
P (время между прибытием <= T) = 1-e- l t
Процесс обслуживания.
Процесс обслуживания определяет, как обслуживаются клиенты. В некоторых случаях в системе может быть более одной станции, на которой предоставляется необходимая услуга. Банки и супермаркеты, опять же, являются хорошими примерами вышесказанного. Каждое окно и каждый регистр - это станции, которые предоставляют одинаковые услуги. Такие структуры известны как многоканальные системы массового обслуживания. В таких системах серверы могут быть идентичными в том смысле, что они предоставляют одинаковый вид услуг так же быстро, или они могут не быть идентичными. Например, если все кассиры в банке имеют одинаковый опыт, их можно считать идентичными.
В отличие от многоканальной системы, рассмотрите производственный процесс с рабочей станцией, предоставляющей требуемые услуги. Все продукты должны пройти через эту рабочую станцию; в данном случае это одноканальная система массового обслуживания. Важно отметить, что даже в одноканальной системе может быть много серверов, которые вместе выполняют необходимую задачу. Например, на автомойке с одной станцией два сотрудника могут одновременно работать с автомобилем.
Еще одна характеристика процесса обслуживания - количество одновременно обслуживаемых клиентов на станции. В банках и супермаркетах (одноканальная система) одновременно обслуживается только один клиент. Напротив, ожидающих на остановке пассажиров обслуживают группами в зависимости от вместимости прибывающего автобуса.
Другой характеристикой процесса обслуживания является то, разрешен ли приоритет, то есть может ли сервер остановить процесс с клиентом, который он обслуживает, чтобы вызвать клиента, который только что прибыл? Например, в отделении неотложной помощи приоритет имеет место, когда врач, который занимается некритическим случаем, вызывается для оказания помощи в более критическом случае. Каким бы ни был процесс обслуживания, вы должны иметь представление о том, сколько времени потребуется для выполнения услуги. Эта сумма важна, потому что чем дольше длится услуга, тем дольше приходящим клиентам придется ждать. Как и в случае с процессом прибытия, это время может быть детерминированным или вероятностным. С детерминированным временем обслуживания,каждому клиенту требуется точно такое же известное количество времени для обслуживания. При вероятном времени обслуживания каждому клиенту требуется разное и неопределенное количество времени обслуживания. Вероятностное время обслуживания математически описывается распределением вероятностей. На практике трудно определить, каково реальное распределение, однако распределение, которое доказало свою надежность во многих приложениях, является экспоненциальным распределением. В этом случае его функция плотности зависит от параметра, скажем (греческая буква my) и даетсяНа практике трудно определить, каково реальное распределение, однако распределение, которое доказало свою надежность во многих приложениях, является экспоненциальным распределением. В этом случае его функция плотности зависит от параметра, скажем (греческая буква my) и даетсяНа практике трудно определить, каково реальное распределение, однако распределение, которое доказало свою надежность во многих приложениях, является экспоненциальным распределением. В этом случае его функция плотности зависит от параметра, скажем (греческая буква my) и дается
s (t) = (1 / m) e - m t
в котором:
m = среднее количество клиентов, обслуживаемых за единицу времени, так что:
1 / м = среднее время, потраченное на обслуживание клиента
В общем, время обслуживания может соответствовать любому распределению, но прежде чем вы сможете проанализировать систему, вам необходимо идентифицировать это распределение.
Показатели эффективности для оценки системы массового обслуживания
Конечная цель теории массового обслуживания состоит в том, чтобы ответить на административные вопросы, касающиеся проектирования и работы системы массового обслуживания. Управляющий банком может решить, назначить ли на обед трех или четырех кассиров. В производственной структуре менеджер может захотеть оценить влияние покупки новой машины, которая может обрабатывать продукты быстрее.
Любая система очередей проходит два основных этапа. Например, когда банк открывается утром, в системе никого нет, поэтому первый клиент обслуживается сразу. По мере поступления новых клиентов очередь постепенно формируется, и время ожидания начинает увеличиваться. В течение дня система достигает состояния, при котором эффект первоначальной нехватки клиентов устраняется, а время ожидания для каждого клиента достигает довольно стабильного уровня.
Некоторые общие показатели эффективности
Существует множество различных показателей производительности, которые используются для оценки устойчивой системы массового обслуживания. При проектировании и эксплуатации системы очередей администраторы обычно заботятся об уровне обслуживания, которое получает клиент, а также о правильном использовании сервисных средств компании. Некоторые из показателей, используемых для оценки производительности, возникают в результате следующих вопросов:
Вопросы, связанные со временем и ориентированные на клиента, такие как:
- Какое среднее время новичок должен стоять в очереди, прежде чем его обслужат? Соответствующий показатель производительности - это среднее время ожидания, представленное как Wq. Сколько времени клиент проводит во всей системе, включая время ожидания и время обслуживания? Соответствующий показатель производительности - это среднее время в системе, обозначаемое W
Количественные вопросы, связанные с номером клиента, например:
- Сколько в среднем клиентов ждут в очереди на обслуживание? Соответствующий показатель производительности - это средняя длина очереди, представленная как Lq. Каково среднее количество клиентов в системе? Соответствующий показатель производительности - это среднее число в системе, представленное L
Вероятностные вопросы, касающиеся как клиентов, так и серверов, например:
- Какова вероятность того, что клиенту придется ждать обслуживания? Соответствующим показателем производительности является вероятность блокировки, которая представлена как pw. Какова вероятность того, что сервер занят в любой конкретный момент времени? Соответствующим показателем производительности является использование, обозначенное буквой U. Этот показатель также указывает долю времени, в течение которого сервер занят. Какова вероятность того, что в системе имеется n клиентов? Соответствующий показатель производительности получается путем вычисления вероятности Po того, что в системе нет клиентов, вероятности Pi того, что в системе есть покупатель, и так далее. Это приводит к распределению вероятности состояний, представленному Pn, n = 0,1 …… Если пространство ожидания конечно,Какова вероятность того, что очередь заполнена и прибывающий заказчик не обслуживается? Соответствующим показателем производительности является вероятность отказа в обслуживании, представленная Pd.
Вопросы, связанные с затратами, например:
- Какова стоимость единицы времени для работы системы? Сколько рабочих станций необходимо, чтобы быть более рентабельным?
Конкретный расчет этих показателей эффективности зависит от класса системы массового обслуживания. Некоторые из этих мер взаимосвязаны. Знание значения меры позволяет определить значение связанной меры.
Связь между показателями эффективности
Расчет многих показателей производительности зависит от процессов поступления и обслуживания конкретной системы массового обслуживания. Эти процессы математически описываются прибытием и распределением услуг. Даже не зная конкретного распределения, отношения между некоторыми показателями производительности могут быть получены для определенных систем массового обслуживания только с использованием следующих параметров процессов поступления и обслуживания.
l = среднее количество прибытий в единицу времени
m = среднее количество клиентов, обслуживаемых за единицу времени в секции
Предположим, что количество клиентов бесконечно велико, а время ожидания в очереди ограничено. Общее время, которое клиент проводит в системе, - это время, затраченное на очередь, плюс время, в течение которого она обслуживается:
Среднее время в системе = время ожидания + время обслуживания
Среднее время в системе и среднее время ожидания представлены величинами W и Wq соответственно. Среднее время обслуживания можно выразить с помощью & параметров. Например, если & составляет 4 клиента в час, то в среднем каждому клиенту требуется 1/4 для обслуживания. В общем, время обслуживания равно 1 / &, что приводит нас к следующему соотношению:
W = Wq + 1 / м
Давайте теперь рассмотрим взаимосвязь между средним количеством клиентов в системе и средним временем, которое каждый клиент проводит в системе. Давайте представим, что клиент только что прибыл и, как ожидается, останется в системе в среднем полчаса. В течение этого получаса другие клиенты продолжают приходить со скоростью, скажем, двенадцать в час? Когда соответствующий клиент покидает систему, через полчаса он оставляет в среднем (1/2) * 12 = 6 новых клиентов.
То есть в среднем в системе одновременно находится шесть клиентов. Так:
Среднее время клиентов = Количество приходов X * Среднее время в системе.
так что:
L = l * W
Используя аналогичную логику, получается соотношение между средним количеством заявок, ожидающих в очереди, и средним временем ожидания в очереди:
Среднее время клиента = количество прибывших X единица времени в очереди
так что:
Lq = l * Wq
ВЫВОД
Теория очередей - это математическое исследование очередей или очередей. Очередь - это, конечно, обычное явление, которое возникает всякий раз, когда платежеспособный спрос на услугу превышает эффективное предложение.
Компаниям часто приходится принимать решения о том, какой объем услуг они должны быть готовы предложить. Однако во многих случаях невозможно точно предсказать, когда прибудут клиенты, которые потребуют услуги, и / или сколько времени потребуется, чтобы предоставить эту услугу; Вот почему эти решения связаны с дилеммами, которые необходимо решать с небольшим количеством информации. Готовность предложить любую запрашиваемую от нас услугу в любое время может означать поддержание неиспользуемых ресурсов и чрезмерных затрат. Но, с другой стороны, отсутствие достаточной мощности обслуживания приводит к возникновению чрезмерно длинных очередей в определенное время. Когда клиентам приходится стоять в очереди, чтобы получить наши услуги, они вовремя платят более высокую стоимость, чем они ожидали.Таким образом, длинные очереди обходятся компании дорого, поскольку приводят к потере престижа и клиентов.
Теория очередей сама по себе не решает проблему напрямую, но дает важную информацию, необходимую для принятия соответствующих решений, предсказывая некоторые характеристики очереди: вероятность формирования, среднее время ожидания.
Но если мы используем концепцию «внутренних клиентов» в организации компании, связывая ее с теорией очередей, мы будем приближаться к модели организации бизнеса «точно в срок», в которой мы пытаемся минимизировать затраты, связанные с бездействие ресурсов в производственной цепочке.
БИБЛИОГРАФИЯ
- Арбонас, М. Е. Промышленная оптимизация (I): Распределение ресурсов. Сборник продуктов № 26. Маркомбо С.А., 1989. Арбонас М.Э. Оптимизация промышленности (II): программирование ресурсов. Сборник продуктов № 29. Marcombo SA, 1989. Moskowitz, H. и Райт Г. П. Исследования операций. Prentice_Hall Hispanoamericana SA 1991.Buffa, E: Операционный менеджмент: проблемы и модели. Революционное издание, Гавана, 1968 год.
