Требуется решить задачи 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).

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

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

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

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

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

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

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

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% поступающих заявок? И какая доля каналов при этом будет простаивать?

Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов.

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

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

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

Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживании имеет интенсивность μ, обратную среднему времени обслуживания заявки 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 + ρ + ρ 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а .

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

Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью.

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

Есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n 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 (мин.). Предлагаем такому придирчивому читателю ответить на вопрос: а насколько надо его уменьшить, чтобы «рационализаторское предложение» стало выгодным?

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

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

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

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

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

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

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

Рисунок 0 - 2 Потоки событий (а) и простейший поток (б)

10.5.2.1. Стационарность

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

Рисунок 0-2 , а) зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.

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

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут рассматриваться как стационарные. Например, поток вызовов, поступающих на телефонную станцию, скажем, на интервале от 12 до 13 часов может считаться стационарным. Тот же поток в течение целых суток уже не будет стационарным (ночью интенсивность потока вызовов гораздо меньше, чем днем). Заметим, что так же обстоит дело и с большинством физических процессов, которые мы называем «стационарными» в действительности они стационарны только на ограниченном участке времени, а распространение этого участка до бесконечности лишь удобный прием, применяемый в целях упрощения.

10.5.2.2. Отсутствие последействия

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

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

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

Рисунок 0 - 3 Распределение Пуассона

Рассмотрим на оси t простейший поток событий с интенсивностью λ. (Рисунок 0-2 б). Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:

F(t) = P(T (0-2)

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

F (t ) = 1 - Р0

Вероятность Р 0 найдем по формуле (1), полагая m = 0:

откуда функция распределения величины Т будет:

(0-3)

Чтобы найти плотность распределения f (t ) случайной величины Т, необходимо продифференцировать выражение (0‑1) по t :

0-4)

Закон распределения с плотностью (0‑4) называется показательным (или экспоненциальным). Величина λ называется параметром показательного закона.

Рисунок 0 - 4 Экспоненциальное распределение

Найдем числовые характеристики случайной величины Т - математическое ожидание (среднее значение) M [ t ]= m t , и дисперсию D t . Имеем

( 0-5)

(интегрируя по частям) .

Дисперсия величины Т составляет:

(0-6)

Извлекая корень квадратный из дисперсии, найдем среднее квадратическое отклонение случайной величины Т.

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

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

Пример СМО- 1 .

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

Рассчитаем вероятность Р (m ) появления m сообщений в 1 с. Так как λ = 2, то из предыдущей формулы имеем

Подставляя m = 0, 1, 2, 3, получим следующие величины (с точностью до четырех десятичных знаков):

Рисунок 0 - 5 Пример простейшего потока

Возможно поступление и более 9 сообщений в 1 с, но вероятность этого очень мала (около 0,000046).

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

Пример СМО- 2 .

Прибор (сервер), обрабатывающей три сообщения в 1с.

Пусть имеется оборудование, которое может обрабатывать три сообщения в 1 с (µ=3). Поступает всреднем два сообщения в 1с, причем в соответствии c распределением Пуассона. Какая часть этих сообщений будет обрабатываться сразу же после поступления?

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

Если система может обрабатывать максимум 3 сообщения в 1 с, то вероятность того, что она не будет перегружена, равна

Другими словами, 85,71% сообщений будут обслуживаться немедленно, а 14,29% с некоторой задержкой. Как видим, задержка в обработке одного сообщения на время, большее времени обработки 3 сообщений, будет встречаться редко. Время обработки 1сообщения составляет в среднем 1/3 с. Следовательно, задержка более 1с будет редким явлением, что вполне приемлемо для большинства систем.

Пример СМО- 3

· Если кассир банка занят в течение 80% своего рабочего времени, а остальное время он тратит на ожидание клиентов, то его можно рассматривать как устройство с коэффициентом использования 0,8.

· Если канал связи используется для передачи 8-битовых символов со скоростью 2400 бит/с, т. е. передается максимум 2400/8 символов в 1 с, и мы строим систему, в которой суммарный объем данных составляет 12000 символов, посылаемых от различных устройств через канал связи в минуту наибольшей нагрузки (включая синхронизацию, символы конца сообщений, управляющие и т. д.), то коэффициент использования оборудования канала связи в течение этой минуты равен

· Если механизм доступа к файлу в час наибольшей нагрузки осуществляет 9000 обращений к файлу, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования механизма доступа в час наибольшей нагрузки составляет

Понятие коэффициента использования оборудования будет использоваться довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

Используя предыдущую формулу, можно составить таблицы значений функции Пуассона, по которым можно определить вероятность поступления m или более сообщений в данный отрезок времени. Например, если в среднем поступает 3,1 сообщения в секунду [т. е. λ = 3,1], то вероятность поступления 5 и более сообщений в данную секунду равна 0,2018 (для m = 5 в таблице). Или в аналитическом виде

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

Часто первоначальные расчеты могут быть проведены для значений загрузки оборудования

ρ ≤ 0,9

Эти значения можно получить с помощью таблиц Пуассона.

Пусть снова средняя скорость поступления сообщений λ = 3,1 сообщения/с. Из таблиц следует, что вероятность поступления 6 или более сообщений в 1 с равна 0,0943. Следовательно, это число можно взять в качестве критерия нагрузки для проведения начальных расчетов.

10.6.2. Задачи проектирования

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

