Основы теории очередей. Теория массового обслуживания Какие ученые занимались разработкой теории массовых очередей
Теория массового обслуживания (англоязычное название - queueing theory - теория очередей) возникла в начале 20 века. Ее основоположником считается датский ученый А.К. Эрланг, работавший в шведской телефонной компании и занимавшийся вопросами проектирования телефонных сетей. В дальнейшем теория получила интенсивное развитие и применение в различных областях науки, техники, экономики, производства. Это объясняется тем, что эта теория изучает широко распространенные в человеческой практике ситуации, когда имеется некоторый ограниченный ресурс и множество (поток) запросов на его использование, следствием чего являются задержки или отказы в обслуживании некоторых запросов. Стремление понять объективные причины этих задержек или отказов и по возможности уменьшить их воздействие является побудительным мотивом развития теории массового обслуживания.
Как правило, поступление запросов (или их групп) происходит в случайные моменты времени и для их удовлетворения требуется случайная часть ограниченного ресурса (или случайное время его использования). Поэтому изучение процесса удовлетворения потребности в ресурсе (процесса обслуживания) обычно проводится в рамках теории случайных процессов как специальной области теории вероятностей. Иногда исследование процесса обслуживания требует применения достаточно тонких математических методов и серьезного математического аппарата. Это делает полученные результаты практически недоступными инженеру, потенциально заинтересованному в их применении к исследованию реального объекта.
Что, в свою очередь, лишает автора математического результата «обратной связи», важной для правильного выбора направления для дальнейшего обобщения результатов и объектов исследования. Эта серьезная проблема подмечена в обзоре известного специалиста Р. Сиски, отмечающего опасность возможности распада единой теории массового обслуживания на абстрактную и инженерную. Прямым следствием этой проблемы при написании книги обычно является вопрос выбора языка и соответствующего уровня строгости изложения результатов. Данная книга ориентирована как на специалистов в области теории массового обслуживания, так и на специалистов в области ее приложения к исследованию реальных объектов (в первую очередь, компьютерных сетей). Поэтому в данной главе приведем краткий обзор методов анализа систем массового обслуживания на среднем уровне строгости. Предполагается знакомство читателя с теорией вероятностей в рамках курса для технического вуза. При необходимости, некоторые сведения приводятся непосредственно в тексте.
Важным этапом в применении теории массового обслуживания для исследования реального объекта является формальное описание функционирования этого объекта в терминах той или иной системы массового обслуживания (СМО). СМО считается заданной, если полностью описаны следующие ее компоненты:
Входящий поток запросов (заявок, требований, сообщений, вызовов);
Количество и типы обслуживающих устройств (приборов);
Емкости накопителей (буферов), где запросы, заставшие все приборы занятыми, ожидают начала обслуживания;
Времена обслуживания запросов на приборах;
Дисциплина обслуживания (она определяет порядок обработки запроса в системе, начиная с момента его поступления в систему и до момента, когда он покидает СМО).
Стохастическое моделирование
Ключевые слова: стохастичность, теория очередей, системы массового обслуживания, накопитель, очередь, транзакт
Стохастическое моделирование – это один из видов имитационного моделирования, базирующийся на теории Монте-Карло. Его определение можно представить так:
& Стохастическое моделирование (англ. stochastic modeling) – разновидность имитационного моделирования, в котором моделируемый объект представляется в виде совокупности параметров, описывающих внешнюю работу системы (внутренняя особенность объекта неизвестна) и имеющих случайную природу.
Если рассмотренные выше блочные и пошаговые модели со случайными процессами являются во многом детерминированными (их структура полностью или частично известна), то для процессов, имеющих менее определённый характер, требуется иной подход.
С внедрением автоматизации на предприятиях длительность изготовления продукции существенно сократилась за счёт ускорения выполнения роботами операций и внедрения конвейера. Производственный/обслуживающий процесс в основном стал сводиться к последовательности чётко разделённых технологических циклов, следующих друг за другом последовательно. Увеличился объём выпускаемой продукции, а следовательно, и нагрузки на обслуживающие элементы системы, что привело к возникновению задачи эффективной статистической оценки работы как системы в целом, так и её отдельных частей. Так появился подход, называемый теорией массового обслуживания или теорией очередей.
Стохастическое моделирование, или теория очередей – классическая область применения методов имитационного моделирования. Базовыми понятиями в этой области являются очередь , канал обслуживания и транзакт .
В зависимости от сочетания и настроек базовых элементов теории очередей можно описывать сложные технологические процессы, регистрируя только количественные и временные характеристики их работы.
Стохастическое моделирование можно охарактеризовать следующими признаками:
– использованием для моделирования дискретного времени;
– отсутствием информации о внутренней логике работы подсистем (всё задано случайными процессами во времени);
– наличием чёткой последовательности технологических операций в моделируемом процессе;
– рассмотрением однотипных объектов на каждом этапе процесса обслуживания;
– выделением законов движения транзакта путём наблюдения за моделируемой системой и обработки полученной статистики;
– просчётом, который позволяет визуализировать эволюцию модели на каждом шаге моделирования;
– представлением экспериментальных данных в виде таблицы-отчёта и графиков.
Условно в теории очередей рассматривается последовательность изменения состояния обслуживаемой заявки (транзакта) между этапами «поступление», «ожидание в очереди», «обслуживание», «покидание системы». При этом процесс внутренней работы подсистем (обслуживание) не детализируется, как в других моделях, а лишь характеризуется обобщенными временными характеристиками (высокая стохастичность). По этой причине подобные модели получили ещё одно название – системы массового обслуживания .
& Система массового обслуживания (англ. queue(ing) system, СМО ) – система, описывающая движение транзактов в исследуемом сложном объекте, характеризуемом траекторией обслуживания транзактов в виде временных интервалов.
Целью исследования в модели будут этапы обслуживания – наиболее трудно формализуемые элементы в системе.
Каждый этап обслуживания в модели имеет индивидуальную характеристику длительности и обозначается термином «накопитель». Для каждого накопителя в системе можно посчитать пропускную способность (число обслуженных заявок), коэффициент загрузки, среднюю скорость обслуживания одной заявки.
Наряду с накопителями, центральными понятиями в теории очередей являются транзакт и очередь. Рассмотрим их подробней.
& Транзакт (англ. transact) – элементарный элемент обслуживания в модели (заявка), траектория обработки которого описывается на всём этапе его присутствия в системе в соответствии с особенностями технологического процесса.
Транзакт может моделировать человека в очереди, процесс в памяти ЭВМ, товар на прилавке и тому подобное. Каждый транзакт имеет уникальный порядковый номер и обладает рядом характеристик, которые делятся на следующие группы:
1) человеческие (например, клиенты торговой точки);
2) финансовые (например, заявка на денежный перевод в отделение банка);
3) информационные (например, вызов на междугороднюю АТС);
4) прочие (например, техническое устройство, требующее ремонта или обслуживания).
По времени жизни:
1) с фиксированным временем жизни (например, скоропортящийся продукт питания после попадания в торговую точку может находиться там только ограниченное количество времени);
2) с бесконечным временем жизни (например, заявка в отдел заказов книжного магазина на доставку литературы).
По способу обслуживания:
1) с привилегиями, или приоритетами (например, обслуживание в кассе ветеранов Великой Отечественной войны без очереди);
2) без приоритетов (например, очередь в кассу кинотеатра).
Транзакты являются теми элементарными единицами обслуживания в системе, с помощью которых можно производить исследования моделируемых процессов. Последовательная совокупность транзактов, поступающая к месту обслуживания (накопителю), образует поток.
Непосредственно перед входом на этап обслуживания перед накопителем выстраивается очередь, образованная потоком транзактов. Она является важной характеристикой при оценивании работоспособности исследуемой системы, поэтому выделяют следующие виды очередей:
По положению:
1) внешняя (например, ожидание принтером ремонта в сервисном центре);
2) внутренняя (например, ожидание очередного этапа обработки изделия в середине технологического цикла (очередь внутри системы).
По длине:
1) с отказами (например, если на автостоянке нет свободных мест для парковки, то автомобиль уезжает, не дожидаясь освобождения места);
2) фиксированной длины (например, очередь запросов на соединение абонентов на АТС).
3) произвольной длины (например, очередь в супермаркете).
По интенсивности поступления новых запросов:
1) стационарные (регулярное поступление транзактов) (например, скорость движения конвейера задаёт интенсивность поступление товара в очередь для транспортировки на склад);
2) нестационарные (случайная интенсивность поступления транзактов) (например, поступление клиентов к пункту обслуживания столовой).
По направлению обслуживания транзактов:
1) правило FIFO: First Input – First Output, то есть ′первым пришел – первым вышел′ (например, очередь к парикмахерскую);
2) правило FILO: First Input – Last Output, то есть ′первым пришел – последним вышел′ (например, последовательность вынимания из постоянно пополняющегося контейнера деталей для последующей обработки: внизу находятся те детали, которые прибыли в контейнер первыми, поэтому они будут обработаны в последнюю очередь).
3) случайно (например, последовательность регистрации книг, поступивших в одной партии для книжного магазина).
Таким образом, для каждой очереди можно посчитать её среднюю длину; интенсивность поступления и выбытия из очереди; процент заявок, вышедших из системы по истечению срока ожидания; вероятность того, что система будет свободна; вероятность нахождения определённого числа клиентов в системе.
К перечисленным характеристикам добавляется параметр различного приоритета транзактов, что усложняет поведение заявок в системе. Многие процессы, сводимые к теории массового обслуживания, достаточно сложно оценить аналитически. Поэтому имитирование работы подобных систем – рациональный подход для определения характеристик исследуемой предметной области.
Очереди и управление ими – один из важнейших аспектов операционного менеджмента. Знать, как обращаться с ними, необходимо при составлении графиков, проектировании операций, планировании товарно-материальных запасов и т.д.
Существование очередей – это нормальное состояние произв. системы; ими довольно эффективно можно управлять с помощью средств системного менеджмента и проектирования.
Хар-ки входящих потоков:
1) вид входящего потока (управляемый, неуправляемый);
2) размер единицы входящего потока заявок: (одиночная заявка, групповая заявка);
3) распределение входящего потока (равномерное, экспоненциальное или пуассоновское, другое);
Очередь очередь очереди и ушел).
Параметры очередей:
1) длина очереди (бесконечная, ограниченная пропускной способностью);
2) кол-во очередей (однолинейная, многолинейная);
3) дисциплина очереди (первым прибыл, первым обслужен; первоочередное обслуживание клиентов с наименьшим временем обслуживания; первоочередное обслуживание по предварит. заказам; первоочередное обслуживание в случае крайней необходимости; ограничение потребностью; другая дисциплина).
Структура очередей:
1. Одноканальная (однофазовая, многофазовая);
2. Многоканальная (однофазовая, многофазовая);
3. Комбинированная:
Структура с переходом многоканального обслуживания в одноканальное (однофазовая, многофазовая),
Структура альтернативного пути.
Сценарии выхода из системы клиента:
1) возвращается в исходную генеральную совокупность;
2) низкая вероятность повторного обслуживания.
-
4) уровень терпеливости клиентов (терпеливый - стал в очередь и ждет, нетерпеливый - прибыл, осмотрел очередь и ушел; прибыл, немного постоял в очереди и ушел). Параметры очередей -
4) уровень терпеливости клиентов (терпеливый - стал в очередь и ждет, нетерпеливый - прибыл, осмотрел очередь и ушел; прибыл, немного постоял в очереди и ушел). Параметры очередей -
Сущность теории очередей , основные понятия .
основных -
Сущность теории очередей , основные понятия .
Это документ, в соответствии с которым происходит разбиение общего объема на совокупность основных пакетов работ, подлежащих выполнению. -
Сущность теории очередей , основные понятия . Очереди -
Сущность теории очередей , основные понятия . Очереди и управление ими – один из важнейших аспектов операционного менеджмента. Знать, как о. Стратегии преодоления проблем, которые обусловленные неоднородностью спроса. -
Сущность теории очередей , основные понятия . Очереди -
Сущность теории очередей , основные понятия . Очереди и управление ими – один из важнейших аспектов операционного менеджмента. Знать, как обращат... подробнее ». -
Понятие , сущность , основные
теории основные разновидности, или направления. -
Многочисленные демократические теории условно можно подразделить на три основные разновидност. Понятие , сущность , основные признаки политического режима демократии.
Найдено похожих страниц:10
Каждый из нас не раз в своей жизни стоял в очередях и знает, как много времени это отнимает.
Многие модели, призванные решить или оптимизировать эту проблему, требуют сложных математических формулировок .
Очередь - это линия ожидания . Теория очередей - часть более широкой теории, в рамках которой проводятся оперативные исследования и создаются математические модели. Все это делается с одной целью - решить проблемы, которые создает стояние в очередях. Здесь важно найти компромиссный вариант, учитывающий систему расходов и среднее время ожидания в очереди. анализировать телефонную систему в Копенгагене, чтобы разрешить проблему загруженности телефонных линий.
Первопроходцем в теории очередей был датский математик Агнер Краруп
(1878-1929), взявшийся
анализировать телефонную систему в Копенгагене, чтобы разрешить проблему загруженности телефонных линий.
В теории изучения очередей существуют законы Харпера , подобные знаменитым законам Мерфи.
- Первый закон Харпера : неважно, в какую очередь ты становишься - всегда есть одна, движущаяся быстрее остальных.
- Второй закон Харпера : если ты переходишь в другую очередь, та, которую ты покинул, начинает двигаться быстрее.
Проблема очередей
Современный человек проводит в ожидании более или менее значительную часть своей жизни. Разве есть среди нас те, кто никогда не стоял в очереди? Мир ожидания очень разнообразен: очереди машин на въезде на платную дорогу, очереди самолетов на выезде на взлетную полосу и, как следствие, очереди пассажиров к стойкам регистрации; очередь к банкоматам в больших зданиях, очередь на прием к врачу или очередь телефонных звонков, которые должны быть обработаны на пожарной станции… Это лишь некоторые примеры. пытается создать модели, поддающиеся последующей математической обработке.
Модели очередей
Некоторые модели очередей очень просты, другие требуют применения сложных математических теорий. Первичная классификация разбивает их на две большие группы.
Детерминированная очередь - наиболее простая модель, которую можно заранее спрогнозировать, опираясь на известные условия, например, временные интервалы прибытия и ожидания. Это «очередь без сюрпризов».
Вероятностная очередь не может быть описана без применения вероятностей. Это более реалистичная модель, чем предыдущая. В дождливый день, например, есть большая вероятность того, что увеличатся очереди на стоянках такси и уменьшатся очереди в кассы зоопарка.
Ожидание того или иного вида обслуживания является частью нашей повседневной жизни. Мы ожидаем, чтобы пообедать в ресторане, мы стоим в очереди к кассам в магазинах и выстраиваемся в очередь в почтовых отделениях. Очередь возникает практически во всех присутственных местах: налоговых инспекциях, паспортных столах, страховых компаниях и пр. Феномен ожидания характерен не только для людей: работы, поставленные в очередь для выполнения; группа пассажирских самолетов, ожидающих разрешения на посадку в аэропорту; автомобили, движение которых приостановлено сигналом светофора на пути их следования, грузовые суда, ожидающие погрузки/разгрузки в порту, и т.п.
Изучение очередей в системах массового обслуживания (СМО) озволяет определить критерии функционирования обслуживающей системы, среди которых наиболее значимыми являются среднее время ожидания в очереди и средняя длина очереди. Эта информация используется затем для выбора надлежащего уровня обслуживания, что продемонстрировано в следующем примере.
Пример 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 и не зависят от того, когда и как система пришла в это состояние. Рассмотренные ниже модели относятся к марковским системам.
В случае немарковских процессов задачи исследования СМО значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Загрузка...
