Модели систем массового обслуживания (СМО). · среднее число заявок в СМО
Большой класс систем, которые сложно изучить аналитическими способами, но которые хорошо изучаются методами статистического моделирования, сводится к системам массового обслуживания (СМО).
В СМО подразумевается, что есть типовые пути (каналы обслуживания), через которые в процессе обработки проходятзаявки . Принято говорить, что заявкиобслуживаются каналами. Каналы могут быть разными по назначению, характеристикам, они могут сочетаться в разных комбинациях; заявки могут находиться в очередях и ожидать обслуживания. Часть заявок может быть обслужена каналами, а части могут отказать в этом. Важно, что заявки, с точки зрения системы, абстрактны: это то, что желает обслужиться, то есть пройти определенный путь в системе. Каналы являются также абстракцией: это то, что обслуживает заявки.
Заявки могут приходить неравномерно, каналы могут обслуживать разные заявки за разное время и так далее, количество заявок всегда весьма велико. Все это делает такие системы сложными для изучения и управления, и проследить все причинно-следственные связи в них не представляется возможным. Поэтому принято представление о том, что обслуживание в сложных системах носит случайный характер.
Примерами СМО (см. табл. 30.1) могут служить: автобусный маршрут и перевозка пассажиров; производственный конвейер по обработке деталей; влетающая на чужую территорию эскадрилья самолетов, которая «обслуживается» зенитками ПВО; ствол и рожок автомата, которые «обслуживают» патроны; электрические заряды, перемещающиеся в некотором устройстве и т. д.
Таблица 30.1. Примеры систем массового обслуживания |
||||||||||||||||||
|
Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых, с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.
К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 30.1, но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 - но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.
Результат (например, пропускная способность системы), конечно, тоже будет случайной величиной на отдельных промежутках времени. Но измеренная на большом промежутке времени, эта величина будет уже, в среднем, соответствовать точному решению. То есть для характеристики СМО интересуются ответами в статистическом смысле.
Итак, систему испытывают случайными входными сигналами, подчиненными заданному статистическому закону, а в качестве результата принимают статистические показатели, усредненные по времени рассмотрения или по количеству опытов. Ранее, в лекции 21 (см.рис. 21.1 ), мы уже разработали схему для такого статистического эксперимента (см. рис. 30.2).
Во-вторых, все модели СМО собираются типовым образом из небольшого набора элементов (канал, источник заявок, очередь, заявка, дисциплина обслуживания, стек, кольцо и так далее), что позволяет имитировать эти задачи типовым образом. Для этого модель системы собирают из конструктора таких элементов. Неважно, какая конкретно система изучается, важно, что схема системы собирается из одних и тех же элементов. Разумеется, структура схемы будет всегда различной.
Перечислим некоторые основные понятия СМО.
Каналы - то, что обслуживает; бывают горячие (начинают обслуживать заявку в момент ее поступления в канал) и холодные (каналу для начала обслуживания требуется время на подготовку). Источники заявок - порождают заявки в случайные моменты времени, согласно заданному пользователем статистическому закону. Заявки, они же клиенты, входят в систему (порождаются источниками заявок), проходят через ее элементы (обслуживаются), покидают ее обслуженными или неудовлетворенными. Бывают нетерпеливые заявки - такие, которым надоело ожидать или находиться в системе и которые покидают по собственной воле СМО. Заявки образуют потоки - поток заявок на входе системы, поток обслуженных заявок, поток отказанных заявок. Поток характеризуется количеством заявок определенного сорта, наблюдаемым в некотором месте СМО за единицу времени (час, сутки, месяц), то есть поток есть величина статистическая.
Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out - первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out - последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример - патроны в рожке автомата). SF (Short Forward - короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.
Дадим яркий пример, показывающий, как правильный выбор той или иной дисциплины обслуживания позволяет получить ощутимую экономию по времени.
Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 30.3).
Время обслуживания t обслуж. на рис. 30.3 показывает, сколько времени продавец затратит на обслуживание одного покупателя. Понятно, что при покупке штучного товара продавец затратит меньше времени на обслуживание, чем при покупке, скажем, сыпучих продуктов, требующих дополнительных манипуляций (набрать, взвесить, высчитать цену и т. п). Время ожидания t ожид. показывает, через какое время очередной покупатель будет обслужен продавцом.
В магазине № 2 реализована дисциплина SF (см. рис. 30.4), означающая, что штучный товар можно купить вне очереди, так как время обслуживания t обслуж. такой покупки невелико.
Как видно из обоих рисунков, последний (пятый) покупатель собирается приобрести штучный товар, поэтому время его обслуживания невелико - 0.5 минут. Если этот покупатель придет в магазин № 1, он будет вынужден выстоять в очереди целых 8 минут, в то время как в магазине № 2 его обслужат сразу же, вне очереди. Таким образом, среднее время обслуживания каждого из покупателей в магазине с дисциплиной обслуживания FIFO составит 4 минуты, а в магазине с дисциплиной обслуживания КВ - лишь 2.8 минуты. А общественная польза, экономия времени составит: (1 – 2.8/4) · 100% = 30 процентов! Итак, 30% сэкономленного для общества времени - и это лишь за счет правильного выбора дисциплины обслуживания.
Специалист по системам должен хорошо понимать ресурсы производительности и эффективности проектируемых им систем, скрытые в оптимизации параметров, структур и дисциплинах обслуживания. Моделирование помогает выявить эти скрытые резервы .
При анализе результатов моделирования важно также указать интересы и степень их выполнения. Различают интересы клиента и интересы владельца системы. Заметим, что эти интересы совпадают не всегда.
Судить о результатах работы СМО можно по показателям. Наиболее популярные из них:
вероятность обслуживания клиента системой;
пропускная способность системы;
вероятность отказа клиенту в обслуживании;
вероятность занятости каждого из канала и всех вместе;
среднее время занятости каждого канала;
вероятность занятости всех каналов;
среднее количество занятых каналов;
вероятность простоя каждого канала;
вероятность простоя всей системы;
среднее количество заявок, стоящих в очереди;
среднее время ожидания заявки в очереди;
среднее время обслуживания заявки;
среднее время нахождения заявки в системе.
Судить о качестве полученной системы нужно по совокупности значений показателей. При анализе результатов моделирования (показателей) важно также обращать внимание на интересы клиента и интересы владельца системы, то есть минимизировать или максимизировать надо тот или иной показатель, а также на степень их выполнения. Заметим, что чаще всего интересы клиента и владельца между собой не совпадают или совпадают не всегда. Показатели будем обозначать далее H = { h 1 , h 2 , …} .
Параметрами СМО могут быть: интенсивность потока заявок, интенсивность потока обслуживания, среднее время, в течение которого заявка готова ожидать обслуживания в очереди, количество каналов обслуживания, дисциплина обслуживания и так далее. Параметры - это то, что влияет на показатели системы. Параметры будем обозначать далее как R = { r 1 , r 2 , …} .
Пример. Автозаправочная станция (АЗС).
1. Постановка задачи . На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.
На АЗС две одинаковые колонки, статистическая производительность каждой из которых известна. Первая колонка в среднем обслуживает 1 машину в час, вторая в среднем - 3 машины в час. Владелец АЗС заасфальтировал для машин место, где они могут ожидать обслуживания. Если колонки заняты, то на этом месте могут ожидать обслуживания другие машины, но не более двух одновременно. Очередь будем считать общей. Как только одна из колонок освободится, то первая машина из очереди может занять ее место на колонке (при этом вторая машина продвигается на первое место в очереди). Если появляется третья машина, а все места (их два) в очереди заняты, то ей отказывают в обслуживании, так как стоять на дороге запрещено (см. дорожные знаки около АЗС). Такая машина уезжает прочь из системы навсегда и как потенциальный клиент является потерянной для владельца АЗС. Можно усложнить задачу, рассмотрев кассу (еще один канал обслуживания, куда надо попасть после обслуживания в одной из колонок) и очередь к ней и так далее. Но в простейшем варианте очевидно, что пути движения потоков заявок по СМО можно изобразить в виде эквивалентной схемы, а добавив значения и обозначения характеристик каждого элемента СМО, получаем окончательно схему, изображенную на рис. 30.6.
2. Метод исследования СМО . Применим в нашем примере принцип последовательной проводки заявок (подробно о принципах моделирования см.лекцию 32 ). Его идея заключается в том, что заявку проводят через всю систему от входа до выхода, и только после этого берутся за моделирование следующей заявки.
Для наглядности построим временную диаграмму работы СМО, отражая на каждой линейке (ось времени t ) состояние отдельного элемента системы. Временных линеек проводится столько, сколько имеется различных мест в СМО, потоков. В нашем примере их 7 (поток заявок, поток ожидания на первом месте в очереди, поток ожидания на втором месте в очереди, поток обслуживания в канале 1, поток обслуживания в канале 2, поток обслуженных системой заявок, поток отказанных заявок).
Для генерации времени прихода заявок используем формулу вычисления интервала между моментами прихода двух случайных событий (см. лекцию 28 ):
В этой формуле величина потока λ должна быть задана (до этого она должна быть определена экспериментально на объекте как статистическое среднее), r - случайное равномерно распределенное число от 0 до 1 из ГСЧ илитаблицы , в которой случайные числа нужно брать подряд (не выбирая специально).
Задача. Сгенерируйте поток из 10 случайных событий с интенсивностью появления событий 5 шт/час.
Решение задачи. Возьмем случайные числа, равномерно распределенные в интервале от 0 до 1 (см. таблицу ), и вычислим их натуральные логарифмы (см. табл. 30.2).
Таблица 30.2. Фрагмент таблицы случайных чисел и их логарифмов |
||||||||||
|
Формула пуассоновского потока определяет расстояние между двумя случайными событиями следующим образом: t = –Ln(r рр)/ λ . Тогда, учитывая, что λ = 5 , имеем расстояния между двумя случайными соседними событиями: 0.68, 0.21, 0.31, 0.12 часа. То есть события наступают: первое - в момент времени t = 0 , второе - в момент времени t = 0.68 , третье - в момент времени t = 0.89 , четвертое - в момент времени t = 1.20 , пятое - в момент времени t = 1.32 и так далее. События - приход заявок отразим на первой линейке (см. рис. 30.7).
|
||
Рис. 30.7. Временная диаграмма работы СМО |
Берется первая заявка и, так как в этот момент каналы свободны, устанавливается на обслуживание в первый канал. Заявка 1 переносится на линейку «1 канал».
Время обслуживания в канале тоже случайное и вычисляется по аналогичной формуле:
где роль интенсивности играет величина потока обслуживания μ 1 или μ 2 , в зависимости от того, какой канал обслуживает заявку. Находим на диаграмме момент окончания обслуживания, откладывая сгенерированное время обслуживания от момента начала обслуживания, и опускаем заявку на линейку «Обслуженные».
Заявка прошла в СМО весь путь. Теперь можно, согласно принципу последовательной проводки заявок, также проимитировать путь второй заявки.
Если в некоторый момент окажется, что оба канала заняты, то следует установить заявку в очередь. На рис. 30.7 это заявка с номером 3. Заметим, что по условиям задачи в очереди в отличие от каналов заявки находятся не случайное время, а ожидают, когда освободится какой-то из каналов. После освобождения канала заявка поднимается на линейку соответствующего канала и там организуется ее обслуживание.
Если все места в очереди в момент, когда придет очередная заявка, будут заняты, то заявку следует отправить на линейку «Отказанные». На рис. 30.7 это заявка с номером 6.
Процедуру имитации обслуживания заявок продолжают некоторое время наблюдения T н. Чем больше это время, тем точнее в дальнейшем будут результаты моделирования. Реально для простых систем выбирают T н, равное 50-100 и более часов, хотя иногда лучше мерить эту величину количеством рассмотренных заявок.
ВВЕДЕНИЕ
ГЛАВА I. ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ
1.1 Общие понятие теории массового обслуживания
1.2 Моделирование систем массового обслуживания
1.3 Графы состояний СМО
1.4 Случайные процессы
Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
2.1 Уравнения Колмогорова
2.2 Процессы «рождения – гибели»
2.3 Экономико-математическая постановка задач массового обслуживания
Глава III. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
3.1 Одноканальная СМО с отказами в обслуживании
3.2 Многоканальная СМО с отказами в обслуживании
3.3 Модель многофазной системы обслуживания туристов
3.4 Одноканальная СМО с ограниченной длиной очереди
3.5 Одноканальная СМО с неограниченной очередью
3.6 Многоканальная СМО с ограниченной длиной очереди
3.7 Многоканальная СМО с неограниченной очередью
3.8 Анализ системы массового обслуживания супермаркета
ЗАКЛЮЧЕНИЕ
Введение
В настоящее время появилось большое количество литературы, посвященной непосредственно теории массового обслуживания, развитию ее математических аспектов, а также различных сфер ее приложения - военной, медицинской, транспортной, торговле, авиации и др.
Теория массового обслуживания опирается на теорию вероятностей и математическую статистику. Первоначальное развитие теории массового обслуживания связано с именем датского ученого А.К. Эрланга(1878-1929),с его трудами в области проектирования и эксплуатации телефонных станций.
Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.
Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами. Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого, варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и от простоев каналов обслуживания.
В коммерческой деятельности применение теории массового обслуживания пока не нашло желаемого распространения.
В основном это связано с трудностью постановки задач, необходимостью глубокого понимания содержания коммерческой деятельности, а также надежного и точного инструментария, позволяющего просчитывать в коммерческой деятельности различные варианты последствий управленческих решений.
Глава I . Постановка задач массового обслуживание
1.1 Общие понятие теории массового обслуживания
Природа массового обслуживания, в различных сферах, весьма тонка и сложна. Коммерческая деятельность связана с выполнением множества операций на этапах движения, например товарной массы из сферы производства в сферу потребления. Такими операциями являются погрузка товаров, перевозка, разгрузка, хранение, обработка, фасовка, реализация. Кроме таких основных операций процесс движения товаров сопровождается большим количеством предварительных, подготовительных, сопутствующих, параллельных и последующих операций с платежными документами, тарой, деньгами, автомашинами, клиентами и т.п.
Для перечисленных фрагментов коммерческой деятельности характерны массовость поступления товаров, денег, посетителей в случайные моменты времени, затем их последовательное обслуживание (удовлетворение требований, запросов, заявок) путем выполнения соответствующих операций, время выполнения которых носит также случайный характер. Все это создает неравномерность в работе, порождает недогрузки, простой и перегрузки в коммерческих операциях. Много неприятностей доставляют очереди, например, посетителей в кафе, столовых, ресторанах, или водителей автомобилей на товарных базах, ожидающих разгрузки, погрузки или оформления документов. В связи с этим возникают задачи анализа существующих вариантов выполнения всей совокупности операций, например, торгового зала супермаркета, ресторана или в цехах производства собственной продукции для целей оценки их работы, выявления слабых звеньев и резервов для разработки в конечном итоге рекомендаций, направленных на увеличение эффективности коммерческой деятельности.
Кроме того, возникают другие задачи, связанные с созданием, организацией и планированием нового экономичного, рационального варианта выполнения множества операций в пределах торгового зала, кондитерского цеха, всех звеньев обслуживания ресторана, кафе, столовой, планового отдела, бухгалтерии, отдела кадров и др.
Задачи организации массового обслуживания возникают практически во всех сферах человеческой деятельности, например обслуживание продавцами покупателей в магазинах, обслуживание посетителей на предприятиях общественного питания, обслуживание клиентов на предприятиях бытового обслуживания, обеспечение телефонных разговоров на телефонной станции, оказание медицинской помощи больным в поликлинике и т.д. Во всех приведенных примерах возникает необходимость в удовлетворении запросов большого числа потребителей.
Перечисленные задачи можно успешно решать с помощью методов и моделей специально созданной для этих целей теории массового обслуживания (ТМО). В этой теории поясняется, что обслуживать необходимо кого-либо или что-либо, что определяется понятием «заявка (требование) на обслуживание», а операции обслуживания выполняются кем-либо или чем-либо, называемыми каналами (узлами) обслуживания. Роль заявок в коммерческой деятельности выполняют товары, посетители, деньги, ревизоры, документы, а роль каналов обслуживания - продавцы, администраторы, повара, кондитеры, официанты, кассиры, товароведы, грузчики, торговое оборудование и др. Важно заметить, что в одном варианте, например, повар в процессе приготовления блюд является каналом обслуживания, а в другом - выступает в роли заявки на обслуживание, например к заведующему производством за получением товара.
Заявки в силу массовости поступления на обслуживание образуют потоки, которые до выполнения операций обслуживания называются входящими, а после возможного ожидания начала обслуживания, т.е. простоя в очереди, образуют потоки обслуживания в каналах, а затем формируется выходящий поток заявок. В целом совокупность элементов входящего потока заявок, очереди, каналов обслуживания и выходящего потока заявок образует простейшую одноканальную систему массового обслуживания - СМО.
Под системой понимается совокупность взаимосвязанных и. целенаправленно взаимодействующих частей (элементов). Примерами таких простейших СМО в коммерческой деятельности являются места приема и обработки товаров, узлы расчета с покупателями в магазинах, кафе, столовых, рабочие места экономист та, бухгалтера, коммерсанта, повара на раздаче и т.д.
Процедура обслуживания считается завершенной, когда заявка на обслуживание покидает систему. Продолжительность интервала времени, требуемого для реализации процедуры обслуживания, зависит в основном от характера запроса заявки на обслуживание, состояния самой обслуживающей системы и канала обслуживания.
Действительно, продолжительность пребывания покупателя в супермаркете зависит, с одной стороны, от личностных качеств покупателя, его запросов, от ассортимента товаров, который он собирается приобрести, а с другой - от формы организации обслуживания и обслуживающего персонала, что может значительно повлиять на время пребывания покупателя в супермаркете и интенсивность обслуживания. Например, овладение кассирами-контролерами работы «слепым» методом на кассовом аппарате позволило увеличить пропускную способность узлов расчета в 1,3 раза и сэкономить время, затрачиваемое на расчеты с покупателями по каждой кассе более чем на 1,5 ч в день. Внедрение единого узла расчета в супермаркете дает ощутимые преимущества покупателю. Так, если при традиционной форме расчетов время обслуживания одного покупателя составляло в среднем 1,5 мин, то при введении единого узла расчета - 67 с. Из них 44 с уходят на оформление покупки в секции и 23 с непосредственно на расчеты за покупки. Если покупатель делает несколько покупок в разных секциях, то потери времени сокращаются при приобретении двух покупок в 1,4 раза, трех - в 1,9, пяти - в 2,9 раза.
Под обслуживанием заявок будем понимать процесс удовлетворения потребности. Обслуживание имеет различный характер по своей природе. Однако, во всех примерах поступившие заявки нуждаются в обслуживании со стороны какого-либо устройства. В некоторых случаях обслуживание производится одним человеком (обслуживание покупателя одним продавцом, в некоторых - группой людей (обслуживание больного врачебной комиссией в поликлинике), а в некоторых случаях - техническими устройствами (продажа газированной воды, бутербродов автоматами). Совокупность средств, которые осуществляют обслуживание заявок, называется каналом обслуживания.
Если каналы обслуживания способны удовлетворить одинаковые заявки, то каналы обслуживания называются однородными. Совокупность однородных каналов обслуживания называется обслуживающей системой.
В систему массового обслуживания поступает большое количество заявок в случайные моменты времени, длительность обслуживания которых также является случайной величиной. Последовательное поступление заявок в систему обслуживания называется входящим потоком заявок, а последовательность заявок, покидающих систему обслуживания,- выходящим потоком.
Аналитическое исследование систем массового обслуживания (СМО) является подходом, альтернативным имитационному моделированию, и состоит в получении формул для расчета выходных параметров СМО с последующей подстановкой значений аргументов в эти формулы в каждом отдельном эксперименте.
В моделях СМО рассматривают следующие объекты:
1) заявки на обслуживание (транзакты);
2) обслуживающие аппараты (ОА), или приборы.
Практическая задача теории массового обслуживания связана с исследованием операций этими объектами и состоит из отдельных элементов, на которые влияют случайные факторы.
В качестве примера задач, рассматриваемых в теории массового обслуживания, можно привести: согласование пропускной способности источника сообщения с каналом передачи данных, анализ оптимального потока городского транспорта, расчет емкости зала ожидания для пассажиров в аэропорту и пр.
Заявка может находиться либо в состоянии обслуживания, либо в состоянии ожидания обслуживания.
Обслуживающий прибор может быть либо занят обслуживанием, либо свободен.
Состояние СМО характеризуется совокупностью состояний обслуживающих приборов и заявок. Смена состояний в СМО называется – событие.
Модели СМО используются для исследования процессов происходящие в системе, при подаче на входы потоков заявок. Эти процессы представляют собой последовательность событий.
Важнейшие выходные параметры СМО
Производительность
Пропускная способность
Вероятность отказа в обслуживании
Среднее время обслуживания;
Коэффициент загрузки оборудования (ОА).
Заявками могут быть заказы на производство изделий, задачи, решаемые в вычислительной системе, клиенты в банках, грузы, поступающие на транспортировку и др. Очевидно, что параметры заявок, поступающих в систему, являются случайными величинами и при исследовании или проектировании могут быть известны лишь их законы распределения.
В связи с этим анализ функционирования на системном уровне, как правило, носит статистический характер. В качестве математического аппарата моделирования удобно принять теорию массового обслуживания, а в качестве моделей систем на этом уровне использовать системы массового обслуживания.
Простейшие модели СМО
В простейшем случае СМО представляет собой некоторое устройство, называемое обслуживающим аппаратом (ОА), с очередями заявок на входах.
М о д е л ьо б с л у ж и в а н и я с о т к а з а м и (рис.5.1)
Рис. 5.1. Модель СМО с отказами:
0 – источник заявок;
1 – обслуживающий прибор;
а – входной поток заявок на обслуживание;
в – выходной поток обслуженных заявок;
с – выходной поток необслуженных заявок.
В этой модели отсутствует накопитель заявок на входе ОА. Если заявка приходит от источника 0 в момент времени, когда ОА занят обслуживанием предыдущей заявки, то вновь пришедшая заявка выходит из системы (так как ей отказано в обслуживании) и теряется (поток с ).
М о д е л ь о б с л у ж и в а н и я с о ж и д а н и е м (рис. 5.2)
Рис. 5.2. Модель СМО с ожиданием
(N– 1) – количество заявок, которое может поместиться в накопителе
В этой модели имеется накопитель заявок на входе ОА. Если заявка приходит от источника 0 в момент времени, когда ОА занят обслуживанием предыдущей заявки, то вновь пришедшая заявка попадает в накопитель, где неограниченно долго ожидает, пока освободится ОА.
М о д е л ь о б с л у ж и в а н и я с о г р а н и ч е н н ы м в р е м е н е м
о ж и д а н и я (рис. 5.3)
Рис. 5.4. Многоканальная модель СМО с отказами:
n – количество одинаковых обслуживающих аппаратов (приборов)
В этой модели имеется не один ОА, а несколько. Заявки, если это специально не оговорено, могут поступать к любому свободному от обслуживания ОА. Накопителя нет, поэтому данная модель включает свойства модели, показанной на рис. 5.1: отказ в обслуживании заявки означает ее безвозвратную потерю (это происходит только в том случае, если в момент прихода этой заявки все ОА заняты).
в р е м е н е м о ж и д а н и я (рис. 5.5)
Рис. 5.6. Многоканальная модельСМО с ожиданием и восстановлением ОА:
e – обслуживающие аппараты, вышедшие из строя;
f – восстановленные обслуживающие аппараты
Данная модель обладает свойствами моделей, представленных на рис. 5.2 и 5.4, а кроме того свойствами, позволяющими учитывать возможные случайные отказы ОА, которые в этом случае поступают в ремонтный блок 2, где пребывают в течение случайных промежутков времени, затрачиваемых на их восстановление, а затем вновь возвращаются в обслуживающий блок 1.
М н о г о к а н а л ь н а я м о д е л ь СМО с о г р а н и ч е н н ы м
в р е м е н е м о ж и д а н и я и в о с с т а н о в л е н и е м ОА (рис. 5.7)
Рис. 5.7. Многоканальная модель СМО с ограниченным временем ожидания и восстановлением ОА
Данная модель является довольно сложной, поскольку одновременно учитывает свойства двух не самых простых моделей (рис. 5.5 и 5.6).
Допущения о пуассоновском характере потока заявок и о показательном распределении времени обслуживания позволяют применить в теории массового обслуживания аппарат марковских. Процесс, протекающий в физической системе, называется марковским (или процессом без последействия), если для каждого момента времени вероятность любого состояния системы в будущем зависит только от состояния системы в настоящий моменти не зависит от того, каким образом система пришла в это состояние.
Рассмотрим СМО с конечным дискретным множеством состояний (рис. 2.). Определим состояние как состояние СМО, соответствующее наличию в данный моментзанятых каналов. При этом система может изменять свое состояниедискретно в соответствующие дискретные моменты времени. При поступлении на вход СМО одной заявки система изменяет свое состояние сна,
а при уходе одной заявки из системы и соответствующем освобождении одного канала - с на.
Рис. 2. Диаграмма состояний и переходов СМО
Типичным примером СМО является телекоммуникационная система с несколькими обслуживающими серверами. Заявка, поступающая на вход такой СМО, может быть либо обслужена, либо поставлена в очередь, либо получить отказ в обслуживании. В связи с этим СМО делятся на два основных типа: а) СМО с отказами; б) СМО с ожиданием.
В системах с отказами заявка, поступившая в момент, когда все каналы обслуживания заняты, немедленно получает отказ, покидает систему и в дальнейшем процессе обслуживания не участвует.
В системах с ожиданием заявка, заставшая все каналы занятыми, не покидает систему, а становится в очередь и ожидает, пока не освободится какой-нибудь канал.
Классификационные признаки систем массового обслуживания.
В системах массового обслуживания различают три основных этапа, которые проходит каждая заявка:
1) появление заявки на входе в систему;
2) прохождение очереди;
3) процесс обслуживания, после которого заявка покидает систему.
На каждом этапе используются определенные характеристики, которые следует обсудить прежде, чем строить математические модели.
Характеристики входа:
1) число заявок на входе (размер популяции);
2) режим поступления заявок в систему обслуживания;
3) поведение клиентов.
Число заявок на входе. Число потенциально возможных заявок (размер популяции) может считаться либо бесконечным (неограниченная популяция), либо конечным (ограниченная популяция). Если число заявок, поступивших на вход системы с момента начала процесса обслуживания до любого заданного момента времени, является лишь малой частью потенциально возможного числа клиентов, популяция на входе рассматривается как Неограниченная. Примеры неограниченных популяций: автомобили, проходящие через пропускные пункты на скоростных дорогах, покупатели в супермаркете и т. п. В большинстве моделей очередей на входе рассматриваются именно неограниченные популяции.
Если количество заявок, которые могут поступить в систему, сравнимо с числом заявок, уже находящихся в системе массового обслуживания, популяция считается Ограниченной. Пример ограниченной популяции: компьютеры, принадлежащие конкретной организации и поступающие на обслуживание в ремонтную мастерскую.
Режим поступления заявок, в систему обслуживания. Заявки могут поступать в систему обслуживания в соответствии с определенным графиком (например, один пациент на прием к стоматологу каждые 15 мин, один автомобиль на конвейере каждые 20 мин) или случайным образом. Появления клиентов считаются Случайными, если они независимы друг от друга и точно непредсказуемы. Часто в задачах массового обслуживания число появлений в единицу времени может быть оценено с помощью пуассоновского распределения вероятностей. При заданном темпе поступления (например, два клиента в час или четыре грузовика в минуту)
дискретное распределение Пуассона описывается следующей формулой:
Где Р (х) - вероятность поступления Х заявок в единицу времени;
Х - число заявок в единицу времени;
L - среднее число заявок в единицу времени (темп поступления заявок);
Е = 2,7182 - основание натурального логарифма.
Соответствующие значения вероятностей Р(х) нетрудно определить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок - два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки - около 0,27, двух - также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре - с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или более, близка нулю.
На практике вероятности появления заявок, разумеется, не всегда подчиняются пуассоновскому распределению (они могут иметь какое-то другое распределение). Поэтому требуется проводить предварительные исследования для того, чтобы проверить, что пуассоновское распределение может служить хорошей аппроксимацией.
Поведение клиентов. Большинство моделей очередей основывается на предположении, что поведение клиентов является стандартным, т. е. каждая поступающая в систему заявка встает в очередь, дожидается обслуживания и не покидает систему до тех пор, пока ее не обслужат. Другими словами, клиент (человек или машина), вставший в очередь, ждет до тех пор, пока он не будет обслужен, не покидает очередь и не переходит из одной очереди в другую.
Жизнь значительно сложнее. На практике клиенты могут покинуть очередь
потому, что она оказалась слишком длинной. Может возникнуть и другая ситуация: клиенты дожидаются своей очереди, но по каким-то причинам уходят необслуженными. Эти случаи также являются предметом теории массового обслуживания.
Характеристики очереди:
2) правило обслуживания.
Длина очереди. Длина может быть ограничена либо не ограничена. Длина очереди (очередь) Ограничена, если она по каким-либо причинам (например, из-за физических ограничений) не может увеличиваться до бесконечности. Если очередь достигает своего максимального размера, то следующая заявка в систему не допускается и происходит отказ. Длина очереди не ограничена, Если в очереди может находиться любое число заявок. Например, очередь автомобилей на бензозаправке.
Правило обслуживания. Большинство реальных систем использует правило «первым пришел - первым ушел» (FIFO - first in, first out). В некоторых случаях, например в приемном покое больницы, в дополнение к этому правилу могут устанавливаться различные приоритеты. Пациент с инфарктом в критическом состоянии, по-видимому, будет иметь приоритет в обслуживании по сравнению с пациентом, сломавшим палец. Порядок запуска компьютерных программ - другой пример установления приоритетов в обслуживании.
Классификация, основные понятия, элементы модели, расчет основных характеристик.
При решении задач рациональной организации торговли, бытового обслуживания, складского хозяйства и т.д. весьма полезной бывает интерпретация деятельности производственной структуры как системы массового обслуживания , т.е. системы в которой, с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой - происходит постоянное удовлетворение этих запросов.
Всякая СМО включает четыре элемента : входящий поток, очередь, обслуживающее устройство, выходящий поток.
Требованием (клиентом, заявкой) в СМО называется каждый отдельный запрос на выполнение какой-либо работы.
Обслуживание - это выполнение работы по удовлетворению поступившего требования. Объект, выполняющий обслуживание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.
Временем обслуживания называется период, в течение которого удовлетворяется требование на обслуживание, т.е. период от начала обслуживания и до его завершения. Период от момента поступления требования в систему и до начала обслуживания называется временем ожидания обслуживания. Время ожидания обслуживания в совокупности с временем обслуживания составляет время пребывания требования в системе.
СМО классифицируются по разным признакам .
1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.
2. В зависимости от условий ожидания требованием начала обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.
В СМО с потерями требования , поступившие в момент, когда все приборы заняты обслуживанием, получают отказ, они теряются для данной системы и никакого влияния на дальнейший процесс обслуживания не оказывают. Классическим примером системы с отказами является телефонная станция - требование на соединение получает отказ, если вызываемый абонент занят.
Для системы с отказами основной характеристикой эффективности функционирования является вероятность отказа или средняя доля заявок, оставшихся необслуженными.
В СМО с ожиданием требования , поступившее в момент, когда все приборы заняты обслуживанием, не покидает систему, а становится в очередь и ожидает пока не освободится один из каналов. При освобождении очередного прибора одна из заявок, стоящих в очереди, немедленно принимается на обслуживание.
Для СМО с ожиданием основными характеристиками являются математические ожидания длины очереди и времени ожидания.
Примером системы с ожиданием может служить процесс восстановления телевизоров в ремонтной мастерской.
Встречаются системы, лежащие между указанными двумя группами (смешанные СМО ). Для них характерно наличие некоторых промежуточных условий: ограничениями могут быть ограничения по времени ожидания начала обслуживания, по длине очереди и т.п.
В качестве характеристик эффективности может применяться вероятность отказа как в системах с потерями (или характеристики времени ожидания) и в системах с ожиданием.
3. По дисциплине обслуживания СМО делятся на системы с приоритетом в обслуживании и на системы без приоритета в обслуживании.
Требования могут обслуживаться в порядке их поступления либо случайным образом, либо в зависимости от установленных приоритетов.
4. СМО могут быть однофазными и многофазными.
В однофазных системах требования обслуживаются каналами одного типа (например рабочими одной профессии) без передачи их от одного канала к другому, в многофазных системах такие передачи возможны.
5. По месту нахождения источника требований СМО делятся на разомкнутые (когда источник требования находится вне системы) и замкнутые (когда источник находится в самой системе).
К замкнутым относятся системы, в которых поступающий поток требований ограничен. Например, мастер, задачей которого является наладка станков в цехе, должен периодически их обслуживать. Каждый налаженный станок становится в будущем потенциальным источником требований на наладку. В подобных системах общее число циркулирующих требований конечно и чаще всего постоянно.
Если питающий источник обладает бесконечным числом требований, то системы называются разомкнутыми . Примерами подобных систем могут служить магазины, кассы вокзалов, портов и т.п. Для этих систем поступающий поток требований можно считать неограниченным.
Методы и модели исследования СМО можно условно разбить на аналитические и статистические (имитационного моделирования процессов массового обслуживания).
Аналитические методы позволяют получить характеристики системы как некоторые функции от параметров ее функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО.
К сожалению, аналитическому решению поддается лишь довольно ограниченный круг задач теории массового обслуживания. Несмотря на постоянно ведущуюся разработку аналитических методов, во многих реальных случаях аналитическое решение либо невозможно получить, либо итоговые зависимости оказываются настолько сложными, что их анализ становится самостоятельной трудной задачей. Поэтому ради возможности применения аналитических методов решения приходится прибегать к различным упрощающим предположениям, что в некоторой степени компенсируется возможностью применения качественного анализа итоговых зависимостей (при этом, разумеется, необходимо, чтобы принятые допущения не искажали реальной картины процесса).
В настоящее время теоретически наиболее разработаны и удобны в практических приложениях методы решения таких задач массового обслуживания, в которых поток требований является простейшим (пуассоновским ).
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t, равное k требований задается формулой:
где λ - параметр потока (см. ниже).
Простейший поток обладает тремя основными свойствами: ординарностью, стационарностью и отсутствием последействия.
Ординарность потока означает практическую невозможность одновременного поступления двух и более требований. Например, достаточно малой является вероятность того, что из группы станков, обслуживаемых бригадой ремонтников, одновременно выйдут из строя несколько станков.
Стационарным называется поток , для которого математическое ожидание числа требований, поступающих в систему в единицу времени (обозначим через λ), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества требований в течение заданного промежутка времени Δt зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за время t + Δt.
Например, если на ткацком станке в данный момент произошел обрыв нити, и он устранен ткачихой, то это не определяет того, произойдет новый обрыв на данном станке в следующий момент или нет, тем более это не влияет на вероятность возникновения обрыва на других станках.
Важной характеристикой СМО является время обслуживания требований в системе. Время обслуживания является, как правило, случайной величиной и, следовательно, может быть описано законом распределения. Наибольшее распространение в теории и, особенно в практических приложениях, получил экспоненциальный закон. Для этого закона функция распределения вероятностей имеет вид:
F(t) = 1 – e -μt ,
т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой (1 – e -μt), где μ -параметр экспоненциального закона времени обслуживания требований в системе - величина, обратная среднему времени обслуживания, т.е. .
Рассмотрим аналитические модели СМО с ожиданием (наиболее распространенные СМО, в которых требования, поступившие в момент, когда все обслуживающие единицы заняты, становятся в очередь и обслуживаются по мере освобождения обслуживающих единиц).
Задачи с очередями являются типичными в производственных условиях, например при организации наладочных и ремонтных работ, при многостаночном обслуживании и т.д.
Постановка задачи в общем виде выглядит следующим образом.
Система состоит из n обслуживающих каналов. Каждый из них может одновременно обслуживать только одно требование. В систему поступает простейший (пуассоновский) поток требований с параметром λ. Если в момент поступления очередного требования в системе на обслуживании уже находится не меньше n требований (т.е. все каналы заняты), то это требование становится в очередь и ждет начала обслуживания.
Время обслуживания каждого требования t об является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром μ.
Как отмечалось выше, СМО с ожиданием можно разбить на две большие группы: замкнутые и разомкнутые.
Особенности функционирования каждой из этих двух видов систем накладывают свой оттенок на используемый математический аппарат. Расчет характеристик работы СМО различного вида может быть проведен на основе расчета вероятностей состояний СМО (формулы Эрланга).
Поскольку система замкнутая, то к постановке задачи следует добавить условие: поток поступающих требований ограничен, т.е. в системе обслуживания одновременно не может находиться больше m требований (m - число обслуживаемых объектов).
В качестве основных критериев, характеризующих качество функционирования рассматриваемой системы, выберем: 1) отношение средней длины очереди к наибольшему числу требований, находящихся одновременно в обслуживающей системе -коэффициент простоя обслуживаемого объекта; 2) отношение среднего числа незанятых обслуживающих каналов к их общему числу - коэффициент простоя обслуживаемого канала.
Рассмотрим расчет необходимых вероятностных характеристик (показателей качества функционирования) замкнутой СМО.
1. Вероятность того, что в системе находится k требований при условии, когда их число не превышает числа обслуживающих аппаратов n:
P k = α k P 0 , (1 ≤ k ≤ n),
где
λ - частота (интенсивность) поступления требований в систему от одного источника;
Средняя продолжительность обслуживания одного требования;
m - наибольшее возможное число требований, находящихся в обслуживающей системе одновременно;
n - число обслуживающих аппаратов;
Р 0 - вероятность того, что все обслуживающие аппараты свободны.
2. Вероятность того, что в системе находится k требований при условии, когда их число больше числа обслуживающих аппаратов:
P k = α k P 0 , (n ≤ k ≤ m),
где
3. Вероятность того, что все обслуживающие аппараты свободны, определяется из условия
следовательно,
4. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди):
5. Коэффициент простоя требования в ожидании обслуживания:
6. Вероятность того, что все обслуживающие аппараты заняты:
7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания):
8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:
9. Среднее время простоя требования в очереди на обслуживание:
10. Среднее число свободных обслуживающих аппаратов:
11. Коэффициент простоя обслуживающих аппаратов:
12. Вероятность того, что число требований, ожидающих обслуживания, больше некоторого числа В (вероятность того, что в очереди на обслуживание находится более В требований):