Чем больше коэффициент использования оборудования, тем длиннее возникающие очереди. Как будет показано ниже, можно спроектировать удовлетворительно работающую систему с коэффициентом использований ρ =0,7 но коэффициент, превышающий ρ > 0,9, может привести к ухудшению качества обслуживания. Другими словами, если канал пересылки массива данных имеет загрузку 20%, вряд ли на нем возникнет очередь. Если же загрузка; составляет 0,9, то, как правило, будут образовываться очереди, иногда очень большие.

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

При проектировании системы обычно делается оценка коэффициента использования для различных видов оборудования; соответствующие примеры будут приведены в последующих главах. Знание этих коэффициентов позволяет рассчитать очереди к соответствующему оборудованию.

· Какова длина очереди?

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

На вопросы подобного типа можно ответить с помощью теории очередей.

10.6.3. Системы массового обслуживания, их классы и основные характеристики

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

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

СМО классифицируются на системы с:

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

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

Обслуживание (дисциплина очереди) в системе с ожиданием может быть

· упорядоченным (заявки обслуживаются в порядке поступления),

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

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

· Приоритетным

o со статическим приоритетом

o с динамическим приоритетом

(в последнем случае приоритет может, например, увеличиваться с длительностью ожидания заявки).

Системы с очередью делятся на системы

· с неограниченным ожиданием и

· с ограниченным ожиданием.

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

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

· длины очереди (числа заявок, одновременно находящихся в очереди система с ограниченной длиной очереди),

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

· общего времени пребывания заявки в СМО

и т. д.

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

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

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

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

· среднее относительное время простоя системы в целом и отдельного канала

и т. д.

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

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

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

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

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

а также и другие характеристики ожидания.

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

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

В зависимости от значений этих параметров выражаются характеристики эффективности работы СМО.

10.6.4. Формулы расчета характеристик СМО для случая обслуживания с одним прибором

Рисунок 0 - 6 Модель системы массового обслуживания с очередью

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

Рассмотрим случай простейшего потока заявок на обслуживание.

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

Каждая из характеристик меняется в зависимости от используемых средств.

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

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

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

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

С другой стороны, разброс времени обслуживания не так велик, как в случае произвольного или экспоненциального его распределения, т.е., σ s редко достигает значений t s . Этот случай иногда считают "наихудшим и потому пользуются формулами, относящимися к экспоненциальному распределению времен обслуживания. Такой расчет может дать несколько завышенные размеры очередей и времен ожидания в них, но эта ошибка, по крайней мере, не опасна.

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

Рассмотрим следующий пример. Имеется шесть типов сообщений с временами обслуживания 15, 20, 25, 30, 35 и 300. Число сообщений каждого типа одинаково. Стандартное отклонение указанных времен несколько выше их среднего. Значение последнего времени обслуживания намного больше других. Это приведет к тому, что сообщения будут находиться в очереди значительно дольше, чем, если бы времена обслуживания были одного порядка. В таком случае при проектировании целесообразно принять меры для уменьшения длины очереди. Например, если указанные цифры связаны с длинами сообщений, то, возможно, очень длинные сообщения стоит разделить на части.

10.6.6. Пример расчета

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

Время ответа системы и его стандартное отклонение рассчитаны с учетом времени ввода данных с АРМа, печатания и оформления документа.

Действия кассира были прохронометрированы. Время обслуживания ts равно общему времени, затрачиваемому кассиром на клиента. Коэффициент использования кассира ρ пропорционален времени его занятости. Если λ число клиентов в часы пик, то ρ для кассира равно

Предположим, что в часы пик приходит 30 клиентов в час. В среднем кассир тратит 1,5 мин на клиента. Тогда

ρ =(1,5 * 30) / 60 = 0,75

т. е. кассир используется на 75%.

Число людей в очереди можно быстро оценить с помощью графиков. Из них следует, что если ρ = 0,75, то среднее число nq людей в очереди у кассы лежит между 1,88 и 3,0 в зависимости от стандартного отклонения для t s .

Предположим, что измерение стандартного отклонения для t s дало величину 0,5 мин. Тогда

σ s = 0,33 t s

Из графика на первом рисунке находим, что nq = 2,0, т. е. в среднем у кассы буду ожидать два клиента.

Общее время, в течение которого клиент стоит у кассы, может быть найдено как

t ∑ = t q + t s = 2,5 мин + 1,5 мин=4мин

где t s вычисляется с помощью формулы Хинчина-Полачека.

10.6.7. Фактор усиления

Анализируя кривые, изображенные на рисунках, мы видим, что, когда оборудование, обслуживающее очередь, используется более чем на 80%, кривые начинают расти с угрожающей быстротой. Этот факт очень важен при проектировании систем передачи данных. Если мы проектируем систему, в которой оборудование используется более чем на 80%, то незначительное увеличение трафика может привести к резкому спаду производительности системы или даже заставить ее работать в аварийном режиме.

Увеличение входного трафика на небольшое число х%. приводит к увеличению размеров очереди приблизительно на

Если коэффициент использования оборудования равен 50%, то это увеличение равно 4ts % для экспоненциального закона распределения времени обслуживания. Но если коэффициент использования оборудования равен 90%, то увеличение размера очереди равно 100ts %, что в 25 раз больше. Незначительное увеличение нагрузки при 90%-ном использовании оборудования приводит к 25-кратному увеличению размеров очереди по сравнению со случаем 50%-ного использования оборудования.

Аналогично время пребывания в очереди увеличивается на

