Устройство для моделирования систем массового обслуживания

 

1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ, содержащее первый канал обслуживания заявок,состоящий из реверсивного счетчика, разрядные выходы которого соединены соответственно с входами первого элемента И и первого элемента ИЛИ, выход которого соединен с входом запуска блока обслуживания , второй элемент И, блок регистрации , отличающееся тем, что, с цепью .расширения функциональных во:зможностей путем модели.рования ухода заявок из канала обслуживания с заданной вероятностью, оно дополнительно содержит коммутатор импульсов, второй канал обслуживания заявок, состоящий из последовательно соединенных реверсивного счетчика , элемента ИЛИ и блока обслуживания , и блок анализа ситуации, сост ТОЯ1ЦИЙ из генератора импульсов, генератора случайных импульсов, регистра сдвига, элемента И, двух элементов ИЛИ, двух элементов задержки, группы элементов И, выход генератора импульсов соединен с сдвигающим входом регистра сдвига и входом первого элемента задержки, разрядные выходы реверсивного счетчика подключены соответственно к входам первого элемента ИЛИ, выход которого подключен к входу генератора случайных импульсов , выход которого соединен с вычитающим выходом реверсивного счетчика и входом второго элемента задержки, выход которого подключен к первому входу элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, разрядные выходы регистра сдвига подключены.соответственно к первым входам элементов И группы, второй вход первого элемента И группы подключен к выходу третьего элемента И группы, вто§ рые входы К-го и (K+D-ro элементов, группы объединены и соединены с &} выходом (К+3)-го элемента И группы (, П-1), вторые входы п -го и (П+1)-го элементов И группы соединены с выходом генератора случайных импульсов, второй вход (П+2)го элемента И группы подключен к выходу первого элемента задержки, СО входы второго элемента ИЛИ соедине;о : ны с соответствунмцими выходами элементов И группы, разрядные входы гаS шения сигнала регистра сдвигд соединены с выходами соответствукяцихэлементов И группы, выход элемента И блока анализа ситуации подключен к первому информационному входу коммутатора импульсов и первому вычитающему входу реверсивного счетчи ка, второй вычитающий вход которого соединен с первым выходом блока обслуткивания первого канала обслуживания и первым входом блока регистрации , второй вход которого соединен С выходом последнего элемента И группы блока анализа ситуации, треть

ае Oи

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК цр G 06 F 15/20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ASTOPCHOMY СВИДЕТЕЛЬСТВУ

% 1 (21) 3563109/18-24 (22) 11.03.83 (46) 23.06.84 Бюл. И 23 (72) Ю,Н,Беленов и А.В.Горностай (53) 681.3 (088.8) (56) 1. Авторское свидетельство СССР

У 311280, кл. G 06 G 7/48, 1970.

2. Авторское свидетельство СССР

Ф 521569, кл. G 06 F 15/20, 1974 (прототип). (54) (57) 1. УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ, содержащее первый канал обслуживания заявок, состоящий из реверсивного счетчика, разрядные выходы которого соединены соответственно с входами первого элемента И и первого элемента ИЛИ, выход которого соединен с входом запуска блока обслуживания, второй элемент И, блок регистрации, о т л и ч а ю щ е е с я тем, что, с целью .расширения функциональных возможностей путем модели;. рования ухода заявок из канала обслуживания с заданной вероятностью, оно дополнительно содержит коммутатор импульсов, второй канал обслуживания заявок, состоящий из последовательно соединенных реверсивного счетчика, элемента ИЛИ и блока обслуживания, и блок анализа ситуации, сос-. тоящий из генератора импульсов, гене. ратора случайных импульсов, регистра сдвига, элемента И, двух элементов

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

:к входу генератора случайных импульсов, выход которого соединен с вычитающим выходом реверсивного счетчика и входом второго элемента задержки, выход которого подключен к первому входу элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, разрядные выходы регистра сдвига подключены соответственно к первым входам элементов И группы, второй вход первого элемента И группы подключен к выходу третьего элемента И группы, вторые входы К-ro и (К+1)-го элементов Е

O группы объединены и соединены с выходом (К+3)-ro элемента И группы (K=2, 11 -1), вторые входы 11 -го и (0+1)-го элементов И группы соединены с выходом генератора случай- а .й ных импульсов, второй вход (11+2)- .

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

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

Ф с:

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

Известно устройство для моделирования очереди, содержащее генератор заявок, блок обслуживания заявок, регистр сдвига и реверсивный счет чик f1) .

