Устройство для моделирования систем массового обслуживания Советский патент 1982 года по МПК G06N7/08 G06G7/48 

(54) УСТГОЙСТВО ДЛЯ МОДЕШ1ГОВАНИЯ СИСТЕМ МАССОВОГО

I

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

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

Наиболее близким по технической сущности к изобретению является устройство для моделирования систем массового обслужива,ния, содержащее m блоков моделирования фазы систем массового обслуживания, блок генераторов случайных потоков импульсов, входы и выходы которых соединены на наборном поле в соответствии с топологией фаз системы массового обслуживания, причем каждый блок моделирования фазы системы маеОБСЛУЖИВАНИЯ

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

10 выход которого соединен с первыми входами элементов И, вторые входы которых соединены с выходами триггеров соответственно, BXOjUd которых соединены с выходами первого дешифратора соответственно, входы котоISрото соедансны с разрядными выходами счетчика соотв« тственно, а вычитающий вход реверсивного счетчика соединен с выходом третьего элемента ИЛИ, входы koToporo соединены с входами генераторов случайных

временных интервалов и подключены к выходам элементов И соответственно, третьи выходы которых соединены с выходами элементов НЕ соответственно, вхопы которых подключены к выходам генераторов случайных временных Интервалов и к входам элементов дифференцировання соответственно, выходы к торых являются выходами блока, четвертый вход каждого i-ro элемента И соединен с вы ходом каждого (i-l)-ro генератора случайных временных интервалов соответственно. Данное устройство позволяет моделировать многоканальные массового обслуживания с расчетом числа каналов обслуживания в каждом звене, исходя из заданной дли ны очереди в нем. При зтом не учитывается время пребывания заявок в системе 2. Вместе с тем, имеется достаточно большое чнсло сложных систем, в которых время пре бьгеания заявок не должно превышать допустимого, т.е. P(t Tc|on)P9on, )- вероятность того, что . время пребьшания заявки в системе меньше до пустимого; допустимая вероятность времени пребьшания заявки в системе. Цель изобретения - расширение функциона ных возможностей за счет оптимального выбора количества каналов обслуживания в фазах. Указанная цель достигается тем, что в устройство для моделирования, содержашее m блоков моделирования фазы систем массового обслуживания и блок генераторов потока заявок, входы и выходы которых соединены на наборном поле согласно топологии фаз системы массового обслуживания, пр чем блок генераторов потока заявок включает генератор тактовых импульсов и датчики случайных импульсов, а каждый блок моделирования фазы системы массового обслужи вания содержит элементы ИЛИ, элементы И, триггеры, генераторы случайных временных интервалов / элементы НЕ, дифференцирующие элементы, первый дешифратор, счетчик и реверсивный счетчик, суммирующий вход которого соединен с выходом первого элемента ИЛИ, входы которого являются группой входов блока моделирования фазы системы массового обслуживания, разрядные выходь, реверсивного счетчика соединены с входами второго элемента ИЛИ, выход которого подключен к первым входам первого, второго и третьего элементов И, вторые входы которых соединены с выходами триггеров соответ ственно, входы которых подключены к выхо дам первого дешифратора соответственно. 34 входы которого соединены с разрядными выходами счетчика соответственно, вычитающий вход реверсивного счетчика подключен к выходу третьего элемента ИЛИ, входы которого соединены соответственно с выходами первого, второго и третьего элементов И и подключены к входам первого, второго и третьего генераторов случайных временных интервалов соответственно, выход каждого из которых через одноименный элемент НЕ соединен с третьим входом одноименного элемента И, выход первого генератора случайных временных интервалов подключен к четвертому входу второго элемента И, выходы генераторов случайных временных интервалов соединены с входами: дифференцирующих элементов соответственно, выходы которых являются группой выходов блока моделирования фазы системы массового обслуживания, каждый блок моделирования фазы системы массового обслуживания Дополнительно содержит коммутатор, выход которого соединен с входом счетчика, разрядные выходы реверсивного счетчика через второй дешифратор подключены к группе коммутатора, вход которого является входом блока моделирования фазы системы массового обслуживания, в блок генераторов потока заявок дополнительно введен элемент запрета, выход которого соединен с входами датчиков случайных импульсов, а выход генератора тактовых импульсов подключен к первому входу элемента запрета, а также в устройство введен блок оптимизации, содержащий элементы ИЛИ, элементы запрета, дифференцирующие элементы, элементы задержки, триггеры, дешифратор, регистр, счетчики, сумматоры, причем вьисод первого элемента ИЛИ в блоке оптимизации подключен к первому входу первого элемента запрета, выход которого соединен с первым входом первого счетчика, разрядные выходы которого соединены с входами дешифратора, один выход которого подключен к входу первого дифференцирующего элемента, другие выходы дешифратора соединены с входами второго элемента ЛЛИ, выход которого подключен к входу второго дифференцир)тощего элемента, выход которого соединен со счетным входом первого триггера и с единичным входом второго триггера, нулевой выход которого подключен к входу второго элемента запрета, выход которого соединен с первыми входами первого и второго элементов И, выходы которых подключены к первым входам второго и третьего счетчиков соответственно, выходы которых соединены с первым и вторым входами первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого соединен с первым входом третьего