При экспоненциально распределенном времени обслуживания эта величина имеет значение 4 t s 2 для коэффициента использования оборудования, равного 50%, и 100 t s 2 для коэффициента 90%, т. е. снова в 25 раз хуже.

Кроме того, для малых коэффициентов использования оборудования влияние изменений σs на размер очереди незначительно. Однако для больших коэффициентов изменение σ s сильно сказывается на размере очереди. Поэтому при проектировании систем с высоким коэффициентом использования оборудования желательно получить точные сведения о параметре σ s . Неточность предположения относительно экспоненциальности распределения t s наиболее ощутима при больших значениях ρ. Более того, если вдруг время обслуживания возрастет, что возможно в каналах связи при передаче длинных сообщений, то в случае большого ρ образуется значительная очередь.

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

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

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

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

Таблица 30.1. Примеры систем массового обслуживания

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

Но все эти системы объединены в один класс СМО, поскольку подход к их изучению един. Он состоит в том, что, во-первых , с помощью генератора случайных чисел разыгрываются случайные числа, которые имитируют СЛУЧАЙНЫЕ моменты появления заявок и время их обслуживания в каналах. Но в совокупности эти случайные числа, конечно, подчинены статистическим закономерностям.

К примеру, пусть сказано: «заявки в среднем приходят в количестве 5 штук в час». Это означает, что времена между приходом двух соседних заявок случайны, например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис. 30.1 , но в сумме они дают в среднем 1 (обратите внимание, что в примере это не точно 1, а 1.1 — но зато в другой час эта сумма, например, может быть равной 0.9); и только за достаточно большое время среднее этих чисел станет близким к одному часу.

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

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

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

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

Перечислим некоторые основные понятия СМО.

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

Очереди характеризуются правилами стояния в очереди (дисциплиной обслуживания), количеством мест в очереди (сколько клиентов максимум может находиться в очереди), структурой очереди (связь между местами в очереди). Бывают ограниченные и неограниченные очереди. Перечислим важнейшие дисциплины обслуживания. FIFO (First In, First Out — первым пришел, первым ушел): если заявка первой пришла в очередь, то она первой уйдет на обслуживание. LIFO (Last In, First Out — последним пришел, первым ушел): если заявка последней пришла в очередь, то она первой уйдет на обслуживание (пример — патроны в рожке автомата). SF (Short Forward — короткие вперед): в первую очередь обслуживаются те заявки из очереди, которые имеют меньшее время обслуживания.

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

Пусть имеется два магазина. В магазине № 1 обслуживание осуществляется в порядке очереди, то есть здесь реализована дисциплина обслуживания FIFO (см. рис. 30.3 ).

Рис. 30.3. Организация очереди по дисциплине FIFO

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

В магазине № 2 реализована дисциплина SF (см. рис. 30.4 ), означающая, что штучный товар можно купить вне очереди, так как время обслуживания t обслуж. такой покупки невелико.

Рис. 30.4. Организация очереди по дисциплине SF

Как видно из обоих рисунков, последний (пятый) покупатель собирается приобрести штучный товар, поэтому время его обслуживания невелико — 0.5 минут. Если этот покупатель придет в магазин № 1, он будет вынужден выстоять в очереди целых 8 минут, в то время как в магазине № 2 его обслужат сразу же, вне очереди. Таким образом, среднее время обслуживания каждого из покупателей в магазине с дисциплиной обслуживания FIFO составит 4 минуты, а в магазине с дисциплиной обслуживания КВ — лишь 2.8 минуты. А общественная польза, экономия времени составит: (1 – 2.8/4) · 100% = 30 процентов! Итак, 30% сэкономленного для общества времени — и это лишь за счет правильного выбора дисциплины обслуживания.

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

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

Судить о результатах работы СМО можно по показателям . Наиболее популярные из них:

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

Судить о качестве полученной системы нужно по совокупности значений показателей. При анализе результатов моделирования (показателей) важно также обращать внимание на интересы клиента и интересы владельца системы , то есть минимизировать или максимизировать надо тот или иной показатель, а также на степень их выполнения. Заметим, что чаще всего интересы клиента и владельца между собой не совпадают или совпадают не всегда. Показатели будем обозначать далее H = {h 1 , h 2 , …} .

Параметрами СМО могут быть: интенсивность потока заявок, интенсивность потока обслуживания, среднее время, в течение которого заявка готова ожидать обслуживания в очереди, количество каналов обслуживания, дисциплина обслуживания и так далее. Параметры — это то, что влияет на показатели системы. Параметры будем обозначать далее как R = {r 1 , r 2 , …} .

Пример. Автозаправочная станция (АЗС) .

1. Постановка задачи . На рис. 30.5 приведен план АЗС. Рассмотрим метод моделирования СМО на ее примере и план ее исследования. Водители, проезжая по дороге мимо АЗС по дороге, могут захотеть заправить свой автомобиль. Хотят обслужиться (заправить машину бензином) не все автомобилисты подряд; допустим, что из всего потока машин на заправку в среднем заезжает 5 машин в час.

Рис. 30.5. План моделируемой АЗС

