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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Введение

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

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



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

1.1 ОСНОВНЫЕ ЭЛЕМЕНТЫ СМО

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

,

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

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

,

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

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

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

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

P0(t) - вероятность состояния S0 , P1(t) - вероятность состояния S1 . Составим систему уравнений Колмогорова:

,

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

;

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

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

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

или

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

.

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

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

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

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

1.4 ВХОДЯЩИЙ ПОТОК

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

.



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

2.1 СИСТЕМА С ОТКАЗАМИ

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

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

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

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

;

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

;

Среднее число занятых обслуживанием каналов:

;

Доля каналов, занятых обслуживанием:

;

Абсолютная пропускная способность СМО:

;

2.2 СИСТЕМА С НЕОГРАНИЧЕННЫМ ОЖИДАНИЕМ

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

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

Для таких систем характерно отсутствие отказа в обслуживании, т.е. и .

Для систем с ожиданием существует дисциплина очереди:

Обслуживание в порядке очереди по принципу “первым пришел - первым обслужен”;

Случайное неорганизованное обслуживание по принципу “последний пришел - первым обслужен”;

Обслуживание с приоритетами по принципу “самые главные вне очереди”;

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

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

;

Предполагается, что .

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

, ;

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

;

Вероятность того, что заявка окажется в очереди:

;

Среднее число заявок в очереди:

;

Среднее время ожидания заявки в очереди:



;

Среднее время пребывания заявки в СМО:

;

Среднее число занятых обслуживанием каналов:

;

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

;

Коэффициент занятости каналов обслуживания:

;

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

;



2.3 СИСТЕМА С ОЖИДАНИЕМ И ОГРАНИЧЕННОЙ ДЛИНОЙ ОЧЕРЕДИ

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

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

Ограничения на длину очереди могут быть из-за:

Ограничения сверху времени пребывания заявки в очереди;

Ограничения сверху длины очереди;

Ограничения общего времени пребывания заявки в системе.

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

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

;

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

;

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

;



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

;

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

;

Среднее число заявок в очереди:

;

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

;

Среднее число заявок в системе:

;

Среднее время пребывания в системе:

;



2.4 ОДНОКАНАЛЬНАЯ СИСТЕМА С ОЖИДАНИЕМ

Пусть простейший поток заявок на обслуживание - простейший поток с интенсивностью л.

Интенсивность потока обслуживания равна м. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующий вид:

S0 - канал свободен;

S1 - канал занят, очереди нет;

S2 - канал занят, одна заявка в очереди;

…………………………………………….

Sn - канал занят, n-1 заявка в очереди;

…………………………………………….

SN - канал занят, N-1 заявка в очереди.

Процесс в данной системе будет описан системой алгебраических уравнений:

где ;

n - номер состояния.

Система уравнений имеет следующее решение;

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

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

;

Относительная пропускаемая способность СМО:

;

Абсолютная пропускная способность СМО:

;

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

;

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



Средняя продолжительность пребывания заявки в очереди:

;

Среднее число заявок в очереди:

;

2.5 МНОГОКАНАЛЬНАЯ СИСТЕМА С ОЖИДАНИЕМ

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

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

Пусть .

При условии решение системы уравнений имеет вид

.

; при ,

; при .

Здесь есть вероятность того, что в СМО n клиентов находится на обслуживании. Среднее число клиентов в очереди на обслуживание определяется следующей формулой:

.

Среднее число находящихся в СМО клиентов (на обслуживании и в очереди):

.

Средняя продолжительность пребывания клиента (заявки) в очереди:

.

Средняя продолжительность пребывания клиента в СМО:

.



ЗАКЛЮЧЕНИЕ

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

Размещено на Allbest.ru