сумматора, выход которого подключен к входу третьего дифференцирующего элемента, выход которого является выходом блока оптими зации и через первый элемент задержки соединен с нулевым входом третьего триггера, еди- s ничный выход которого подключен к второму входу первого элемента запрета, выход первого дифференцирующего элемента соединен с единичным входом третьего триггера, нулевым входом второго триггера, с первыми входами третьего и четвертого элементов ИЛИ и с входом второго элемента задержки, выход которого подключен к второму входу первого счетчика, к третьему входу первого сумматор и к входу третьего элемента задержки, выход которого соединен с вторым входом второго сумматора и через регистр подключен к второ му входу третьего сумматора, выход первого счетчика соединен с третьим входом второго сумматора, нулевой выход первого триггера подключен к второму входу первого элемента И и через четвертый дифференцирующий элемент соединен с вторым входом третьего элемента ИЛИ, выход которого подключен к второму входу третьего счетчика, единичный выход первого триггера соединен с втврым входом второго элемента И и через пятый дифференцирующий элемент подключен к второму входу четвертого элемента ИЛИ, выход которого подключен к второму входу второго счетчика, выход элемента запрета блока генераторов потока заявок соединен с вторым входом второго элемента запрета блока оптимизации, единичный выход третьего триггера блока оптимизации подключен к второму входу первого элемента запрета блока оптимизации и к второму входу элемента запрета блока генераторов потока заявок, группа входов i-ro блока моделирования фазы систем массового обслуживания (где i 1-п) соединена соответственно с группой выходов (i-l)-ro блока моделирования фазы систем массового обслуживания, группа вы ходов п-го блока моделирования фазы систем массового обслуживания подключена к группе входов блока оптимизации, выходы которого соединены с входами всех коммутаторов блоков моделирования фазы систем массового обслуживания. На чертеже показана функциональная схема предлагаемого устройства. Устройство содержит блок 1 генераторов потоков заявок, блок 2 моделирования фазы cHCTeivibi массового обслуживания и блок 3 оптимизации. Блок 1 генераторов потоков заявок состоит из генератора 4 тактовых импульсов, элемента 5 запрета, датчиков 6i, 62,..., 6 случайных импульсов.

9266636

