Непрерывно-стохастические модели (Q-схемы)

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

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

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

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

Элементы СМО:

- средства обслуживания – обслуживающие приборы или каналы обслуживания (К), являющиеся статическими элементами Q -схем;

- обслуживаемые заявки – транзакты, являющиеся динамическими элементами Q -схем;

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

Состояние СМО характеризуется:

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

- состояниями всех транзактов, каждый из которых может находиться в состоянии “обслуживание” или “ожидание”;

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

Переменные СМО:

- независимые величины:

 а) интервал поступления – интервал времени между последовательными моментами поступления заявок в систему;

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

- системные величины, являющиеся предметом исследования системы и назначаемые исследователем, например:

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

б) число заявок, поступивших на обслуживание сразу же по прибытии;

в) среднее время пребывания заявок в очереди;

г) средние длины очередей;

д) максимальная длина очереди;

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

На рис. приведён пример системы обслуживания одним обслуживающим аппаратом и очередью. Система функционирует следующим образом. Заявка из источника заявок приходит на обслуживание. Если обслуживающий аппарат свободен, то заявка занимает его, и начинается процесс обслуживания. Если обслуживающий аппарат занят, то заявка поступает в очередь, где ожидает окончания обслуживания предыдущей заявки. Обслуженная заявка освобождает обслуживающий аппарат и покидает систему. Заявки, приходящие на обслуживание, образуют поток заявок; заявки, поступающие на обслуживание, образуют поток обслуживания; а заявки, покидающие систему по окончании обслуживания, образуют выходной поток. Эти потоки характеризуются интенсивностью l прихода заявок на обслуживание, интенсивностью m обслуживания и интенсивностью h ухода заявок из системы.

К

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

 

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

1.                        – источник заявок;                 

 

2.                        – материальные потоки (движение транзактов);

 

3.                        – информационные потоки (управляющие сигналы);

 

4.                        – клапан;

 

 

5.                        – накопитель;

 

6.                        – канал обслуживания;

 

7. – узел − правило, определяющее направление транзактов.

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

Движение заявок через Q –схему представляет собой материальные потоки. А для управления системы обслуживания используются информационные потоки.

 

 

 

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

И – источник заявок; Н1 и Н2 – накопители; К – канал обслуживания;

1, 2, 3 – клапаны

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

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

Поток однородных событий – это поток, который характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью { t _n } = {0 £ t ₁ £ t ₂ £…£ t _n £…}, где – момент наступления n –го события – неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности промежутков времени между n –м и (n –1)–м событиями { t _n }, которая однозначно связана с последовательностью вызывающих моментов { t _n }, где интервал прибытия t _n = t _n – t _{n - 1}, n ³ 1, t ₀ = 0, т.е. t ₁ = t ₁.

Поток неоднородных событий – это последовательность { t _n, f _n }, где t _n – вызывающие моменты; f _n  – набор признаков события. Например, применительно к процессу обслуживания для неоднородного потока заявок может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Поток с ограниченным последействием – это поток, в котором интервалы прибытия t ₁, t ₂, … являются случайными величинами, независимыми между собой.

Ординарный поток событий – это поток, для которого вероятность того, что на малый интервал времени D t, примыкающий к моменту времени t, попадает больше одного события P _>1 (t, D t), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени D t попадает ровно одно событие P ₁ (t, D t), т.е. P ₁ (t, D t) >> P _>1 (t, D t).

Стационарный поток событий – поток, для которого вероятность появления того или иного числа событий на интервале времени t зависит лишь от длины этого интервала и не зависит от того, где на оси времени взят этот интервал. Для стационарного потока его интенсивность не зависит от времени и представляет собой постоянное значение, равное среднему числу событий, поступающих в единицу времени l (t) = l = const.

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

 

Q = < W, U, Y, H, Z, R, A >,                           (2.12)

 

где   W – поток заявок;

U – поток обслуживания;

Y – выходной поток;

H – собственные параметры;

Z – внутреннее состояние;

R – оператор сопряжения;

A – оператор алгоритмов поведения заявок.

Поток заявок w _i Î W, т.е. интервалы времени между моментами появления заявок (вызывающие моменты) на входе системы, образует множество неуправляемых переменных.

 Поток обслуживания u _i Î U, т.е. интервалы времени между началом и окончанием обслуживания заявок обслуживающими аппаратами системы, образует множество управляемых переменных.