Недостатком данного устройства является невозможность моделирования систем с очередью, в которой заявка не покидала бы ее до тех пор, пока не получит обслуживание. элемента задержки и сдвигающим входом регистра сдвига, информацион. ный вход первого разряда регистра сдвига является первым входом блока, вторым входом которого является вход генератора случайных импульсов, выход которого соединен с входом второго элемента задержки, выход которого подключен к первому входу элемента И, второй вход которого соединен с выходом элемента ИЛИ, выход элемента И является первым выходoм блока, вторым выходом которого является выход последнего эле мента И группы, входы элемента ИЛИ подключены к выходам соответствующих элементов И группы, первые входы ко. торых соединены с разрядными выходами регистра сдвига, входы гашения сигнала каждого разряда регистра сдвига подключены к выходам соответствующего элемента И группы, второй вход первого элемента И группы подключен к выходу третьего элемента И группы, вторые входы К-го и (К+1)-ro элемента И группы объединены и соединены с выходом (K+3)-ro элемента И группы (К=2, fl -1), второй вход последнего элемента И группы подключен к выходу первого элемента задержки, а выход генератора случайных импульсов соединен с вторыми входами И -го и (tl+1)-го элементов цуппы.

Наиболее близким по технической сущности и достигаемому результату к предлагаемому является устройство для моделирования очереди, содержащее реверсивный счетчик, первая груп= па выходов которого соединена с соответствующими входами блока имитации длины очереди, вторая группа выходов — с соответствующими входа10 ми эадатчика ограничения очереди, выход которого соединен с первым входом блока выявления переполнения очереди, выход которого подключен к первому входу второго канала об15 служивзния. Данное устройство позволяет моделировать системы массово1099316

t5

25 за

Э го обслуживания (СМО) с переменной длиной очереди $23 .

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

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

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

Поставленная цель достигается тем, что в устройство для моделирования систем массового обслуживания, содержащее первый канал обслуживания заявок, состоящий из реверсивного счетчика, разрядные выходы которого соединены соответственно с входами первого элемента И и первого элемента ИЛИ, выход которого соединен с входом зайуска блока обслуживания, второй элемент И, блок регистрации, введены коммутатор импульсов, второй канал обслуживания заявок, состоящий из последовательно соединенных реверсивного счетчика, элемента ИЛИ и блока обслуживания, и блок анализа ситуации, состоящий из генератора импульсов, генератора случайных импульсов, регистра сдвига, элемента И, двух элементов ИЛИ, двух элементов задержки, группы элементов И, выход генератора импульсов соединен с сдвигающим входом регистра сдвига и входом первого элемента задержки, разрядные выходы реверсивного счет- чика подключены соответственно к вхо. дам первого элемента ИЛИ, выход которого подключен к входу генератора случайных импульсов, выход которого соединен с вычитающим выходом реверсивного счетчика и входом второго элемента задержки, выход которого подключен к первому входу элемента И, второй вход которого соединен с выходом второго элемен-. та ИЛИ, разрядные выходы регистра сдвига подключены соответственно к первым входам элементов И группы, второй вход первого элемента И группы подключены к выходу третьего элемента И группы, вторые входы К-го и (К+1) -го элементов группы объединены и соединены с выходом (К+3)-го элемента И группы (К=2, п-1), вторые входы H-"ro и (hi+1)-го элементов

И группы соединены с выходом генератора случайных импульсов второй вход (0+2)-ro элемента И группы подключен к выходу первого элемента задержки, входы второго элемента

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

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

1099316

Блок обслуживания содержит генератор импульсов, генератор случайных импульсов, регистр сдвига, группу элементов И, элемент ИЛИ, элемент И, два элемента задержки, выход генератора импульсов соединен с входом первого элемента задержки и сдвига— юп;им входом регистра сдвига, информационный вход первого разряда регист ° ра .сдвига является первым входом блока, вторым входом которого являет. ся вход генератора случайных импульсов, выход которого соединен с входом второго элемента задержки, выход которого подключен к первому входу элемента И, второй вход которого соединен с выходом элемента ИЛИ, выход элемента И является первым выходом блока, вторым выходом которого является выход последнего элемента И группы, входы элемента ИЛИ подключены к выходам соответствующих элементов И группы, первые входы которых соединены с разрядными выходами. регистра. сдвига, входы гашения сигнала каждого разряда регистра сдвига подключены к выходам соответствующего элемента И группы, второй вход первого элемента И группы подключен к выходу третьего элемента И 30 группы, вторые входы К- ro и (K+1)-ro элементов И группы объединены и сое" динены с выходом (K+3)-ro элемента И группы (К=2, г1-1), второй вход последнего элемента И группы подключен к выходу первого элемента задержки, а выход генератора случайных импульсов соединен с вторыми входами h-го и (г1+1)-го элементов И группы.

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

Устройство содержит реверсивный 45 счетчик 1, блок,2 анализа ситуации, элемент ИЛИ 3, коммутатор 4 импульсов, первый элемент И 5, блок 6 обслуживания, второй элемент И 7, блок 8 регистрации, вход 9 устройства.

