Материал: Основные понятия теории очередей. Система с отказами

Основные понятия теории очередей. Система с отказами

Введение

В повседневной жизни мы постоянно сталкиваемся с состоянием ожидания. Это состояние в очередях, на телефонных станциях в ожидании освобождения линии абонента, на складах организации в ожидании разгрузки или погрузки транспортных средств. Во всех перечисленных случаях имеем дело с массовостью и обслуживанием. Изучением таких ситуаций занимается теория систем массового обслуживания.

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

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ОЧЕРЕДЕЙ

.1 ОСНОВНЫЕ ЭЛЕМЕНТЫ СМО

Основными элементами СМО являются источники заявок, их входящий поток, каналы обслуживания и выходящий поток.

Это можно изобразить так:

Входящий поток          Очередь              Каналы обслуживания                             Выходящий поток

В зависимости от формирования СМО, ее различают на:

Системы с отказами, в которых при занятости, заявка не встает в очередь и при это она покидает систему обслуживания.

Системы с неограниченными ожиданиями, в которых заявка встает в очередь, если в момент поступления все каналы были заняты.

Существуют и системы смешанного типа с ожиданием ограниченной длиной очереди, это когда заявка получает отказ, если приходит в момент, когда все места в очереди заняты. Заявка, попавшая в очередь, обязательно обслуживается.

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

В зависимости от расположения источника требований системы могут быть разомкнутыми, (источник заявок находится вне системы) и замкнутыми (источник находится в самой системе).

.2 ХАРАКТЕРИСТИКИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

Характеристики систем массового обслуживания:

Среднее время обслуживания;

Среднее время ожидания в очереди;

Среднее время пребывания в СМО;

Средняя длина очереди;

Среднее число заявок в СМО;

Количество каналов обслуживания;

Интенсивность входного потока заявок;

Интенсивность обслуживания;

Интенсивность нагрузки;

Коэффициент нагрузки;

Относительная пропускная способность;

Абсолютная пропускная способность;

Доля времени простоя СМО;

Доля обслуженных заявок;

Доля потерянных заявок;

Среднее число занятых каналов;

Среднее число свободных каналов;

Коэффициент загрузки каналов;

Среднее время простоя каналов;

.3 ПАРАМЕТРЫ СТРУКТУРЫ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

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

Простейшей одноканальной моделью с вероятностным входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид

,

где l - интенсивность поступления заявок в систему.

Под интенсивностью потока понимают

,

где m(t, t+t) - среднее число событий в интервале (t, t+t).

Плотность распределения длительностей обслуживания:

,

где m - интенсивность обслуживания.

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

Для простейшего потока интенсивность l = const.

Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способности системы. Система имеет два состояния: S0 - канал свободен и S1 - канал занят. Обозначим вероятности состояний:(t) - вероятность состояния S0 , P1(t) - вероятность состояния S1 . Составим систему уравнений Колмогорова:

,

учетом того, что  , решение системы такое:

;

Для 1-канальной СМО с отказами вероятность есть не что иное, как относительная пропускная способность системы

По истечении большого интервала времени (при ) достигается стационарный режим:

Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить СМО в единицу времени:

или

Вероятность отказа в обслуживании заявки будет равна вероятности состояния "канал занят":

.

В свою очередь, многоканальные СМО могут содержать одинаковые и различные по производительности каналы обслуживания.

Производительность канала обслуживания обратно длительности обслуживания заявки равной промежутку времени, необходимому каналу обслуживания для обслуживания заявки. В общем случае это случайная величина с функцией распределения , плотностью распределения  и математическим ожиданием . Типы заявок различаются либо законами распределения, либо только математическими ожиданиями при одинаковых законах распределения. При этом принимается допущение о независимости длительностей обслуживания для различных заявок одного типа, вполне корректное для большинства реальных систем. Наряду с математическим ожиданием длительности обслуживания используется понятие интенсивности потока обслуживания

Если в момент появления заявки на входе в СМО хотя бы один канал свободен от обслуживания, ее обслуживание будет начато немедленно. Однако вполне вероятна ситуация, когда все m каналы заняты обслуживанием. В этом случае обслуживание заявки задерживается, и заявка встает в очередь. Таким образом, вторым важным компонентом является очередь, параметром которой является число мест в очереди n. В приоритетных системах очередь может быть разделена на несколько очередей, для каждой из которых должно быть указанно число мест. На число мест в очереди может быть наложено ограничение, это может быть сделано для каждой очереди в отдельности, так и на все очереди в целом. При этом могут быть конфликтные ситуации. При этом на заявку может быть отказ системы принять заявку.

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

.4 ВХОДЯЩИЙ ПОТОК

Входящий поток наиболее распространен в практике это простейший поток заявок, обладающий свойствами стационарности, ординарности и отсутствия последствия. Свойством стационарности, которое выражает неизменность вероятностного режима потока по времени. Это значит, что число требований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погрузку в среднем в сутки должно быть одинаковым для различных периодов времени. Отсутствие последствия, которое обслуживает взаимную независимость поступления того или иного числа требований на обслуживание в непересекающиеся промежутки времени. Это значит, что число требований, поступающих в данный отрезок времени, не зависит от числа требований, обслуженных в предыдущем промежутке времени.

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

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

Существует также наличие последствия, когда количество требований на отпуск товаров в конце месяца зависит от их удовлетворения в начале месяца.

.5 ВЫХОДЯЩИЙ ПОТОК

Совокупность обслуженных и потерянных заявок образует выходящий поток СМО.

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

В свою очередь, поток потерянных заявок может состоять из потока заявок, получивших отказ, и потока не «терпеливых» заявок, покинувших систему, так как их время пребывания превысило допустимую величину.

Выходящий поток в общем случае распадается на поток обслуженных и поток потерянных заявок.

Выходящий поток заявок связан с потоком обслуживания в канале, где длительность обслуживания tобс является случайной величиной и подчиняется закону распределения с плотностью

где μ - интенсивность потока обслуживания, т.е. среднее число заявок, обслуживаемых в единицу времени:

 (чел./мин, р./ дн., кг/ч, докум./дн.),

где  - среднее время обслуживания.

Важной характеристикой СМО, объединяющей λ и μ, является интенсивность нагрузки

.

2.ВИДЫ СИСТЕМ

.1 СИСТЕМА С ОТКАЗАМИ

Заявка, поступившая в систему с отказами, при этом все каналы заняты, получает отказ и покидает систему необслуженной. Показателем качества обслуживания выступает вероятность получения отказа. Предполагается, что все каналы доступны в равной степени всем заявкам, входящий поток является простейшим, длительность (время) обслуживания одной заявки  распределена по показательному закону.

По ниже написанным формулам можно рассчитать СМО с отказами:

Вероятность простоя каналов обслуживания, когда нет заявок (k = 0):