На АЗС две одинаковые колонки, статистическая производительность каждой из которых известна. Первая колонка в среднем обслуживает 1 машину в час, вторая в среднем — 3 машины в час. Владелец АЗС заасфальтировал для машин место, где они могут ожидать обслуживания. Если колонки заняты, то на этом месте могут ожидать обслуживания другие машины, но не более двух одновременно. Очередь будем считать общей. Как только одна из колонок освободится, то первая машина из очереди может занять ее место на колонке (при этом вторая машина продвигается на первое место в очереди). Если появляется третья машина, а все места (их два) в очереди заняты, то ей отказывают в обслуживании, так как стоять на дороге запрещено (см. дорожные знаки около АЗС). Такая машина уезжает прочь из системы навсегда и как потенциальный клиент является потерянной для владельца АЗС. Можно усложнить задачу, рассмотрев кассу (еще один канал обслуживания, куда надо попасть после обслуживания в одной из колонок) и очередь к ней и так далее. Но в простейшем варианте очевидно, что пути движения потоков заявок по СМО можно изобразить в виде эквивалентной схемы, а добавив значения и обозначения характеристик каждого элемента СМО, получаем окончательно схему, изображенную на рис. 30.6 .

Рис. 30.6. Эквивалентная схема объекта моделирования

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

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

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

В этой формуле величина потока λ должна быть задана (до этого она должна быть определена экспериментально на объекте как статистическое среднее), r — случайное равномерно распределенное число от 0 до 1 из ГСЧ или таблицы , в которой случайные числа нужно брать подряд (не выбирая специально).

Задача . Сгенерируйте поток из 10 случайных событий с интенсивностью появления событий 5 шт/час.

Решение задачи . Возьмем случайные числа, равномерно распределенные в интервале от 0 до 1 (см. таблицу), и вычислим их натуральные логарифмы (см. табл. 30.2).

Формула пуассоновского потока определяет расстояние между двумя случайными событиями следующим образом: t = –Ln(r рр)/λ . Тогда, учитывая, что λ = 5 , имеем расстояния между двумя случайными соседними событиями: 0.68, 0.21, 0.31, 0.12 часа. То есть события наступают: первое — в момент времени t = 0 , второе — в момент времени t = 0.68 , третье — в момент времени t = 0.89 , четвертое — в момент времени t = 1.20 , пятое — в момент времени t = 1.32 и так далее. События — приход заявок отразим на первой линейке (см. рис. 30.7 ).

Рис. 30.7. Временная диаграмма работы СМО

Берется первая заявка и, так как в этот момент каналы свободны, устанавливается на обслуживание в первый канал. Заявка 1 переносится на линейку «1 канал».

Время обслуживания в канале тоже случайное и вычисляется по аналогичной формуле:

где роль интенсивности играет величина потока обслуживания μ 1 или μ 2 , в зависимости от того, какой канал обслуживает заявку. Находим на диаграмме момент окончания обслуживания, откладывая сгенерированное время обслуживания от момента начала обслуживания, и опускаем заявку на линейку «Обслуженные».

Заявка прошла в СМО весь путь. Теперь можно, согласно принципу последовательной проводки заявок, также проимитировать путь второй заявки.

Если в некоторый момент окажется, что оба канала заняты, то следует установить заявку в очередь. На рис. 30.7 это заявка с номером 3. Заметим, что по условиям задачи в очереди в отличие от каналов заявки находятся не случайное время, а ожидают, когда освободится какой-то из каналов. После освобождения канала заявка поднимается на линейку соответствующего канала и там организуется ее обслуживание.

Если все места в очереди в момент, когда придет очередная заявка, будут заняты, то заявку следует отправить на линейку «Отказанные». На рис. 30.7 это заявка с номером 6.

Процедуру имитации обслуживания заявок продолжают некоторое время наблюдения T н . Чем больше это время, тем точнее в дальнейшем будут результаты моделирования. Реально для простых систем выбирают T н , равное 50—100 и более часов, хотя иногда лучше мерить эту величину количеством рассмотренных заявок.

Анализ временной диаграммы

Анализ проведем на уже рассмотренном примере.

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

