Элементы теории массового обслуживания
Предметом исследования в теории массового обслуживания (ТМО) являются вероятностные модели систем обслуживания разного рода, в которых в случайные моменты времени возникают заявки на обслуживание и имеются устройства, обеспечивающие выполнение этих заявок.
На первичное развитие теории массового обслуживания особое влияние оказали работы известного датского ученого А. К. Эрланга — сотрудника Копенгагенской телефонной компании, который заложил основы математической теории телефонных сообщений и получил широко используемые в настоящее время в теории телетрафика формулы для расчета потерь и времени ожидания в коммутационных системах.
Задача Эрланга является классическим примером задачи массового обслуживания. Поэтому приведем ее.
Пусть обслуживающая система состоит из п обслуживающих устройств. Входящий поток — простейший с параметром X. Заявка обслуживается на любом свободном обслуживающем устройстве и теряется, если в момент ее поступления таковых нет. Время обслуживания произвольной заявки л. — случайная величина с непрерывной функцией распределения Мц = ц.
где рп можно интерпретировать как вероятность потери требования в произвольно взятый момент времени.
В дальнейшем оказалось, что задачи типа телефонных возникают в самых разнообразных направлениях: в вычислительной технике, экономике, транспорте, военном деле, организации производства.
Термин "теория массового обслуживания" ввел советский математик А. Я. Хинчин. В иностранных источниках чаще используется термин "теория очередей" (theory of queues).
А. Я. Хинчин сыграл огромную роль в развитии этой теории. Его книга "Математические методы теории массового обслуживания" явилась первым трудом, в котором строго были сформулированы идеи и методы теории систем массового обслуживания. Большой вклад по дальнейшему развитию идей и методов внес академик Б. В. Гнеденко со своими учениками.
Теория массового обслуживания применяется в различных областях, таких как: обслуживание рабочим или группой рабочих нескольких станков; организация обслуживания абонентов на телефонной станции; организация обслуживания пассажиров на железнодорожном, водном и авиационном транспорте; ремонт машин и профилактическое обслуживание в масштабе большого автохозяйства; обработка информации в сложных управляющих и вычислительных системах; математическое моделирование и организация всевозможных систем военного назначения; медицинское обслуживание и др.
Идею метода удобно пояснить на упрощенном примере.
Пример
Предположим, что известно число поступающих ] ia ремонт приборов в среднем в год (для конкретизации примера примем v = 120 шт/год). Известно также, что один сотрудник цеха (не будем пока различать их по квалификации) может отремонтировать один прибор в среднем за полмесяца (т = 0.5 мес. = 1 /24 года). Варьировать в этой задаче можно число требуемых для выполнения ремонтных работ данного вида сотрудников: например, определить, сколько сотрудников должно одновременно находиться в штате лаборатории (цеха) и при необходимости одновременно выполнять ремонтные работы, чтобы не задерживать поступившие на ремонт приборы более чем полмесяца, т.е. ровно столько, сколько требуется в среднем времени на выполнение ремонтных работ.
Попытавшись применить для решения этой задачи аналитические представления, можно рассуждать только так: если нужно отремонтировать 120 приборов, а на ремонт одного прибора одним человеком затрачивается 0,5 мес., то, чтобы не задерживать прибор в лаборатории больше чем планируемые полмесяца, нужно иметь в штате 120 сотрудников, которым нужно поручить ремонт всех поступивших приборов.
Маловероятно, чтобы все 120 приборов, поступающих в среднем на ремонт в год, были бы сданы в ремонт в один день или хотя бы в принятый дискретный интервал — 0,5 мес.
Если применить для решения задачи элементы теории массового обслуживания, использующей статистические представления, то можно получить другое решение.
Предположим, что поступление приборов в ремонт подчиняется закону Пуассона (рис. 3.5):
где /. — математическое ожидание, или среднее значение случайной величины: этому же значению в законе Пуассона равна и дисперсия случайной величины, т.е. X = тх=а, V плотность потока, т.е. среднее число поступающих на ремонт приборов в год, т — среднее время обслуживания, т.е. в данном случае среднее время ремонта одного прибора одним сотрудником, е = 2,7.
Рис. 3.5
Тогда X = 120 х 1/124 = 5, т.е. если поток запросов подчиняется закону Пуассона, то одновременно па ремонт могут поступать 1,2, но не более пяти приборов (математическое ожидание числа поступающих приборов равно 5).
Используя график плотности вероятностей распределения Пуассона при X = 5. приведенный на рис. 3.5 (вместо того, чтобы проводить подсчеты по формуле (3.10)), можно определить, с какой вероятностью цех будет справляться с задачей не задерживать приборы более 0,5 мес., если в цехе будет всего пять сотрудников, т.е. столько, сколько ожидается запросов в течение каждых полумесяцев:
Таким образом, если в цехе будет пять сотрудников, занимающихся ремонтом приборов данного вида, то он будет справляться с задачей с вероятностью 0,6, т.е. будет возвращать отремонтированные приборы через обещанные полмесяца немногим более чем с 50%-й гарантией.
Если желательно увеличить вероятность выполнения ремонтных работ в отведенные сроки, то следует увеличить число сотрудников. Например, при увеличении их числа до 9 цех будет справляться с задачей с вероятностью
Р =Р + Рч + ... + Рэ = 0>03 + 0,08 + 0,14 + 0,175 + 0,175 + 0,15 + 0.1 + + 0,07 + 0,03 = 0,95.
Очевидно, что для того чтобы вероятность выполнения поставленной цели стала равной единице, т.е. для получения абсолютно достоверного результата, потребовалось бы увеличить число сотрудников до 120 (как и рекомендовал нам аналитический подход).
При практическом применении рассматриваемого метода необходимо доказывать правомерность применения выбранного статистического распределения путем предварительного обследования потока приборов, т.е. учета предшествующего опыта. Конечно, это требует определенной подготовительной работы. Но в условиях автоматизированного хранения и поиска информации такая работа становится реально выполнимой. А для проведения расчетов при применении теории массового обслуживания в математическом обеспечении есть соответствующий пакет прикладных программ.
Предмет ТМО — системы массового обслуживания (СМО) и сети массового обслуживания. Под СМО понимают динамическую систему, предназначенную для эффективного обслуживания случайного потока заявок при ограниченных ресурсах системы. Обобщенная структура СМО приведена на рис. 3.6.
Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа / (г= 1, М) обозначена Х-г Совокупность заявок всех типов — входящий поток СМО.
Обслуживание заявок выполняется т каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа ) считаются известными функции распределения т^-,(т) длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов является неопределенным назначение этих заявок па данный канал.
Рис. 3.6
В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем. Например, потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий па сборочном конвейере цеха, заявки на обработку информации ЭВМ от удаленных терминалов и т.д. При этом характерным для работы таких объектов является случайное поведение заявок (требований) па обслуживание и завершение обслуживания в случайные моменты времени.
Модель системы со структурным принципом управления представляет собой совокупность моделей элементов и их функциональные взаимосвязи. Модель элемента (агрегата, обслуживающего прибора) — это в первую очередь набор правил (алгоритмов) поведения устройства по отношению к выходным воздействиям (заявкам) и правил изменений состояний элемента. Элемент отображает функциональное устройство на том или ином уровне детализации. К правилам поведения устройства относятся правила выборки заявок из очереди; реакция устройства на поступление заявки, когда устройство занято или к нему имеется очередь заявок; реакция устройства на возникновение отказа в процессе обслуживания заявки и некоторые другие.
В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. На каждый элемент прибора обслуживания поступают потоки событий
Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС (ОПС) характеризуется только моментами поступления этих событий (вызывающими моментами) и задается последовательностью {t„}={0 < t < £2 ••• ^ tn< ...}, где tn — момент поступления и-го события — неотрицательное вещественное число. ОПС может быть также задай в виде последовательности промежутков времени между п-м яп- 1-м событиями {хп}. Неоднородным ПС называется последовательность {tn, где t„ — вызывающие моменты; fn — набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.
Для оценки адекватности и качества обслуживания в зависимости от вида и назначения системы могут применяться те или иные показатели.
Для систем, представленных в виде моделей СМО с потерями, одной из важнейших характеристик является вероятность потери требования. Для систем без потерь (с неограниченным ожиданием) весьма важными показателями качества обслуживания являются: среднее число требований в очереди, среднее число требований в системе, среднее время ожидания требований в системе, среднее время пребывания требования в системе, коэффициент загрузки обслуживающей системы и др.
Основной задачей анализа системы массового обслуживания является отыскание функциональных зависимостей выбранных показателей качества обслуживания от характеристик потока, параметров, характеризующих обслуживающую систему, от правила формирования очереди и дисциплины обслуживания и др. Методы анализа систем массового обслуживания представлены двумя классами: 1) аналитические; 2) имитационные.
Аналитические методы исследования СМО связаны с разработкой теории большого числа классов случайных процессов: марковских, полумарковских, регенерирующих, процессов восстановления, линейчатых марковских процессов и др. Эти классы процессов служат моделями процессов обслуживания в системах СМО с различного рода структурными, алгоритмическими и временными особенностями. Самым распространенным в практических приложениях является класс марковских случайных процессов (процессов без последействия), в которых описываются СМО с простейшими потоками требований на входе и экспоненциальным законом обслуживания в каналах.
Различные аспекты теории СМО освещены во многих книгах, как строго математических, так и прикладного характера.
Из отечественной литературы но теории СМО следует отметить монографию Б. В. Гнеденко и И. Н. Коваленко, учебное пособие Г. И. Ивченко, В. А. Каштанова и И. И. Коваленко.
Развитию приложений теории массового обслуживания во многом способствовало изложение ее основ в известном учебнике Е. С. Вентцель "Исследование операций" и учебном пособии Л. Л. Денисова, Д. Н. Колесникова "Теория больших систем управления", а также в книгах Л. А. Овчарова "Прикладные задачи теории массового обслуживания", В. Я. Розенберга и А. И. Прохорова "Что такое теория массового обслуживания".
Из мировой литературы обобщающего характера по теории СМО следует отметить работы Л. Клейнрока и А. Кофмана и Р. Крюона.
Несмотря на все разнообразия аналитических подходов, возможности их строгого применения ограничены для разрешения многих задач организации производства, автоматизации управления, математической экономики и системного анализа. Поэтому существенную роль в задачах анализа играют имитационные методы.
Имитационной моделью (ИМ) системы массового обслуживания называются машинные программы или алгоритмы, позволяющие имитировать на ЭВМ поведение системы и ее отдельных компонентов и связей между ними в течение заданного времени моделирования.
Метод ИМ заключается в создании логико-аналитической (математической модели системы и внешних воздействий), имитации функционирования системы, т.е. в определении временных изменений состояния системы под влиянием внешних воздействий и в изучении выборок значений выходных параметров, по которым определяются их основные вероятностные характеристики.
Данное определение справедливо для стохастических систем. При исследовании детерминированных систем отпадает необходимость изучения выборок значений выходных параметров.
Имитационное моделирование (ИМ) — это метод исследования, который основан на том, что анализируемая динамическая система заменяется имитатором и с ним производятся эксперименты для получения сведений об изучаемой системе. Роль имитатора зачастую выполняет программа ЭВМ.
Имитационное моделирование СМО обычно проходит следующие основные этапы: формулировку проблемы и цели имитации; построение математической модели; выбор способа имитации; алгоритмизацию математических моделей в рамках выбранного способа имитации; программирование модели; отладку, тестирование, проверку адекватности ИМ; планирование экспериментов; проведение экспериментов и обработку результатов.
Для реализации имитационного моделирования существуют различные алгоритмы: по принципу особых состояний (в приведенном примере), по принципу постоянного приращения модельного времени (принцип Д£) и др.
Программирование моделей может проводиться как с использованием универсальных языков программирования (УЯП), так и с использованием языков имитационного моделирования (ЯИМ) и языков общего назначения (см. классификацию ЯИМ и ЯОН в приложении 2).
При разработке ИМ на практике отдается предпочтение специализированным ЯИМ в силу ряда их преимуществ: простота изучения, удобство программирования, концептуальная выразительность, надежность компилятора, автоматизация сбора, обработки и представления результатов моделирования; возможность подключения модулей, написанных на универсальных языках программирования. Хотя следует также отметить, что ЯИМ не всегда обеспечивают необходимую гибкость и быстродействие ИМ.
Многообразие ЯИМ (сейчас их более 500) вызвано применением ИМ в различных предметных областях. Принимая во внимание дискретный характер моделей СМО, наиболее распространенные ЯИМ в практических приложениях -SIMSCRIPT, SIMULA, GPSS (GPSSV, GPSS/H).
Общетеоретические вопросы построения имитационных моделей СМО представлены в обширной монографической и учебной литературе. Значительный вклад в применение метода имитационного моделирования к решению задач массового обслуживания внесли Р. Шеннон, H. П. Бусленко, А. Я. Хинчин.
Особенности и возможности применения статистических представлений
Основной принципиальной особенностью статистических представлений по сравнению с аналитическими методами является то, что при их применении на основе выборочного исследования получают статистические закономерности и распространяют их на поведение системы в целом с какой-то вероятностью. Последнее весьма существенно учитывать.
Возможность распространения результатов, полученных на основе исследования выборки, на поведение системы в целом зависит от репрезентативности выборки. При определении репрезентативной выборки необходимо учитывать ее качественные и количественные характеристики.
При определении выборки и проведении статистического исследования применяют свойства эргодичности, т.е. взаимозаменяемости объема выборки в текущий период (в этом случае нужно учитывать закон больших чисел или теорему Бернулли) и объема выборки, взятой за достаточно длительный период времени.
На базе статистических представлений возникли и развиваются ряд прикладных направлений: статистическая радиотехника, статистическая теория распознавания образов, экономическая статистика, теория массового обслуживания; а также развившиеся из направлений, возникших на базе аналитических представлений, — стохастическое программирование, новые разделы теории игр и т.п.
Расширение возможностей отображения сложных систем и процессов по сравнению с аналитическими методами можно объяснить тем, что при применении статистических представлений процесс постановки задачи как бы частично заменяется статистическими исследованиями, позволяющими, не выявляя все детерминированные связи между изучаемыми объектами (событиями) или учитываемыми компонентами сложной системы, на основе выборочного исследования получать статистические закономерности и распространять их на поведение системы в целом с какой-то вероятностью.
В то же время не всегда может быть определена репрезентативная выборка, доказана правомерность применения полученных на ее основе статистических закономерностей. Если не удается доказать репрезентативность выборки или для этого требуется недопустимо большое время, то применение статистических методов может привести к неверным результатам. В таких случаях целесообразно обратиться к методам, объединяемым под общим названием — методы дискретной математики, которые помогают разрабатывать языки моделирования, модели и методики постепенной формализации процесса принятия решения. Однако не всегда можно получить статистические закономерности, не всегда может быть определена репрезентативная выборка, доказана правомерность применения статистических закономерностей. Если же не удается доказать репрезентативность выборки или для этого требуется недопустимо большое время, то применение статистических методов может привести к неверным результатам.