Коммутатор 4 импульсов содержит элементы ИЛИ 10-12, элементы И 13-16, элементы 17-19 задержки, элемент

20 запрета, входы 21-23, выходы

24 и 25.

Блок 6 обслуживания содержит первый 26 и второй 27 элементы за" держки, элемент И 28, элемент ИЛИ

29, группу элементов И 30, генератор 31 импульсов, генератор 32 случайных импульсов, регистр 33 сдвига, выходы 34 и 35.

Блок 2 анализа ситуации содержит

I выходы 36 и 37, второй элемент ИЛИ .

38,. элемент И 39, первый элемент ИЛИ

40, первый 4 1 и второй 42 элементы задержки,, реверсивный счетчик 43, генератор 44 импульсов, генератор

45 случайных импульсов, регистр 46 сдвига, группу элементов И 47.

Устройство работает следующим образом.

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

24 на первый вход второго элементаИ7

Поступающие на входы коммутатора

4 (фиг. 2) заявки (вход 9 — входной поток, вход 21 — из второго канала обслуживания, вход 22 — с выхода бло. ка анализа ситуации) вначале попадают на элемент ИЛИ 11. В блоке предусмотрено устройство, не позволяющее потерять заявки, если они приходят одновременно по двум или трем входам. Если заявки проходят одновременно по двум из трех входов, то наряду с сигналом, зафиксированным через элемент ИЛИ 11, происходит также фиксация сигнала одним из.элементов И 14-16 и через элемент ИЛИ 12 и элемент 19 задержки второй сигнал поступает на один из вьгходов. Таким образом, в реверсивном счетчике 1 фиксируется поступление двух заявок. Если же заявки поступают одновременно по трем входам 9, 21 и 22, то фиксируется поступ ление трех заявок: первой — через элемент ИЛИ 11, второй — через один из элементов И 14-16, элемент ИЛИ

12 и элемент 19 задержки, третьей— через элемент И 13 и элементы 17 и 18 задержки, Заявки уходят из коммутатора 4 или через элемент 20 запрета при отсут1099316 ствии очереди определенной длины, или непосредственно с выхода элемента ИЛИ 10 при наличии очереди.

В последнем случае на управляющий вход элемента 20 запрета подается 5 сигнал с выхода задатчика ограничения очереди (элемента И 5), который фиксирует определенную длину очереди на. реверсивном счетчике 1. При срабатывании элемента И 5 сигнал с его выхода поступает на вход элемента 20 запрета для переключения выходов коммутатора 4 и одновременно подается на первый вход элемента И 7, подготавливая его к открытию. В этом 15 случае заявки с выхода 24 коммутатора 4 поступают на второй вход элемента И 7 и далее с его выхода на первый вход второго канала обслуживания. Во втором канале обслужива- 20 ния, построенном аналогично первому, заявки проходят обслуживание. Необслуженная по каким-либо причинам во втором канале заявка возвращается в первый канал по входу 21 ком- 25 мутатора 4. Если очередь, зафиксированная в реверсивном счетчике 1, меньше установленной предельной величины, элемент И 7 закрыт, а эле. мент 20 открыт и заявки поступают gp на выход 25.

Наличие очереди фиксируется элементом ИЛИ 3 (фиг . 3) . Если в очереди, имеется хотя бы одна заявка, то сигнал оо этом с выхода элемента ИЛИ

3 подается в блок 6 обслуживания, где происходит включение генератора

32, имитирующего случайное время обслуживания заявки. Пока на выходе элемента ИЛИ 3 есть сигнал, генератор 32 включен. Время между случайными импульсами с. генератора 32 принимается за время обслуживания очередной заявки. Кроме генератора 32, имитирующего время обслуживания заявки, основными элементами блока 6 обслуживания являются также генератор 3 1 тактовых импульсов {ГТИ), УРС и элемент ИЛИ 29. ГТИ и УРС служат для запоминания на время ь д

50 заявки, поступившей в блок 6 обслуживания. Это время устанавливается путем продвижения вспомогательного сиг нала по УРС импульсами сдвига от

ГТИ, поступающими на вход Q регистра 33. Вспомогательный сигнал в

УРС блока 6 поступает с выхода 25 коммутатора 4. Если за время доя с генератора 32 поступает сигнал о завершении обслуживания очередной заявки, то она считается обслуженной и сигнал об этом проходит на выходе. 35 блока 6 обслуживания.

Время ьддд определяется разрядностью регистра 33 и частотой тактовых импульсов ГТИ 31;

Для обеспечения прохождения сигнала об обслуживании заявки на выход 35 блока 6 с выхода генератора

32 в УРС поступает импульс, который используется для селективного гаше— ния вспомогательного сигнала, поступившего с выхода 25 коммутатора и продвигаемого по УРС. Гашение вспомогательного сигнала в УРС происходит следующим образом. Если в единичном состоянии находится И -й разряд регистра 33, то на первом входе соответствующего элемента И группы

