СТОХАСТИЧЕСКАЯ МОДЕЛЬ МНОГОКАНАЛЬНОЙ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ Советский патент 1973 года по МПК G06N1/00 

1

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

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

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

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

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

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

В состав унифицированного блока моделей обслуживающих приборов входят вентили / и

2, импульс 1ые входы которых объединены; статический триггер 3, осуществляющий управление ве тилями; вентили 4 и 5, потенциальные входы которых объединены; схема «ИЛИ 6, служащая для объединения выходов вентилей 4 -и 5; схемы «ИЛИ 7 и 8, предназначенные для попадания заявки в свободный канал; вентили 9 и 10, запрещающие поступление заявки в занятый канал; модели обслуживающих приборов 11, дающие возможность моделировать процесс обслуживания заявок; схема «ИЛИ 12, входы которой соединены с моделями обслуживающих приборов //; с.хема 13 совпадения, в.ходы которой также соединены с моделями обслуживающих

приборов //; схема 14 отрицания, инвертирующая выходной сигнал схемы 13; схема 15 совпадения, которая вместе с логической схемой 13, схемой «ИЛИ 12 и схемой 14 осуществляет анализ занятости каналов.

Триггер 3, вентилЕ /, 2, 4, 5, 9 и 10 и логические схемы «ИЛИ 6, 7, 8 (см. фиг. 1) образуют логический блок распределения 16.

Логические схемы «ИЛИ 12 и схемы 13- 15 образуют блок анализа занятости 17.

Модели обслуживающих приборов //, логический блок распределения .16 и блок анализа занятости 17 (см. фиг. 1) образуют унифидированный блок моделей обслуживающих приборов 18.

В состав генератора потоков случайных событии, распределенных в пространстве, входят датчик потока случайных имлульсов 19, непрерывно генерирующий случайную импульсную последовательность, в которой случайные временные интервалы между соседН1ИМИ сигналами распределены по известному (экспоненциальному) закону; набор генераторов импульсов 20 - генераторов регулярных импульсных последовательностей с регулируемыми частотами; группа вентилей 21, импульсные входы которых связаны соответственно с генераторами, импульсов 20; вентиль 22, выделяющий первый после поступивщей заявки импульс в случайном потоке, вырабатываемом датчиком потока случайных импульсов 19; статический триггер 23, осуществляющий управление вентилями 21 и вентилем 22, и линия задержки 24, связанная с триггером 23.

Датчик потока случайных импульсов 19, набор генераторов импульсов 20, группа вентилей 21, вентиль 22 и триггер 23 в соединении с линией задержки 24 образуют генератор потоков событий, распределенных в пространстве 25.

В состав стохастической модели, четырехканальной системы массового обслуживания (см. фиг. 3) входят логический блок распределения 16, осуществляющий, вероятное распределение заявок между свободными каналами; блок анализа занятости 17, анализирующий состояние каналов; унифи.цированные блоки моделей обслуживающих приборов , позволяющие получить многоканальную структуру модели; генератор потоков событий, распределенных в пространстве 25, осуществляющий вероятностную установку триггеров 3, входящих во все логические блоки распределения /5, в соответствии с переключательной матрицей; генератор входного потока заявок 26, иммитирующий поток заявок с заданными характеристиками; схемы «ИЛИ 27, служащие для получения многоканальной структуры системы; группа вентилей 28, импульсные входы которых соединены с генера.тором потоков событий, распределенных в пространстве 25; схемы «ИЛИ 29, выходы которых соединены с потенциальными входами вентилей 28; схемы «ИЛИ 30, служащие для объединения выходов вентилей 28; дещифратор 31, предназначенный для автоматического изменения вероятностей распределения заявок между свободными каналами в зависимости от порядковых номеров свободных каналов.

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

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

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

