Файл: Лекция 6 основы теории массового обслуживания теория массового обслуживания.pdf

ЛЕКЦИЯ № 6 ОСНОВЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ
Теория массового обслуживания
составляет один из разделов теории вероятностей.
В
этой теории рассматриваются
вероятностные задачи и математические модели.
Детерминированная
математическая
модель
отражает поведение объекта (системы, процесса) с позиций полной
определенности в настоящем и будущем.
Вероятностная математическая модель учитывает влияние случайных факторов на поведение объекта (системы, процесса)
и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.
Рассмотрим
понятия,
характеризующие
«стохастическую
неопределенность», когда неопределенные факторы, входящие в задачу, представляют собой случайные величины (или случайные функции), вероятностные характеристики которых либо известны, либо могут быть получены из опыта. Такую неопределенность называют еще
«благоприятной»,
«доброкачественной».

Строго говоря, случайные возмущения присущи любому процессу. Проще привести примеры случайного, чем неслучайного процесса. Даже, например, процесс хода часов (вроде бы это строгая выверенная работа – «работает как часы») подвержен случайным изменениям (уход вперед, отставание, остановка). Но до тех пор, пока эти возмущения несущественны, мало влияют на интересующие нас параметры, мы можем ими пренебречь и рассматривать процесс как детерминированный, неслучайный.
Пусть имеется некоторая система S (техническое устройство, группа таких устройств, технологическая система – станок, участок, цех,
предприятие, отрасль промышленности и т.д.). В системе S
протекает случайный процесс, если она с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом.
Пример 1. Система S – технологическая система (участок станков).
Станки время от времени выходят из строя и ремонтируются.
Процесс, протекающий в этой системе, случаен.
Случайный процесс, протекающий в системе, называется Марковским,
если для любого момента времени t
0
вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t
0
и не зависят от того, когда и как система пришла в это состояние.

Пусть в настоящий момент t
0
система находится в определенном состоянии S
0
Мы знаем характеристики состояния системы в настоящем t
0

S
0
и все, что было при t < t
0
(предысторию процесса). Можем ли мы предугадать (предсказать) будущее,
т.е. что будет при t > t
0
?
В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того,
что через некоторое время

система S окажется в состоянии S
1
или останется в состоянии S
0
и т.д.
На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием
«предыстории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели.
В исследовании операций большое значение имеют Марковские случайные процессы с
дискретными
состояниями
и
непрерывным временем.
Процесс называется процессом с дискретным состоянием, если его возможные состояния S
1
, S
2
,
… можно заранее определить,
и переход системы из состояния в состояние происходит
«скачком», практически мгновенно.

Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент.
Пример 2. Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное,
случайное время. Возможны следующие состояния системы:
S
0
- оба станка исправны,
S
1
- первый станок ремон- тируется, второй исправен,
S
2
- второй станок ремон- тируется, первый исправен,
S
3
- оба станка ремонтиру- ются.
Граф состояний системы

Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой
–
графом
состояний. Вершины графа – состояния системы. Дуги графа –
возможные переходы из состояния в состояние.
Переход из состояния S
0
в S
3
на рисунке не обозначен, т.к.
предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков пренебрегаем.
Поток событий
– последовательность однородных событий,
следующих одно за другим в какие-то случайные моменты времени.
В предыдущем примере – это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.
Поток событий можно наглядно изобразить рядом точек на оси времени
Положение каждой точки случайно и здесь изображена лишь какая- то одна реализация потока.
Интенсивность потока событий (

)
– это среднее число событий, приходящееся на единицу времени.

Свойства (виды) потоков событий
Поток событий называется
стационарным
,
если его вероятностные характеристики не зависят от времени.
Интенсивность

стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера,
и среднее число событий,
приходящееся на единицу времени, постоянно и от времени не зависит.
Поток событий называется
потоком без последствий
,
если для любых двух непересекающихся участков времени

1
и

2
(см.
рисунок) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой → события,
образующие поток, появляются в те или иные моменты времени
независимо
друг
от друга
и вызваны каждое своими собственными причинами.

Поток событий называется
ординарным
,
если события в нем появляются поодиночке, а не группами по нескольку сразу.
Поток событий называется
простейшим
(или
стационарным
пуассоновским
),
если он обладает сразу тремя свойствами:
1)
стационарен,
2)
ординарен,
3)
не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую роль, как и закон нормального распределения среди других законов распределения → при наложении достаточно большого числа независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.

Для простейшего потока с интенсивностью

интервал T между соседними событиями имеет так называемое показательное
(экспоненциальное) распределение с плотностью где

- параметр показательного закона.
Для случайной величины
T,
имеющей показательное распределение, математическое ожидание m
T
есть величина,
обратная параметру, а среднее квадратичное отклонение

T
равно математическому ожиданию.
t
e
t
f




)
(


/
1


T
T
m

Задачи теории массового обслуживания
Примеры систем массового обслуживания (СМО): телефонные станции, ремонтные мастерские, билетные кассы, справочные бюро, станочные и другие технологические системы, системы управления гибких производственных систем и т.д.
Каждая СМО состоит из какого – то количества обслуживающих единиц, которые называются
каналами обслуживания
(это станки, транспортные тележки, роботы, линии связи, кассиры,
продавцы и т.д.). Всякая СМО предназначена для обслуживания какого – то потока заявок (требований), поступающих в какие –
то случайные моменты времени.

Обслуживание заявки продолжается какое-то случайное время,
после чего канал освобождается и готов к приему следующей заявки.
Случайный характер потока заявок и
времени обслуживания приводит к тому, что в какие-то периоды времени на входе СМО скапливается излишне большое количество заявок (они либо становятся в очередь, либо покидают СМО
необслуженными). В другие же периоды СМО будет работать с недогрузкой или вообще простаивать.
Процесс работы СМО – случайный процесс с дискретными состояниями и непрерывным временем. Состояние СМО
меняется скачком в моменты появления каких-то событий
(прихода новой заявки, окончания обслуживания, момента, когда заявка, которой надоело ждать, покидает очередь).

Предмет
теории
массового
обслуживания
–
построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы,
характер потока заявок)
с интересующими нас характеристиками – показателями эффективности СМО. Эти показатели описывают способность СМО справляться с потоком заявок. Ими могут быть: среднее число заявок, обслуживаемых
СМО в единицу времени; среднее число занятых каналов;
среднее число заявок в очереди; среднее время ожидания обслуживания и т.д.
Математический анализ работы СМО очень облегчается, если процесс этой работы
Марковский,
т.е.
потоки событий,
переводящие систему из состояния в состояние – простейшие.
Иначе математическое описание процесса очень усложняется и его редко удается довести до конкретных аналитических зависимостей.
На практике не
Марковские процессы с
приближением приводятся к Марковским.

Классификация систем массового обслуживания
Первое деление (по наличию очередей)
:
1.
СМО с отказами,
2.
СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь – ограничена или не ограничена.
Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».

Второе деление:
-
СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
-
СМО с обслуживанием и приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.
Кроме этого СМО делятся на
открытые
СМО и
замкнутые
СМО.
В открытой СМО характеристики потока заявок не зависят от того,
в каком состоянии сама СМО (сколько каналов занято). В
замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.