Ожидание того или иного вида обслуживания является частью нашей повседневной жизни. Мы ожидаем, чтобы пообедать в ресторане, мы стоим в очереди к кассам в магазинах и выстраиваемся в очередь в почтовых отделениях. Очередь возникает практически во всех присутственных местах: налоговых инспекциях, паспортных столах, страховых компаниях и пр. Феномен ожидания характерен не только для людей: работы, поставленные в очередь для выполнения; группа пассажирских самолетов, ожидающих разрешения на посадку в аэропорту; автомобили, движение которых приостановлено сигналом светофора на пути их следования, грузовые суда, ожидающие погрузки/разгрузки в порту, и т.п.
Изучение очередей в системах массового обслуживания (СМО) озволяет определить критерии функционирования обслуживающей системы, среди которых наиболее значимыми являются среднее время ожидания в очереди и средняя длина очереди. Эта информация используется затем для выбора надлежащего уровня обслуживания, что продемонстрировано в следующем примере.
Пример 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 и не зависят от того, когда и как система пришла в это состояние. Рассмотренные ниже модели относятся к марковским системам.
В случае немарковских процессов задачи исследования СМО значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Стохастическое моделирование
Ключевые слова: стохастичность, теория очередей, системы массового обслуживания, накопитель, очередь, транзакт
Стохастическое моделирование – это один из видов имитационного моделирования, базирующийся на теории Монте-Карло. Его определение можно представить так:
& Стохастическое моделирование (англ. 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) случайно (например, последовательность регистрации книг, поступивших в одной партии для книжного магазина).
Таким образом, для каждой очереди можно посчитать её среднюю длину; интенсивность поступления и выбытия из очереди; процент заявок, вышедших из системы по истечению срока ожидания; вероятность того, что система будет свободна; вероятность нахождения определённого числа клиентов в системе.
К перечисленным характеристикам добавляется параметр различного приоритета транзактов, что усложняет поведение заявок в системе. Многие процессы, сводимые к теории массового обслуживания, достаточно сложно оценить аналитически. Поэтому имитирование работы подобных систем – рациональный подход для определения характеристик исследуемой предметной области.
Очередь грузовиков под разгрузку на склад, ожидание клиентами банка свободного кассира. Если, например, клиентам приходится слишком долго ждать кассира, они могут решить перенести свои счета в другой банк. Подобным образом, если грузовикам приходится слишком долго дожидаться разгрузки, они не смогут выполнить столько ездок за день, сколько положено. Таким образом, принципиальная проблема заключается в уравновешивании расходов на дополнительные каналы обслуживания (больше людей для разгрузки грузовиков, больше кассиров, больше клерков, занимающихся предварительной продажей билетов на самолеты) и потерь от обслуживания на уровне ниже оптимального (грузовики не могут сделать лишнюю остановку из-за задержек под разгрузкой, потребители уходят в другой банк или обращаются к другой авиакомпании из-за медленного обслуживания).
Теория игр - это метод, используемый для оценки влияния какого-либо действия на конкурентов. Моделями теории очередей можно пользоваться в соответствии со спросом на них. Модели управления запасами помогают руководителю синхронизировать размещение заказов на ресурсы и оптимизировать их объемы, а также определять оптимальное для склада количество готовой продукции . Модели линейного программирования позволяют установить оптимальный способ распределения дефицитных ресурсов между конкурирующими потребностями в них. Имитационное моделирование - это использование устройства, которое имитирует реальный мир. В экономическом анализе используется ряд методов для определения экономического положения организации или осуществимости действия с экономической точки зрения.
Настоятельная потребность маркетинга и. предпринимательства в целом в полном и объективном освещении рыночных процессов , в достоверном предсказании возможного развития рынка. Понятие маркетингового исследования , его роль в бизнесе и удовлетворении информационно-аналитических потребностей маркетинга. Место маркетингового исследования в разработке стратегии маркетинга , планировании маркетинга и его контроллинге. Предмет и объекты маркетингового исследования . Цели маркетингового исследования . Принципы маркетингового исследования . Два направления маркетингового исследования формализация и качественные оценки. Достоинства и недостатки каждого из них. Возможности их консолидации. Основы методологии маркетингового исследования . Особая роль статистики и эконометрики в маркетинговых исследованиях . Теория массового обслуживания (теория очередей). Понятие статистического банка (набора статистических приемов обработки информации).
Данный метод также предусматривает разложение проблемы на части и изучение каждой из них. Важным инструментом данного метода является разработка и проигрывание с использованием количественных методов и компьютеров различных моделей решения. Разработаны и используются модели с привлечением системного подхода , исследования операций , теории игр, теории очередей, уп-
В 60-е гг. широко применялась такая техника планирования , как оперативное исследование. Речь идет об использовании научной техники управления для анализа проблемы и оценки возможных решений. Сюда входят теория очередей, игр, имитационное моделирование . Применение той или иной модели в процессе планирования зависит от накопления и анализа объективной информации. Предполагается, что информация должна поступать в каналы управления в достаточном объеме и в нужное время. Это самый ценный актив организации.
К числу важнейших инструментов и методов исследования операций относятся теория вероятности , метод обратных связей , линейное программирование , символическая логика, теория информации и связей, теория очередей, теория игр, теория поисков.
Изложенные обстоятельства позволяют для моделирования науки в регионе использовать математический аппарат теории очередей. Согласно этой теории, науку можно считать системой массового обслуживания (СМО). СМО, как известно, называется любая система, предназначенная для обслуживания каких-либо заявок, поступающих в нее в случайные моменты времени.
Теория очередей позволяет находить вероятности различных состояний СМО, а также устанавливать зависимости между заданными параметрами (числом каналов п, интенсивностью потока заявок Я, распределением времени обслуживания и т.д.) и характеристиками эффективности работы СМО. В качестве таких характеристик могут рассматриваться следующие
Усовершенствуем формулы теории очередей применительно к специфике науки. Условия существования стационарного режима, по мнению автора, будут иметь место при следующих обстоятельствах
Читатель найдет здесь доступное описание основных экономико-математических методов , построенных как на традиционном аппарате математики и логики, известном из школьных программ (дроби, проценты, уравнения, прогрессии, геометрические и логические задачи), так и на основе методов исследования операций - современном математическом аппарате , специально созданном для решения тех задач, с которыми элементарная математика не справляется. Это методы оптимизации (линейное, нелинейное и динамическое программирование), теория вероятностей и математическая статистика , теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), теория игр и статистических решений, сетевое планирование.
Наряду с элементарной математикой и логикой рассматриваются также задачи, требующие применения аппарата высшей математики, особенно в теории вероятностей и математической статистике , а также в таких сравнительно молодых методах, как математическое программирование (линейное, нелинейное, динамическое), теория игр и статистических решений, теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), сетевое планирование.
Если при поступлении очередной заявки все имеющиеся каналы (аппараты) оказываются занятыми, происходит сбой в обслуживании и начинает образовываться очередь. Поэтому теорию массового обслуживания называют также теорией очередей.
Центральным понятием теории очередей является функция стоимости, равная
Если величина N больше 1, вычисления приобретают более сложный характер. Общая формула приведена в Приложении 1, где также обсуждаются другие проблемы теории очередей. Для JV, равных 2 и 3, формулы выглядят следующим образом
В этой главе рассмотрены различные аспекты выбора места и планировки производственных площадей . Сокращение денежных, трудовых, временных и иных затрат возможно на основе определения общей производственной мощности , а для сферы услуг - использования теории очередей (массового обслуживания) для нахождения оптимального баланса между объемом простаивающего оборудования и временем ожидания покупателя в очереди.
В русскоязычной литературе теория очередей иногда называется теорией массового обслуживания.
Применение М. М.-К. можно проиллюстрировать примером из области теории очередей. Предположим, надо определить, как часто и как долго придется ждать покупателям в очереди в магазине при заданной его пропускной способности (допустим, для того, чтобы принять решение , следует ли расширять магазин). Подход покупателей носит случайный характер, распределение времени подхода (так можно назвать промежуток времени между каждыми двумя приходами покупателей) может быть установлено из имеющейся информации. Время обслуживания покупателей тоже носит случайный характер, и его распределение тоже может быть выявлено. Таким образом, имеются два стохастических или случайных процесса , взаимодействие которых и создает очередь.
Следует сказать и о терминах "Т.м.о." и "теория очередей". Во многих работах они трактуются как равнозначные, в других - теория очередей рассматривается лишь как раздел Т.м.о., поскольку последней изучаются системы не только с очередями, но и с отказами (напр., когда телефонная станция занята, очередь абонентов не образуется), а также некоторые иные.
Рыжиков Ю.И. Теория очередей и управление запасами . -СПб. Питер, 2001.-384 с.
Статистика - наука, изучающая массовые явления и процессы, поддающиеся количественному измерению, позволяющая выявлять тенденции и закономерности общественного развития, определять пропорции и оценивать колеблемость. Эконометрия -применение экономико-математических методов анализа , измерение параметров математических выражений, характеризующих определенную социально-экономическую концепцию, моделирование сложных, многомерных процессов и явлений. Достаточно широко в маркетинге используются методы линейного и динамического программирования , приемы теории массового обслуживания (теории очередей), теории принятия решений (теории риска), теории связей (сигнальной информации о процессах, выходящих за пределы установленных параметров). Социометрия - характеристика структуры и функционирования определенных человеческих групп с помощью количественных оценок . Квалиметрия - методология количественных оценок качества товаров . Бихевиоризм - наука о вкусах и предпочтениях людей, которая помогает разобраться в процессах формирования и изме-
Часто бывает, что запросы на обслуживание отдельных клиентов или заказы индивидуальных покупателей продукции поступают в систему случайным образом. Это так называемая проблема случайных клиентов. Единственный путь, который позволяет удовлетворять таких заказчиков, если накопление продукции и ожидание клиентов исключается, это составление внешнеориентированного расписания в сочетании с общим избытком мощности системы (избытком всех ее ресурсов). На практике такое расточительное резервирование встречается редко и поэтому части заказчиков, обращающихся в систему, приходится либо предлагать ожидание, либо отказывать, неся при этом определенные экономические Управление качеством (1974) -- [
Эта теория представляет особый раздел теории случайных процессов и использует, в основном, аппарат теории вероятностей. Первые публикации в этой области относятся к 20-м гг. XX в. и принадлежат датчанину А. Эрлангу, занимавшемуся исследованиями функционирования телефонных станций - типичных СМО, где случайны моменты вызова, факт занятости абонента или всех каналов, продолжительность разговора. В дальнейшем теория очередей нашла развитие в работах многих советских и зарубежных математиков.
Теория очередей, - раздел теории вероятностей, изучающий математические модели разного рода реальных массового обслуживания систем. Эти модели представляют собой случайные процессы специального вида, которые называются иногда процессами обслуживания. Чаще всего используется описательное определение этих процессов, поскольку формальное их построение оказывается весьма сложным и не всегда эффективным.
Теория массового обслуживания использует главным образом аппарат теории вероятностей. Основные задачи теории массового обслуживания обычно состоят в том, чтобы на основании "локальных" свойств рассматриваемых случайных процессов изучить их стационарные характеристики (если таковые существуют) или поведение этих характеристик за большой промежуток времени. Одна из главных конечных целей исследований в этой области состоит в выборе наиболее разумной организации систем массового обслуживания.
Системы массового обслуживания (СМО)-- это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требование из находящихся в очереди, с тем, чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания.
Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, в случайные моменты времени.
Примерами систем массового обслуживания могут служить: Магазины, банки, ремонтные мастерские, почтовые отделения, посты технического обслуживания автомобилей, посты ремонта автомобилей, персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач, аудиторские фирмы, отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий, телефонные станции и т.д.
Основными компонентами системы массового обслуживания любого вида являются:
входной поток поступающих требований или заявок на обслуживание;
дисциплина очереди;
механизм обслуживания.
Входной поток требований. Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.
Дисциплина очереди -- это важный компонент системы массового обслуживания, он определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:
- - первым пришел - первый обслуживаешься;
- - пришел последним -- обслуживаешься первым;
- - случайный отбор заявок;
- - отбор заявок по критерию приоритетности;
- - ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»).
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продолжительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процедуры. Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».
Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода обслуживающего прибора по истечении некоторого ограниченного интервала времени.
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего, следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживание.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно. Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Рассмотрев основные компоненты систем обслуживания, можно констатировать, что функциональные возможности любой системы массового обслуживания определяются следующими основными факторами:
- - вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);
- - вероятностным распределением времени продолжительности обслуживания;
- - конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);
- - количеством и производительностью обслуживающих каналов;
- - дисциплиной очереди;
- - мощностью источника требований.
В качестве основных критериев эффективности функционирования систем массового обслуживания, в зависимости от характера решаемой задачи могут выступать:
- - вероятность немедленного обслуживания поступившей заявки;
- - вероятность отказа в обслуживании поступившей заявки;
- - относительная и абсолютная пропускная способность системы;
- - средний процент заявок, получивших отказ в обслуживании;
- - среднее время ожидания в очереди;
- - средняя длина очереди;
- - средний доход от функционирования системы в единицу времени и т.п.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО:
- - системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;
- - системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов.
Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием.
В системах с ограниченным ожиданием может ограничиваться:
- - длина очереди;
- - время пребывания в очереди.
В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживание неограниченно долго, т.е. пока не подойдет очередь.
По количеству каналов обслуживания СМО подразделяются на следующие группы:
Одноканальные СМО. Она состоит из одной очереди и одного устройства обслуживания. Термин "одноканальная" говорит о том, что к устройству обслуживания ведет только один путь.
Многоканальные СМО. Обслуживание очередной заявки может начаться до окончания обслуживания предыдущей заявки. Каждый канал действует как самостоятельное обслуживающее устройство.
По кругу обслуживаемых объектов различают два вида.
Замкнутые СМО. Замкнутая система массового обслуживания - это система массового обслуживания, в которой обслуженные требования могут возвращаться в систему и вновь поступать на обслуживание. Примерами замкнутой СМО являются ремонтные мастерские, сберегательные банки.
Открытые СМО. Для открытой СМО предполагается, что исходная совокупность на столько велика, что изменение ее размеров, вследствие прибытия или возвращения обслуженной заявки в исходную совокупность не оказывает существенного влияния на вероятность появления очередной заявки. массовый обслуживание математический однофазный
Если приборы обслуживания соединяются параллельно, то такое обслуживание называется однофазным, а если приборы соединяются последовательно, то многофазным, (ряд последовательных операций).
Однофазные СМО - это однородные системы, которые выполняют одну и ту же операцию обслуживания.
Многофазные СМО - это системы, в которых каналы обслуживания расположены последовательно и выполняют различные операции обслуживания. Примером многофазной СМО являются станции технического обслуживания автомобилей.
Приведенная классификация СМО является условной. На практике чаще всего СМО выступают в качестве смешанных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами.
В 1953 году Г. Кендалл предложил стандартные обозначения определений, которые используются исследователями без изменений. Для однофазных СМО символика Кендалла выглядит следующим образом:
A / B / n / m 2.1
Где A и B входной поток и поток обслуживания соответственно,
n - число каналов, n 1,
m - ёмкость накопителя.
Потоки случайных событий могут иметь различный вид:
- - М - экспоненциальное распределение длительностей интервалов поступления заявок или длительностей обслуживания (индекс М от определяющего слова марковский процесс, т.е. такой, когда поведение процесса после момента времени t зависит лишь от состояния процесса в момент времени t и не зависит от поведения до момента времени t),
- - D - детерминированное распределение длительностей интервалов поступления заявок или длительностей обслуживания,
- - Ек - поток Эрланга к - го порядка для длительностей интервалов между приходами заявок или длительностей обслуживания,
- - GI - рекуррентный поток (длительности интервалов статистически независимы и имеют одинаковое распределение),
- - G - общий вид распределения.
Тогда в символах Кендалла вместо А и В подставляется символ одного из упомянутых потоков, например:
M/M/1 - экспоненциальные потоки с одним каналом обслуживания и неограниченной ёмкостью.
D/GI/5/10 - детерминированный входной поток, рекуррентный поток обслуживания, многоканальное СМО с 5 одинаковыми каналами, ёмкость накопителя 10 и т.д.
Математика подобна мясорубке, она может
переработать любое мясо, но для того, чтобы
получить хорошие котлеты, нужно и хорошее мясо.
Один воин вышел из города и проходил по 12 верст в день, а другой вышел одновременно и шел так: в первый день прошел 1 версту, во второй день 2 версты, в третий день 3 версты, в четвертый 4 версты, в пятый 5 верст и так прибавлял каждый день по версте, пока не настиг первого. Через сколько дней второй воин настигнет первого?
Старинная задача
Основные понятия теории очередей
Многие экономические задачи связаны с системами массового обслуживания , в которых происходит удовлетворение требований на выполнение каких–либо услуг.
Исследованием систем массового обслуживания занимается теория очередей, на начальное развитие которой оказали особое влияние труды датского ученого Эрланга А.К. (1878–1929) в области проектирования и эксплуатации телефонных станций.
Общая схема системы массового обслуживания показана на рис. 11.1.
Требование на обслуживание (например, неисправный автомобиль) поступает в обслуживающую систему (автомастерскую). Если есть свободные каналы обслуживания (мастера), то требование выполняется. Если все каналы заняты, то требование ставится в очередь по определенным правилам или покидает систему не обслуженным.
Основная задача теории массового обслуживания сводится к определению оптимального соотношения между входным потоком требований и числом обслуживающих каналов, при котором общие суммарные затраты минимальны.
Общие суммарные затраты складываются из затрат обслуживания и затрат ожидания, причем по мере увеличения сервиса затраты обслуживания увеличиваются, а затраты ожидания уменьшаются.
Систему массового обслуживания можно описать, задавая следующие ее компоненты: входной поток требований, дисциплину очереди и механизм обслуживания.
Входной поток требований характеризуется вероятностным законом распределения моментов поступления требований в систему и количеством требований в каждом поступлении.
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких задач теории очередей, в которых поток требований является простейшим (пуассоновским) .
Простейший поток событий обладает тремя свойствами:
- стационарностью – постоянным количеством событий в единицу времени;
- отсутствием последействия – независимостью количества событий после любого момента времени от количества событий до него;
- ординарностью – практической невозможностью одновременного поступления нескольких требований.
Для простейшего потока частота наступления событий подчиняется закону Пуассона, то есть вероятность того, что за время t произойдет k событий определится
где l – количество событий в единицу времени (интенсивность потока).
Вероятность выхода из строя одной установки (k = 1) при отказе в среднем в единицу времени двух установок (l = 2)
Вероятность отсутствия вышедших из строя установок за любой случайный час – 13%, вероятность выхода из строя одной установки – 27%, двух – 27%, трех – 18%, четырех – 9% и т.д. (рис. 1.2).
Рис. 10.2. Распределение Пуассона для l = 2
По теореме сложения вероятностей вероятность суммы независимых событий равна сумме вероятностей этих событий, отсюда вероятность отказа в единицу времени не более четырех установок равна сумме вероятности отсутствия отказа и вероятностей отказа одной, двух, трех, четырех установок:
Вероятность отказа более четырех установок
P (m >4) = 1– 0,945 = 0,055.
Дисциплина очереди описывает порядок обслуживания требований в системе. Длина очереди может быть ограниченной или неограниченной. Правила постановки в очередь: FIFO – «первым пришел первым обслуживаешься», LIFO – «последним пришел первым обслуживаешься», по другим приоритетам или случайно.
Механизм обслуживания характеризуется продолжительностью процедур обслуживания и количеством одновременно обслуживаемых требований.
Время обслуживания требований в системе является случайной величиной и обычно описывается экспоненциальным законом распределения , то есть распределение длительности оставшейся части работ по обслуживанию не зависит от того, сколько оно уже продолжалось.
Вероятность того, что время обслуживания не превосходит некоторой величины t , определяется формулой:
где m – величина, обратная среднему времени обслуживания:
Введем в рассмотрение параметр a – коэффициент загрузки системы или среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступающие требования:
где l – среднее число требований, поступающих в единицу времени; m – среднее число требований, удовлетворяемых в единицу времени; Т обс – среднее время обслуживания одним каналом одного требования.
Заметим, что если a меньше количества каналов обслуживания, то очередь не может расти безгранично, то есть число обслуживающих каналов должно быть больше среднего числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступившие требования.
Различают следующие виды систем массового обслуживания.
В зависимости от условий ожидания требованием начала обслуживания различают системы массового обслуживания с отказами и с ожиданием.
В системах с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и утрачиваются.
В системах с ожиданием требование, застав все обслуживающие каналы занятыми, ставится на очередь вплоть до освобождения любого из каналов.
Системы, допускающие очередь, но с ограниченным числом требований в ней, называются системами с ожиданием и ограниченной длиной очереди .
Системы, допускающие очередь, но с ограниченным сроком пребывания каждого требования в ней, называются системами с ограниченным временем ожидания .
Системы массового обслуживания, допускающие очередь, но с ограниченным числом циркулирующих в системе требований, называются системами с ограниченным потоком требований .
По числу каналов обслуживания различают одноканальные и многоканальные системы .
По числу фаз обслуживания – однофазные и многофазные (последовательная обработка требований на нескольких каналах).
