Примеры решения задач систем массового обслуживания

Требуется решить задачи 1–3. Исходные данные приведены в табл. 2–4.

Некоторые обозначения, применяемые в теории массового обслуживания, для формул:

n – число каналов в СМО;

λ – интенсивность входящего потока заявок П вх;

v – интенсивность выходящего потока заявок П вых;

μ – интенсивность потока обслуживания П об;

ρ – показатель нагрузки системы (трафик);

m – максимальное число мест в очереди, ограничивающее длину очереди заявок;

i – число источников заявок;

p к – вероятность k-го состояния системы;

p о – вероятность простаивания всей системы, т. е. вероятность того, что все каналы свободны;

p сист – вероятность принятия заявки в систему;

p отк – вероятность отказа заявке в принятии ее в систему;

р об – вероятность того, что заявка будет обслужена;

А – абсолютная пропускная способность системы;

Q – относительная пропускная способность системы;

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

Об – среднее число заявок под обслуживанием;

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

Оч – среднее время ожидания заявки в очереди;

Об – среднее время обслуживания заявки, относящееся только к обслуженным заявкам;

Сис – среднее время пребывания заявки в системе;

Ож – среднее время, ограничивающее ожидание заявки в очереди;

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

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

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

При решении задач массового обслуживания необходимо придерживаться нижеприведенной последовательности:

1) определение типа СМО по табл. 4.1;

2) выбор формул в соответствии с типом СМО;

3) решение задачи;

4) формулирование выводов по задаче.

1.Схема гибели и размножения. Мы знаем, что, имея в распоряжении размеченный граф состояний, можно легко написать уравнения Колмогорова для вероятностей состояний, а также написать и решить алгебраические уравнения для финальных вероятностей. Для некоторых случаев удается последние уравнения

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 ,…,S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний - правым и левым, а крайние состояния (S 0 , S n) - только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состоянии), существование вытекает из того, что из каждого состояния можно перейти в каждое другое, в число состояний конечно). Для первого состояния S 0 имеем:

(19.1)

Для второго состояния S 1:

В силу (19.1) последнее равенство приводится к виду

где k принимает все значения от 0 до п. Итак, финальные вероятности p 0 , p 1 , ..., р n удовлетворяют уравнениям

(19.2)

кроме того, надо учесть нормировочное условие

p 0 + p 1 + p 2 +…+ p n =1. (19.3)

Решим эту систему уравнений. Из первого уравнения (19.2)выразим p 1 через р 0 :

p 1 = p 0. (19.4)

Из второго, с учетом (19.4), получим:

(19.5)

Из третьего, с учетом (19.5),

(19.6)

и вообще, для любого k (от 1 до n ):

(19.7)

Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний р 0 , p 1 , ..., р n выражены через одну из них (р 0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку р 0:

отсюда получим выражение для р 0 :

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (19.4) - (19.7)). Заметим, что коэффициенты при р 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.

^ 2. Формула Литтла. Теперь мы выведем одну важную формулу, связывающую (для предельного, стационарного режима) среднее число заявок L сист, находящихся в системе массового обслуживания (т. е. обслуживаемых или стоящих в очереди), и среднее время пребывания заявки в системе W сист.

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

Обозначим: X(t} - число заявок, прибывших в СМО до момента t. Y (t ) - число заявок покинувших СМО

до момента t. И та, и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X (t )) и уходов заявок (Y(t)). Вид функций X(t) и Y(t) показан на рис. 19.2; обе линии - ступенчатые, верхняя - X(t), нижняя-Y(t). Очевидно, что для любого момента t их разность Z (t ) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО. Когда линии X(t) и Y(t) сливаются, в системе нет заявок.

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

L сист. = . (19.9) о

Но этот интеграл представляет собой не что иное, как площадь фигуры, заштрихованной на рис. 19.2. Разглядим хорошенько этот рисунок. Фигура состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т. д.). Обозначим эти времена t 1 , t 2 ,... Правда, под конец промежутка Т некоторые прямоугольники войдут в заштрихованную фигуру не полностью, а частично, но при достаточно большом Т эти мелочи не будут играть роли. Таким образом, можно считать, что

(19.10)

где сумма распространяется на все заявки, пришедшие за время Т.

Разделим правую и левую часть (.19.10) на длину интервала Т. Получим, с учетом (19.9),

L сист. = . (19.11)

Разделим и умножим правую часть (19.11) на интенсивность X:

L сист. = .

Но величина Тλ есть не что иное, как среднее число заявок, пришедших за время ^ Т. Если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист. Итак,

L сист. = λW сист. ,

W сист. = . (19.12)

Это и есть замечательная формула Литтла: для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.

Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди ^ W оч и среднее число заявок в очереди L оч:

W оч = . (19.13)

Для вывода достаточно вместо нижней линии на рис. 19.2 взять функцию U(t) - количество заявок, ушедших до момента t не из системы, а из очереди (если заявка, пришедшая в систему, не становится в очередь, а сразу идет под обслуживание, можно все же считать, что она становится в очередь, но находится в ней нулевое время).

Формулы Литтла (19.12) и (19.13) играют большую роль в теории массового обслуживания. К сожалению, в большинстве существующих руководств эти формулы (доказанные в общем виде сравнительно недавно) не приводятся 1).

§ 20. Простейшие системы массового обслуживания и их характеристики

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

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

1) В популярной книжке дан несколько иной, по сравнению с вышеизложенным, вывод формулы Литтла. Вообще, знакомство с этой книжкой («Беседа вторая») полезно для первоначального ознакомления с теорией массового обслуживания.

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

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

^ 1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;

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

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

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

^ Р отк - вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;

k - среднее число занятых каналов.

Решение. Состояния системы ^ S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

S 0 - в СМО нет ни одной заявки,

