МИНИСТЕРСТВО ОБРАЗОВАНИЯ И
НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО
ОБРАЗОВАНИЯ
«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
ФАКУЛЬТЕТ УПРАВЛЕНИЯ И РЕГИОНАЛЬНОЙ
ЭКОНОМИКИ
КАФЕДРА ЭКОНОМИЧЕСКОЙ ИНФОРМАТИКИ
И УПРАВЛЕНИЯ
ДОКЛАД
Основные категории теории
массового обслуживания.
Волгоград, 2013
Теория массового
обслуживания - раздел теории вероятностей,
целью исследований которого является
рациональный выбор структуры системы
обслуживания и процесса обслуживания
на основе изучения потоков требований
на обслуживание, поступающих в систему
и выходящие из неё, длительности ожидания
и длины очередей. В теории массового обслуживания
используются методы теории вероятностей
и математической статистики.
История
Основоположником теории массового
обслуживания считается датский ученый
А. К. Эрланг. Являясь сотрудником Копенгагенской
телефонной компании, он опубликовал в
1909 году работу «Теория вероятностей и
телефонные переговоры», в которой решил
ряд задач по теории систем массового
обслуживания с отказами.
Значительный вклад в создание
и разработку общей теории массового обслуживания
внес выдающийся советский математик
Александр Яковлевич Хинчин (1984 – 1959),
который предложил сам термин теория массового
обслуживания. В зарубежной литературе
чаще используется название теория очередей.
Предмет, цель и задачи
теории массового обслуживания
Предметом изучения
теории массового обслуживания являются
СМО.
Во многих областях производства,
бытового обслуживания, экономики и финансов
важную роль играют системы специального
вида, реализующие многократное выполнение
однотипных задач. Подобные системы называют системами массового
обслуживания (СМО). В качестве примеров
СМО в финансово-экономической сфере можно
привести системы, представляющие собой
банки, страховые организации, налоговые
инспекции, аудиторские службы. В сфере
производства и обслуживания примерами
СМО могут служить: различные системы
связи (в том числе телефонные станции),
погрузочно-разгрузочные комплексы (порты,
товарные станции), автозаправочные станции,
магазины, парикмахерские, билетные кассы,
пункты обмена валюты, ремонтные мастерские,
больницы и т.д. Такие системы как компьютерные
сети, системы сбора, хранения и обработки
информации, транспортные системы, автоматизированные
производственные участки и, в военной
области, системы противовоздушной или
противоракетной обороны также могут
рассматриваться как своеобразные СМО.
Каждая СМО включает в свою
структуру некоторое число обслуживающих
устройств (единиц, приборов,
линий), которые называют каналами обслуживания.
Роль каналов могут играть лица, выполняющие
те или иные операции (кассиры, операторы,
продавцы, парикмахеры и т.д.), линии
связи, автомашины, краны, ремонтные бригады,
железнодорожные пути, бензоколонки и
т.д.
Каждая СМО предназначена для
обслуживания (выполнения)
некоторого потока заявок (или
требований), поступающих на вход системы
большей частью не регулярно, а в случайные
моменты времени. Обслуживание заявок,
в общем случае, также длится не постоянное,
заранее известное, а случайное время.
После обслуживания заявки канал освобождается
и готов к приему следующей заявки. Случайный
характер потока и времени их обслуживания
приводит к неравномерной загруженности
СМО: в некоторые промежутки времени на
входе СМО могут скапливаться необслуженные
заявки (они либо становятся
в очередь, либо покидают СМО необслуженными),
в другие же периоды при свободных каналах
на входе СМО заявок не будет, что приводит
к недогрузке СМО, т.е. к простаиванию каналов.
Таким образом, во всякой СМО
можно выделить следующие основные элементы:
входящий поток заявок;
очередь;
каналы обслуживания;
выходящий поток обслуженных
заявок.
Каждая СМО в зависимости от
своих параметров: характера потока заявок,
числа каналов обслуживания и их производительности,
а также от правил организации работы,
обладает определенной эффективностью
функционирования (пропускной способностью),
позволяющей ей более или менее успешно
справляться с потоком заявок.
Цель теории массового
обслуживания – выработка рекомендаций
по рациональному построению СМО, рациональной
организации их работы и регулированию
потока заявок для обеспечения высокой
эффективности функционирования СМО.
Для достижения этой цели ставятся задачи теории массового
обслуживания, состоящие в установлении
зависимостей эффективности функционирования
СМО от ее организации (параметров): характера
потока заявок, числа каналов и их производительности
и правил работы СМО.
- Основные
группы (обычно средних) показателей СМО:
- Показатели эффективности использования
СМО:
- Абсолютная
пропускная способность СМО – среднее
число заявок, которое сможет обслужить
СМО в единицу времени.
- Относительная
пропускная способность СМО – отношение
среднего числа заявок, обслуживаемых
СМО в единицу времени, к среднему числу
поступивших за это же время заявок.
- Средняя
продолжительность периода занятости
СМО.
- Коэффициент
использования СМО – средняя доля времени,
в течение которого СМО занята обслуживанием
заявок, и т.п.
- Показатели качества обслуживания заявок:
- Среднее
время ожидания заявки в очереди.
- Среднее
время пребывания заявки в СМО.
- Вероятность
отказа заявке в обслуживании без ожидания.
- Вероятность
того, что вновь поступившая заявка немедленно
будет принята к обслуживанию.
- Закон
распределения времени ожидания заявки
в очереди.
- Закон
распределения времени пребывания заявки
в СМО.
- Среднее
число заявок, находящихся в очереди.
- Среднее
число заявок, находящихся в СМО, и т.п.
- Показатели эффективности функционирования
пары «СМО – клиент», где под «клиентом»
понимают всю совокупность заявок или
некий их источник. К числу таких показателей относится,
например, средний доход, приносимый СМО
в единицу времени, и т.п.
Случайный характер потока
заявок и длительности их обслуживания
порождает в СМО случайный процесс.
Определение. Случайным процессом
(или случайной функцией) называется соответствие,
при котором каждому значению аргумента
(в данном случае – моменту из промежутка
времени проводимого опыта) ставится в
соответствие случайная величина (в данном
случае – состояние СМО).
Поэтому для решения задач теории
массового обслуживания необходимо изучить
случайный процесс, протекающий в СМО,
т.е. необходимо построить и проанализировать
его математическую модель. Математический
анализ работы СМО существенно упрощается,
если этот случайный процесс удовлетворяет
определенным условиям, которые будут
рассмотрены ниже.
Классификация систем
массового обслуживания
Системы массового обслуживания
делятся на типы (или классы) по ряду признаков.
По числу каналов СМО подразделяют на одноканальные (когда имеется один
канал обслуживания) и многоканальные, точнее n -канальные
(когда количество каналов n ≥ 2).
Здесь и далее будем полагать,
что каждый канал одновременно может обслуживать
только одну заявку и, если не оговорено
специально, каждая находящаяся под обслуживанием
заявка обслуживается только одним каналом.
Многоканальные СМО могут состоять из
однородных каналов, либо из разнородных,
отличающихся длительностью обслуживания
одной заявки. Практически время обслуживания
каналом одной заявки об T является непрерывной
случайной величиной. Однако при условии
абсолютной однородности поступающих
заявок и каналов время обслуживания может
быть и величиной постоянной (T const об = ).
По дисциплине обслуживания
СМО подразделяют на три класса:
СМО с отказами, в которых
заявка, поступившая на вход СМО в момент,
когда все каналы заняты, получает
«отказ» и покидает СМО («пропадает»).
Чтобы эта заявка все же была обслужена,
она должна снова поступить на вход СМО
и рассматриваться при этом как заявка,
поступившая впервые. Примером СМО с отказами
может служить работа АТС: если набранный
телефонный номер (заявка, поступившая
на вход) занят, то заявка получает отказ,
и, чтобы дозвониться по этому номеру,
следует его набрать еще раз (заявка поступает
на вход как новая).
СМО с ожиданием (неограниченным
ожиданием или очередью). В таких системах
заявка, поступившая в момент занятости
всех каналов, становится в очередь и ожидает
освобождения канала, который примет ее
к обслуживанию. Каждая заявка, поступившая
на вход, в конце концов будет обслужена.
Такие СМО часто встречаются в торговле,
в сфере бытового и медицинского обслуживания,
на предприятиях (например, обслуживание
станков бригадой наладчиков).
СМО смешанного типа
(с ограниченным ожиданием). Это такие
системы, в которых на пребывание заявки
в очереди накладываются некоторые ограничения.
Эти ограничения могут накладываться
на длину очереди, т.е.
максимально возможное число заявок,
которые одновременно могут находиться
в очереди. В качестве примера такой системы
можно привести мастерскую по ремонту
автомобилей, имеющую ограниченную по
размерам стоянку для неисправных машин,
ожидающих ремонта.
Ограничения ожидания могут
касаться времени пребывания
заявки в очереди, по истечению которого
она выходит из очереди и покидает систему,
либо касаться общего времени пребывания
заявки в СМО (т.е. суммарного времени пребывания
заявки в очереди и под обслуживанием).
По ограничению потока заявок СМО делятся на замкнутые и открытые.
Если поток заявок ограничен
и заявки, покинувшие систему, могут в
нее возвращаться, то СМО является замкнутой, в противном
случае – открытой. Классическим примером
замкнутой СМО служит работа бригады наладчиков
в цеху. Станки являются источниками заявок
на обслуживание, и их количество ограничено,
наладчики – каналы обслуживания. После
проведения ремонтных работ вышедший
из строя станок снова становится источником
заявок на обслуживание. В открытой СМО
характеристики потока заявок не зависят
от того, в каком состоянии сама СМО (сколько
каналов занято). В замкнутой СМО – зависят.
Так, в рассмотренном выше примере интенсивность
потока «заявок» со стороны станков (т.е.
количество заявок в единицу времени)
зависит от того, сколько их неисправно
и ждет наладки.
По количеству этапов обслуживания СМО делятся на однофазные и многофазные
системы. Если каналы СМО однородны, т.е.
выполняют одну и ту же операцию обслуживания,
то такие СМО называются однофазными. Если
каналы обслуживания расположены последовательно
и они неоднородны, так как выполняют различные
операции обслуживания (т.е. обслуживание
состоит из нескольких последовательных
этапов или фаз), то СМО называется многофазной. Примером
работы многофазной СМО является обслуживание
автомобилей на станции технического
обслуживания (мойка, диагностирование
и т.д.). Далее будем рассматривать только
однофазные СМО.
Потоки событий
Под потоком событий
понимается последовательность однородных
событий, следующих одно за другим
в какие-то случайные моменты времени
(например, поток вызовов на телефонной
станции, поток покупателей, поток заказных
писем, поступающих в почтовое отделение
и т.п.).
Поток характеризуется интенсивностью
λ – частотой появления событий или средним
числом событий, поступающих в СМО в единицу
времени.
Поток событий называется регулярным, если
события следуют одно за другим через
определенные равные промежутки времени.
Например, поток изделий на конвейере
сборочного цеха (с постоянной скоростью
движения) является регулярным. Такой
поток сравнительно редко встречается
в реальных системах, но представляет
интерес как предельный случай. Типичным
для системы массового обслуживания является
случайный поток заявок.
Однородный поток
Поток заявок однороден, если:
все заявки равноправны,
рассматриваются только моменты
времени поступления заявок, т.е. факты
заявок без уточнения деталей каждой конкретной
заявки.
Поток без последействия
Поток без последействия,
если число событий любого интервала времени
(t, t+x) не зависит от числа событий на любом
другом непересекающемся с нашим (t, t+x)
интервале времени.
Стационарный поток
Поток заявок стационарен,
если вероятность появления n событий
на интервале времени (t, t+x) не зависит
от времени t, а зависит только от длины
этого участка.
Простейший поток
Однородный стационарный поток
без последействий является простейшим, потоком Пуассона.
Число событий такого потока,
выпадающих на интервал , распределено
по Закону Пуассона:
Пуассоновский поток заявок
удобен при решении задач ТМО. Строго говоря
простейшие потоки редки на практике,
однако многие моделируемые потоки допустимо
рассматривать как простейшие.
Мгновенная плотность
Мгновенная плотность (интенсивность)
потока равна пределу отношения среднего
числа событий, приходящихся на элементарный
интервал времени (t, t+x) к длине интервала
(x), когда последний стремится к нулю.
или, для простейшего потока,
где M(x) равно математическому
ожиданию числа событий на интервале X.
Формула Литтла
Среднее число заявок в системе
равно произведению интенсивности входного
потока на среднее время пребывания заявки
в системе.
Источники