В первом состоянии вентили 9 и 10 унифицированных блоков моделей обслуживающих приборов 18 и логического блока распределения 16 открыты потенциалами, поступающими соответственно с моделей обслуживающих приборов 11 и со схем «ИЛИ 27, и вентили 4 н 5 тех же блоков закрыты потенциалами, приходящими соответственно с блоков анализа занятости 17 (см. фиг. 1) и с блока анализа занятости 17 (см. фиг. 3).

Блок анализа занятости реализует логику, в соответствии с которой разрещающий потенциал на выходе этого блока появляется только в том случае, когда на любом его входе, но только одном, присутствует разрещающий потенциал, поступающий либо с моделей обслуживающих приборов //, либо со схем «ИЛИ 27.

До прихода импульса., представляющего собой очередную заявку, с генератора входного потока заявок 26 триггер 23 поддерживается в единичном состоянии импульсами, приходящими .на единичный вход этого триггера с датчика потока случайных импульсов 19. С нулевого выхода триггера 23 на всю группу вентилей 21 и на вентиль 22 поступает запрещающий потенциал.

В каждой группе вентилей 28, соединенных с одной схемой «ИЛИ 30, открыт только один вентиль 28, на потенциальный вход которого через схему «ИЛИ 29 поступает разрещающий потенциал с дешифратора 31.