S 1 - в СМО находится одна заявка (один канал занят, остальные свободны),

S k - в СМО находится k заявок (k каналов заняты, остальные свободны),

S n - в СМО находится п заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим этот граф - проставим у стрелок интенсивности потоков событий. Из S 0 в S 1 систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S 0 в S 1). Тот же поток заявок переводит

Систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии ^ S 1 (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S 1 → S 0 интенсивность μ. Теперь представим себе, что система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами - kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.

А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:

Члены разложения будут представлять собой коэффициенты при р 0 в выражениях для p 1

Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим

λ/μ = ρ (20.3)

И будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл-среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:

Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга - в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.

Таким образом, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем ^ Р отк . - вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все п каналов были заняты, значит,

Р отк = р n = . (20.6)

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

Q = 1 – P отк. = 1 - (20.7)

Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:

A = λQ = λ . (20.8)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р 0 р 1 , ..., р n:

k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n .

Подставляя сюда выражения (20.5) для р k , (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i .шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно

k = A/μ, (20.9)

или, учитывая (20.8),

k = (20.10)

Рекомендуем читателю самостоятельно решить пример. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t об = 2 (мин.), все потоки событий (как и во всем этом параграфе) - простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P отк, k. На всякий случай сообщаем ответы: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, р 3 = 9/26 ≈ 0,346,

А ≈ 0,981, Q ≈ 0,654, P отк ≈ 0,346, k ≈ 1,96.

Из ответов видно, между прочим, что наша СМО в значительной мере перегружена: из трех каналов занято в среднем около двух, а из поступающих заявок около 35% остаются не обслуженными. Предлагаем читателю, если он любопытен и неленив, выяснить: сколько потребуется каналов для того, чтобы удовлетворить не менее 80% поступающих заявок? И какая доля каналов при этом будет простаивать?

Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому и любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.

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

Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживании имеет интенсивность μ, обратную среднему времени обслуживания заявки t об. Требуется найти финальные вероятности состояний СМО, а также характеристики ее эффективности:

L сист. - среднее число заявок в системе,

W сист. - среднее время пребывания заявки в системе,

^ L оч - среднее число заявок в очереди,

W оч - среднее время пребывания заявки в очереди,

P зан - вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности:

в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому А = λ, по той же причине Q = 1.

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

S 0 - канал свободен,

S 1 - канал занят (обслуживает заявку), очереди нет,

S 2 - канал занят, одна заявка стоит в очереди,

S k - канал занят, k - 1 заявок стоят в очереди,

Теоретически число состояний ничем не ограничено (бесконечно). Граф состоянии имеет вид, показанный на рис. 20.2. Это - схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью λ переводит систему слева направо, а справа налево - поток обслуживании с интенсивностью μ.

Прежде всего спросим себя, а существуют ли в этом случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t → ∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если ρ строго меньше единицы (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t → ∞ растет неограниченно. Особенно «непонятным» кажется этот факт при ρ = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При ρ = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживании стать хотя бы чуточку случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!

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

p 0 = -1 =

= (1 + р + р 2 + ... + р k +… .) -1 . (20.11)

Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р 0 , p 1 , ..., p k , ... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - ρ. (20.12)

Вероятности р 1 , р 2 , ..., р k , ... найдутся по формулам:

p 1 = ρp 0 , p 2 = ρ 2 p 0 ,…,p k = ρp 0 , ...,

Откуда, с учетом (20.12), найдем окончательно:

p 1 = ρ (1 - ρ), p 2 = ρ 2 (1 - ρ), . . . , p k = ρ k (1 - ρ), . . .(20.13)

Как видно, вероятности p 0 , p 1 , ..., p k , ... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р 0 - вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.

Найдем среднее число заявок в СМО ^ L сист . . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p 0 , р 1 , р 2 , ..., p k , ... Ее математическое ожидание равно

L сист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k +…= (20.14)

(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).

Подставим в формулу (20.14) выражение для p k (20.13):

L сист. =

Теперь вынесем за знак суммы ρ (1-ρ):

L сист. = ρ (1-ρ)

Тут мы опять применим «маленькую хитрость»: k ρ k -1 есть не что иное, как производная по ρ от выражения ρ k ; значит,

L сист. = ρ (1-ρ)

Меняя местами операции дифференцирования п суммирования, получим:

L сист. = ρ (1-ρ) (20.15)

Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма

равна , а ее производная .Подставляя это выражение в (20.15), получим:

L сист = . (20.16)

Ну, а теперь применим формулу Литтла (19.12) и найдем среднее время пребывания заявки в системе:

W сист = (20.17)

Найдем среднее число заявок в очереди L оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L оч равно среднему числу заявок в системе L сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р зан). Очевидно, Р зан равно единице минус вероятность р 0 того, что канал свободен:

Р зан = 1 - р 0 = ρ. (20.18)

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

^ L об = ρ, (20.19)

L оч = L сист – ρ =

и окончательно

L оч = (20.20)

По формуле Литтла (19.13) найдем среднее время пребывания заявки в очереди:

(20.21)

Таким образом, все характеристики эффективности СМО найдены.

Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование)

состава длится случайное (показательное) время со средним значением t об = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее, число составов l сист, связанных со станцией, среднее время W сист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число L оч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время W оч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях L внеш и среднее время этого ожидания W внеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: L сист. = 2 (состава), W сист. = 1 (час), L оч = 4/3 (состава), W оч = 2/3 (часа), L внеш = 16/27 (состава), W внеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а : Ш ≈ 14,2а .

^ 3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью. Нумерация состояний - опять по числу заявок, находящихся в системе:

S 0 - в СМО заявок нет (все каналы свободны),

S 1 - занят один канал, остальные свободны,

S 2 - занято два канала, остальные свободны,

S k - занято k каналов, остальные свободны,

S n - заняты все п каналов (очереди нет),

S n+1 - заняты все n каналов, одна заявка стоит в очереди,

S n+r - заняты вес п каналов, r заявок стоит в очереди,

Граф состояний показан на рис. 20.3. Предлагаем читателю самому обдумать и обосновать значения интенсивностей, проставленных у стрелок. Граф рис. 20.3

λ λ λ λ λ λ λ λ λ

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n <1. Если ρ/n ≥ 1, очередь растет до бесконечности.

Предположим, что условие ρ/n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0 будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем ρ/n . Суммируя ее, найдем

(20.22)

Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k == λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L сист и среднее число заявок в очереди L оч. Из них легче вычислить второе, по формуле

L оч =

выполняя соответствующие преобразования по образцу задачи 2

(с дифференцированием ряда), получим:

L оч = (20.23)

Прибавляя к нему среднее число заявок под обслуживанием (оно же - среднее число занятых каналов) k = ρ, получим:

L сист = L оч + ρ. (20.24)

Деля выражения для L оч и L сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

(20.25)

А теперь решим любопытный пример. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: λ А = λ В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ А + λ В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна - только в пункт А , другая - только в пункт В. Разумность этого предложения вызывает споры - кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий - простейшие (на качественной стороне выводов это не скажется).

Ну, что же, возьмемся за дело. Рассмотрим два варианта организации продажи билетов - существующий и предлагаемый.

Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W оч ≈ 8,54 (мин.).

Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L оч = 8,1.

Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L оч на λ = 0,45, получим W оч ≈ 18 (минут).

Вот так рационализация! Вместо того чтобы уменьшиться, и средняя длина очереди, и среднее время ожидания в ней увеличились!

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

Ну, ладно,- готов согласиться читатель,- увеличение можно объяснить, но почему оно такое существенное? Нет ли тут ошибки в расчете?

И на этот вопрос мы ответим. Ошибки нет. Дело в том, что в нашем примере обе СМО работают на пределе своих возможностей; стоит немного увеличить время обслуживания (т. е. уменьшить μ), как они уже перестанут справляться с потоком пассажиров, и очередь начнет неограниченно возрастать. А «лишние простои» кассира в каком-то смысле равносильны уменьшению его производительности μ.

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

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

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

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

^ 4. Одноканальная СМО с ограниченной очередью. Задача отличается от задачи 2 только тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка приходит в момент, когда все места в очереди заняты, она покидает СМО не обслуженной (получает отказ).

Надо найти финальные вероятности состояний (кстати, они в этой задаче существуют при любом ρ - ведь число состояний конечно), вероятность отказа Р отк, абсолютную пропускную способность А, вероятность того, что канал занят Р зан, среднюю длину очереди L оч, среднее число заявок в СМО L сист , среднее время ожидания в очереди W оч , среднее время пребывания заявки в СМО W сист. При вычислении характеристик очереди можно пользоваться тем же приемом, какой мы применяли в задаче 2, с той разницей, что суммировать надо не бесконечную прогрессию, а конечную.

^ 5. Замкнутая СМО с одним каналом и m источниками заявок. Для конкретности поставим задачу в следующей форме: один рабочий обслуживает т станков, каждый из которых время от времени требует наладки (исправления). Интенсивность потока требований каждого работающего станка равна λ. Если станок вышел из строя в момент, когда рабочий свободен, он сразу же поступает на обслуживание. Если он вышел из строя в момент, когда рабочий занят, он становится в очередь и ждет, пока рабочий освободится. Среднее время наладки станка t об = 1/μ. Интенсивность потока заявок, поступающих к рабочему, зависит от того, сколько станков работает. Если работает k станков, она равна k λ. Найти финальные вероятности состояний, среднее число работающих станков и вероятность того, что рабочий будет занят.

Заметим, что и в этой СМО финальные вероятности

будут существовать при любых значениях λ и μ = 1/t об, так как число состояний системы конечно.

1. Одноканальная СМО с отказами.

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

Интенсивность потока автомобилей = 1,0 (автомобиль в час).

Средняя продолжительность обслуживания - 1,8 часа.

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

Требуется определить в установившемся режиме предельные значения:

Относительной пропускной способности q ;

Абсолютной пропускной способности А ;

Вероятности отказа P отк .

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

2. Одноканальная СМО с ожиданием

Характеристика системы

Ø СМО имеет один канал.

Ø Входящий поток заявок на обслуживание - простейший поток с интенсивностью.

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

Ø Длительность обслуживания - случайная величина, подчиненная показательному закону распределения.

Ø Поток обслуживания является простейшим пуассоновским потоком событий.

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

Граф состояний

Состояния СМО имеют следующую интерпретацию:

S 0 - «канал свободен»;

S 1 - «канал занят» (очереди нет);

S 2 - «канал занят» (одна заявка стоит в очереди);

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

Sn - «канал занят» (n -1 заявок стоит в очереди);

SN - «канал занят» (N - 1 заявок стоит в очереди).

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

Решением системы уравнений является:

3. Одноканальная СМО с ограниченной очередью.

Длина очереди:(N - 1)

Характеристики системы:

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

2. Относительная пропускная способность системы:

3. Абсолютная пропускная способность системы:

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

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

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

7. Среднее число заявок (клиентов) в очереди (длина очереди):

Пример.

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

Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3 [(N - 1) = 3]. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится.

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

Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час.

4. Одноканальная СМО с ожиданием

без ограничения на длину очереди

Условия функционирования СМО остаются без изменений с учетом того, что N .

Стационарный режим функционирования такой СМО существует:

для любого n = 0, 1, 2, ... и когда λ < μ .

Система уравнений, описывающих работу СМО:

Решение системы уравнений имеет вид:

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

3. Среднее число клиентов в очереди на обслуживании:

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

Пример.

Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, не ограниченно. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность λ = 0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час.

Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме.

В результате решения задачи необходимо определить финальные значения следующих вероятностных характеристик:

ü вероятности состояний системы (поста диагностики);

ü среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);