1. Вероятность обслуживания: P обс. = N обс. /N = 5/7 = 0.714 . Для расчета вероятности обслуживания заявки в системе достаточно разделить число заявок, которым удалось обслужиться за время T н (см. линейку «Обслуженные») N обс. , на число заявок N , которые хотели обслужиться за это же время. Как и раньше вероятность экспериментально определяем отношением свершившихся событий к общему числу событий, которые могли совершиться!
2. Пропускная способность системы: A = N обс. /T н = 7/5 = 1.4 [шт/час] . Для расчета пропускной способности системы достаточно разделить число обслуженных заявок N обс. на время T н , за которое произошло это обслуживание (см. линейку «Обслуженные»).
3. Вероятность отказа: P отк. = N отк. /N = 3/7 = 0.43 . Для расчета вероятности отказа заявке в обслуживании достаточно разделить число заявок N отк. , которым отказали за время T н (см. линейку «Отказанные»), на число заявок N , которые хотели обслужиться за это же время, то есть поступили в систему. Обратите внимание . P отк. + P обс. в теории должно быть равно 1. На самом деле экспериментально получилось, что P отк. + P обс. = 0.714 + 0.43 = 1.144 . Эта неточность объясняется тем, что время наблюдения T н мало и статистика накоплена недостаточная для получения точного ответа. Погрешность это показателя сейчас составляет 14%!
4. Вероятность занятости одного канала: P 1 = T зан. /T н = 0.05/5 = 0.01 , где T зан. — время занятости только одного канала (первого или второго). Измерениям подлежат временные отрезки, на которых происходят определенные события. Например, на диаграмме ищутся такие отрезки, во время которых заняты или первый или второй канал. В данном примере есть один такой отрезок в конце диаграммы длиной 0.05 часа. Доля этого отрезка в общем времени рассмотрения (T н = 5 часов) определяется делением и составляет искомую вероятность занятости.
5. Вероятность занятости двух каналов: P 2 = T зан. /T н = 4.95/5 = 0.99 . На диаграмме ищутся такие отрезки, во время которых одновременно заняты и первый, и второй канал. В данном примере таких отрезков четыре, их сумма равна 4.95 часа. Доля продолжительности этих события в общем времени рассмотрения (T н = 5 часов) определяется делением и составляет искомую вероятность занятости.
6. Среднее количество занятых каналов: N ск = 0 · P 0 + 1 · P 1 + 2 · P 2 = 0.01 + 2 · 0.99 = 1.99 . Чтобы подсчитать, сколько каналов занято в системе в среднем, достаточно знать долю (вероятность занятости одного канала) и умножить на вес этой доли (один канал), знать долю (вероятность занятости двух каналов) и умножить на вес этой доли (два канала) и так далее. Полученная цифра 1.99 говорит о том, что из возможных двух каналов в среднем загружено 1.99 канала. Это высокий показатель загрузки, 99.5%, система хорошо использует ресурс.
7. Вероятность простоя хотя бы одного канала: P * 1 = T простоя1 /T н = 0.05/5 = 0.01 .
8. Вероятность простоя двух каналов одновременно: P * 2 = T простоя2 /T н = 0 .
9. Вероятность простоя всей системы: P * c = T простоя сист. /T н = 0 .
10. Среднее количество заявок в очереди: N сз = 0 · P 0з + 1 · P 1з + 2 · P 2з = 0.34 + 2 · 0.64 = 1.62 [шт] . Чтобы определить среднее количество заявок в очереди, надо определить отдельно вероятность того, что в очереди будет одна заявка P 1з , вероятность того, в очереди будет стоять две заявки P 2з и т. д. и снова с соответствующими весами их сложить.
11. Вероятность того, что в очереди будет одна заявка: P 1з = T 1з /T н = 1.7/5 = 0.34 (всего на диаграмме четырех таких отрезка, в сумме дающих 1.7 часа).
12. Вероятность того, в очереди будет стоять одновременно две заявки: P 2з = T 2з /T н = 3.2/5 = 0.64 (всего на диаграмме три таких отрезка, в сумме дающих 3.25 часа).
13. Среднее время ожидания заявки в очереди:

    

    (Сложить все временные интервалы, в течение которых какая-либо заявка находилась в очереди, и разделить на количество заявок). На временной диаграмме таких заявок 4.

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

    

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

15. Среднее время нахождения заявки в системе: T ср. сист. = T ср. ож. + T ср. обсл. .
16. Среднее количество заявок в системе:

    

    Разобьем интервал наблюдения, например, на десятиминутки. Получится на пяти часах K подынтервалов (в нашем случае K = 30 ). В каждом подынтервале определим по временной диаграмме, сколько заявок в этот момент находится в системе. Смотреть надо на 2, 3, 4 и 5-ю линейки — какие из них заняты в данный момент. Затем сумму K слагаемых усреднить.

Далее следует оценить точность каждого из полученных результатов. То есть ответить на вопрос: насколько мы можем доверять этим значениям? Оценка точности проводится по методике, описанной в лекции 34 .

Если точность не является удовлетворительной, то следует увеличить время эксперимента и тем самым улучшить статистику. Можно сделать и по-другому. Снова несколько раз запустить эксперимент на время T н . А в последствии усреднить значения этих экспериментов. И снова проверить результаты на критерий точности. Эту процедуру следует повторять до тех пор, пока не будет достигнута требуемая точность.

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

Таблица 30.3. Показатели СМО

Показатель	Формула	Значение	Интересы владельца СМО	Интересы клиента СМО
Вероятность обслуживания	P обс. = N обс. /N	0.714	Вероятность обслуживания мала, много клиентов уходят из системы неудовлетворенными, их деньги для владельца потеряны. Это «минус».	Вероятность обслуживания мала, каждый третий клиент хочет, но не может обслужиться. Это «минус».
Среднее количество заявок в очереди	N сз = 0 · P 0з + 1 · P 1з + 2 · P 2з	1.62	Очередь практически все время вся забита. Все места в очереди используются достаточно эффективно. Вложения на организацию очереди окупают затраты на нее. Это «плюс». Клиенты, которые долго стоят в очереди, могут уйти, не дождавшись обслуживания. Клиенты, простаивая, могут нанести ущерб системе, ломать оборудование. Много отказов, потерянных клиентов. Это «минусы».	Очередь практически все время вся забита. Клиенту приходится стоять в очереди, прежде чем он попадет на обслуживание. Клиент может не попасть даже в очередь. Это «минус».
Общий итог:			В интересах владельца: а) увеличить пропускную способность каналов, чтобы не терять клиентов (правда, модернизация каналов стоит денег); б) увеличить число мест в очереди (это тоже стоит денег), чтобы задержать потенциальных клиентов.	Клиенты заинтересованы в значительном увеличении пропускной способности для уменьшения времени ожидания и уменьшения отказов.

Синтез СМО

Мы проделали анализ существующей системы. Это дало возможность увидеть ее недостатки и определить направления улучшения ее качества. Но остаются непонятными ответы на конкретные вопросы, что именно надо сделать — увеличивать количество каналов или увеличивать их пропускную способность, или увеличивать количество мест в очереди, и, если увеличивать, то насколько? Есть и такие вопросы, что лучше — создать 3 канала с производительностью 5 шт/час или один с производительностью 15 шт/час?

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