Выходной поток y _i Î Y, т.е. интервалы времени между моментами выхода заявок из системы, образует множество выходных переменных. Выходной поток составляют обслуженные заявки и заявки, покинувшие систему по различным причинам необслуженными (например, из-за переполнения накопителей).

Внутреннее состояние z _i Î Z определяется множеством состояний всех элементов, образующих систему. Процесс функционирования системы обслуживания можно представить как процесс изменения состояний его элементов во времени z _i (t). Переход в новое состояние для элемента системы означает изменение количества заявок, которые в нём находятся (в канале K _i и в накопителе H _i). Таким образом, состояние для элемента системы имеет вид , где  – состояние накопителя H _i (  = 0 – накопитель пуст,  = 1 – в накопителе имеется одна заявка, …,  =  – накопитель полностью заполнен); – ёмкость накопителя H _i, измеряемая числом заявок, которые в нём могут поместиться;  – состояние канала K _i (  = 0 – канал свободен,  = 1 – канал занят и т.д.).

Оператор сопряжения R отражает взаимосвязь элементов структуры системы (каналов и накопителей) между собой. Q –схемы образуются композицией многих обслуживающих аппаратов. Если каналы обслуживания соединены параллельно (рис. 2.9), то имеет место многоканальное обслуживание (многоканальная Q – схема).

 

 

Рис. 2.9. Схема параллельного соединения каналов обслуживания:

а – с общей очередью; б – с раздельными очередями

 

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

 

 

 

Рис. 2.10. Схема последовательного соединения каналов обслуживания

 

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

Собственные (внутренние) параметры H Q –схемы включают:

– количество фаз L _Ф;

– количество каналов в каждой фазе L_{K j} ();

– количество накопителей каждой фазы L_{H k} ();

– ёмкость i -го накопителя .

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

– система с потерями (  = 0, т.е. накопитель у обслуживающего аппарата отсутствует, а имеется только канал обслуживания K_i);

–  система с ожиданием (  → ∞, т.е. накопитель H_i имеет бесконечную ёмкость и очередь заявок не ограничивается);

– система смешанного типа (с ограниченной ёмкостью накопителя H_i).

Вся совокупность собственных параметров Q –схемы образует множество H.

Оператор алгоритмов (дисциплин) поведения заявок A определяет набор правил поведения заявок в системе в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы (дисциплины) ожидания заявок в накопителе H_i и обслуживания заявок каналом K_i каждого обслуживающего аппарата Q –схемы. Неоднородность заявок, отражающая процесс в той или иной реальной системе, учитывается с помощью введения классов приоритетов.

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

Алгоритмы (дисциплины) обслуживания заявок представляют собой набор правил, по которым заявки покидают накопитель H_i и канал K_i: для накопителя H_i – либо правила переполнения, по которым заявки в зависимости от заполнения H_i покидают систему, либо правила ухода, связанные с истечением времени ожидания заявки в H_i, для канала K_i – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале K_i или не допускаются до обслуживания каналом K_i, т.е. правила блокировок каналов. При этом различают блокировки канала K_i по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q –схеме, регулирующих поток заявок в зависимости от состояний Q –схемы. Весь набор возможных алгоритмов поведения заявок в Q –схеме представляется в виде оператора поведения заявок A.

Аналитическое решение Q –схемы, заданной Q = < W, U, Y, H, Z, R, A >, возможно только при следующих упрощениях:

– входные потоки W и потоки обслуживания U – стационарные, ординарные, ограниченного последействия;

– оператор сопряжения элементов структуры R – однофазное одноканальное обслуживание в разомкнутой системе;

– множество собственных параметров H – обслуживание с бесконечной ёмкостью накопителя;

– оператор алгоритмов обслуживания заявок A – бесприоритетное обслуживание без прерываний и блокировок.

Таким образом, возможности оценки характеристик с использование аналитических моделей теории массового обслуживания являются весьма ограниченными по сравнению с требованиями практики исследования и проектирования систем, формируемых в виде Q –схем. Несравненно большими возможностями обладают имитационные модели, позволяющие исследовать Q –схему, заданную Q = < W, U, Y, H, Z, R, A > без ограничений. На работу с Q –схемами при машинной реализации моделей ориентированы языки имитационного моделирования, например: SIMULA, SIMSCRIPT, GPSS и др.