ü среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);

ü среднее число автомобилей в очереди на обслуживании;

ü среднюю продолжительность пребывания автомобиля в очереди.

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

μ = 0,952; ψ = 0,893.

2. Предельные вероятности состояния системы:

P 0 (t ) определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В примере эта доля составляет 10,7%, так как P 0 (t ) = 0,107.

3. Среднее число автомобилей, находящихся в системе

(на обслуживании и в очереди):

4. Средняя продолжительность пребывания клиента в системе

5. Среднее число автомобилей в очереди на обслуживание:

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

7. Относительная пропускная способность системы:

q = 1, т. е. каждая заявка, пришедшая в систему, будет обслужена.

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

Презентационное оформление материала представлено в файле «ТМО»

Вопросы и задачи

(по Афанасьеву М.Ю. )

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

1) многоканальную однофазовую с ограниченной популяцией;

2) одноканальную однофазовую с неограниченной популяцией;

3) одноканальную многофазовую с ограниченной популяцией;

4) одноканальную однофазовую с ограниченной популяцией;

5) многоканальную однофазовую с неограниченной популяцией.

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

1) нормальное;

2) экспоненциальное;

3) пуассоновское;

4) биномиальное;

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

1) фиксированным или переменным;

2) ограниченным или неограниченным;