Например, для 12 показателей нашего примера можно получить 12 зависимостей от одного параметра: зависимость вероятности отказов P отк. от количества мест в очереди (КМО), зависимость пропускной способности A от количества мест в очереди, и так далее (см. рис. 30.8 ).

Рис. 30.8. Примерный вид зависимостей показателей от параметров СМО

Затем так же можно снять еще 12 зависимостей показателей P от другого параметра R , зафиксировав остальные параметры. И так далее. Образуется своеобразная матрица зависимостей показателей P от параметров R , по которой можно провести дополнительный анализ о перспективах движения (улучшения показателей) в ту или иную сторону. Наклон кривых хорошо показывает чувствительность, эффект от движения по определенному показателю. В математике эту матрицу называют якобианом J , в которой роль наклона кривых играют значения производных ΔP i /ΔR j , см. рис. 30.9 . (Напомним, что производная связана геометрически с углом наклона касательной к зависимости.)

Рис. 30.9. Якобиан — матрица чувствительностей показателей
в зависимости от изменения параметров СМО

Если показателей 12, а параметров, например, 5, то матрица имеет размерность 12 x 5. Каждый элемент матрицы — кривая, зависимость i -го показателя от j -го параметра. Каждая точка кривой — среднее значение показателя на достаточно представительном отрезке T н или усреднено по нескольким экспериментам.

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

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

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

Поэтому сейчас обсудим только первый вопрос. Как принять решение, каким должно быть все-таки значение параметра, если с его ростом показатель все время монотонно улучшается? Вряд ли значение бесконечности устроит инженера.

Параметр R — управление, это то, что находится в распоряжении владельца СМО (например, возможность заасфальтировать площадку и тем самым увеличить количество мест в очереди, поставить дополнительные каналы, увеличить поток заявок за счет увеличения затрат на рекламу и так далее). Меняя управление, можно влиять на значение показателя P , цель, критерий (вероятность отказов, пропускную способность, среднее время обслуживания и так далее). Из рис. 30.10 видно, что если увеличивать управление R , то можно добиться всегда улучшение показателя P . Но очевидно, что любое управление связано с затратами Z . И чем больше прилагают усилия для управления, чем больше значение управляющего параметра, тем больше затраты. Обычно затраты на управление растут линейно: Z = C 1 · R . Хотя встречаются случаи, когда, например, в иерархических системах, они растут экспоненциально, иногда — обратно экспоненциально (скидки за опт) и так далее.

Рис. 30.10. Зависимость показателя Р
от управляемого параметра R (пример)

В любом случае ясно, что когда-то вложение все новых затрат просто перестанет себя окупать. Например, эффект от заасфальтированной площадки размером в 1 км 2 вряд ли окупит затраты владельца бензоколонки в Урюпинске, там просто не будет столько желающих заправиться бензином. Иными словами показатель P в сложных системах не может расти бесконечно. Рано или поздно его рост замедляется. А затраты Z растут (см. рис. 30.11 ).

Рис. 30.11. Зависимости эффекта от применения показателя Р

Из рис. 30.11 видно, что при назначении цены C 1 за единицу затрат R и цены C 2 за единицу показателя P , эти кривые можно сложить. Кривые складывают, если их требуется одновременно минимизировать или максимизировать. Если одна кривая подлежит максимизации, а другая минимизации, то следует найти их разность, например по точкам. Тогда результирующая кривая (см. рис. 30.12 ), учитывающая и эффект от управления и затраты на это, будет иметь экстремум. Значение параметра R , доставляющего экстремум функции, и есть решение задачи синтеза .

Рис. 30.12. Суммарная зависимость эффекта от применения показателя Р
и затрат Z на его получение как функции управляемого параметра R

Кроме управления R и показателя P в системах действует возмущение. Возмущения обозначим как D = {d 1 , d 2 , …} , см. рис. 30.13 . Возмущение — это входное воздействие, которое, в отличие от управляющего параметра, не зависит от воли владельца системы. Например, низкие температуры на улице, конкуренция снижают, к сожалению, поток клиентов, поломки оборудования досадно снижают производительность системы. И управлять этими величинами непосредственно владелец системы не может. Обычно возмущение действует «назло» владельцу, снижая эффект P от управляющих усилий R . Это происходит потому, что, в общем случае, система создается для достижения целей, недостижимых самих по себе в природе. Человек, организуя систему, всегда надеется посредством ее достичь некоторой цели P . На это он затрачивает усилия R , идя наперекор природе. Система — организация доступных человеку, изученных им природных компонент для достижения некоторой новой цели, недостижимой ранее другими способами .

Рис. 30.13. Условное обозначение изучаемой системы,
на которую воздействуют управляющие воздействия R и возмущения D

Итак, если мы снимем зависимость показателя P от управления R еще раз (как показано на рис. 30.10 ), но в условиях появившегося возмущения D , то, возможно, характер кривой изменится. Скорее всего, показатель будет при одинаковых значениях управлений находиться ниже, так как возмущение носит «противный» характер, снижая показатели системы (см. рис. 30.14 ). Система, предоставленная сама себе, без усилий управляющего характера, перестает обеспечивать цель, для достижения которой она была создана . Если, как и ранее, построить зависимость затрат, соотнести ее с зависимостью показателя от параметра управления, то найденная точка экстремума сместится (см. рис. 30.15 ) по сравнению со случаем «возмущение = 0» (см. рис. 30.12 ).