30 присутствует разрешающий потенциал с выхода этого разряда. Тогда при появлении импульса с генератора

32 при втором входе этого элемента И он проходит на нулевой вход h -го разряда регистра 33 и через элемент

ИЛИ 29 — на первый вход элемента И

28. На второй вход элемента И 28 поступает тот же импульс с генератора 32 через элемент 27 задержки.

Если к моменту появления сигнала с генератора 32 ц -й разряд регистра

33 находится в нулевом состоянии, то разрешающий сигнал имеется на инверсном выходе этого разряда и импульс с генератора 32 проходит на соответствующие два элемента И группы 30 (r}-1)-го разряда. Если (11-1)-й разряд регистра 33 был в единичном состоянии, то он обнуляет ся. В противном случае сигнал с генератора 32 передается на следующий (11-2)-й разряд, т.е. поиск ближайшего разряда регистра 33 с единичным состоянием продолжается.

С выхода 35 блока 6 обслуживания сигнал о конце обслуживания заявки за время, меньшее или равное с дд подается на вычитающий вход реверсивного счетчика 1 для снятия заявки с учета из системы обслуживания и на суммирующий вход реверсивного счетчика блока 8 регистрации. Если за врел мя ьAä< в УРС не поступает импульс с генератора 32, то заявка считается не обслуженной. В этом случае сигнал об отказе в обслуживании поступает с

1099

9 выхода 4" -ro разряда УРС через соответствующий элемент И группы 30 на вход 34 блока 6 и далее на вход блока

2 анализа ситуации.

Необслуженная в блоке 6 заявка 5 в блоке 2 производит "анализ ситуации" (фиг. 4). В результате анализа заявка может с некоторой вероятностью уйти во второй канал обслуживайия — выход 36 блока 2. Вторая возможность заявки состоит в том, что она с вероятностью 1-q возвращается в прежний канал обслуживания через коммутатор 4 по входу 37. В обоих случаях необслуженная заявка, покидая 15 блок 2, снимается с учета данного канала через вычитающие входы реверсивного счетчика 1. Когда заявка покидает данный канал обслуживания, уходя в другой канал, то сигнал об, Ю этом подается на вычитающий вход реверсивного счетчика блока 8, фиксируя тем самым уход данной заявки из системы обслуживания.

Работа блока 2 анализа ситуации 25 аналогична работе блока 6 обслуживания. Поступающая по входу 34 необслуженная заявка производит "оценку ситуации" эа время ь„ од, которое определяется разрядностью регистра 46 3о и частотой генератора 44 блока 2 (фиг. 4). Заявка включает генератор

45 случайных импульсов с помощью реверсивного счетчика 43 и элемента

ИЛИ 40. Генератор 45 включен, пока в блоке 2 находится хотя бы одна заявка. Генератор 45 имитирует случайное время принятия решения заяв- ° кой. Если за < - время продвижения вспомогательного сигнала по УРС 40 блока 2 с генератора 45 поступает сигнал, то заявка проходит через элементы 38 и 39 на вход 37 блока 4.

В этом случае заявка остается в прежнем канале обслуживания. При 45 этом селективное гашение вспомо гательного сигнала в УРС блока 2 происходит точно так же, как и в блоке 6 обслуживания.

Если за время ь <„ дс генератора 45 не поступает сигнал, то считается, 316

10 что заявка "приняла решение" уйти из данного канала во второй канал.

Технически это осуществляется за счет того, что с генератора 45 за времяЙ, д не поступил сигнал селективного гашения. Следовательно, сигнал с и„ -го выхода регистра 46

4 поступает на выход 36 блока 2 и во второй канал обслуживания. Этот же сигнал поступает также на вычитаннщий вход реверсивного счетчика блока 8, где регистрируется как определенные потери для данного канала обслуживания. В итоге в блоке 8 регистрации определяется результат эффективности данного канала. Аналогично определяется эффективность второго канала.

Подключив счетчик импульсов к входу

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

Тогда блок регистрации первого канала дает число заявок N< обслуженных первым каналом, а блок результатов второго канала дает число заявок 17<, обслуженных им. Если обозначить число заявок, не получивших обслуживания к моменту времени и находящихся в очередях каналов обслуживания или в состоянии оценки ситуации через N, то оно будет равно

N = N - N 1.- -М

3 1 2

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

Технически второй канал обслуживания выполнен точно также, как и первый. Для придания ему свойств с другими характеристиками достаточ" но изменить разрядность УРС или частоту ГТИ.

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

1099316

1099316

1099316

ФигЗ

1099316

Фиг.Ф

ВНВШИ Заказ 4373/40 Тираж 699 . Поутисное

Фиимэл ШШ Патэмт р Г Ужгород, ул. Проектная, 4