3) известным или неизвестным;

4) случайным или детерминированным;

5) ничто из вышеуказанного не является верным.

Вопрос 4. Двумя основными параметрами, которые определяют конфигурацию системы массового обслуживания, являются:

1) темп поступления и темп обслуживания;

2) длина очереди и правило обслуживания;

3) распределение времени между заявками и распределение времени обслуживания;

4) число каналов и число фаз обслуживания;

5) ничто из вышеуказанного не является верным.

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

1) нормальное;

2)экспоненциальное;

3) пуассоновское;

4) биномиальное;

5) ничто из вышеуказанного не является верным.

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

1) многоканальную с ограниченной популяцией;

2) одноканальную с неограниченной популяцией;

3) одноканальную с ограниченной популяцией;

4) одноканальную с ограниченной очередью;

5) многоканальную с неограниченной популяцией.

Ответы на вопросы : 1 -4, 2 - 3, 3 -2, 4 -4, 5 -2, 6 -1.

СЕТЕВОЕ ПЛАНИРОВАНИЕ И УПРАВЛЕНИЕ

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

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

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

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

Цели

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

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

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

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

После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь определять и использовать для экономи­ческого анализа следующие понятия:

Система массового обслуживания;

Очередь;

Темп поступления заявок;

Темп обслуживания;

Среднее время, которое заявка проводит в очереди;

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

Среднее время, которое заявка проводит в системе обслужи­вания;

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

Издержки функционирования системы обслуживания;

Издержки ожидания.

Модели

Классификационные признаки систем массового обслуживания.

В системах массового обслуживания различают три основных эта­па, которые проходит каждая заявка:

1) появление заявки на входе в систему;

2) прохождение очереди;

3) процесс обслуживания, после которого заявка покидает систему.

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

Характеристики входа:

1) число заявок на входе (размер популяции);

2) режим поступления заявок в систему обслуживания;

3) поведение клиентов.

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

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

Режим поступления заявок, в систему обслуживания. Заявки могут поступать в систему обслуживания в соответствии с опреде­ленным графиком (например, один пациент на прием к стомато­логу каждые 15 мин, один автомобиль на конвейере каждые 20 мин) или случайным образом. Появления клиентов считаются Случай­ными, если они независимы друг от друга и точно непредсказу­емы. Часто в задачах массового обслуживания число появлений в единицу времени может быть оценено с помощью пуассоновского распределения вероятностей. При заданном темпе поступления (например, два клиента в час или четыре грузовика в минуту) дискретное распределение Пуассона описывается следующей фор­мулой:

Где Р (х) - вероятность поступления Х заявок в единицу вре­мени;

Х - число заявок в единицу времени;

L - среднее число заявок в единицу времени (темп по­ступления заявок);

Соответствующие значения вероятностей Р(х) нетрудно опре­делить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок - два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки - около 0,27, двух - также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре - с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или бо­лее, близка нулю.

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

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

Жизнь значительно сложнее. На практике клиенты могут по­кинуть очередь потому, что она оказалась слишком длинной. Может возникнуть и другая ситуация: клиенты дожидаются сво­ей очереди, но по каким-то причинам уходят необслуженными. Эти случаи также являются предметом теории массового обслу­живания, однако здесь не рассматриваются.

Характеристики очереди:

2) правило обслуживания.

Длина очереди. Длина может быть ограничена либо не ограни­чена. Длина очереди (очередь) Ограничена, если она по каким-либо причинам (например, из-за физических ограничений) не может увеличиваться до бесконечности. Если очередь достигает своего максимального размера, то следующая заявка в систему не допускается и происходит отказ. Длина очереди Не ограничена, Если в очереди может находиться любое число заявок. Например, очередь автомобилей на бензозаправке.

Правило обслуживания. Большинство реальных систем исполь­зует правило «первым пришел - первым ушел» (FIFO - first in, first out). В некоторых случаях, например в приемном покое боль­ницы, в дополнение к этому правилу могут устанавливаться раз­личные Приоритеты. Пациент с инфарктом в критическом со­стоянии, по-видимому, будет иметь приоритет в обслуживании по сравнению с пациентом, сломавшим палец. Порядок запуска компьютерных программ - другой пример установления приорите­тов в обслуживании.

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

