Стохастическая модель системы массового обслуживания

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (и) 526920

Союз. Сплетал нн

Социалистических

Республик (61) Дополнительное к II:.I.. спид-I:ó 311280 (22) Заявлено 06.06.74 (21) 2032341, 24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 30.08.76. Бюллетень J¹ 32

,51) х1. 1х.1. - G 06О 7 48

Государственный комитет

Совета Министров СССР (53) УДК 681.325(088.8) по делам изобретений н открытий

Дата опубликования QIIIIc3IIIIB 10.12.76 (72) Авторы изобретения

В. H. Четвериков, Э. А. Баканович, М. А. Орлов, А. В. Меньков и С. Ф. Костюк

Минский радиотехнический институт и Московское ордена Ленина и ордена Трудового Красного Знамени высшее техническое училище им. Н. Э. Баумана (71) Заявители (54) СТОХАСТИЧЕСКАЯ МОДЕЛЬ СИСТЕМЫ МАССОВОГО

ОБСЛУЖИВАНИЯ

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

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

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

Целью изобретения является расширение класса решаемых задач.

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

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

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

15 Схема содержит устройство 1 генерирования входного потока заявок с регулируемыми вероятностными характеристиками пнтервалов времени между моментами появления заявок; устройство 2 регистрации длины очереди, пред20 ставляющее собой реверсивный счетчик; элемент ИЛИ 3, анализирующий наличие очереди на обс.1уживанпс; модель 4 обслуживающего прибора с регулируемыми вероятностными характеристиками времени обслуживания зая25 вок, начинающая работу при наличии в очереди на обслуживание хотя бы одной заявки; устройство 5 имитации очереди, позволяющее задавать произвольные требуемые вероятностные характеристики допустимого времени пре526920

3 бывания заявок в очереди; регистр 6 сдвига, ocólllÎoTÂëÿIoIl1èÉ запоминание заявок, поступгпощих на обслуукпванпе на допустисмое время пребывания пх в очереди; блок 7 поиска и селсктнвпого гашения заявок, обеспечивающий гашение (исключение из очереди) заявки, находящейся в регистре сдвига и обслужснной моделью обслужпгающего прибора; генераторы 8 и 9--пуассоновских импульсных потоIcon, настраиваемые таким образом, iiто формируемые ими временные интервалы между соседними импульсами могут подчиняться любому наперед заданному (в том числе и регулярному) закону распределения; регулпрозкой характеристик импульсных потоков, формируемых генераторами 9, достигается задание требуемой функции распределения случайного допустимого времени пребывания заявки в очсреди; двухвходовыс элементы И 10 и элемент ИЛИ 11.

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

Устройство 1 генерирования входного потока "àÿâîê выдает через промежутки времени, распределенные в соответствии с заданным законом (в том числе и через регулярные проме кутки времени при соответствующей настройке), заяьки (импульсы), поступающие на вход сложения устройства 2 регистрации длины очереди заявок и образующие очередь в устройстве 5 имитации очереди.

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

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

Для каждой заявки, находящейся на очереди, случайная величина т допустимого времени пребывания ее в очереди может принимать значения от нуля до т,. Этот закон распределения величины т зависит от распределения интервалов в потоках, формируемых генераторами 8 и 9 импульсных потоков. Значение величины т„, зависит от разрядности Л регистра сдвига, средней частоты следования импульсов сдвига и закона распределения временных интервалов в потоке импульсов от генератора

8 сдвигающих импульсов.

Наиболее просто осуществляется воспроизведение любой функции распределения допустимого времени т пребывания заявок в очереди при регулярном потоке импульсов сдвига, поступающих от генератора 8, и пуассоновских потоках импульсов, формируемых генераторами 9. Пусть в некоторый момент времени единичный сигнал (заявка) находится в I-ом разряде регистра 6 сдвига. За время т " =1/f пре5

2) 30

Величина т„равна при этом суммарному времени пребывания единичного сигнала во всех разрядах регистра 6 сдвига „= Лс//.