Поступающий с генератора входного потока заявок 26 импульс, представляющий собой очередную заявку, устанавливает триггеры 3 унифицированных блоков моделей, обслуживающих приборов 18 и логического блока распределения 16 в единичные состояния При этом вентилИ / открыты, а вентили 2 закрыты. Тот же импульс с генератора входного потока заявок 26 переводит триггер 23 в нулевое состояние. В результате чего на всю группу вентилей 21 и вентиль 22 поступает разрешающий сигнал. Триггер 23 находится в нулевом состоянии до тех пор, пока на его единичный вход не поступит очередной импульс с датчика потока случайных импульсов 19. Таким образом, триггер 23 находится в нулевом состоянии случайный отрезок времени Д с момента прихода заявки до момента появления первого после заявки импульса в случайном потоке, поступающем на триггер 23 с датчика потока случайных импульсов 19. За этот случайный отрезок времени Л, в течение которого все вентили 21 открыты, на импульсный вход каждого вентиля 21 с соответствующего генератора импульсов 20 с вероятностью1-е-где , 2,... Ti - период регулярного импульсного потока;К - интенсивность пуассоновского потока (датчик потока случайных импульсов 19) может вырабатывать импульсныи поток, в котором временные интервалы между соседними импульсами распределены по любому закону. В предлагаемой модели используется датчик потока случайных импульсов, вырабатывающий импульсный поток, временные интервалы которого распределены по экспоненциальному закону, если, поступит хотя бы один импульс регулярной частоты. Эти импульсы регулярных частот пройдут через открытые вентили 21 и поступят на импульсные входы вентилей 28, которые разбиты Hia три группы. Та:К как в каждой группе вентилей 28, объединепных одной схемой «ИЛИ 30, открыт всего лишь ОДИН вентиль, то из всего множества импульсов регулярной частоты, поступивщих на импульсные входы вентилей 28. каждой группой вентилей 28 будет выделено по одному импульсу регулярной частоты. Эти три Импульса пройдут через схему «ИЛИ 30 и перебросят соответствующие триггеры 3 логического блока распределения 16 и универсальных блоков моделей обслуживающих приборов /5 из единичных состояний в нулевые. В результате чего вентили J закроются, а вентили 2 откроются. Обозначим гоуппы вентилей 28, соединенные через схемы «ИЛИ 29 с логическим .блоком распределения 16, первым и вторым унифилированными блоками моделей обслуживающих приборов 18, соответственно первой, второй и третьей. Обозначим через Pis вероятность того, что в течение случайного отрезка времени , при котором открыты вентили 21, на выходе схемы «ИЛИ 30 oй группы вентилей 28 (1 1, 2, 3) появится импульс регулярной частоты, прощедщий через открытый вентиль 2S этой группы, соответствующий s-му состоянию (, 2, ..., 16) модели (Pis равна одному из значений Р,-). Тогда вероятности того, что за случайный отрезок времени Д/ триггеры 3 логического блока распределения 16 первого и второго универсальных блоков моделей обслуживающих приборов 18 перебросятся из единичных состояний в нулевые, при которых вентили 2 будут открыты, а вентили / закрыты, соответственно равны PII, PSI. РЗЬ В случае, когда за случайный отрезок впемени Д/ на импульсные входы вентилей 21, соединенных с открытыми вентилями 28, с соответствующих генераторов импульсов 20 не придет ни одного импульса регулярной частоты, триггеры 3 логического блока распределения 16 первого и второго унифицированных блоков моделей обслуживающих приборов 18 останутся в единичных состояниях. Вероятности таких событий соответственно равны (1-PU), (1-P2i) и (1-PSI). При этом вентили / останутся открытыми, а вентили 2 - закрытыми. Перебросы триггеров 3 в логическом блоке распределения 16 в первом и во втором унифииироваиных блоках моделей обслуживающих приборов 18 за случайный отрезок времени Д являются независимыми событиями. Первый после заявки импульс случайного потока, поступающего на триггео 23 и вентиль 22 с датчика потока случайных импульсов 19, пойдет, с одной стороны, через линию задержки 24 на переброс триггера 23 из нулевого состояния в единичное, что соответствует снятию разрешающего потенциала с вентилей 21 и 22, и, с другой стороны, через открытый вентиль 22 - на объединенные импульсные входы вентилей / и 2 логического блока распределения 16. Импульс случайного потока, вырабатываемого датчиком потока случайных импульсов 19, поступающий на импульсные входы вентилей / и 2, представляет собой заявку, задержаННую на случайный отрезок времени Д. Этот импульс пройдет или через вентиль / логического блока распределения 16. если за случайный отрезок впемени триггер 3 этого блока остался в единичном состоянии (вероятность такого события равна (1-Рц), или через вентиль 2 логического блока распределения 16, если триггер 3 этого блока за случайный отрезок времени перебросится в нулевое состояние (вероятность такого события равна Рц)В том случае, если заявка прошла через вентиль /, через схему «ИЛИ 7 и открытый вентиль 9 логического блока распределения 16 попадет на первый унифицированный блок моделей обслуживающих приборов 18.

Внутри этого блока заявка, может пройти или через вентиль /, схему «ИЛИ 7, открытый вентиль 9 и поступить на первую модель обслуживающего прибора //, если за случайный отрезок времени А/ триггер 3 остался в единичном состоянии (вероятность такого события равна (1--Ри) (), или через вевтиль 2, схему «ИЛИ 5, открытый вентиль 10 и может поступить на вторую модель о бслуживающего прибора 11, если за случайный отрезок времени Д/ триггер 3 перебросился в нулевое состояние (вероятность такого события равна (1-P.i)-Pzi.

В том случае, если заявка прошла через вентиль 2 логического блока распределения 16, она через схему «ИЛИ 8 открытый вентиль 10 этого блока попадет на второй унифицированный блок моделей обслуживающих приборов 18.

Внутри этого блока заявка пройти или через вентиль /, схему «ИЛИ 7; открытый вентиль 9 и поступить на третью модель обслуживающего прибора 11, если за случайный отрезок времени А триггер 3 остался в единичном состоянии (вероятность такого события равна Ри-(1--Psi), или через вентиль 2, схему «ИЛИ 5, открытый вентиль 10 и поступить на четвертую модель обслуживающего прибора //, если за случайный отрезок времени триггер 5 перебросился в нулевое состояние (вероятность такого события равва Рц-Рзь

Во втором состоянии вентили 9 и 10 логического блока распределения 16 и первого унифицированного блока моделей обслуживающих приборов 18 открыты потенциалами, поступающими соответственно со схем «Р1ЛИ 27 и с моделей обслуживающих приборов //, а вентили 4 i 5 тех же блоков, закрыты потенциалами, приходящими с блока анализа занятости 17.

Вентиль 9 и вентили 4 к 5 второго унифицированного блока моделей обслуживающих приборов 18 открыты потенциалами, приходящими соответственно с третьей модели обслуживающего прибора // и блока анализа занятости У7, входящих в состав второго унифицированного блока 18. Вентиль 10 этого блока закрыт потенциалом, поступающим с четвертой модели обслуживающего прибора 11.

В каждой группе вентилей 28 открыто по одному вентилю, соответствующему второму состоянию. Это обеспечивает дешифратор 31.

Состояние остальных элементов, а также работа схемы на начальном этапе, включая проход заявки или через вентиль 9 логического блока распределения 16 с вероятностью ,(1-PIS), или через вентиль 0 того же блока

с вероятностью Piz аналогичны случаю, рассмотренному выше.

В том случае, если заявка прошла через вентиль 9 и попала на первый унифицированный блок моделей обслуживающих приборов 18, она распределится между первой и второй моделями обслуживающих приборов // с соответствующими вероятностями (() и (1-Piz}-Pi2 таким образом, как

это было показано при первом состоянии модели.

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

Внутри этого блока заявка должна попасть

только на третью модель обслуживающего

прибора 1L Осуществляется это следующим

образом.

Если заявка пройдет через вентиль /, схему «ИЛИ 7, открытый вентиль 9, то она с вероятностью () попадет на третью модель обслуживающего прибора //. Одновременно заявка пойдет и по другому пути - через открытый вевтиль 5 схемы «ИЛИ 6 и

5 и попадет на закрытый вентиль /О, через который заявка не сможет попасть в четвертую модель обслуживающего прибора //. Если заявка пройдет через вентиль 2, то она, с одной стороны, через схему «ИЛИ 8 поступит на закрытый вентиль 10, и, с другой стороны, через открытый вентиль 4, схемы «ИЛИ 6 и 7 н вентиль 9 с вероятностью Рм-Ру2 попадет в третью модель обслуживающего прибора 11.

Таким образом, внутри второго унифицированного блока моделей обслуживающих приборов 18 заявка е любом случае с вероятностью (1-Рзг) -Pi2 попадет на свободную третью модель обслул иваю дего

прибора //.

В третьем состоянии в логическом блоке распределения 16 открыты вентпли 9, 4 5 (вентиль 10 закрыт), В первом унифицированном блоке моделей

обслуживающих приборов 18 открыты вентили 9 и 10, вентили 4 и 5 закрыты.

Во втором унифицированном блоке моделей обслуживающих приборов 18 закрыты вентили 4, 5, 9 и Ю.

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

работа схемы на начальном, этапе, включая

проход заявки или через вентиль У, или через

вентиль 2 логического блока распределения

16 аналогичны первому состоянию модели.

При третьем состоянии модели логический

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

в этом случае аналогична работе логического блока распределения 16 второго унифицированного блока моделей обслуживающих приборов 18 при втором состоянии модели. Распределение заявок внутри первого унифицированного блока моделей обслуживающих приборов 18 между первой и второй моделями обслуживающих при-боров // соответствующими вероятностями (1-Р2з) и PZZ осуществляется таким же образом, как при первом и втором состояниях моделей. В четвертом состоянии в логическом блоке распределения 16 вентили 9 и 10 закрыты, поэтому заявка не сможет попасть ни на какую модель обслуживающего прибора //. Вероятности распределения заявок между- моделями обслуживающих приборов // прИ любом состоянии модели задаются переключательной матрицей. Сумма вероятностей любой строки, за исключением четвертой, равна единице. Это означает, что при наличии хотя бы одного свободного кавала в модели не происходит потери заявки (для правильной работы модели необходимо, чтобы интенсивность потокя. вырабатываемого датчиком потока случайных импульсов 19, была бы по крайней мере на порядок выше интенсивности потока заявок). Если необходимо получить модель на большее, чем четыре, число каналов, например восемь, то используется следующий способ. Два блока па четыре каиала, один из которых показан на фИГ. 3, объединяются в блок на восемь каналов с помощью дополнительных элементов: одного логического блока распределепия 16; одного блока анализа зан ятости /7; двух схем «ИЛИ 27; одной группы вентилей 28 с соответствующими схемами «ИЛИ 29 и 30. При этом используется один дешифратор 31 восемь входов и один генератор потоков событий, распределенных в пространстве 25, число выходов которого увеличено па необходимую величину, определяемую по переключательной матрице. Объединение двух четырехканальных блоков фиг. 3 с помощью дополнительных элементов осуществляется следующим образом. Входы логических блоков распределения 16 четырехканальнътх блоков, которые раньше соединялись с выходом генератора потоков событий, распределенных в пространстве 25, отключаются от этого генератора и подключаются к выходам дополнительного логического блока распределения 16. Отключенный выход генератора подается на вход этого блока. Другой вход этого блока соединяется с выходом генератора входного потока заявок 26. Выходы схем «ИЛИ 27 каждого четырехканального блока фиг. 3 подключаются к дополнительной схеме «ИЛИ 27, выход которой, с одной стороны, подается на вход дополнительного логического блока распределения 16 и, с другой стороны, подключенного ко входу дополнительного блока анализа занятости 17. Выход этого блока также соединяется со Бходом дополнительного логического блока распределения 16. Соответствующие выходы генератора потоков событий, распределенных в пространстве 25, через дополнительную группу вентилей 28 соединяются со входом дополнительного логического блока распределения 16. при этом входы схем «ИЛИ 28 подключаются к соответствующим выходам дещифратора 31 на восемь входов. Выходы всех восьми моделей обслуживаюп их приборов // подаются Hia этот дещифратор. Остальные связи внутри каждого четырехканального блока сохраняются. Этот принцип использовался для получения четырехканальпой модели фиг. 3 из двух унифицированных блоков моделей обслуживающих приборов /5. Если необходимо получить многоканальную систему с числом каналов, заключенным от до 2, но не равным этим значениям, то к блоку с числом каналов надо подключать блоки с числом каналов 2 (, 2, ..., п-2) или непосредственно модель обслуживающего прибора //. Например, если требуется получить систему на три канала, то вместо второго унифицированного блока моделей обслуживающих приборов 18 к выходу логического блока распределения 16 подключается непосредственно модель обслуживающего прибора //. При этом необходимость использования схемы «ИЛИ 27, соединенной с этим унифицированным блоком, а также группы вентилей 28 отпадает. Выход этой модели обслуживающего прибора // соедин-яется, с одной стороны, со входом логического блока распределения 16, с другой стороны, - со входом блока анализа занятости 17 и, с третьей стороны,- со входом дешифратора 31. Необходимость в связи этой модели обслуживающего прибора // с генератором входного потока заявок 26 отпадает. Остальные связи, показанные на фиг. 3. остаются. Предмет и з о б р е т е н: и я Стохастическая модель многоканальной системы массового обслуживания, содержащая генератор входного потока заявок, соединенный с генератором случайных событий, распределенных в пространстве, связанным с логическим блоком распределения, модели облуживающих приборов, соединенные через хемы «ИЛИ с блоком анализа, и подклюенные к блоку распределения логические хемы «ИЛИ и вентили, отличающаяся тем, то, с целью автоматизации изменения веротностей попадания заявок в свободные канаы в зависимости от их порядковых номеров, одель содержит дешифратор, в.чоды котороо подключены к выходам моделей обслужиающих приборов, а выходы объединены в руппы, соединенные входами с шестью схемами «ИЛИ, выходы которых соответственно подключены к шести вентилям; вторые входы всех вен-тилей соединены с выходами генератора случайных событий, распределенных в пространстве; выходы первого и второго вентилей и выходы третьего и четвертого

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

Г

-

Фаг. 2