1) конфигурация системы обслуживания (число каналов и чис­ло фаз обслуживания);

2) режим обслуживания.

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

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

На рис. 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. В многоканальной системе для обслуживания открыты два ка­нала или более. Предполагается, что клиенты ожидают в общей очереди и обращаются в первый освободившийся канал обслужи­вания.

Пример такой многоканальной однофазовой системы можно увидеть во многих банках: из общей очереди клиенты обращают­ся в первое освободившееся окошко для обслуживания.

В многоканальной системе поток заявок подчиняется Пуассоновскому закону, а время обслуживания - Экспоненциальному. Приходящий первым обслуживается первым, и все каналы обслу­живания работают в одинаковом темпе. Формулы, описывающие модель В, достаточно сложны для использования. Для расчета параметров многоканальной системы обслуживания удобно ис­пользовать соответствующее программное обеспечение.

Время нахождения заявки в очереди;

Время нахождения заявки в системе.

III. Модель С- модель с постоянным временем обслуживания M/ D/ 1.

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

Формулы, описывающие модель С:

- средняя длина очереди;

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

Среднее число клиентов в системе;

Среднее время ожидания в системе.

IV. Модель D - модель с ограниченной популяцией.

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

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

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

Как частный случай модели с ограниченной очередью можно рассматривать Модель с отказами, если количество мест в очере­ди сократить до нуля.

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

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

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

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

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

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

Примерами СМО являются кассы, АЗС, аэропорты, продавцы, парикмахеры, врачи, телефонные станции и другие объекты, в которых осуществляется обслуживание тех или иных заявок.

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

Главная особенность задач данного класса – явная зависимость результатов анализ и получаемых рекомендаций от двух внешних факторов: частоты поступления и сложности заказов (а значит и времени их исполнения).

Предмет теории массового обслуживания – это установление зависимости между характером потока заявок, производительностью отдельного канала обслуживания, числом каналов и эффективностью обслуживания.

В качестве характеристик СМО рассматриваются:

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

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

3.1 Модели систем массового обслуживания.

Каждую СМО может характеризовать выражением: (a / b / c) : (d / e / f) , где

a - распределение входного потока заявок;

b - распределение выходного потока заявок;

c – конфигурация обслуживающего механизма;

d – дисциплина очереди;

e – блок ожидания;

f – емкость источника.

Теперь рассмотрим подробнее каждую характеристику.

Входной поток заявок – количество поступивших в систему заявок. Характеризуется интенсивностью входного потока l .

Выходной поток заявок – количество обслуженных системой заявок. Характеризуется интенсивностью выходного потока m .

Конфигурация системы подразумевает общее число каналов и узлов обслуживания. СМО может содержать:

1. один канал обслуживания (одна взлетно-посадочная полоса, один продавец);
2. один канал обслуживания, включающий несколько последовательных узлов (столовая, поликлиника, конвейер);
3. несколько однотипных каналов обслуживания, соединенных параллельно (АЗС, справочная служба, вокзал).

Таким образом, можно выделить одно- и многоканальные СМО.

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

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

Дисциплина очереди – это правило обслуживания заявок из очереди. К основным типам очереди можно отнести следующие:

1. ПЕРППО (первым пришел – первым обслуживаешься) – наиболее распространенный тип;
2. ПОСППО (последним пришел – первым обслуживаешься);
3. СОЗ (случайный отбор заявок) – из банка данных.
4. ПР – обслуживание с приоритетом.

Длина очереди может быть

• неограничена – тогда говорят о системе с чистым ожиданием;
• равна нулю – тогда говорят о системе с отказами;
• ограничена по длине (система смешанного типа).

Блок ожидания – «вместимость» системы – общее число заявок, находящихся в системе (в очереди и на обслуживании). Таким образом, е=с+ d .

Емкость источника , генерирующего заявки на обслуживание – это максимальное число заявок, которые могут поступить в СМО. Например, в аэропорту емкость источника ограничена количеством всех существующих самолетов, а емкость источника телефонной станции равна количеству жителей Земли, т.е. ее можно считать неограниченной.

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

3.2 Входной поток требований.

С каждым отрезком времени [a , a + T ], свяжем случайную величину Х , равную числу требований, поступивших в систему за время Т .

Поток требований называется стационарным , если закон распределения не зависит от начальной точки промежутка а , а зависит только от длины данного промежутка Т . Например, поток заявок на телефонную станцию в течение суток (Т =24 часа) нельзя считать стационарным, а вот с 13 до 14 часов (Т =60 минут) – можно.

Поток называется без последействия , если предыстория потока не влияет на поступления требований в будущем, т.е. требования не зависят друг от друга.

Поток называется ординарным , если за очень короткий промежуток времени в систему может поступить не более одного требования. Например, поток в парикмахерскую – ординарный, а в ЗАГС – нет. Но, если в качестве случайной величины Х рассматривать пары заявок, поступающих в ЗАГС, то такой поток будет ординарным (т.е. иногда неординарный поток можно свести к ординарному).

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

Основная теорема. Если поток – простейший, то с.в. Х [ a . a + T ] распределена по закону Пуассона, т.е. .

Следствие 1 . Простейший поток также называется пуассоновским.

Следствие 2 . M (X )= M (Х [ a , a + T ] )= l T , т.е. за время Т l T заявок. Следовательно, за одну единицу времени в систему поступает в среднем l заявок. Эта величина и называется интенсивностью входного потока.

Рассмотрим ПРИМЕР.

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

Решение.

По условию задачи, l =3, Т =2 дня, входной поток пуассоновский, n ³5. при решении удобно ввести противоположное событие, состоящее в том, что за время Т поступит меньше 5 заявок. Следовательно, по формуле Пуассона, получим

^