Рис. 30.14. Зависимость показателя P от управляющего параметра R
при различных значениях действующих на систему возмущений D

Если снова увеличить возмущение, то кривые изменятся (см. рис. 30.14 ) и, как следствие, снова изменится положение точки экстремума (см. рис. 30.15 ).

Рис. 30.15. Нахождение точки экстремума на суммарной зависимости
при различных значениях действующего возмущающего фактора D

В конечном итоге, все найденные положения точек экстремума переносятся на новый график, где образуют зависимость Показателя P от Управляющего параметра R при изменении Возмущений D (см. рис. 30.16 ).

Рис. 30.16. Зависимость показателя P от управляющего
параметра R при изменении значений возмущений D
(кривая состоит только из точек экстремумов)

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

Этот график (см. рис. 30.16 ) связывает Показатель P , Управление (ресурс) R и Возмущение D в сложных системах, указывая, как действовать наилучшим образом ЛПР (лицу, принимающему решение) в условиях возникших возмущений. Теперь пользователь может, зная реальную обстановку на объекте (значение возмущения), быстро по графику определить, какое управляющее воздействие на объект необходимо, чтобы обеспечить наилучшее значение интересующего его показателя.

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

Примечание . В тексте лекции мы использовали слова «управление» и «ресурс», то есть считали, что R = U . Следует пояснить, что управление действительно играет роль некоторой ограниченной ценности для владельца системы. То есть всегда является ценным для него ресурсом, за который всегда приходится платить, и которого всегда не хватает. Действительно, если бы эта величина не была ограничена, то мы бы могли достигать за счет бесконечной величины управлений бесконечно больших значений целей, а вот бесконечно больших результатов в природе явно не наблюдается.

Иногда различают собственно управление U и ресурс R , называя ресурсом некоторый запас, то есть границу возможного значения управляющего воздействия. В этом случае понятия ресурс и управление не совпадают: U < R . Иногда различают предельное значение управления U ≤ R и интегральный ресурс ∫U d t ≤ R .

Математический (абстрактный) объект, элементами которого являются (рис. 2.1):

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

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

Рис. 2.1.

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

Обслуживание - задержка заявки в обслуживающем приборе на некоторое время.

Длительность обслуживания - время задержки (обслуживания) заявки в приборе.

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

Заявка, поступившая в СМО, может находиться в двух состояниях:

• 1) обслуживания (в приборе);
• 2) ожидания (в накопителе), если все приборы заняты обслуживанием других заявок.

Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок в накопителе, ожидающих обслуживания, - длина очереди.

Дисциплина буферизации (дисциплина постановки в очередь) - правило занесения поступающих заявок в накопитель (буфер).

Дисциплина обслуживания - правило выбора заявок из очереди для обслуживания в приборе.

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

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

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

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

В системах ИМ при реализации СМО принимаются следующие ограничения и допущения:

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

Остановимся на некоторых элементах СМО более подробно.

Входной (входящий) поток заявок. Потоком событий называется последовательность однородных событий, следующих одно за другим и происходящих в какие-то, вообще говоря, случайные моменты времени. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок в общем случае необходимо задать интервалы времени т = t k - t k-1 между соседними моментами t k _ k и t k поступления заявок с порядковыми номерами к - 1 и к соответственно (к - 1, 2, ...; t 0 - 0 - начальный момент времени).

Основной характеристикой потока заявок является его интенсивность X - среднее число заявок, поступающих на вход СМО за единицу времени. Величина т = 1/Х определяет средний интервал времени между двумя последовательными заявками.

