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

Лекция 11

(Q-схемы)

Особенности непрерывно-стохастического подхода рассмотрим на примере использования в качестве типовых математических схем систем массового обслуживания (англ. Queueing system), которые будем называть Q-схемамu. Системы массового обслуживания представляют собой класс математических схем, разработанных в теории массового обслуживания и различных приложениях для формализации процессов функционирования систем, которые по своей сути являются процессами обслуживания [5,6,7].

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и со­бственно обслуживание заявки. Это можно изобразить в виде неко­торого i-ro прибора обслуживания П (рис. 5.1), состоящего из накопителя заявок H , в котором может одновременно находиться l = заявок, где - емкость i-ro накопителя, и канала об­служивания заявок (или просто канала) K . На каждый элемент прибора обслуживания П поступают потоки событий: в накопитель H - поток заявок w , на канал K - поток обслуживаний u .

u Пi

H i К _i

w y

Рис. 5.1. Прибор обслуживания заявок.

Потоком событий называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных собы­тий. Поток событий называется однородным, если он характеризу­ется только моментами поступления этих событий (вызываю­щими моментами) и задается последовательностью { t } = { 0≤t ≤t …≤t ≤… }, где t - момент наступления n-го собы­тия - неотрицательное вещественное число. Однородный поток событий также может быть задан в виде последовательности про­межутков времени между n-м и (n-1)-м событиями {τ }, которая однозначно связана с последовательно­стью вызывающих моментов { t }, где τ= t - t , n ≥1, t =0, т.е. τ = t .

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

Возможные приложения. Обычно в приложениях при моделиро­вании различных систем применительно к элементарному каналу обслуживания K можно считать, что поток заявок W, т. е. интервалы времени между моментами появления заявок (вызыва­ющие моменты) на входе K образует подмножество неуправля­емых переменных, а поток обслуживания u U, т. е. интервалы времени между началом и окончанием обслуживания заявки, об­разует подмножество управляемых переменных.

Заявки, обслуженные каналом K , и заявки, покинувшие прибор П , по различным причинам необслуженными (например, из-за переполнения накопителя H ), образуют выходной поток y У, т. е. интервалы времени между моментами выхода заявок образуют подмножество выходных переменных.

Процесс функционирования прибора обслуживания П можно представить как процесс изменения состояний его элементов во времени z (t). Переход в новое состояние для П означает изменение количества заявок, которые в нем находятся (в канале K и в накопителе Н ). Таким образом, вектор состояний для П имеет вид , где состояние накопителя H ( =0 - накопитель пуст, = 1 - в накопителе имеется одна заявка,..., z =L_j^H - накопи­тель полностью заполнен); L - емкость накопителя H ; измеря­емая числом заявок, которые в нем могут поместиться; z - состо­яние канала K ( z = 0 – канал свободен, z = 1 - канал занят и т. д.).

В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации ис­пользуются не отдельные приборы обслуживания, а Q-схемы, об­разуемые композицией многих элементарных приборов обслужива­ния П (сети массового обслуживания). Если каналы K различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы П и их параллельные композиции соединены последовате­льно, то имеет место многофазное обслуживание (многофазная Q-схема). Таким образом, для задания Q-схемы необходимо ис­пользовать оператор сопряжения R, отражающий взаимосвязь эле­ментов структуры (каналов и накопителей) между собой.

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

Собственными (внутренними) параметрами Q-схемы будут яв­ляться количество фаз L_ф , количество каналов в каждой фазе L , j = 1, L , количество накопителей каждой фазы L , k=1, L_ф, емкость i – го накопителя L . Следует отметить, что в теории массового обслуживания в зависимости от емкости накопителя применяют следующую терминологию для систем массового обслуживания: системы с потерями (L = 0, т.е.накопитель в приборе П отсутствует, а имеется только канал обслуживания K ), системы с ожиданием (L ∞ т.е. накопитель H имеет бесконечную ем­кость и очередь заявок не ограничивается) и системы смешанного типа (с ограниченной емкостью накопителя H ). Всю совокупность собственных параметров Q-схемы обозначим как подмножество Н.

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

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

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

Таким образом, Q- схема, описывающая процесс функциониро­вания системы массового обслуживания любой cложности, одно­значно задается в виде Q= (W, U, Н, Z, R, А).

При ряде упрощающих предположений относительно подмно­жеств входящих потоков W и потоков обслуживания U (выполнение условий стационарности, ординарности и ограниченного последей­ствия) оператора сопряжения элементов структуры R (однофазное одноканальное обслуживание в разомкнутой системе), подмножест­ва собственных параметров H (обслуживание с бесконечной ем­костью накопителя), оператора алгоритмов обслуживания заявок А (бесприоритетное обслуживание без прерываний и блокировок) для оценки вероятностно-временных характеристик можно исполь­зовать аналитический аппарат, разработанный в теории массового обслуживания. При принятых предположениях в обозначениях Д. Кендалла будет иметь место классическая система обслуживания типа М/М/l (одноканальная система с марковским входящим пото­ком заявок и марковским потоком обслуживания).

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