3.3 Состояние системы. Матрица и граф переходов.

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

Е 0 – все каналы свободны;

Е 1 – занят один канал;

Е n – заняты все каналы;

Е n +1 – заняты все каналы и одна заявка в очереди;

Е n + m – заняты все каналы и все места в очереди.

Аналогичная система с отказами может находиться в состояниях E 0 – E n .

Для СМО с чистым ожиданием существует бесконечное множество состояний. Таким образом, состояниеE n СМО в момент времени t – это количество n заявок (требований), находящихся в системе в данный момент времени, т.е. n = n (t ) – случайная величина, E n (t ) – исходы этой случайной величины, а P n (t ) – вероятность пребывания системы в состоянии E n .

С состоянием системы мы уже знакомы. Отметим, что не все состояния системы равнозначны. Состояние системы называется источником , если система может выйти из этого состояния, но не может в него вернуться. Состояние системы называется изолированным, если система не может выйти из этого состояния или в него войти.

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

Рисунок 3.1 – граф переходов

Сост.	Е 0	Е 1	Е 2
Е 0	Р 0,0	Р 0,1	Р 0,2
Е 1	Р 1,0	Р 1,1	Р 1,2
Е 2	Р 2,0	Р 2,2	Р 2,2

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

Так как система обязательно перейдет из одного

состояния в другое, то сумма вероятностей в каждой строке всегда равна единице.

3.4 Одноканальные СМО.

3.4.1 Одноканальные СМО с отказами.

Будем рассматривать системы, удовлетворяющие требованиям:

(Р/Е/1):(–/1/¥) . Предположим также, что время обслуживания требования не зависит от количества требований, поступивших в систему. Здесь и далее «Р» означает, что входной поток распределен по закону Пуассона, т.е. простейший, «Е» означает, что выходной поток распределен по экспоненциальному закону. Также здесь и далее основные формулы даются без доказательства.

Для такой системы возможно два состояния: Е 0 – система свободна и Е 1 – система занята. Составим матрицу переходов. Возьмем D t – бесконечно малый промежуток времени. Пусть событие А состоит в том, что в систему за время D t поступило одно требование. Событие В состоит в том, что за время D t обслужено одно требование. Событие А i , k – за время D t система перейдет из состояния E i в состояние E k . Так как l – интенсивность входного потока, то за время D t в систему в среднем поступает l*D t требований. То есть, вероятность поступления одного требования Р(А)= l* D t , а вероятность противоположного событияР(Ā)=1- l*D t . Р(В)= F (D t )= P (b < D t )=1- e - m D t = m D t – вероятность обслуживания заявки за время D t . Тогда А 00 – заявка не поступит или поступит, но будет обслужена. А 00 =Ā+А* В. Р 00 =1- l*D t . (мы учли, что(D t ) 2 – бесконечно малая величина)

А 01 – заявка поступит, но не будет обслужена. А 01 =А* . Р 01 = l*D t .

А 10 – заявка будет обслужена и новой не будет. А 10 =В* Ā. Р 10 = m*D t .

А 11 – заявка не будет обслужена или поступит новая, которая еще не обслужена. А 11 =+В* А. Р 01 =1- m*D t .

Таким образом, получим матрицу переходов:

Сост.	Е 0	Е 1
Е 0	1-l* Dt	l* Dt
Е 1	m* Dt	1-m* Dt

Вероятность простоя и отказа системы.

Найдем теперь вероятность нахождения системы в состоянии Е 0 в любой момент времени t (т.е. р 0 ( t ) ). График функции
изображен на рисунке 3.2.

Асимптотой графика является прямая
.

Очевидно, начиная с некоторого момента t ,

1

Рисунок 3.2

Окончательно получим, что
и
, где р 1 (t ) – вероятность того, что в момент времени t система занята (т.е. находится в состоянии Е 1 ).

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

Стационарный режим работы и коэффициент загрузки системы.

Если вероятность нахождения системы в состоянии Е k , т.е. Р k (t ), не зависит от времени t , то говорят, что в СМО установился стационарный режим работы. При этом величина
называется коэффициентом загрузки системы (или приведенной плотностью потока заявок). Тогда для вероятностейр 0 (t ) ир 1 (t ) получаем следующие формулы:
,
. Можно также сделать вывод:чем больше коэффициент загрузки системы, тем больше вероятность отказа системы (т.е. вероятность того, что система занята).

На автомойке один блок для обслуживания. Автомобили прибывают по пуассоновскому распределению с интенсивностью 5 авто/час. Среднее время обслуживания одной машины – 10 минут. Найти вероятность того, что подъехавший автомобиль найдет систему занятой, если СМО работает в стационарном режиме.

Решение. По условию задачи, l =5, m y =5/6. Надо найти вероятность р 1 – вероятность отказа системы.
.

3.4.2 Одноканальные СМО с неограниченной длиной очереди.

Будем рассматривать системы, удовлетворяющие требованиям: (Р/Е/1):(d/¥/¥). Система может находиться в одном из состояний E 0 , …, E k , … Анализ показывает, что через некоторое время такая система начинает работать в стационарном режиме, если интенсивность выходного потока превышает интенсивность входного потока (т.е. коэффициент загрузки системы меньше единицы). Учитывая это условие, получим систему уравнений

решая которую найдем, что . Таким образом, при условии, что y <1, получим
Окончательно,
и
– вероятность нахождения СМО в состоянии Е k в случайный момент времени.

Средние характеристики системы.

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

• n – количество требований, находящихся в СМО (в очереди и на обслуживании);
• v – длину очереди;
• w – время ожидания начала обслуживания;
• w 0 – общее время нахождения в системе.

Нас будут интересовать средние характеристики (т.е. берем математическое ожидание от рассматриваемых случайных величин, и помним, что y <1).

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

