Теория массового обслуживания (теория очередей). Смотреть страницы где упоминается термин теория очередей Смотреть что такое "Очередей теория" в других словарях
Очередь грузовиков под разгрузку на склад, ожидание клиентами банка свободного кассира. Если, например, клиентам приходится слишком долго ждать кассира, они могут решить перенести свои счета в другой банк. Подобным образом, если грузовикам приходится слишком долго дожидаться разгрузки, они не смогут выполнить столько ездок за день, сколько положено. Таким образом, принципиальная проблема заключается в уравновешивании расходов на дополнительные каналы обслуживания (больше людей для разгрузки грузовиков, больше кассиров, больше клерков, занимающихся предварительной продажей билетов на самолеты) и потерь от обслуживания на уровне ниже оптимального (грузовики не могут сделать лишнюю остановку из-за задержек под разгрузкой, потребители уходят в другой банк или обращаются к другой авиакомпании из-за медленного обслуживания).
Теория игр - это метод, используемый для оценки влияния какого-либо действия на конкурентов. Моделями теории очередей можно пользоваться в соответствии со спросом на них. Модели управления запасами помогают руководителю синхронизировать размещение заказов на ресурсы и оптимизировать их объемы, а также определять оптимальное для склада количество готовой продукции . Модели линейного программирования позволяют установить оптимальный способ распределения дефицитных ресурсов между конкурирующими потребностями в них. Имитационное моделирование - это использование устройства, которое имитирует реальный мир. В экономическом анализе используется ряд методов для определения экономического положения организации или осуществимости действия с экономической точки зрения.
Настоятельная потребность маркетинга и. предпринимательства в целом в полном и объективном освещении рыночных процессов , в достоверном предсказании возможного развития рынка. Понятие маркетингового исследования , его роль в бизнесе и удовлетворении информационно-аналитических потребностей маркетинга. Место маркетингового исследования в разработке стратегии маркетинга , планировании маркетинга и его контроллинге. Предмет и объекты маркетингового исследования . Цели маркетингового исследования . Принципы маркетингового исследования . Два направления маркетингового исследования формализация и качественные оценки. Достоинства и недостатки каждого из них. Возможности их консолидации. Основы методологии маркетингового исследования . Особая роль статистики и эконометрики в маркетинговых исследованиях . Теория массового обслуживания (теория очередей). Понятие статистического банка (набора статистических приемов обработки информации).
Данный метод также предусматривает разложение проблемы на части и изучение каждой из них. Важным инструментом данного метода является разработка и проигрывание с использованием количественных методов и компьютеров различных моделей решения. Разработаны и используются модели с привлечением системного подхода , исследования операций , теории игр, теории очередей, уп-
В 60-е гг. широко применялась такая техника планирования , как оперативное исследование. Речь идет об использовании научной техники управления для анализа проблемы и оценки возможных решений. Сюда входят теория очередей, игр, имитационное моделирование . Применение той или иной модели в процессе планирования зависит от накопления и анализа объективной информации. Предполагается, что информация должна поступать в каналы управления в достаточном объеме и в нужное время. Это самый ценный актив организации.
К числу важнейших инструментов и методов исследования операций относятся теория вероятности , метод обратных связей , линейное программирование , символическая логика, теория информации и связей, теория очередей, теория игр, теория поисков.
Изложенные обстоятельства позволяют для моделирования науки в регионе использовать математический аппарат теории очередей. Согласно этой теории, науку можно считать системой массового обслуживания (СМО). СМО, как известно, называется любая система, предназначенная для обслуживания каких-либо заявок, поступающих в нее в случайные моменты времени.
Теория очередей позволяет находить вероятности различных состояний СМО, а также устанавливать зависимости между заданными параметрами (числом каналов п, интенсивностью потока заявок Я, распределением времени обслуживания и т.д.) и характеристиками эффективности работы СМО. В качестве таких характеристик могут рассматриваться следующие
Усовершенствуем формулы теории очередей применительно к специфике науки. Условия существования стационарного режима, по мнению автора, будут иметь место при следующих обстоятельствах
Читатель найдет здесь доступное описание основных экономико-математических методов , построенных как на традиционном аппарате математики и логики, известном из школьных программ (дроби, проценты, уравнения, прогрессии, геометрические и логические задачи), так и на основе методов исследования операций - современном математическом аппарате , специально созданном для решения тех задач, с которыми элементарная математика не справляется. Это методы оптимизации (линейное, нелинейное и динамическое программирование), теория вероятностей и математическая статистика , теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), теория игр и статистических решений, сетевое планирование.
Наряду с элементарной математикой и логикой рассматриваются также задачи, требующие применения аппарата высшей математики, особенно в теории вероятностей и математической статистике , а также в таких сравнительно молодых методах, как математическое программирование (линейное, нелинейное, динамическое), теория игр и статистических решений, теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), сетевое планирование.
Если при поступлении очередной заявки все имеющиеся каналы (аппараты) оказываются занятыми, происходит сбой в обслуживании и начинает образовываться очередь. Поэтому теорию массового обслуживания называют также теорией очередей.
Центральным понятием теории очередей является функция стоимости, равная
Если величина N больше 1, вычисления приобретают более сложный характер. Общая формула приведена в Приложении 1, где также обсуждаются другие проблемы теории очередей. Для JV, равных 2 и 3, формулы выглядят следующим образом
В этой главе рассмотрены различные аспекты выбора места и планировки производственных площадей . Сокращение денежных, трудовых, временных и иных затрат возможно на основе определения общей производственной мощности , а для сферы услуг - использования теории очередей (массового обслуживания) для нахождения оптимального баланса между объемом простаивающего оборудования и временем ожидания покупателя в очереди.
В русскоязычной литературе теория очередей иногда называется теорией массового обслуживания.
Применение М. М.-К. можно проиллюстрировать примером из области теории очередей. Предположим, надо определить, как часто и как долго придется ждать покупателям в очереди в магазине при заданной его пропускной способности (допустим, для того, чтобы принять решение , следует ли расширять магазин). Подход покупателей носит случайный характер, распределение времени подхода (так можно назвать промежуток времени между каждыми двумя приходами покупателей) может быть установлено из имеющейся информации. Время обслуживания покупателей тоже носит случайный характер, и его распределение тоже может быть выявлено. Таким образом, имеются два стохастических или случайных процесса , взаимодействие которых и создает очередь.
Следует сказать и о терминах "Т.м.о." и "теория очередей". Во многих работах они трактуются как равнозначные, в других - теория очередей рассматривается лишь как раздел Т.м.о., поскольку последней изучаются системы не только с очередями, но и с отказами (напр., когда телефонная станция занята, очередь абонентов не образуется), а также некоторые иные.
Рыжиков Ю.И. Теория очередей и управление запасами . -СПб. Питер, 2001.-384 с.
Статистика - наука, изучающая массовые явления и процессы, поддающиеся количественному измерению, позволяющая выявлять тенденции и закономерности общественного развития, определять пропорции и оценивать колеблемость. Эконометрия -применение экономико-математических методов анализа , измерение параметров математических выражений, характеризующих определенную социально-экономическую концепцию, моделирование сложных, многомерных процессов и явлений. Достаточно широко в маркетинге используются методы линейного и динамического программирования , приемы теории массового обслуживания (теории очередей), теории принятия решений (теории риска), теории связей (сигнальной информации о процессах, выходящих за пределы установленных параметров). Социометрия - характеристика структуры и функционирования определенных человеческих групп с помощью количественных оценок . Квалиметрия - методология количественных оценок качества товаров . Бихевиоризм - наука о вкусах и предпочтениях людей, которая помогает разобраться в процессах формирования и изме-
Часто бывает, что запросы на обслуживание отдельных клиентов или заказы индивидуальных покупателей продукции поступают в систему случайным образом. Это так называемая проблема случайных клиентов. Единственный путь, который позволяет удовлетворять таких заказчиков, если накопление продукции и ожидание клиентов исключается, это составление внешнеориентированного расписания в сочетании с общим избытком мощности системы (избытком всех ее ресурсов). На практике такое расточительное резервирование встречается редко и поэтому части заказчиков, обращающихся в систему, приходится либо предлагать ожидание, либо отказывать, неся при этом определенные экономические Управление качеством (1974) -- [
Стохастическое моделирование
Ключевые слова: стохастичность, теория очередей, системы массового обслуживания, накопитель, очередь, транзакт
Стохастическое моделирование – это один из видов имитационного моделирования, базирующийся на теории Монте-Карло. Его определение можно представить так:
& Стохастическое моделирование (англ. 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) случайно (например, последовательность регистрации книг, поступивших в одной партии для книжного магазина).
Таким образом, для каждой очереди можно посчитать её среднюю длину; интенсивность поступления и выбытия из очереди; процент заявок, вышедших из системы по истечению срока ожидания; вероятность того, что система будет свободна; вероятность нахождения определённого числа клиентов в системе.
К перечисленным характеристикам добавляется параметр различного приоритета транзактов, что усложняет поведение заявок в системе. Многие процессы, сводимые к теории массового обслуживания, достаточно сложно оценить аналитически. Поэтому имитирование работы подобных систем – рациональный подход для определения характеристик исследуемой предметной области.
Теория массового обслуживания (теория очередей)
Модель теории очередей используется для определения оптимального числа каналов обслуживания по отношению к потребности в них. К ситуациям, в которых модели теории очередей могут быть полезны, можно отнести звонки людей через телефонную станцию, выход в Интернет через провайдера, обслуживание покупателей в магазине или банке, разгрузка грузовиков на транспортном терминале. В любом случае принципиальная проблема заключается в уравновешивании расходов на дополнительные каналы обслуживания (больше оборудования на АТС, больше модемов у провайдера, больше кассиров и клерков, больше людей и техники для разгрузки грузовиков) и потерь от обслуживания на уровне ниже оптимального (потребители обращаются к другой компании, грузовики стоят под разгрузкой вместо использования их по прямому назначению).
Управление запасами
Модели управления запасами используется для определения времени размещения заказов на ресурсы и их количества, а также массы готовой продукции на складах. Любая организация должна поддерживать некоторый уровень запасов во избежание задержек на производстве и в сбыте. Цель данной модели - сведение к минимуму отрицательных последствий накопления запасов, что выражается в определенных издержках.
Поддержание высокого уровня запасов избавляет от потерь, обусловливаемых их нехваткой. Закупка в больших количествах материалов, необходимых для создания запасов, во многих случаях сводит к минимуму издержки на размещение заказов, поскольку фирма может получить соответствующие скидки и снизить объем «бумажной работы». Однако эти потенциальные выгоды перекрываются дополнительными издержками типа расходов на хранение, перегрузку, затрат на страхование, потерь от порчи, воровства и дополнительных налогов. Кроме того, руководство должно учитывать возможность связывания оборотных средств избыточными запасами, что препятствует вложению капитала в приносящие прибыль акции, облигации и др.
Может быть выбрана одна из разновидностей моделей управления запасами: модель с фиксированным количеством, модель с фиксированным временем и др.
Сетевое планирование
Модели сетевого планирования используются при управлении сложными многоэтапными проектами (строительство здания, разработка нового продукта и т.п.) Методы сетевого планирования позволяют оптимизировать выполнение проекта, определить и улучшить характеристики его критических этапов и т.п.
Имитационное моделирование
Все описанные выше модели подразумевают применение имитации в широком смысле, поскольку все они являются заменителями реальности. В узком смысле, имитация состоит в использовании некоего устройства для имитации реальной системы для того, чтобы исследовать и понять ее свойства, поведение и характеристики. Имитация используется в ситуациях, слишком сложных для математически методов типа линейного программирования. Это может быть связано с чрезмерно большим числом переменных, трудностью математического анализа определенных зависимостей между переменными или высоким уровнем неопределенности. Примером может служить метод Монте-Карло .
Экономический анализ
Экономический анализ вбирает в себя почти все методы оценки издержек и экономических выгод, а также относительной рентабельности деятельности предприятия. Типичная экономическая модель основана на анализе безубыточности , методе принятия решений с определением точки (объема производства), в которой общий доход уравнивается с суммарными издержками, т.е. точки, начиная с которой предприятие становится прибыльным. Точка безубыточности (break-even point - BEP) определяется делением постоянных издержек на цену единицы продукции за вычетом переменных издержек на ее изготовление (данная формула может применяться в простейшем линейном случае).
Метод дерева решений
Дерево решений - схематичное представление проблемы принятия решений. Дерево решений дает руководителю возможность учесть различные направления действий, соотнести с ними финансовые результаты, скорректировать их в соответствии с приписанной им вероятностью, а затем сравнить альтернативы.
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
ГОУ ВПО «Уральский Государственный Технический Университет – УПИ»
Теория очередей. Закономерности образования очередей и способы предсказания среднего размера очереди.
По дисциплине: Теория информационных процессов и систем
Екатеринбург, 2007г.
ВВЕДЕНИЕ | |
1. КЛАССИЧЕСКАЯ ЗАДАЧА ЭРЛАНГА | |
1.1. Составление уравнений | |
1.2. Определение стационарного решения | |
1.3. Некоторые подготовительные результаты | |
1.4. Определение функции распределения длительности ожидания | |
1.5. Средняя длительность ожидания | |
2. ПОСТАНОВКА ЗАДАЧИ | |
2.1. Математическая модель | |
2.2. Решение поставленной задачи | |
2.3. Анализ результатов | |
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ |
Введение.
Во многих областях практической деятельности человека мы сталкиваемся с необходимостью пребывания в состоянии ожидания. Подобные ситуации возникают в очередях, в билетных кассах, в крупных аэропортах, при ожидании обслуживающим персоналом самолетов разрешение на взлет или посадку, на телефонных станциях в ожидании освобождения линии абонента, в ремонтных цехах, в ожидании ремонта станков и оборудования, на складах организации в ожидании разгрузки или погрузки транспортных средств.
В теории систем массового обслуживания обслуживаемый объект называют требованием . В общем случае под требованием обычно понимают запрос на удовлетворение некоторой потребности, например, разговор с абонентом, посадка самолета, покупка билета, получение материалов на складе.
Средства, обслуживающие требования, называются обслуживающими устройствами или каналами обслуживания. Например, к ним относятся каналы телефонной связи, посадочные полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.
Системы массового отсчета с ожиданием распространены наиболее широко. Эти системы определяют так же, как системы с ограниченным входящим потоком. Их можно разделить на две группы:
1) Замкнутые - системы, в которых поступающий поток требований ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится в будущем потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
2) Если питающий источник обладает бесконечным числом требований, то системы называются разомкнутыми. Примерами подобных систем могут служить магазины, кассы вокзалов, портов и др. Для этих систем поступающий поток требований можно считать неограниченным.
Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства, (каналы) и выходящий поток требований.
Это можно изобразить так:
https://pandia.ru/text/78/375/images/image001_340.jpg" width="61" height="19">Входящий поток Очередь
Обслуживающие устройства Выходящий поток
Изучение СМО начинается с анализа входящего потока требований. Входящий поток требований представляет собой совокупность требований, которые поступают в систему и нуждаются в обслуживании. Входящий поток требований изучается с целью установления закономерностей этого потока и дальнейшего улучшения качества обслуживания.
В большинстве случаев входящий поток неуправляем и зависит от ряда случайных факторов. Число требований, поступающих в единицу времени, случайная величина. Случайной величиной является также интервал времени между соседними поступающими требованиями. Однако среднее количество требований, поступивших в единицу времени, и средний интервал времени между соседними поступающими требованиями предполагаются заданными.
Среднее число требований, поступающих в систему обслуживания за единицу времени, называется интенсивностью поступления требований и определяется следующим соотношением:
где Т - среднее значение интервала между поступлением очередных требований.
Для многих реальных процессов поток требований достаточно хорошо описывается законом распределения Пуассона. Такой поток называется простейшим.
Простейший поток обладает такими важными свойствами:
1) Свойством стационарности , которое выражает неизменность вероятностного режима потока по времени. Это значит, что число требований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погрузку в среднем в сутки должно быть одинаковым для различных периодов времени, к примеру, в начале и в конце декады.
2) Отсутствия последействия , которое обуславливает взаимную независимость поступления того или иного числа требований на обслуживание в непересекающиеся промежутки времени. Это значит, что число требований, поступающих в данный отрезок времени, не зависит от числа требований, обслуженных в предыдущем промежутке времени. Например, число автомобилей, прибывших за материалами в десятый день месяца, не зависит от числа автомобилей, обслуженных в четвертый или любой другой предыдущий день данного месяца.
3) Свойством ординарности, которое выражает практическую невозможность одновременного поступления двух или более требований (вероятность такого события неизмеримо мала по отношению к рассматриваемому промежутку времени, когда последний устремляется к нулю).
Первые математические работы по системам обслуживания появились в начале двадцатого века. Они были тесно связаны с практическими задачами, касавшимися вопросов обслуживания телефонных линий, определения оптимального количества касс и продавцов в торговых предприятиях, выработки правил расчета запасов в магазинах, достаточных для их бесперебойной работы. Среди этих работ особо важное место занимают исследования датского ученого.
1. Классическая задача Эрланга.
Рассмотрим классическую задачу Эрланга: На m одинаковых приборов поступает простейший поток требований интенсивности l . Если в момент поступления требования имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь поступившее требование становится в очередь за всеми теми требованиями, которые поступили раньше и еще не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживания очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент не более одного требования.
Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x) .
За x берем время (часы, минуты и т. д.).
Предполагается, что при x ³ 0
F(x) = 1 - e- m x
где m > 0 - постоянная.
Эрланг решил эту задачу, имея в виду постановки вопросов возникших к тому времени в телефонном деле.
Выбор распределения вероятностей F(x) для описания деятельности обслуживания произведен не случайно. Дело в том, что в этом предположении задача допускает простое решение, которое с удовлетворительной для практики точности описывает ход интересующего нас процесса. Мы увидим, что распределение вероятностей F(x) играет в теории массового обслуживания исключительную роль, которая в значительной мере вызвана следующим свойством:
При показательном распределении длительности обслуживания распределение деятельности оставшейся части работы по обслуживанию не зависит от того, сколько оно уже продолжалось.
Действительно, пусть fa(t) означает вероятность того, что обслуживание, которое уже продолжается время a , продлится еще не менее чем t . В предположении, что длительность обслуживания распределена показательно, f0(t)=e- m t .
f 0 (a )= e - m a и f 0 (a + t )= e - m (a +1) .
А так как всегда
f0(a+t) = f0(a) fa(t), то e- m (a+t) = e- m a f0(t)
и, следовательно,
fa(t) = e- m t = fo(t).
Требуемое доказано.
Несомненно, что в реальной обстановке показательное время обслуживания является, как правило, лишь грубым приближением к действительности. Так, нередко время обслуживания не может быть меньше, чем некоторая определенная величина. Предположение распределения вероятностей F(x) приводит к тому, что значительная доля требований нуждается лишь в кратковременной операции близкой к 0. Позднее перед нами возникает задача освобождения от излишнего ограничения, накладываемого предположением распределения вероятностей F(x) . Необходимость этого была ясна уже самому Эрлангу, и он в ряде работ делал усилия найти иные удачные распределения для длительности обслуживания. В частности, им было предложено так называемое распределение Эрланга , плотность распределения которого дается формулой
где, m > 0, а k - целое положительное число.
Распределение Эрланга представляет собой распределение суммы k независимых слагаемых, каждое из которых имеет распределение вероятностей F(x)
Обозначим для случая распределения вероятностей F(x) через h время обслуживания требования. Тогда средняя длительность обслуживания равна
Это равенство дает нам способ оценки параметра m по опытным данным. Как легко вычислить, дисперсия длительности обслуживания равна
1. Составление уравнений.
Система с ожиданием в случае простейшего потока и показательного времени обслуживания представляет собой случайный процесс Маркова.
Найдём те уравнения, которым удовлетворяют вероятности Pk(t). Одно из уравнений очевидно, а именно для каждого t
Найдем сначала вероятность того, что в момент t+h все приборы свободны. Это может произойти следующими способами:
В момент t все приборы были свободны и за время h новых требований не поступало;
В момент t один прибор был занят обслуживанием требования, все остальные приборы свободны; за время h обслуживание требования было завершено и новых требований не поступило.
Остальные возможности, как-то: были заняты два или три прибора и за время h работа на них была закончена - имеют вероятность o(h), как легко в этом убедится.
Вероятность первого из указанных событий равна
вероятность второго события
Таким образом,
Отсюда очевидным образом приходим к уравнению
Перейдем теперь к составлению уравнений для Pk(t) при k ³ 1. Рассмотрим отдельно два различных случая:
1) Пусть вначале 1 £ k < m . Перечислим только существенные состояния, из которых можно прийти в состояние Ek в момент t+h . Эти состояния таковы:
В момент t Ek , за время h новых требований не поступило, и ни один прибор не окончил обслуживания. Вероятность этого события равна
В момент t система находилась в состоянии Ek-1 , за время h поступило новое требование, но ни одно ранее находившееся требование не было закончено обслуживанием. Вероятность этого события равна
В момент t система находилась в состоянии Ek+1 , за время h новых требований не поступило, но одно требование было обслужено. Вероятность этого равна
Все остальные мыслимые возможности перехода в состояние Ek за промежуток времени h имеют вероятность, равную 0(h).
Собрав воедино найденные вероятности, получаем следующее
равенство:
Несложные преобразования приводят нас к такому уравнению
для 1 £ k < m:
2) Подобные же рассуждения для k ³ m приводят к уравнению
Для определения вероятностей Pk(t) мы получили бесконечную систему дифференциальных уравнений. Ее решение представляет несомненные технические трудности.
2. Определение стационарного решения.
В теории массового обслуживания обычно изучают лишь установившееся решение для t ® ¥ . Существование таких решений устанавливается так называемыми эргодическими теоремами. В рассматриваемой задаче оказывается, что предельные или, как говорят обычно, стационарные вероятности существуют. Введем для них обозначения Pk . Заметим, что при t ® ¥ .
Сказанное позволяет заключить, что уравнения
для стационарных вероятностей принимают следующий вид:
при 1 £ k < m
при k ³ m
К этим уравнениям добавляется нормирующее условие
Для решения полученной бесконечной алгебраической системы введем обозначения:
при 1 £ k < m
при k ³ m
Система уравнений в этих обозначениях принимает такой вид:
z1 = 0, zk - zk+1 = 0 при k ³ 1
Отсюда заключается, что при всех k ³ 1 zk = 0
т. е. при 1 £ k < m
k m Pk = l Pk-1
и при k ³ m
m m Pk= l Pk-1
Введем для удобства записи обозначение
r = l / m .
Уравнение k m Pk = l Pk-1 позволяет заключить, что при 1 £ k < m
При k ³ m из уравнения m m Pk= l Pk-1 находим, что
и следовательно, при k ³ m
Остается найти P0. Для этого в подставляем выражения полученного Pk.
В результате
Так бесконечная сумма, стоящая в квадратных скобках, находится только при условии, что
r < m
то при этом положении находим равенство
Если условие r < m не выполнено, т. е. если r ³ m, то ряд, стоящий в квадратной скобке уравнения для определения P0 , расходится и, значит, P0 должно быть равно 0..gif" width="71" height="44 src=">при всех k ³ 1 оказывается Pk = 0.
Методы теории цепей Маркова позволяют заключить, что при r ³ m с течением времени очередь стремится к ¥ по вероятности.
3. Некоторые подготовительные результаты.
Для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания. Длительность ожидания представляет собой случайную величину, которую обозначим буквой g . Рассмотрим сейчас только задачу определения распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания. Обозначим далее через P { g > t } вероятность того, что длительность ожидания превзойдет t, и через Pk { g > t } вероятность неравенства, указанного в скобке, при условии, что в момент поступления требования, в очереди уже находится k требований. В силу формулы полной вероятности имеем равенство
P { g > t } = .
Прежде чем преобразовать эту формулу к виду, удобному для пользования, приготовим некоторые необходимые нам для дальнейшего сведения.
Вычислим теперь вероятность того, что все приборы будут заняты в какой-то наудачу взятый момент. Очевидно, что эта вероятность равна
4. Определение функции распределения длительности ожидания.
Если в момент поступления требования в очереди уже находились k - m требований, то поскольку обслуживание происходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены
k – m + 1 требований.
Пусть qs(t) означает вероятность того, что за промежуток времени длительности t после поступления интересующего нас требования закончилось обслуживание ровно S требований. Ясно, что k ³ m имеет место равенство
Так как распределение длительности обслуживания предположено показательным и независящим ни от того, сколько требований находится в очереди, ни от того, как велики длительности обслуживания других требований, то вероятность за время t не завершить ни одного обслуживания (т. е. вероятность того, что не освободится ни один из приборов) равна
Если все приборы заняты обслуживанием и еще имеется достаточная очередь требований, которые ожидают обслуживания, то поток обслуженных требований будет простейшим. Действительно, в этом случае все три условия - стационарность, отсутствие последействия и ординарность - выполнены. Вероятность освобождения за промежуток времени t ровно s приборов равна (это можно показать и простым подсчетом)
и, следовательно,
Но вероятности Pk известны:
очевидными преобразованиями приводим правую часть последнего равенства к виду
Из формул и 
следует, что , поэтому при t>0
.
Само собой разумеется, что при t<0 .
Функция имеет в точке t = 0 разрыв непрерывности, равный вероятности застать все приборы занятыми.
5. Средняя длительность ожидания.
Формула позволяет находить все интересующие нас числовые характеристики длительности ожидания. В частности, математическое ожидание длительности ожидания начала обслуживания или, как предпочитают говорить, средняя длительность ожидания равна
Несложные вычисления приводят к формуле
Дисперсия величины g равна
.
Формула дает среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшими в систему обслуживания в течение промежутка времени T . За время T в систему поступает l T требований в среднем; общая потеря ими времени на ожидание в среднем равна
Приведем небольшие арифметические подсчеты, которые продемонстрируют нам, как быстро возрастают суммарные потери времени па ожидание с изменением величины . При этом мы ограничиваемся случаем Т=1 и рассматриваем лишь самые малые значения т: т = 1 и т = 2.
При т=1 в силу (20)
При р = 0,1; 0,3; 0,5; 0,9 значение приблизительно равно 0,011; 0,267; 0,500; 1,633; 8,100.
При m = 2 в силу (24)
При = 0,1; 1,0; 1,5; 1,9 значение приблизительно равно 00003; 0,333; 1,350; 17,537.
Приведённые данные иллюстрируют хорошо известный факт относительно большой чувствительности систем обслуживания, уже достаточно сильно загруженных, к возрастанию загрузки. Потребитель при этом сразу ощущает значительное возрастание длительности ожидания. Этот факт обязательно следует учитывать при расчёте загрузки оборудования в системах массового обслуживания.
Постановка задачи.
На станции технического обслуживания (СТО) легковых автомобилей имеется 7 рабочих мест по обслуживанию клиентов. По статистическим данным в час поступает 2 заявки на обслуживания легковых автомобилей. Среднее время обслуживания 1 заявки составляет 3 часа 24 минуты.
Если поступивший клиент застает на СТО весь рабочий персонал занятым, то он встает в очередь и ждет до тех пор, пока не освободится рабочее место.
Каждый мастер, в любой момент времени, может обслуживать не более одного клиента. Обслуженный клиент покидает СТО.
Проанализировать структуру и процесс обслуживания СТО. Для этого требуется разработать показатели эффективности систем массового обслуживания. Например, требуется знать: вероятность того, что занято или свободно k приборов; распределение вероятностей свободных или занятых приборов от обслуживания; вероятность того, что в очереди находится заданное число требований; вероятность того, что время ожидания в очереди превысит заданное. К показателям, характеризующих эффективное функционирование системы в среднем, относятся: средняя длина очереди; среднее число занятых приборов; коэффициент загрузки системы.
1. Математическая модель.
Имеем систему массового обслуживания, из n = 7 идентичных приборов, на которую поступает поток требований α = 2, интенсивностью β = 0,29411(1/ч).
При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:
вероятность DIV_ADBLOCK171">
где https://pandia.ru/text/78/375/images/image057_47.gif" width="231 height=25" height="25">
где https://pandia.ru/text/78/375/images/image059_45.gif" width="15 height=28" height="28">.gif" width="716 height=299" height="299">
Рис.1. Требование в системе.
Пусть D t – достаточно малый промежуток времени. Вероятность того, что в СМО за время D t не поступит ни одного требования:
Вероятность того, что в СМО за время Dt поступит одно требование:
Вероятность того, что за время Dt в СМО поступит два или более требований:
Вероятность того, что за время Dt требование будет обслужено:
Вероятность того, что за время Dt будет обслужено два или более требования:
Вероятность того, что за время Dt будет обслужено одно из к требований, находящихся в системе, найдем следующим образом:
Https://pandia.ru/text/78/375/images/image069_37.gif" width="381 height=48" height="48">;
Очередей теория
раздел массового обслуживания теории (См. Массового обслуживания теория). О. т. изучает системы, в которых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке (часто с предоставлением приоритета определённым категориям требований). Выводы О. т. используют для рационального планирования систем массового обслуживания. С математической точки зрения задачи О. т. могут быть включены в теорию случайных процессов (См. Случайный процесс), а ответы часто бывают выражены в терминах Лапласа преобразований (См.
Лапласа преобразование)
искомых характеристик. Применение методов О. т. необходимо даже в простейших случаях для правильного понимания статистических закономерностей, возникающих в системах массового обслуживания. Пример. Пусть имеется один обслуживающий прибор, на который поступает случайный поток требований. Если в момент поступления требования прибор свободен, то оно сразу начинает обслуживаться. В противном случае оно становится в очередь и прибор обслуживает требования одно за другим в порядке их поступления. Пусть а -
среднее число требований, поступающих за время одного обслуживания, а
Т - длительность периода занятости, то есть промежутка времени от момента занятия прибора каким-либо требованием, заставшим прибор свободным, до первого момента полного освобождения прибора. О. т. показывает, что при естественных допущениях математическое ожидание Т
равно m
= 1/(1 - а), а дисперсия равна (1 + a
) m 3
(так, при а =
0,8 соответствующие значения равны 5 и 225). Таким образом, для «хорошо загруженного» обслуживающего прибора (то есть при а, близких к 1) среднее значение m
случайной величины Т
является весьма ненадёжной характеристикой Т.
Лит.:
Гнеденко Б. В., Коваленко И. Н., Введение в теорию массового обслуживания, М., 1966; Приоритетные системы обслуживания, М., 1973. Ю. В. Прохоров.
Большая советская энциклопедия. - М.: Советская энциклопедия . 1969-1978 .
- Очанка
- Очередные задачи советской власти
Смотреть что такое "Очередей теория" в других словарях:
ОЧЕРЕДЕЙ ТЕОРИЯ - в математике раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают ее освобождения и затем обслуживаются в том или ином порядке … Большой Энциклопедический словарь
очередей теория - (матем.), раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке. * * * ОЧЕРЕДЕЙ ТЕОРИЯ ОЧЕРЕДЕЙ ТЕОРИЯ, в… … Энциклопедический словарь
ОЧЕРЕДЕЙ ТЕОРИЯ - см. Массового обслуживания теория … Большой энциклопедический политехнический словарь
ОЧЕРЕДЕЙ ТЕОРИЯ - раздел массового обслуживания теории. О. т. изучает системы, в к рых требования, застающие систему занятой, не теряются, а ожидают ее освобождения и затем обслуживаются в том или ином порядке (часто с предоставлением приоритета определенным… … Математическая энциклопедия
ОЧЕРЕДЕЙ ТЕОРИЯ - (матем.), раздел теории массового обслуживания, где изучаются системы, в к рых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке … Естествознание. Энциклопедический словарь
Теория массового обслуживания - (теория очередей) раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие… … Википедия
теория массового обслуживания - — теория массового обслуживания Раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других… … Справочник технического переводчика
Теория массового обслуживания
Теория массового обслуживания - раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других областях как процессы обслуживания, т.е. удовлетворения каких… … Экономико-математический словарь
Теория очередей - см. Теория массового обслуживания … Экономико-математический словарь
Книги
- Логистика и теория очередей
- Логистика и теория очередей , Рыжиков Ю.И.. В учебном пособии рассматривается современное состояние теории логистики, обсуждаются элементы математической модели управления запасами и основы численных методов теории очередей;…