Поток называется детерминированным, если интервалы времени т к между соседними заявками принимают определенные заранее известные значения. Если при этом интервалы одинаковы (х к = т для всех к = 1, 2, ...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока X или значение интервала т = 1/Х.

Поток, в котором интервалы времени х к между соседними заявками представляют собой случайные величины, называется случайным. Для полного описания случайного потока заявок в общем случае необходимо задать законы распределений F fc (x fc) каждого из интервалов времени х к, к = 1,2,....

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

Случайный поток называется рекуррентным, если все интервалы времени х ь т 2 , ... между заявками распределены по одному и тому же закону F(t). Рекуррентных потоков много. Каждый закон распределения порождает свой рекуррентный поток. Рекуррентные потоки иначе называют потоками Пальма.

Если интенсивность X и закон распределения F(t) интервалов между последовательными заявками не меняются со временем, то поток заявок называется стационарнъш. В противном случае поток заявок является нестационарным.

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

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

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

Интервалы времени т между заявками в простейшем потоке распределены по экспоненциальному (показательному ) закону: с функцией распределения F(t) = 1 - е~ м; плотностью распределения/(f) = Хе~" л, где X > 0 - параметр распределения - интенсивность потока заявок.

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

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

• стационарным, если интенсивность X не меняется со временем;
• нестационарным, если интенсивность потока зависит от времени: X = >.(t).

В то же время простейший поток, по определению, всегда является стационарным.

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

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

Сумма N независимых стационарных ординарных потоков с интенсивностями Х ь Х 2 ,..., X N образует простейший поток с интенсивностью

X=Y,^i при условии, что складываемые потоки оказывают более или

менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при N > 5. Значит, при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении N.

• 2. Вероятностное разрежение потока. Вероятностное (но не детерминированное ) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью X* = рХ, где X - интенсивность исходного потока. Поток исключенных заявок с интенсивностью X** = (1 - р)Х - тоже простейший поток.
• 3. Эффективность. Если обслуживающие каналы (приборы) рассчитаны на простейший поток заявок с интенсивностью X, то обслуживание других типов потоков (с той же интенсивностью) будет обеспечено с не меньшей эффективностью.
• 4. Простота. Предположение о простейшем потоке заявок позволяет для многих математических моделей получить в явном виде зависимости показателей СМО от параметров. Наибольшее число аналитических результатов получено для простейшего потока заявок.

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

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

Важной характеристикой входного потока является коэффициент вариации

где т инт - математическое ожидание длины интервала; о - среднее квадратическое отклонение длины интервала х инт (случайной величины) .

Для простейшего потока (а =-, т = -) имеем v = 1. Для большинства

реальных потоков 0

Каналы (приборы) обслуживания. Основная характеристика канала - длительность обслуживания.

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

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

где ц - интенсивность обслуживания, здесь р = _--; т 0 бсл - матема-

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

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

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

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

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

Способы управления потоками заявок определяются дисциплинами:

• буферизации;
• обслуживания.

Дисциплины буферизации и обслуживания могут быть классифицированы по следующим признакам:

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

Вариант классификации дисциплин буферизации (постановки в очередь) в соответствии с перечисленными признаками представлен на рис. 2.2.

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

По способу вытеснения заявок из накопителя можно выделить следующие классы дисциплин буферизации:

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

Рис. 2.2.

Дисциплины буферизации могут использовать следующие правила вытеснения заявок из накопителя:

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

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

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

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

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

• одиночного режима;
• группового режима;
• комбинированного режима.

Рис. 2.3.

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

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

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

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

Бесприоритетные (заявки не имеют привилегий на досрочное обслуживание - захват ресурсов):

• обслуживание в порядке поступления FIFO (first in -first out, первый вошел - первый вышел);
• обслуживание в обратном порядке - заявка выбирается из очереди в режиме LIFO (last in - first out, последний вошел - первый вышел);
• обслуживание в случайном порядке - заявка выбирается из очереди в режиме RAND (random - случайным образом);
• обслуживание в циклическом порядке - заявки выбираются в процессе циклического опроса накопителей в последовательности 1, 2,Н СН - количество накопителей), после чего указанная последовательность повторяется;

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

• с относительными приоритетами - если в процессе текущего обслуживания заявки в систему поступают заявки с более высокими приоритетами, то обслуживание текущей даже бесприоритетной заявки не прерывается, а поступившие заявки направляются в очередь; относительные приоритеты играют роль только в момент окончания текущего обслуживания заявки при выборе из очереди новой заявки на обслуживание.
• с абсолютными приоритетами - при поступлении заявки с высоким приоритетом обслуживание заявки с низким приоритетом прерывается и на обслуживание направляется поступившая заявка; прерванная заявка может быть возвращена в очередь или удалена из системы; если заявка возвращена в очередь, то ее дальнейшее обслуживание может быть выполнено с прерванного места или заново;
• со смешанными приоритетами - строгие ограничения на время ожидания в очереди на обслуживание отдельных заявок требуют присвоения им абсолютных приоритетов; вследствие этого время ожидания заявок с низкими приоритетами может оказаться недопустимо большим, хотя отдельные заявки имеют запас по времени ожидания; для выполнения ограничений по всем видам заявок можно наряду с абсолютными приоритетами некоторым заявкам присвоить относительные приоритеты, а остальные обслуживать в бесприоритетном режиме;
• с чередующимися приоритетами - аналогом относительных приоритетов, приоритет учитывается только в моменты завершения текущего обслуживания группы заявок одной очереди и назначения новой группы на обслуживание;
• обслуживание по расписанию - заявки разных классов (находящиеся в разных накопителях) выбираются на обслуживание согласно некоторому расписанию, задающему последовательность опроса очередей заявок, например в случае трех классов заявок (накопителей) расписание может иметь вид {2, 1, 3, 3, 1, 2} или {1, 2, 3, 3, 2, 1}.

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

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

• длительностью обслуживания;
• приоритетами.

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

Для математического описания дисциплин обслуживания со смешанными приоритетами используется матрица приоритетов, представляющая собой квадратную матрицу Q = (q, ;), i,j - 1,..., Я, Я - число классов заявок, поступающих в систему.

Элемент q (j матрицы задает приоритет заявок класса i по отношению к заявкам класса; и может принимать следующие значения:

• 0 - нет приоритета;
• 1 - приоритет относительный;
• 2 - приоритет абсолютный.

Элементы матрицы приоритетов должны удовлетворять следующим требованиям:

• q n = 0, так как между заявками одного и того же класса не могут быть установлены приоритеты;
• если q (j = 1 или 2, то q ^ = 0, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i (i,j = 1, ..., Я).

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

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

В компьютерных системах ИМ обязательно имеется единственный элемент (объект), через который, и только через него, вводятся заявки в модель. По умолчанию все вводимые заявки бесприоритетные. Но есть возможности присвоения приоритетов в последовательности 1, 2, ..., в том числе и в ходе выполнения модели, т.е. в динамике.

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

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

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

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

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

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

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

Рис. 2.4.

СеМО называют также многофазными СМО.

Пример построения ИМ СеМО мы рассмотрим позже.

Основными элементами СеМО являются узлы (У) и источники (генераторы) заявок (Г).

Узел сети - это система массового обслуживания.

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

Для упрощенного изображения СеМО используется граф.

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

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

Для лучшего восприятия этого творческого потенциала в первом приближении остановимся на классификации моделей СМО.

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.

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

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

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

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

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