– средняя длина очереди.

– среднее время ожидания начала обслуживания, т.е. время ожидания в очереди.

– среднее время, которое заявка проводит в системе – в очереди и на обслуживании.

На автомойке один блок для обслуживания и есть место для очереди. Автомобили прибывают по пуассоновскому распределению с интенсивностью 5 авто/час. Среднее время обслуживания одной машины – 10 минут. Найти все средние характеристики СМО.

Решение. l =5, m =60мин/10мин = 6. Коэффициент загрузки y =5/6. Тогда среднее число автомобилей в системе
, средняя длина очереди
, среднее время ожидания начала обслуживания
часа = 50 мин, и, наконец, среднее время нахождения в системе
час.

3.4.3 Одноканальные СМО смешанного типа.

Предположим, что длина очереди составляет m требований. Тогда, для любого s £ m , вероятность нахождения СМО в состоянии Е 1+ s , вычисляется по формуле
, т.е. одна заявка обслуживается и еще s заявок – в очереди.

Вероятность простоя системы равна
,

а вероятность отказа системы -
.

Даны три одноканальные системы, для каждой l =5, m =6. Но первая система – с отказами, вторая – с чистым ожиданием, а третья – с ограниченной длиной очереди, m =2. Найти и сравнить вероятности простоя этих трех систем.

Решение. Для всех систем коэффициент загрузки y =5/6. Для системы с отказами
. Для системы с чистым ожиданием
. Для системы с ограниченной длиной очереди
. Вывод очевиден: чем больше заявок находится в очереди, тем меньше вероятность простоя системы.

3.5 Многоканальные СМО.

3.5.1 Многоканальные СМО с отказами.

Будем рассматривать системы (Р/Е/s):(-/s/¥) в предположении, что время обслуживания не зависит от входного потока и все линии работают независимо. Многоканальные системы, помимо коэффициента загрузки, можно также характеризовать коэффициентом
, где s – число каналов обслуживания. Исследуя многоканальные СМО, получим следующие формулы (формулы Эрлáнга ) для вероятности нахождения системы в состоянии Е k в случайный момент времени:

, k=0, 1, …

Функция стоимости.

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

Для поиска оптимального варианта надо найти (и это можно сделать) минимальное значение функции стоимости: С(s ) = с 1* l * p s +с 2* , график которой представлен на рисунке 3.3:

Рисунок 3.3

Поиск минимального значения функции стоимости состоит в том, что мы находим ее значения сначала дляs =1, затем для s =2, потом для s =3, и т.д. до тех пор, пока на каком-то шаге значение функции С(s ) не станет больше предыдущего. Это и означает, что функция достигла своего минимума и начала расти. Ответом будет то число каналов обслуживания (значение s ), для которого функция стоимости минимальна.

ПРИМЕР.

Сколько линий обслуживания должна содержать СМО с отказами, если l =2треб/час, m =1треб/час, штраф за каждый отказ составляет 7 тыс.руб., стоимость простоя одной линии – 2 тыс.руб. в час?

Решение. y = 2/1=2. с 1 =7, с 2 =2.

Предположим, что СМО имеет два канала обслуживания, т.е. s =2. Тогда
. Следовательно, С(2) = с 1 *l* p 2 +с 2 *(2- y* (1-р 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Предположим, что s =3. Тогда
, С(3) = с 1 *l* p 3 +с 2 *
=5.79.

Предположим, что имеется четыре канала, т.е. s =4. Тогда
,
, С(4) = с 1 *l* p 4 +с 2 *
=5.71.

Предположим, что СМО имеет пять каналов обслуживания, т.е. s =5. Тогда
, С(5) = 6.7 – больше предыдущего значения. Следовательно, оптимальное число каналов обслуживания – четыре.

3.5.2 Многоканальные СМО с очередью.

Будем рассматривать системы (Р/Е/s):(d/d+s/¥) в предположении, что время обслуживания не зависит от входного потока и все линии работают независимо. Будем говорить, что в системе установилсястационарный режим работы , если среднее число поступающих требований меньше среднего числа требований, обслуженных на всех линиях системы, т.е. l

P(w>0) – вероятность ожидания начала обслуживания,
.

Последняя характеристика позволяет решать задачу об определении оптимального числа каналов обслуживания с таким расчетом, чтобы вероятность ожидания начала обслуживания была меньше заданного числа. Для этого достаточно просчитать вероятность ожидания последовательно при s =1, s =2, s =3 и т.д.

ПРИМЕР.

СМО – станция скорой помощи небольшого микрорайона. l =3 вызова в час, а m = 4 вызова в час для одной бригады. Сколько бригад необходимо иметь на станции, чтобы вероятность ожидания выезда была меньше 0.01?

Решение. Коэффициент загрузки системы y =0.75. Предположим, что в наличие имеется две бригады. Найдем вероятность ожидания начала обслуживания при s =2.
,
.

Предположим наличие трех бригад, т.е. s =3. По формулам получим, что р 0 =8/17, Р(w >0)=0.04>0.01 .

Предположим, что на станции четыре бригады, т.е. s =4. Тогда получим, что р 0 =416/881, Р(w >0)=0.0077<0.01 . Следовательно, на станции должно быть четыре бригады.

3.6 Вопросы для самоконтроля

1. Предмет и задачи теории массового обслуживания.
2. СМО, их модели и обозначения.
3. Входной поток требований. Интенсивность входного потока.
4. Состояние системы. Матрица и граф переходов.
5. Одноканальные СМО с отказами.
6. Одноканальные СМО с очередью. Характеристики.
7. Стационарный режим работы. Коэффициент загрузки системы.
8. Многоканальные СМО с отказами.
9. Оптимизация функции стоимости.
10. Многоканальные СМО с очередью. Характеристики.

3.7 Упражнения для самостоятельной работы

1. Закусочная на АЗС имеет один прилавок. Автомобили прибывают в соответствии с пуассоновским распределением, в среднем 2 автомобиля за 5 минут. Для выполнения заказа в среднем достаточно 1.5 минуты, хотя продолжительность обслуживания распределена по экспоненциальному закону. Найти: а) вероятность простоя прилавка; b) средние характеристики; c) вероятность того, что количество прибывших автомобилей будет не менее 10.
2. Рентгеновский аппарат позволяет обследовать в среднем 7 человек в час. Интенсивность посетителей составляет 5 человек в час. Предполагая стационарный режим работы, определить средние характеристики.
3. Время обслуживания в СМО подчиняется экспоненциальному закону,
   m = 7требований в час. Найти вероятность того, что а) время обслуживания находится в интервале от 3 до 30 минут; b) требование будет обслужено в течение одного часа. Воспользоваться таблицей значений функции е х .