Блок 2 моделирования фазы системы массового обслуживания состоит из реверсивного счетчика (длины очереди) 7, счетчика (числа приборов обслуживания) 8, дешифраторов 9 и 10, генераторов 11, 12 и 13 случайных временных интервалов (генераторов обслуживания), триггеров 14, 15 и 16 включения приборов обслуживания элементов И 17, 18 и 19, коммутатора 20, элементов ИЛИ 21, 22 и 23, элементов НЕ 24. 25 и 26, дифферейдирующих элементов 27, 28 и 29. Блок 3 оптимизации состоит из третьего дифференцирующего элемента 30, счетчиков 31 и 32 временных имтгульсов, счетчика 33 числа испытаний, дещифратора 34, триггеров 35, 36 и 37, сумматоров 38, 39 и 40, регистра 41, элементов ИЛИ 42-45, элементов И 46 и 47, элементов 48 и 49 запрета, элементов задержки. 50, 51 и 52 второго, четвертого, пятого и третьего дифференцирующих элементов 53, 54, 55 и 56. Модель исследуемой системы массового обслуживания набирается путем коммутации выходов YO, Y,, ..., YJ и входов Хо, Xi, -, Xj блоков 1 и 2 в соответствии с топологией графа, выходы YQ, Yj, .... YJ последнего блока системы коммутируются с входами ZQ, Zi, ..., Zp блока 3 оптимизации,выходы So, Si, ..., Sr блока 3 оптилшзации соединяются с входами Qn всех коммутаторов системы. Для достаточно больщого числа систем входящий поток заявок подчиняемся - закону Пуассона, а время пребывания в них - экспоненциальному. Тогда , P(t-T)-m ЛИ-екр(-ЯГ4) 0) Интенсивность потока заявок на выходе системы определяется THKJ - t пО-Р) Та Устройство работает следующим образом. Блок 1 генераторов потоков заявок вырабатьшает импульсные потоки. Импульсы от источников заявок или от любого промежуточного звена системы массового обслуживания (СМО) поступают на вход элемента ИЛИ 23. Реверсивный счетчик 7 подсчитьгеает количество заявок, поступающих на обслуживание. В исходном состоянии выход коммутатора 20 скоммутирован через дешифратор 10 с реверсивным счетчиком 7, устанавливающим максимально допустимую очередь заявок в рассматриваемом звене. Счетчик 8 находится в нулевом состоянии, триггер 16 в единичном. На выходе генератора 11 обслуживания сигнал отсутствует. Сигнал о наличии заявок поступает со счетчика 7 через элемент ИЛИ 22 на 7 элемент И 19, на другие входы которого поступают сигналы с элементы НЕ 26 и триггера 16. Сигнал с элемента И 19 запускает генератор 11 обслуживания, моделирующего процесс обслуживания заявки и через элемент ИЛИ 21 вычитает из счётчика 7 единиц Выходной сигнал с генератора 11 обслуживания через элемент НЕ 26 закрьтает элемент И 19, запрещая тем самьп поступление новой заявки на обслуживание по данному каналу. После окончания обслуживания сигнал, продифференцированный дафференцирующим элементом 29, поступает на выходную клемму YO данного звена. Как только очередь достигнет максимально допустимого значения, определяемого разрядом реверсивного счетчика 7, подключенного к выходу коммутатора, на выходе коммутатора 20 появится сигнал, записывающий в счетчик 8 единицу. Дешифратор 9 переводит триггер 15 в единичное cocтoя шe, с выхода которого поступает сигнал на элемент И 17. На другие входы элемента И 17 поступают сигналь с элемента НЕ 25, а также с элемента ИЛИ 22 и генератора 11 обслуживания. Первый сигнал поступает только в том случае, когда второй канал обслуживания (генератор 12 обслуживания) свободен, а второй и третий в -случае наличия заявок и занятости гюрвого канала обслзокивания (генератор 11 обслуживания). Сигнал с элемента И 17 запускает генератор 12 обслуживания и через элемент ИЛИ 21 уменьшает число заявок в очереди, т.е. уменьшает показание реверсивного счетчика 7 на единицу. При очередном заполнении реверсивного счетчика 7 коммутатор 20 вновь пропустит один импульс на счетчик 8, откуда после дешифрации импульс устанавливает соответствующий триггер в единичное состояние, подключая очередной канал обслуживани Блок 3 оптимизации предназначен для определения интенсивности потока обслуженных заявок ( Л ), сравнения ее с заданной и управления величиной максимально допустимой очереди заявок на звеньях систем В начальный момент времени триггеры 35 и 36, счетчики 31, 32 и 33, сумматоры 38, 39 и 40 блока оптимизации находятся в нулевом состоянии. Поток импульсов обслуженных заявок с выходов YO, Yj,..., YJ послед него звена моделируемой системы через входы Zo, Zi, ..., Zp и элемент ИЛИ 42 и открытый элемент 49 запрета поступает из счет чик 33 числа испытаний. С (п-1) выходов дешифратора 34 через элемент ИЛИ 43 и дифференцирующий элемент 53 сигналы счета последовательно поступают на счегаый вход триггера 37, пертбрасьтая его в нулевое или 3 единичное состояние, открывают поочередно элементы И 46, И 47. Допустим, триггер 37 находился в нулевом состоянии. Сигнал с первого выхода дешифратора 34 через элемент ИЛИ 43 и дифференцирующий элемент 53 устанавливает триггер 36в единичное состояние и снимает сигнал запрета с элемента 48 запрета. Импульсы от тактового генератора 4 поступают на элементы И 46 и И 47. Одновременно импульс с выхода дифференцирующего элемента 53 устанавливает триггер 37в единичное состояние. Сигнал с единичного выхода триггера 37 открывает элемент И 46 и тактовые импульсы проходят на счетчик 31. Счетчик 31 будет подсчитывать тактовые импульсы до тех пор, пока на триггер 37 не придет следующий импульс. Таким образом, триггер 37 подсчитывает время tj между первым и вторым импульсами потока обслуженных заявок. Через дифференцирующий элемент 54, элемент ИЛИ 44 поступает сигнал на вход чтение счетчика 32. Так как в данный момент времени в счетчике 32 информации нет, яс- но, что в сумматоре 38 информации не поступает. Следзтощий импульс обслуженного потока проходит через элемент ИЛИ 42, элемент запрета 49, счетчик 33 и появляется на втором выходе дешифратора 34. Через элемент ИЛИ 43 и. дифференцирующий элемент 53 триггер 37 устанавливается вновь в нулевое состояние. Элемент И 47 открывается и счетчик 32 подсчитьшает время (ta) между вторым и третьим импульсами обслуженного потока заявок. При этом триггер 35 по единичному входу подтверждает свое состояние, а сигнал с нулевого выхода триггера 37 через дифференцирующий элемент 55, элемент ИЛИ 45 поступает на вход чтение счетчика 31, считывая информацию э сумматор 38. Таким образом, после счета (п-1) импульсов в сумматоре 38 накопится суммарное время между импульсами (tj + tj + ... + + tti-() обслуженного потока заявок. С приходом п-го имцульса сигнал появится на п-ом выходе дешифратора 34 и через дифференцирующий элемент 56, элементы ИЛИ 44 и 45 поступит на входы чтение счетчиков 31 и 32. Так как содержимое одного из них уже было считано n-1-ым импульсов и в нем нет информации, то чтение происходит лишь из того , который подсчитал время (tn) между 1-1 и п-ым импульсами. Кроме того, импульс с выхода дифференцирующего элемента 56 устанавливает триггер 35 в единичное состояние, обеспечивая запрет на элементах запрета 5 и 49, а триггер .в нулевое состояние, подавая сигнал запрета на элемент запрета-48. При этом на первое звено модели не буду подаваться импульсы потока заявок, в течение времени анализа интенсивности обслуженного потока. Так как модель- будет продолжать обслуживать накопившуюся очередь заявок, то необходимо счетчик 33 закрыть. Это достигается подачей запрещающего сигнала на элемент 49 запрета. Элемент 48 запрета открыт и раз решает прохождение тактовых импульсов на счетчики 31 и 32 только во время работы счетчика 33. Таким образом, с приходом п-го импульса заканчивается время накопления суммы Х tj, и начинается время анализа интенсивности обслуженного потока. Импульс с выхода дифференцирующего элемен та 56, задержанный элементом задержки 50 на вре мя суммирования сумматором 38 двух после них чисел, поступает на входы чтение счетчика 33 и сумматора 38. Сумматор 39 совместно с сумматорами 38 и 40 производит операцию деления двух чисел. Число обслуженных; заявок (п) запи сывается из счетчика 33 в сумматор 39. Сум матор 38 хранит делитель ( .. ti, ) и передает его в сумматор 39. Результат деления UH 1 -т накапливается в сумматоре 40 .-5. . Схема управления делением на чертеже, не показана. После задержки элементом 51 импульс чтение поступает на вход регистра 41, считывая записанную в нем информацию в сумм тор 40. В регистре 41 заранее записша константа Л , рассчитанная по формуле (2). В сумматоре 40 происходит сравнение полученной величины интенсивности обслуженного потока заявок ( ) с заданной интенсивностью С Л. ). При на выходе знакового разряда сумматора 40 появляется сигнал, который после дифференцирования элементом 30 подается через выходы So, Sj, ..., Sr блока оптимизации и вход Qn звеньев модели на коммутатор 20. При этом коммутатор 20 подключает к входу счетчика 8 следующий в сторону уменьшения разряд дешифратора 10, отключая старший разряд де шифратора, уменьшая тем самым допустимую длину очереди на единицу. Этот же импульс через элемент 52 задержки устанавливает, триг гер 35 в нулевое состояние и снимает сигналы запрета с элементов запрета 5 и 49. Модель возобновляет работу. При Я Я J, сигнала с выхода сумматора 40 не будет. Элементы 5 и 49 запрета оста910 нутся закрытыми. Процесс моделирования заканчивается. Количество каналов обслуживания в каждом звене системы равно dj. +1. где d-L - показания счетчика в i-м звене. Экономический эффект от использования предлагаемого устройства достигается за счет оптимального выбора числа каналов обслуживания в звеньях сложных систем по интегральному вероятностному критерию при ограничении длин очередей. Предлагаемое устройство может быть использовано при совершенствовании систем управления или проектировании новых исследований разных структур в различных условиях функционирования. Его применение позволит избежать трудоемкого процесса разработки алгоритмов и программ моделирования СМО на ЭВМ. Формула изобретени.я Устройство для моделирования систем маесового обслуживания, содержащее m блоков моделирования фазы систем массового обслуживания и блок генераторов потока заявок, входы и выходы которых соединены на наборном поле согласно топологии фаз системы массового обслуживания, причем блок, генераторов потока заявок включает генератор тактовых импульсов и датчики случайных импульсов, а каждый блок моделирова1тя фазы системы массового обслуживания содержит элементы ИЛИ, элементь И, триггеры, генераторы случайных временных интервалов, элементы НЕ, дифференцирующие элементы, первый дешифратор, счетчик и реверсивный счетчик, суммирующий вход которого соединен с выходом первого элемента ИЛИ, входы которого являются группой входов блока моделирования фазы системы массового обслуживания, разрядные выходы реверсивного счетчика соединены с входами второго элемента ИЛИ, выход которого подключен к первым входам первого, второго и третьего элементов И, вторые входы которых соединены с выходами триггеров соответственно, входы которых подключены к выходам первого дешифратора соответственно, входы которого соединены с разрядными выходами счетчика соответственно, вычитающий вход реверсивиого счетчика подключен к выходу третьего элемента ИЛИ. входы которого соединены соответственно с выходами первого, второго и третьего элементов И и «подключены к входам первого, второго и третьего генераторов случайных временных интервалов соответственно, выход каждого из которых через одноименный элемент НЕ соединен с третьим входом одноименного элемента И, выход первого генератора случайных временных интер1192валов подключен к четвертому входу второго элемента И, выходы генераторов случакных временных интервалов соединены с входами дифференцирующих элементов соответственно, выходы которых являются группой выходов блока моделирования фазы системы массового обслуживания, отличающееся тем, что, с целью расширения функциональных возможностей за счет оптимального выбора количества каналов обслуживания в фазах, каждый блок моделирования фазы системы массового обслуживания дополнительно содержит коммутатор, выход которого соединен с входом счетчика, разрядные выходы реверсивного счетчика через второй дешифратор подключены к группе входов коммутатора, вход которого является входом блока моделирования фазы системы массового обслуживания, в блок генераторов потока заявок дополнительно введен элемент запрета, выход которого соединен с входами датчиков случайных импульсов, и выход генератора тактовых импульсов, подключен к первому входу элемента запрета, а также в устройство введен блок оптимизации, содержащий элементы ИЛИ, элементы запрета, дифференцирующие элементы, элементы задержки, триггеры, дешифратор, регистр, счетчики, сумматоры, причем выход первого элемента ИЛИ в блоке оптимизации подключен к первому входу первого элемента запрета, выход которого соединен с первым входом первого счетчика, разрядные вХоды которого соединены с входами дешифратора, один выход которого подключен к входу первого дифференцирующего элемента другие выходы дешифратора соединены с входами второго элемента ИЛИ, выход которого подключен к входу второго дифференцирующего элемента, выход которого соединен со счетным входом первого триггера и с единичным входом второго триггера, нулевой вы ход которого подключен к входу второго эле мента запрета, выход которого соединен с пер выми входами первого и второго элементов И, выходы которых подключены к первым входам второго и третьего счетчиков соответственно, выходы которых соединены с первым и вторым входами первого сумматора, выход которого подключен к первому входу второго сумматора, выход которого соединен с первым входом третьего сумматора, выход которого подключен к входу третьего дифференцирующего элемента, выход которого 12 является выходом блока оптимизации и через первый элемент задержки соединен с нулевым входом третьего триггера, единичный выход которого подключен к второму входу первого элемента запрета, выход первого дифференцирующего элемента соединен с единичным входом третьего триггера, нулевым входом второго триггера, с перЬыми входами третьего и четвертого элементов ИЛИ и с входом второго элемента задержки, выход которого подключен к второму входу первого счетчика, к третьему входу первого сумматора и к входу третьего элемента задержки, выход которого соединен с вторым вхоДом второго суммахора и через регистр подключен к второму входу третьего сумматора, выход первого счетчика соединен с третьим входом второго сумматора, нулевой выход первого триггера подключен к второму входу первого элемента И и через четвертый дифференцирующий элемент соединен с вторым входом третьего элемента ИЛИ, выход которого подключен к второму входу третьего счетчика, единичный выход первого триггера соединен с вторым входом второго элемента И и через пятый дифференцирующий элемент подключен к второму входу четвертого элемента ИЛИ, выход которого подключен к второму входу второго счетчика, выход элемента запрета блока генераторов потока заявок соединен с вторым входом второго элемента запрета блока оптимизации, единичный выход третьего триггера блока оптимизации подключен к второму входу первого элемента запрета блока оптимизаидии и к второму входу элемента запрета блока генераторов потока заявок, группа входов i-ro блока моделирования фазы системы массового обслуживания (где i 1-п) соединена соответственно с группой выходов (i-1)-ro блока моделирования фазы систем массового обслуживания, группа выходов п-го блока моделирования фазы систем массового обслуживания подключена к группе входов блока оптимизации, выходы которого соединены с входами всех коммутаторов блоков моделиройания фазы систем массового обслуживания. Источники информации, принятые во внимание при экспертизе 1. ABtopCKoe свидетельство СССР № 347763, кл. G 06 G 7/48, 1970. 2. Авторское свидетельство СССР № 723S80, кл. G 06 F 15/20, 1977 (прототип).

. Г

Si

i

.

i

а

«

.4

:f

s%,

T

1.

- t

.«4j

«V

c

b-.

:

4т

T-V5

ЗЩ

, V

га

t-

на I

|

,.JI

- I

-TN ii

5

I

1

M45

rar

t- cD

IS-J

Hi

n

5Г l

if - tif-Z

M

l

Г I