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

Тема 6.5. Марковские процессы. Модели массового обслуживания 1 Основы знаний об очередях, иногда называемые теорией оче­редей или теорией массового обслуживания, составляют важную часть теории управления производством. Очереди — обычное яв­ление. Они могут носить форму ожидания ремонта автомобиля в центре автосервиса или ожидания студентами консультации у про­фессора. В таблице перечислены некоторые примеры возникно­вения очередей в системах массового обслуживания: Модели очередей (как и линейное программирование, модели управления запасами, методы сетевого анализа проектов) исполь­зуются и в сфере управления материальным производством, и в сфере обслуживания. Анализ очередей в терминах длины очере­ди, среднего времени ожидания, среднего времени обслуживания и других факторов помогает нам лучше понять принципы орга­низации системы обслуживания. Ожидание пациента в приемной врача и ожидание починки сломанной дрели в ремонтной мастер­ской имеют много общего с точки зрения управления процессом обслуживания. Оба процесса используют человеческие ресурсы и ресурсы оборудования для удовлетворения потребностей клиентов. Профессиональный менеджер, принимая решение о совершен­ствовании системы массового обслуживания, оценивает измене­ния, возникающие в затратах на функционирование системы и в издержках, связанных с ожиданием клиентов. Можно нанять большое количество сотрудников, которые будут быстро обслуживать клиентов. Так, администратор супермаркета может умень­шить очереди в кассы, увеличивая в часы пик количество продав­цов и кассиров. Для работы в кассах банков или аэропортов в часы пик могут быть привлечены дополнительные сотрудники. Одна­ко снижение времени ожидания обычно сопряжено с издержка­ми на создание и оснащение рабочих мест, с оплатой труда до­полнительного персонала. Эти издержки могут быть весьма зна­чительны. Можно сэкономить на трудозатратах. Но тогда клиент может не дождаться обслуживания или потерять охоту вернуться еще раз. В последнем случае система массового обслуживания будет нести потери, которые можно назвать издержками ожидания. В некоторых системах обслуживания, например в скорой помо­щи, затраты, связанные с длительным ожиданием, могут оказать­ся чрезвычайно высокими. Основной экономический принцип совершенствования систем массового обслуживания состоит в оценке общих ожидаемых затрат, включающих затраты на обслу­живание и потери, которые несет система в результате ожидания клиента. После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь определять и использовать для экономи­ческого анализа следующие понятия: • система массового обслуживания; • заявка; • очередь; • темп поступления заявок; • темп обслуживания; • среднее время, которое заявка проводит в очереди; • средняя длина очереди; • среднее время, которое заявка проводит в системе обслужи­вания; • среднее число клиентов в системе обслуживания; • издержки функционирования системы обслуживания; • издержки ожидания. Классификационные признаки систем массового обслуживания. В системах массового обслуживания различают три основных эта­па, которые проходит каждая заявка: 1) появление заявки на входе в систему; 2) прохождение очереди; 3) процесс обслуживания, после которого заявка покидает систему. На каждом этапе используются определенные характеристики, которые следует обсудить прежде, чем строить математические модели. Характеристики входа: 1) число заявок на входе (размер популяции); 2) режим поступления заявок в систему обслуживания; 3) поведение клиентов. Число заявок на входе. Число потенциально возможных заявок (размер популяции) может считаться либо бесконечным (неогра­ниченная популяция), либо конечным (ограниченная популяция). Если число заявок, поступивших на вход системы с момента на­чала процесса обслуживания до любого заданного момента вре­мени, является лишь малой частью потенциально возможного числа клиентов, популяция на входе рассматривается как Неогра­ниченная. Примеры неограниченных популяций: автомобили, проходящие через пропускные пункты на скоростных дорогах, покупатели в супермаркете и т. п. В большинстве моделей очередей на входе рассматриваются именно неограниченные популяции. Если количество заявок, которые могут поступить в систему, сравнимо с числом заявок, уже находящихся в системе массо­вого обслуживания, популяция считается Ограниченной. Пример ограниченной популяции: компьютеры, принадлежащие конкрет­ной организации и поступающие на обслуживание в ремонтную мастерскую. Режим поступления заявок, в систему обслуживания. Заявки могут поступать в систему обслуживания в соответствии с опреде­ленным графиком (например, один пациент на прием к стомато­логу каждые 15 мин, один автомобиль на конвейере каждые 20 мин) или случайным образом. Появления клиентов считаются Случай­ными, если они независимы друг от друга и точно непредсказу­емы. Часто в задачах массового обслуживания число появлений в единицу времени может быть оценено с помощью пуассоновского распределения вероятностей. При заданном темпе поступления (например, два клиента в час или четыре грузовика в минуту) дискретное распределение Пуассона описывается следующей фор­мулой: где Р (х) — вероятность поступления Х заявок в единицу вре­мени; Х — число заявок в единицу времени; λ — среднее число заявок в единицу времени (темп по­ступления заявок); Е = 2,7182 — основание натурального логарифма. Соответствующие значения вероятностей Р(х) нетрудно опре­делить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок — два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки — около 0,27, двух — также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре — с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или бо­лее, близка нулю. На практике вероятности появления заявок, разумеется, не всегда подчиняются пуассоновскому распределению (они могут иметь какое-то другое распределение). Поэтому требуется прово­дить предварительные исследования для того, чтобы проверить, что пуассоновское распределение может служить хорошей аппрок­симацией. Поведение клиентов. Большинство моделей очередей основы­вается на предположении, что поведение клиентов является стан­дартным, т. е. каждая поступающая в систему заявка встает в оче­редь, дожидается обслуживания и не покидает систему до тех пор, пока ее не обслужат. Другими словами, клиент (человек или ма­шина), вставший в очередь, ждет до тех пор, пока он не будет обслужен, не покидает очередь и не переходит из одной очереди в другую. Жизнь значительно сложнее. На практике клиенты могут по­кинуть очередь потому, что она оказалась слишком длинной. Может возникнуть и другая ситуация: клиенты дожидаются сво­ей очереди, но по каким-то причинам уходят необслуженными. Эти случаи также являются предметом теории массового обслу­живания, однако здесь не рассматриваются. Характеристики очереди: 1) длина; 2) правило обслуживания. Длина очереди. Длина может быть ограничена либо не ограни­чена. Длина очереди (очередь) Ограничена, если она по каким-либо причинам (например, из-за физических ограничений) не может увеличиваться до бесконечности. Если очередь достигает своего максимального размера, то следующая заявка в систему не допускается и происходит отказ. Длина очереди Не ограничена, Если в очереди может находиться любое число заявок. Например, очередь автомобилей на бензозаправке. Правило обслуживания. Большинство реальных систем исполь­зует правило «первым пришел — первым ушел» (FIFO — first in, first out). В некоторых случаях, например в приемном покое боль­ницы, в дополнение к этому правилу могут устанавливаться раз­личные Приоритеты. Пациент с инфарктом в критическом со­стоянии, по-видимому, будет иметь приоритет в обслуживании по сравнению с пациентом, сломавшим палец. Порядок запуска компьютерных программ — другой пример установления приорите­тов в обслуживании. Характеристики процесса обслуживания: 1) конфигурация системы обслуживания (число каналов и чис­ло фаз обслуживания); 2) режим обслуживания. Конфигурация системы обслуживания. Системы обслуживания различаются по Числу каналов обслуживания. Обычно количество каналов можно определить как число клиентов, обслуживание которых может быть начато одновременно, например: число мас­теров в парикмахерской. Примеры Одноканальной системы об­служивания: банк, в котором открыто единственное окошко для обслуживания клиентов, или ресторан, обслуживающий клиентов в автомобилях. Если же в банке открыто несколько окошек для обслуживания, клиент ожидает в общей очереди и подходит к пер­вому освободившемуся окну, то мы имеем дело с Многоканаль­ной однофазовой системой обслуживания. Большинство банков, также, как почтовые отделения и авиакассы, являются многока­нальными системами обслуживания. Другая характеристика — Число фаз (или последовательных этапов) Обслуживания одного клиента. Однофазовыми являют­ся такие системы, в которых клиент обслуживается в одном пун­кте (на одном рабочем месте), затем покидает систему. Ресторан для обслуживания автомобилей, в котором официант получает деньги и приносит заказ в автомобиль, является примером од­нофазовой системы. Если же в ресторане нужно сделать заказ в одном месте, оплатить его в другом и получить пищу в третьем, то мы имеем дело с Многофазовой (три фазы) системой обслу­живания. На рис. 1 приведены системы обслуживания различной кон­фигурации. Рис. 1 Режим обслуживания. Как и режим поступления заявок, режим обслуживания может характеризоваться либо постоянным, либо случайным временем обслуживания. При Постоянном времени на обслуживание любого клиента затрачивается одинаковое вре­мя. Такая ситуация может наблюдаться на автоматической мойке автомобилей. Однако более часто встречаются ситуации, когда время обслуживания имеет Случайное распределение. Во многих случаях можно предположить, что время обслуживания подчиня­ется экспоненциальному распределению с функцией распреде­ления F(T) = P(T< t) =1 – е–tm, где Р (T < t) — вероятность того, что фактическое время T обслу­живания заявки не превысит заданной величи­ны t; M — среднее число заявок, обслуживаемых в едини­цу времени; Е = 2,7182 — основание натурального логарифма. Параметры моделей очередей. При анализе систем массового обслуживания используются технические и экономические харак­теристики. Наиболее часто используются следующие Технические характери­стики: 1) среднее время, которое клиент проводит в очереди; 2) средняя длина очереди; 3) среднее время, которое клиент проводит в системе обслужи­вания (время ожидания плюс время обслуживания); 4) среднее число клиентов в системе обслуживания; 5) вероятность того, что система обслуживания окажется незанятой; 6) вероятность определенного числа клиентов в системе. Среди Экономических характеристик наибольший интерес пред­ставляют следующие: 1) издержки ожидания в очереди; 2) издержки ожидания в системе; 3) издержки обслуживания. Модели систем массового обслуживания. В зависимости от со­четания приведенных выше характеристик могут рассматривать­ся различные модели систем массового обслуживания. Здесь мы ознакомимся с несколькими наиболее известными моделями. Все они имеют следующие общие характеристики: А) пуассоновское распределение вероятностей поступления заявок; Б) стандартное поведение клиентов; В) правило обслуживания FIFO (первым пришел — первым об­служен); Г) единственная фаза обслуживания. I. Модель А — модель одноканальной системы массового об­служивания М/М/1 с Пуассоновским входным потоком заявок и Экспоненциальным временем обслуживания. Наиболее часто встречаются задачи массового обслуживания с единственным каналом. В этом случае клиенты формируют одну очередь к единственному пункту обслуживания. Предположим, что для систем этого типа выполняются следующие условия: 1. Заявки обслуживаются по принципу «первым пришел — пер­вым обслужен» (FIFO), причем каждый клиент ожидает своей очереди до конца независимо от длины очереди. 2. Появления заявок являются независимыми событиями, од­нако среднее число заявок, поступающих в единицу времени, не­изменно. 3. Процесс поступления заявок описывается пуассоновским распределением, причем заявки поступают из неограниченного множества. 4. Время обслуживания описывается экспоненциальным рас­пределением вероятностей. 5. Темп обслуживания выше темпа поступления заявок. Пусть l — число заявок в единицу времени; M — число клиентов, обслуживаемых в единицу времени; П — число заявок в системе. Тогда система массового обслуживания описывается уравнени­ями, приведенными ниже. Формулы для описания системы М/М/1: — среднее число клиентов в системе; — среднее время обслуживания одного клиента в системе (время ожидания плюс время обслуживания); — среднее число клиентов в очереди; — среднее время ожидания клиента в очереди; — характеристика загруженности системы (доля време­ни, в течение которого система занята обслуживанием); — вероятность отсутствия заявок в системе; — вероятность того, что в системе находится бо­лее чем K заявок. II. Модель В — многоканальная система обслуживания M/M/S. В многоканальной системе для обслуживания открыты два ка­нала или более. Предполагается, что клиенты ожидают в общей очереди и обращаются в первый освободившийся канал обслужи­вания. Пример такой многоканальной однофазовой системы можно увидеть во многих банках: из общей очереди клиенты обращают­ся в первое освободившееся окошко для обслуживания. В многоканальной системе поток заявок подчиняется Пуассоновскому закону, а время обслуживания — Экспоненциальному. Приходящий первым обслуживается первым, и все каналы обслу­живания работают в одинаковом темпе. Формулы, описывающие модель В, достаточно сложны для использования. Для расчета параметров многоканальной системы обслуживания удобно ис­пользовать соответствующее программное обеспечение. Для многоканальной системы с неограниченной очередью должно выполняться условие  < 1, где R — параметр загрузки системы (среднее число занятых каналов), П — минимальное ко­личество каналов, при котором очередь не будет расти до беско­нечности. В противном случае предельные вероятности существо­вать не могут. Формулы для описания системы M/M/S: — вероятность того, что система свободна; — вероятность того, что в системе находится П заявок; — вероятность того, что заявка окажется в очереди; — среднее число занятых каналов; — среднее число заявок в очереди; — среднее число заявок в системе; — время нахождения заявки в очереди; — время нахождения заявки в системе. III. Модель С— модель с постоянным временем обслуживания M/D/1. Некоторые системы имеют Постоянное, а не экспоненциально распределенное время обслуживания. В таких системах клиенты обслуживаются в течение фиксированного периода времени, как, например, на автоматической мойке автомобилей. Для модели С С постоянным темпом обслуживания значения величин Lq и Wq Вдвое меньше, чем соответствующие значения в модели А, име­ющей переменный темп обслуживания. Формулы, описывающие модель С: — средняя длина очереди; — среднее время ожидания в очереди; — среднее число клиентов в системе; — среднее время ожидания в системе. IV. Модель D — модель с ограниченной популяцией. Если число потенциальных клиентов системы обслуживания Ограничено, мы имеем дело со специальной моделью. Такая за­дача может возникнуть, например, если речь идет об обслужива­нии оборудования фабрики, имеющей пять станков. Особенность этой модели по сравнению с тремя рассмотрен­ными ранее в том, что существует Взаимозависимость между длиной очереди и темпом поступления заявок. V. Модель Е — модель с ограниченной очередью. Модель от­личается от предыдущих тем, что число мест в очереди Ограни­чено. В этом случае заявка, прибывшая в систему, когда все ка­налы и места в очереди заняты, покидает систему необслуженной, т. е. получает отказ. Как частный случай модели с ограниченной очередью можно рассматривать Модель с отказами, если количество мест в очере­ди сократить до нуля. Сравнительная характеристика различных моделей систем массового обслуживания приведена в следующей таблице: Пример 1. Обслуживание автомобилей. Иванов, механик автосервиса, может заменить масло в сред­нем в трех автомобилях в течение часа (т. е. в среднем на одном автомобиле за 20 мин). Время обслуживания подчиняется экспо­ненциальному закону. Клиенты, нуждающиеся в этой услуге, при­езжают в среднем по два в час, в соответствии с пуассоновским распределением. Клиенты обслуживаются в порядке прибытия, и их число не ограничено. Рассчитайте основные характеристики системы обслуживания. Решение. На основе исходных данных получаем: L = 2 машины в час — количество машин, поступающих в те­чение часа; M = 3 машины в час — количество машин, обслуживаемых в течение часа;  машины — среднее количество машин, находящихся в системе; — среднее время ожидания в системе; Машины — среднее коли­чество машин, ожидающих в очереди; — среднее время ожи­дания в очереди; — доля времени, в течение которого меха­ник занят; — вероятность того, что в систе­ме нет ни одного клиента. Вероятности того, что в системе находится более чем K машин: Примечание. При K = 0 значение вероятности равно 1 – P0; При K = 1 существует 44,4% шансов на то, что в системе находит­ся более одной машины, и т. д. Пример 2. Сопоставление затрат. После того как мы получили основные характеристики систе­мы обслуживания, часто бывает полезным провести ее экономи­ческий анализ. Как уже отмечалось, задачей менеджера является сопоставление возрастающих затрат на улучшение обслуживания и снижающихся затрат, связанных с ожиданием. Рассмотрим этот случай, дополнив условие примера 1. Владелец автосервиса установил, что затраты, связанные с ожи­данием, выражаются в снижении спроса вследствие неудовлетво­ренности клиентов и равны 100 руб. за час ожидания в очереди. Определите общие затраты функционирования автосервиса. Решение. Так как в среднем каждая машина ожидает в очере­ди 2/3 часа (Wq) и в день обслуживается приблизительно 16 ма­шин (l×8 = 2 машины в час в течение 8-часового рабочего дня), общее число часов, которое проводят в очереди все клиенты, равно Следовательно, затраты, связанные с ожиданием, составляют Другая важная составляющая затрат владельца автосервиса — зарплата механика Иванова. Предположим, что он получает 70 руб. в час, или 560 руб. в день. Следовательно, общие затраты состав­ляют 1066 + 560 = 1626 руб. вдень. Пример 3. Утилизация отходов. Компания «Утиль» собирает и утилизирует в Мытищах алюми­ниевые отходы и стеклянные бутылки. Водители автомобилей, доставляющих сырье для вторичной переработки, ожидают в оче­реди на разгрузку в среднем 15 мин. Время простоя водителя и автомобиля оценивается в 6 тыс. руб. в час. Новый автоматический компактор может обслуживать контейнеровозы с постоянным темпом 12 машин в час (5 мин на одну машину). Время прибытия контейнеровозов подчиняется пуассоновскому закону с параметром l = 8 автомобилей в час. Если но­вый компактор будет использоваться, то амортизационные затра­ты составят 0,3 тыс. руб. на один контейнеровоз. Следует ли ис­пользовать компактор? Решение. Затраты на простой одного автомобиля в очереди за одну ездку в системе без компактора составляют В системе с компактором время ожидания в очереди при l = 8 автомобилей в час и m = 12 автомобилей в час будет равно Затраты на простой автомобиля в очереди в этом случае составят Сокращение времени простоя привело к сокращению затрат на простой одного автомобиля за одну ездку на сумму в 1,5 – 0,5 = 1 тыс. руб. При условии, что затраты по эксплуатации компактора на один контейнеровоз составляют 0,3 тыс. руб., общие затраты составят 0,5 + 0,3 = 0,8 тыс. руб. Система с компактором дает экономию в 1,5 – 0,8 = 0,7 тыс. руб. Таким образом, компактор использовать следует. Марковские процессы в системе массового обслуживания2 Для системы массового обслуживания характерен случайный процесс. Изучение случайного процесса, протекающего в системе, выражение его математически и является предметом теории массового обслуживания. Математический анализ работы системы массового обслуживания значительно облегчается, если случайный процесс этой работы является марковским. Процесс, протекающий в системе, называется марковским, если в любой момент времени вероятность любого состояния системы в будущем зависит только от состояния системы в текущий момент и не зависит от того, каким образом система пришла в это состояние. При исследовании экономических систем наибольшее применение имеют марковские случайные процессы с дискретными и непрерывными состояниями. Случайный процесс называется процессом с дискретными состояниями, если все его возможные состояния можно заранее перечислить, а сам процесс состоит в том, что время от времени система скачком переходит из одного состояния в другое. Случайный процесс называется процессом с непрерывным состоянием, если для него характерен плавный, постепенный переход из состояния в состояние. Также можно выделить марковские процессы с дискретным и непрерывным временем. В первом случае переходы системы из одного состояния в другое возможны только в строго определенные, заранее фиксированные моменты времени. Во втором случае переход системы из состояния в состояние возможен в любой, заранее неизвестный, случайный момент. Если вероятность перехода не зависит от времени, то марковский процесс называют однородным. В исследовании систем массового обслуживания большое значение имеют случайные марковские процессы с дискретными состояниями и непрерывным временем. Исследование марковских процессов сводится к изучению матриц переходных вероятностей (). Каждый элемент такой матрицы (поток событий) представляет собой вероятность перехода из заданного состояния (которому соответствует строка) к следующему состоянию (которому соответствует столбец). В этой матрице предусмотрены все возможные переходы данного множества состояний. Следовательно, процессы, которые можно описывать и моделировать с помощью матриц переходных вероятностей, должны обладать зависимостью вероятности конкретного состояния от непосредственно предшествующего состояния. Так выстраивается цепь Маркова. При этом цепью Маркова первого порядка называется процесс, для которого каждое конкретное состояние зависит только от его предшествующего состояния. Цепью Маркова второго и более высоких порядков называется процесс, в котором текущее состояние зависит от двух и более предшествующих. Ниже представлены два примера матриц переходных вероятностей. Матрицы переходных вероятностей можно изобразить графами переходных состояний, как показано на рисунке. Пример Предприятие выпускает продукт, насытивший рынок. Если предприятие от реализации продукта в текущем месяце получит прибыль (П), то с вероятностью 0,7 получит прибыль и в следующем месяце, а с вероятностью 0,3 – убыток. Если в текущем месяце предприятие получит убыток (У), то с вероятностью 0,4 в следующем месяце оно получит прибыль, а с вероятностью 0,6 – убыток (вероятностные оценки получены в результате опроса экспертов). Рассчитать вероятностную оценку получения прибыли от реализации товара через два месяца работы предприятия. В матричной форме эта информация будет выражена следующим образом (что соответствует примеру матрицы 1): Первая итерация – построение матрицы двухступенчатых переходов. Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно снова получит прибыль, равна Если предприятие в текущем месяце получит прибыль, то вероятность того, что в следующем месяце оно получит убыток, равна Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно получит прибыль, равна Если предприятие в текущем месяце получит убыток, то вероятность того, что в следующем месяце оно вновь получит убыток, равна В результате расчетов получаем матрицу двухступенчатых переходов:  Результат достигается перемножением матрицы т,на матрицу с такими же значениями вероятностей: Для проведения этих процедур в среде Excel необходимо выполнить следующие действия: • 1) формировать матрицу; • 2) вызывать функцию МУМНОЖ; • 3) указывать первый массив – матрицу; • 4) указывать второй массив (эта же матрица или другая); • 5) ОК; • 6) выделить зону новой матрицы; • 7) F2; • 8) Ctrl+Shift+Enter; • 9) получить новую матрицу. Вторая итерация – построение матрицы трехступенчатых переходов. Аналогично рассчитываются вероятности получения прибыли или убытка на следующем шаге и рассчитывается матрица трехступенчатых переходов, она имеет следующий вид: Таким образом, в ближайшие два месяца работы предприятия вероятность получения прибыли от выпуска продукта выше, по сравнению с вероятностью получения убытка. Однако следует заметить, что вероятность получения прибыли падает, поэтому предприятию необходимо осуществить разработку нового продукта для замены производимого продукта.