4. В речном порту один причал, интенсивность входного потока – 5 судов в день. Интенсивность погрузочно-разгрузочных работ – 6 судов в день. Имея в виду стационарный режим работы, определить все средние характеристики системы.
5. l =3, m =2, штраф за каждый отказ равен 5, а стоимость простоя одной линии равна 2?
6. Какое оптимальное число каналов обслуживания должна иметь СМО, если l =3, m =1, штраф за каждый отказ равен 7, а стоимость простоя одной линии равна 3?
7. Какое оптимальное число каналов обслуживания должна иметь СМО, если l =4, m =2, штраф за каждый отказ равен 5, а стоимость простоя одной линии равна 1?
8. Определить число взлетно-посадочных полос для самолетов с учетом требования, что вероятность ожидания должна быть меньше, чем 0.05. При этом интенсивность входного потока 27 самолетов в сутки, а интенсивность их обслуживания – 30 самолетов в сутки.
9. Сколько равноценных независимых конвейерных линий должен иметь цех, чтобы обеспечить ритм работы, при котором вероятность ожидания обработки изделий должна быть меньше 0.03 (каждое изделие выпускается одной линией). Известно, что интенсивность поступления заказов 30 изделий в час, а интенсивность обработки изделия одной линией – 36 изделий в час.
10. Непрерывная случайная величина Х распределена по показательному закону с параметром l=5. Найти функцию распределения, характеристики и вероятность попадания с.в. Х в интервал от 0.17 до 0.28.
11. Среднее число вызовов, поступающих на АТС за одну минуту, равно 3. Считая поток пуассоновским, найти вероятность того, что за 2 минуты поступит: а) два вызова; б) меньше двух вызовов; в) не менее двух вызовов.
12. В ящике 17 деталей, из которых 4 – бракованные. Сборщик наугад извлекает 5 деталей. Найти вероятность того, что а) все извлеченные детали – качественные; б) среди извлеченных деталей 3 бракованных.
13. Сколько каналов должна иметь СМО с отказами, если l =2треб/час, m =1треб/час, штраф за каждый отказ составляет 8т.руб., стоимость простоя одной линии – 2т.руб. в час?

Простейший поток и применение практических задач.

Нестационарные пуассоновские потоки.

Потоки с ограниченными последствиями (потоки Пальма).

Потоки восстановления.

1. Введение.

1.1. Историческая справка.

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

Первые задачи теории систем массового обслуживания (ТСМО) были рассмотрены сотрудником Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878- 1929г) в период между 1908 и 1922гг. Эти задачи были вызваны к жизни стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, морских и речных портов, магазинов, терминальных классов, электронных вычислительных комплексов, радиолокационных станций и т.д. может быть описана в рамках ТСМО.

1.2. Примеры систем массового обслуживания. Анализ задач ТСМО.

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

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

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

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

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

Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.

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

Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.

Пример 5 . На рис 1.1. изображена структурная схема типичной системы массового обслуживания – ремонтного предприятия (например, по ремонту ПЭВМ). Порядок ее работы ясен из схемы и не требует разъяснений.

рис 1.1.

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

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

1. условия “двойной” случайности –

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

2)проблема бича нашего времени – очередей: судов перед шлюзами, машин перед прилавками, задач на входе процессоров вычислительного комплекса и т.д.

А.К. Эрланг обратил внимание на то, что СМО могут быть разделены на два типа, а именно: на системы с ожиданием и системы с потерями. В первом случае – заявка, поступившая на вход системы “ждет” очереди на выполнение, во втором – она из-за занятости канала обслуживания получает отказ и теряется для СМО.

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

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

1.3. Понятия, определения, терминология.

Все СМО имеют вполне определенную структуру, изображенную на рис 1.2

рис 1.2

Определения, термины

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

1.4. Классификация СМО.

1.4.1. По характеру источника требований различают СМО с конечным и бесконечным количеством требований на входе.

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

Во втором случае источник генерирует бесконечное число требований.

Пример 1. Цех с постоянным количеством станков или определенное количество ПЭВМ в терминальном классе, требующих постоянного профилактического осмотра и ремонта.

Пример 2 . Сеть Internet с бесконечным требованием на входе, любой магазин, парикмахерская и т.д.

Первый вид СМО называют замкнутой, второй – разомкнутой.

СМО различают:

1.4.2. По дисциплине обслуживания:

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

1.4.3. по характеру организации:

1. с отказами;
2. с ожиданиями;
3. с ограничением ожидания.

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

1.4.4. По количеству единиц обслуживания:

1. одноканальные;
2. двухканальные;
3. многоканальные.

1.4.5. По числу этапов (фаз) обслуживания - на однофазные и многофазные. (Примером многофазных СМО может служить любая поточная линия).

1.4.6. По свойствам каналов: на однородные, когда каналы имеют одинаковую характеристику и неоднородные в противном случае.