Математическая теория массового обслуживания в транспортных процессах

Лекция 3. Математическая теория массового обслуживания в транспортных процессах 3.1. Марковские системы массового обслуживания (одноканальные и многоканальные, с бесконечной очередью и отказами). 3.2 Оптимизация систем массового обслуживания. Теория массового обслуживания является одним из разделов теории вероятностей. В последние годы она получила развитие и выделилась в самостоятельный раздел математики. Основоположником теории массового обслуживания является датский ученый А.К. Эрланг. Его первая работа по этому вопросу была опубликована в 1909 году. Идеи и методы теории массового обслуживания в настоящее время получают широкое распространение на автомобильном транспорте. Используя теорию массового обслуживания, можно находить оптимальные и близкие к оптимальным решения таких практических задач, как определение числа постов погрузки, выгрузки и технического обслуживания, оптимизация процесса заправки автомобилей топливом, определение величины резерва подвижного состава, выбор количества подвижного состава, обслуживание населения автомобилями-такси и другие. Термин массовое обслуживание означает, что речь идет не о конкретном объекте, а о совокупности объектов, потребности которых требуется удовлетворить. Системы массового обслуживания (СМО) – это системы, предназначенные для обслуживания потока заявок (требований). Особенностью теории массового обслуживания является то, что она рассматривает любой процесс массового обслуживания как вероятностный. Теория массового обслуживания занимается изучением таких транспортных процессов, в которых возникают очереди на обслуживание. Причинами возникновения очередей являются случайно изменяющиеся потребности в обслуживании, вызываемые, например, неравномерным прибытием автомобилей на погрузку–выгрузку; ограниченностью мощности погрузо-разгрузочных постов; неравномерным прибытием автомобилей на заправку топливом, на станцию технического обслуживания и ограниченностью мощности постов обслуживания; прибытие такси по вызову; подход пассажиров к остановкам городского транспорта; прибытие транспортных средств к пассажирским остановкам и так далее. С помощью теории массового обслуживания решаются задачи оптимизации вышеуказанных процессов. Общая модель системы массового обслуживания состоит из обслуживаемой и обслуживающей систем. Обслуживаемая система включает совокупность источников требований и входящего потока требований. Требование – это запрос на выполнение работы (погрузки-выгрузки, заправки топливом, ремонта, посадки в транспорт для поездки и другие). Источник требований – это объект (диспетчер, водитель, пассажир, механизм и так далее), который может послать в обслуживающую систему только одно требование. Носитель требований, например водитель, автомобиль или агрегат, которому могут понадобиться услуги, запасные части, житель города, которому понадобилось свободное такси. Требования и его носитель часто отождествляются. Требования от всех источников в обслуживающую систему образуют входящий поток требований. Обслуживающая система состоит из накопителя и механизма обслуживания. Требования поступают в накопитель, где ожидают начала обслуживания, если есть очередь, или обслуживаются сразу. Обслуживанием считается удовлетворение поступившего запроса на выполнение услуги. Механизм обслуживания состоит из нескольких обслуживающих аппаратов. Обслуживающий аппарат – это часть механизма обслуживания, способная удовлетворить только одно требование. После окончания обслуживания требования покидают систему, образуя выходящий поток требований. Для применения теории массового обслуживания нужно изучать и анализировать фактические данные. Практическая цель применения теории – это предсказание поведения системы при ее будущей работе еще до того, как система создана, то есть на стадии проектирования системы. Основной базовой величиной в теории обслуживания является поток требований на обслуживание. Для рассматриваемых автотранспортных процессов потоки в большинстве случаев принимаются стационарными (не зависящими от начала отсчета времени, а зависящими только от его продолжительности), ординарными (когда в любой момент времени поступает только одно требование) и потоками без последствий (не зависящими от количества ранее поступивших требований). Такие потоки называются простейшими. Работа погрузочно-разгрузочных постов, постов на станциях технического обслуживания, на топливо - заправочных пунктах, обслуживающих подвижной состав, относится к разомкнутым системам. В таких системах отсутствует связь между обслуженным требованием и требованиями, поступившими на обслуживание. В соответствии с поведением требований системы подразделяются на три группы: 1. Система с отказами, в которых требование, заставшее обслуживающие аппараты занятыми, получает отказ и теряется. Например, автомобиль уезжает со станции технического обслуживания, если посты заняты; 2. Система с ожиданиями, например, автомобиль ожидает погрузки; 3. Смешанные системы, например, часть автомобилей уезжает с автозапра- вочной станции, если очередь на заправку велика. Теория массового обслуживания позволяет определить оптимальный характер функционирования системы массового обслуживания по характеристикам ее частей. Процесс работы системы массового обслуживания представляет собой случайный процесс с дискретными состояниями и непрерывным временем. Это означает, что состояние системы массового обслуживания меняется скачком в случайные моменты времени появления каких-то событий (например, прихода новой заявки, окончания обслуживания и т.п.). Случайный характер потока заявок и времени их обслуживания обусловливает неравномерность загрузки СМО: на входе могут накапливаться необслуженные заявки (перегрузка СМО) либо заявок нет или их меньше, чем свободных каналов (недогрузка СМО). Для обозначения простых СМО используется символика, предложенная Кендаллом: a / b / c / d / e a – распределение моментов поступления заявок на обслуживание; b – распределение времени обслуживания (или выбытия обслуженных заявок); c – число параллельно функционирующих обслуживающих приборов; d – максимальное число допускаемых в систему требований (число требований в очереди + число требований, принятых на обслуживание); e – емкость источника, генерирующего заявки на обслуживание. Различают следующие типы СМО:  Система самообслуживания M /M /  Система с отказами M /M / 1/1  Системы массового обслуживания с ожиданием одноканальная система M /M / 1  Система с конечной очередью M /M / 1/ N  Многоканальная система M /M / c  Многоканальная система с отказами M /M / c / N Существуют следующие операционные характеристики СМО: – вероятность того, что в системе находится n заявок на обслуживание; – среднее число находящихся в системе заявок на обслуживание; – среднее число заявок, находящихся в очереди; – средняя продолжительность пребывания заявки в обслуживающей системе; – средняя продолжительность пребывания заявки в очереди на обслуживание; – часть потока клиентов, которая обслуживается в системе; – часть потока клиентов, которая получает отказ в обслуживании; c – количество обслуживающих приборов. Формулы для расчета операционных характеристик зависят от типа СМО. Случайный процесс, протекающий в системе S с дискретными состояниями s1, s2,…, sn,…, называется марковским, если для любого момента времени t0 вероятность каждого из состояний системы в будущем (при t > t0 ) зависит только от ее состояния в настоящем (при t = t0 ) и не зависит от того, когда и как она пришла в это состояние, т. е. не зависит от ее поведения в прошлом (при t < t0 ). Переходы системы S из состояния в состояние происходят под воздействием потоков событий (например, поток требований, поток отказов, поток восстановлений и т.д.); как только произошло первое после момента t0 событие, осуществляется переход из состояния в состояние. В теории массового обслуживания широкое распространение имеет специальный класс случайных процессов, так называемые процессы гибели и размножения. Название этого процесса связано с рядом биологических задач, где он является математической моделью изменения численности биологических популяций. При анализе численности популяции ее увеличение возможно вследствие рождения одного члена, а уменьшение – вследствие гибели. Уравнения Колмогорова для процессов гибели и размножения Сформулируем правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности i-го состояния. В правой части – сумма произведений вероятностей всех состояний (из которых идут стрелки в данное состояние) на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i- го состояния). Система самообслуживания М\М\∞ Система с отказами М /М /1/1 Рассмотрим модель СМО с отказами, в которой имеется один обслуживающий прибор, но в очереди находится лишь одно место, т.е. если клиент приходит и видит, что прибор занят, то он уходит необслуженным. В данной системе возможны два состояния – когда в системе находится одно требование и когда его нет. Система с конечной очередью M /M /1/ N Разница между этой моделью и рассмотренной выше заключается только в том, что максимальное число требований, допускаемых в систему, ограничено N (т.е. максимальное число требований в очереди N-1 и одно требование на обслуживании). Это означает, что при наличии в системе N требований ни одна из дополнительных заявок на обслуживание не может присоединиться к очереди в блоке ожидания. В результате эффективная частота поступлений требований (требований, которые будут обслужены) для указанной системы становится меньше общего потока требований. Финальная вероятность рассчитывается по формуле: Среднее число находящихся в системе заявок на обслуживание: Так как требования получают отказ, когда блок ожидания заполнен, поэтому эффективный поток клиентов: Средняя продолжительность пребывания заявки в обслуживающей системе и в очереди: Многоканальная система M /M / c Процесс массового обслуживания, описываемый моделью (M/M/c), характеризуется интенсивностью входного потока и тем обстоятельством, что параллельно обслуживаются не более с клиентов. Входной и выходной потоки являются пуассоновскими. Конечная цель использования с параллельно включенных обслуживающих приборов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно с клиентов. Таким образом, если n=c, то интенсивность входного (выходного) потока равняется с. С другой стороны, если n