По истечении этого времени заявка (импульс) появляется на (Л +1)-ом выходе регистра 6 сдвига (выход переполнения разрядной сетки регистра) и поступает через элемент

ИЛИ 11 на выход устройства 5 имитации очереди, а также на выход модели.

Таким образом, регулировкой параметров импульсных потоков от генераторов 8 и 9 обеспечивается воспроизведение любых значений вероятностей Р;(т ) и тем самым требуемой произвольной функции распределения F(t) допустимого времени т пребывания заявок в очереди при заданном максимальном значении тм

Дополнительные функциональные возможности предлагаемой стохастической модели системы массового обслуживания состоят в том, бывания заявки в 1-ом разряде регистра 6 сдвига имеется определенная (заранее расчитываемая) вероятность Р;(т" ) появления импульса от с-го генератора 9 импульсного потока на входе i-го эaciieilTa И 10. Этот импульс проходит элемент ИЛИ 11 и появляется на выXOQC уCTpoltCTB2 5 IIV IITQII,IIII очереди, на выходе модели, далее поступает чсрез (-и элемент И 10 на пулевой установочный вход

1-го разряда регистра 6 сдвига и устанавливаcl этот разряд в нулевое состояние, т. е. исключает данную заявку из очереди, так как допустимое время т пребывания ее в очереди истекло. Если же за время т " через 1-й элемент

И 10 не пройдет ни одного импульса от 1-го генератора 9 пуассоновского потока, то очередной импульс от генератора 8 регулярного потока перешлет единичный сигнал (продвинет заявку на позицию вперед) п следующий разряд регистра 6 сдвига.

Значения Pl(T..") при изменении 1 от 1 до до N связаны с приращениями л сР(() воспроизводимой функции распределения F(t) случайной величины T следующим образом:

Р (с4)-с — 1

1 —, Л F (s1

g=l

Воспроизведение вероятностей Pl(T" ) обеспечивается установкой соответствующих интенсивностей 1„. генераторов 9 импульсных потоков, формирующих в рассматриваемом случае экспоненциально распределенные временные интервалы между импульсами, обеспечивающие выполнение равенства, P (" ) = j> e " Ж = 1 — e ", О откуда при заданных значениях Р,(т" ) находятся значения i„

>I = — f1è(1 — Р,()I.

526920 что в ней воспроизводится случаиный характер максимального допустимого времени т„ пребывания заявок в очереди. Это достигается соответствующей настройкой генератора 8 сдвигающих имllyzl con. Так, lip« lcclloHeHqHальном распределении выходного потока генератора 8 величина т,„ будет распределена по закону Эрланга (М вЂ” 1)-го порядка. Настройка генератора 8 сдвигающих импульсов на нормальный закон распределения интервалов в выходном потоке обеспечивает получение нормально распределенной случайной величины т.„. При этом соответствующей настройкой генераторов 9 импульсных потоков обеспечивается аппроксимация требуемых функций распределения допустимого времени т пребывания заявок в очереди, в первом случае смесью распределений Эрланга (i — 1)-го порядка, 1, 2, ..., N, а во втором случае смесью нормальных распределений, являющихся i-кратными, i=1, 2, ..., N, композициями нормальных распределений исходного потока сдвигавших импульсов от генератора 8.

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

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

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

Формула изобретения

20 Стохастическая модель системы массового обслуживания по авт. св. № 3! 1280, о тл и ч аю щ а я с я тем, что, с целью р":ñøèðåíèÿ класса решаемых задач, опа содержит (n — 1) генераторов пуассоновских импульсных потоков

25 с регулируемыми интенсивностями (n — 1), двухвходовых элементов И и один (n — 1) входовой элемент ИЛИ, причем генераторы пуассоновских импульсных потоков через элементы

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

35 элементов И подключены к установочныAl входам соответствующих разрядов управляемого регистра сдвига.

526920

Составитель И. Хазова

Техред 3. Тараненко

Редактор Н. Суханова

Корректор Л. Орлова

Типография, пр. Сапунова, 2

Заказ 2314/16 Изд. № 1650 Тираж 864 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, 7К-35, Раушская наб., д. 4/5