Устройство для моделирования сетевых графиков Советский патент 1984 года по МПК G06G7/48 

Изобретение относится к области вычислительной техники, а именно к электронным моделирующим устройствам. По основному авт.св. № 422002 известно устройство для моделирования сетевых графиков, содержащее блок управления, первый выход которого подключен к первому входу первого элемента ИЛИ блока формирования Топологии, блок моделей ветвей по числуработ сетевого графика, каждая из которых выполнена в виде задатчиков адресов, выходами соединенных с элементами И, причем выход первого элемента И соединен с входом формирователя временных интервалов, вход второго элемента И соединен, через инвертор с первым вх дом элемента ИЛИ, к второму входу которого подключен выход второго элемента И, генератор импульсов, пе вый и второй выходы которого .подключены соответственно к второму входу первого элемента И каждой модели ветви и к первому входу первого элемента И блока формирования топологии, второй вход которого сое динен с входом инвертора блока формирования топологии, каждая модель ветви содержит триггеры, входы которых соединены с формирователем временных интервалов, причем второй вход первого триггера подключен к первому входу второго элемента И, к второму входу которого и к третьему- входу первого элемента И подключены выходы второго триггера входы задатчиков адресов каждой модели ветви соединены с выходом первого элемента. ИЛИ блока формирования топологии, содержащего второй элемент ИЛИ, подключенный через инвертор к второму элементу И, и последовательно соединеннью третий элемент И и третий элемент ИЛИ, выход и вход которого подкотючены соот ветственно к ВХОДУ и второму выходу блока управления, причем первый 1зыход генератора импульсов соединен с вторым входом второго элемента И блока формирования топологии, выход которого подключен к входу формирователя временных интервалов каждой модели ветви, вход блока управления соединен с четвертым входом первого элемента И каждой модели ветви, выход первого триггера каждой модели ветви, подключен к входу второго эле 72J мента ИЛИ блока формирования топологии, выход второго элемента ИЛИ каждой модели ветви соединен с входом третьего элемента И блока формирования топологии ij . Известное устройство позволяет . определить величину критического пути сетевого графика, а также величину длиннейшего пути на сети (на взвешенном ориентированном графе) . Однако оно не позволяет решать .задачу упорядоч(ения работ для одной машины по длительности их выполнения. Между тем последняя задача имеет большой удельный вес в классе .задач теории расписаний. Целью изобретения является расши-г рение класса решаемых задач. Эта цель достигается тем, что в устройство для моделирования сетевых графиков введен блок памяти, в блок фор№1рования топологии введены два учетчика, сдвиговый регистр, два дополнительных элемента И и элемент НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента ИЛИ блока формирования топологии, с первым входом сдвигового регистра и с входом первого счетчика, выходы которого подключены к информационным входам блока памяти, адресные входы которого соединены с выходами второго счетчика, . управляющий вход блока памяти подключен к выходу первого дополнительного элемента И и входу элемента НЕ, выход которого соединен с входом второго счетчика и с первым входом второго дополнительного элемента И, выход которого подключен к второму входу сдвигового регистра, выход которого соединен с вторыми входами первого и второго дополнительных элементов И блока формирования топологии, третий вход первого дополнительного элемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии, выход блока памяти является выходом устройства. На фиг.1 приведена функциональная схема предлагаемого устройства; на фиг. 2 - пример работ, требующих упорядочения; на фиг. 3 - сеть специального вида для работ, требующих упорядочения; на фиг. 4 - формирователь временных интервалов; на фиг.5 блок управления.

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

Каждая модель ветви содержит формирователь 6 вре.менных интервалов, задатчик 7 адреса начального узла, задатчик 8 адреса конечного узла, триггеры 9 и 10, элементы И 11 и 12, элемент ИЛИ 13, инвертор 14. Блок формирования топологии содержит счетчики 15 и 16, сдвиговый регистр 17, элемент И 18-22, элементы ИЛИ 23-25, инвертор 26, элемент НЕ 27.

.Формирователь 6 временных интервалов фиг.4 включает счетчик 28, триггер 29, элементы И 30 и 31, входы 32 и 33, выход 34.

Вход 32 соединед с выходом элемента И 19 (фиг.1) , вход 33 -. с выходом элемента И 11 (фнг.О, выход 34с входом триггера 9 (фиг.1) .

Блок управления содержит счетчики 35-37, триггеры 38-40, элементы И 41-44, элемент Не 45, элемент ИЛИ 46.

Блок 3 управления Лредназначен для выдачи сигналов начала и окончания работы устройства, а также для определения длины критического пути сетевого гоафика. Генератор 4 импульсов предназначен для выдачи импульсов двух серий - / и Б , сдай нутых один относительно другого. Элементы каждой модели ветви соединены между собой таким образом что обеспечивают моделирование длины соответствующей ветвм сетевого графика. Эта дпина отображается временным интервалом, кратным числу импульсов серии Д . Собственно длина ветви модулируется формирователем 6 временнь1 интервалов, остальные элементы модели, ветви и блЪк 2 формирования топологии Обеспечивают выдачу разрешающего сигнала на модель ветви в нужный момент времени. При решении задачи упорядочения работ блоки 1 и 2 предназначены для опредёленя той работы, которая должна быть поставлена

на следующее место р фррмируемой очереди работ.

Предлагаемое устройство может моделировать сетевой график и решать задачу упорядочения набора работ. В последнем случае этот набор работ представляется сетью специального вида, при моделировании которой устройство обеспечивает запись номеров работ в блок памяти в порядке, определяемом длительностью работ. В том и в другом случае элементы и блоки устройства работают одинаково, отличие состоит только в содержании вводимой и, следовательно, накапливаемой в блоке памяти информации, значит данное устройство в том и другом случае моделирует сеть (либо сетевой график, либо сеть специального вида). Блок 5 памяти и дополнительные элементы: счетчики 15 и 16, элементы И 21 и 22, элемент НЕ 27, обеспечивают последовательную запись в ячейках блока памяти упорядоченной последовательности номеров работ при решении задачи упорядочения. Номера работ, требующих упорядочения, при вводе И1 формации в устройство отмечаются единицами в соответствующих разрядах регистра 17. При моделировании сетевого графика содержимое регистра 17 равно нулю и запись информации в блок памяти не производится.

Во время работы формирователя временных интервалов /фиг.4), по входу 33 на него подается разрешающий сигнал, устанавливающий триггер 29 в единицу. В счетчик вначале заносится число N - 1 - 1,где N - емкость счетчика, I - дпина соответствующей ветви. Единичный выход каждого разряда счетчика 28 соединен с соответствующим входом элемента И 3-1 . Таким образом, на выходе 34 появляется единичный сигнал, когда в счетчике записано число N-1, и триггер 29 находится в единичном состоянии (т.е. единичный выход триггера также соединен с одним из входов элемента И 31). Выход элемента h 31 соединен с вхрдо - установки в нуль счетчика. 28. 1

Рассмотрим работу формирователя на примере моделирования ветви длиной .1, начиная с момента, когда на вход 33 подан разрешающий единичный сигнал. По этому сигнапу триггер 29 устанавливается в единицу и импульсы се5 .

рии A начинают поступать через элемент И 30 на вход счетчика 28. Эти импульсы увеличивают содержимое счетчика, которое вначале равно N - 1 - 1 После поступления I импульсов серии А содержимое счетчикастановится равным N-I, т.е. в каждом разряде счетчика имеется единица (например при , , т.е. в двоичном коде это МП и т.д.). Единичный сигнал поступает на выход элемента И 3,-на выход 3i4 формирователя а оттуда - на триггер 9 (фиг.1) , устанавливая-егов единицу. Этот же сигнал сбрасывает в нуль счетчик 28, снимая тем самым сигналы с входов элемента И 31. Если , то исходное содержимое счетчика равно N-1. Тогда после поступления на вход 33 разрешающего сигнала (и после установки в единицу триггера 29 появляется единичнь1й сигнал иа выходе ;элемента И 31 и на выходе 34 формирователя, т.е. ветвь нулевой длины смоделирована сразу после поступления разрешающего сигнала.

Рассмотрим решение устройством задачи упорядочения на конкретном примере. Пусть дан набор из пяти работ (фиг.2, каящая из которых характеризуется своим номером (обозначен справа латинской буквой) и длительностью выполнения (указана над изображением работы. Требуется ; упорядочить эти работы по длительности их выполнения, исходя из принятой дисциплины их выполнения на одной машине. Например, принятая дис циплина выбора кратчейшей работы. Это означает, что требуется получить такую последовательность номеров работ, в которой на первом месте стоит номер самой короткой работы, длительность каждой последующей работы не убывает и последним стоит номер самой длительной работы.

Для решения этой задачи стр оится сеть специального вида .3) сле дующим образом. Все работы из исходного набора представляются ветвямисети, выходящими из начального узла б сети. Длина этой ветви равна длительности соответствуиицей работы, а конечный узел ветвн имеет номер /(адрес), равный номеру этой работы. Так, ветвь 5,а сети соответI v-iw

ствует работе в и т.д. Конечные узлы ветвей, выходящих нз началь8272

ного узла, соединены с конечным узлом К сети ветвями единичной длины. Длины ветвей сети проставле ны над изображениями этих ветвей; 5 Номера узлов , ,k , а , Ь , с , о,i могут быть любьми, но не превьштающими адреса N-1 ,где (N-1) - максимальный адрес узла, который мо-жет быть записан в задатчик адре10 са.

Информация об этой сети кодируется и вводится так же, как и в известном устройстве, отличие состоит только в том, что в N разрядный ре15 гистр 17 заносятся единицы в разряды 01,Ь , С ,cJ , i (схемы начального ввода информации не показаны). Исходные состояния счетчиков 15 и 16 нулевые, емкость каждого счетчи20 ка равна N. Управляющий вход блока памяти является входом разрешения записи, далее он именуется входом записи.

Моделирование сети как в предпа 5 гаемом устройстве, так и в известном выпсшняется посредством чередования двух периодов: периода моделирования длин ветвей и периода формирования топологии сети.. В первый

0 период на модели ветвей через элемент И 19 поступают импульсы серии А, во второй период через элементы И 18 и ИЛИ 23 на модели ветвей поступают импульсы серии б . Введенные дополнительно злементы устройства работают только на этапах формирования топологии сети, поэтому основное внимание уделяется периодам формирования топологии сети.

В начале работы блок 3 управления выдает на вход элемента ИЛИ 23 последовательность из 5 импульсов, которые поступают на входы всех задатчиков 7 и 8 адресов и изменяют их содержимые. Эти же импульсы поступают на вход счетчика 15 и на вход регистра 17, сдвигая его содержимое. Поскольку все триггеры моделей ветвей находятся в нулевом состоянии, на выходе элемента- И 20 блока формирования топологии присутствуют нулевые сигналы в то время, когда на выходе хотя бы одного задатчика 8 присутствует единичный сигнал, а значит и в то вр|эмя, когда на выходе ре гистра 17 появляется единичный сигНал. Таким образом, во воемя поступления д импульсов на выходе элемента И 21 блока формнрования топологии все время имеется нулевой сигнал, который через инвертор .27 и элемент И 22 разрешает запись единиц с выхода регистра 17 в его первый разря Таким образом, в рассматриваемый отрезок времени происходит только циклический сдвиг содержимого регис ра 17, длина зтого цикла равна N, содержимые задатчиков и счетчика 15 также циклически повторяются с той длиной N -цикла. После вьщачи 6 импульсов появля ся единичные сигналы на выходах зад чиков 7 моделей ветвей sa, ab, sc, sd, sf. Блок 3 управления прекращае подачу импульсов на вход элемента ИЛИ 23 и выдает единичный сигнал на вхрд элемента ИЛИ 25, по которому ч рез элементы И 11 моделей ветвей за sb, sc, sd, sf поступают единичные сигналы, подготавливая их формирова тели к отсчету импульсов серии Содержимое счетчика 16 равно нулю, счетчика 15 - s. На модели других ветвей единичные сигналы от элементов И 11 не поступают, так как отсу ствуют единичные сигналы на выходах задатчиков 7. С этого момента начинается моделирование длин ветвей, выходящих из начального узла. В течениб всего периода моделирования длин ветвей на выходах элементов И 20 и ИЛИ 24 присутствуют нулевые сигналы. Нулевой сигнал на выходе элемента ИЛИ 24 через инвертор 26 и элемент И 19 разрешает поступление импульсов серии Д на формирователи б моделей ветвей, выходящих из начального узла сети. Этот нулевой сигнал через элемент И .18 запрещает поступление импульсов серии В чере элемент И 23 на зад тчики 7 и 8 моделей ветвей. После поступления трех импульсов сер Д на выходе формирователя в модели ветви sb появляется единичный сигнал, который устанавливает в единицу триггеры 9 и 10 этой ветви. На выходе элемента ИЛИ 2 появляется единичный сигнал, по которому через инвертор 26 и элемент И 19 прекращается выдача импульсов серии А и через элементы И 18 и ИЛИ 23 разрешается вьщача имиульсов серии Б . Эти импульсы поступают на входы всех задатчиков 7 и 8, а также на счетчик 15 и сдвиговый вход регистра 17. После тогр, как на выходе sal 728 датчика 8 модели ветви sb появился единичньнй сигнал, в счетчике 15 записью ается число Ь , а на выходе ре;гистра 17 присутствует единичный сиг- нал Сигнал на выходе задатчика 8 модели ветви 5Ь появляется после поступления на этот задатчик (M«N + + Ь) импульсов, где М О, I, 2, ... Счетчик 15 после поступления того же числа импульсов будет в состоянии Ь . Назначение элементов И 21 и И 22, элемента НЕ 27 и регистра 17 состоит в том, чтобы обеспечить однократную запись каждого.номера узла из числа выбранных в ячейки блока памяти. Номера выбранных узлов отмечаются единицами в соответствующих разрядах регистра. Единичный сигнал на выходе элемента И 20 появляется каждый раз при просчете номера свершившегося узла, так как триггер 10 модели окончившейся ветви все время находится в единичном состоянии. Бди ничный сигнал с выхода элемента И 21 через элемент НЕ 27 и И 22. запрещает перезапись единицы с выхода регистра 17 на его вход, которая разрешается теми же элементами только для несвершившихся узлов, т.е. при нулевом, сигнале с выхода элемента И 20. . . Единичный сигнал с выхода задатчика 8 модели ветви sb поступает через элемент И 12 на вход и выход элемента ИДИ 13. Поскольку ветвь sb единственная, входящая в узел то на выходах инверторов 14 всех моделей ветвей кроме sb присутствуют единичные сигнапы. Таким образом, на выходе элемента И 20 появляется единичный сигнал. На выходе регистра 17 также есть единичный сигнал. Таким образом, на всех входах элемента И 21 есть единичные сигналы. Единичный сигнал с выхода элемента И 21 поступает на вход записи блока 5 памяти и в ячейку с нулевым адресом записьтаётся содержимое счетчика 15, т.е число Ь . Узел Ь свершипся, номер (адрес) его записан. Единичный сигнал с выхода элемента И 21 через элемент НЕ 27-и элемент.И 22 запрещает завись единицы с выхода регистра 17 на его вход. Таким образом, в С -м разряде регистра 17, начиная с этого момента, записан нуль. Нуль на выходе регистра 17 запрещает появление единичного сигнала на выходе элемента И 21, поэтому при появлении следующего (М-N+Ь)-го импульса серии Б сигнал записи не вьщается и повторной запи си номера Т) не будет. Одновременно триггер 9 модели ветви sb сбрасьшается в нуль, нулевой сигиал на выхо элемента ИЛИ 24 разрешает поступление следующего импульса серии А на модели ветвей за, sd, sc, sf котор еще не окончили свою работу. Разреш ющий сигнал поступает также на формирователь 6 модели ветви bk , так как на всех входах элемента И 11 эт модели ветви есть единичные сигналы. После окончания упомянутого импу са серии б с выхода элемента И 21 чезает единичный сигнал. Это соотве ствует появлению единичного сигнала на выходе элемента НЕ 27, который поступает на вход счетчика 16, увеличивая его содержимое на единицу. Единица прибавляется к содержимому счетчика 16 всякий раз, когда сигнал на выходе элемента И 21 переходит из единичного на нулевой уровень. Таким образом, формируется адрес следующей ячейки блока памяти сразу же после записи информации в предьщущую ячейку. Если записи информации по предыдущему импуль су серии В не было, то содержимое счетчика 16 не меняется. После первого в данном периоде и пульса серии А оканчивается ветвь . Поскольку К-й узел не свершился, то при подаче (MN+K)-ro импульса серии б на модели ветвей на выходе элемента И 20 будет нулевой сигнал, (так как на выходах) элементов ИЛИ 13 моделей ветви аК сК, dK, fК нулевые сигналы). Упомянутый импульс серии Б сбрасьша ет в нуль триггер 9 в bk -и модели ветри и устройство вновь переходит к периоду моделирования длин ветвей Состояния дополнительных элементов устройства не изменяются, так как в К-м разряде регистра 17 стоит нуль. После окончания моделирования всех остальных ветвей, вход щих в К-йузел, за исключением последней происходит то же самое, ч описано дпя ветви Vk . После следующего импульса серии Л устанавливаются в единицу тригге ры 9 и 10 моделей ветвей sd и sf. Н чинается период формирования топологии. Поскольку длины ветвей sd и sf одинаковы, любой из номеров j и i может занимать второе место в формируемой очереди, а именно тот, который будет просчитан раньше. Это определяется суммарным числом импульсов серии Б, поступивших на задатчики с момента начала решения данной задачи, до данного периода формирования топологии..Например, это суммарное число импульсов (М-N + Z) таково, что в данный период формирования топологии первый появляется сигнал на -выходе задатчика 8 адреса конечного узла модели ветви sf. Аналогично описанному для ветви sb номер i записан в ячейку, ноьер которой определяется содержимым счетчика 16, т.е. в первую ячейку. После окончания импульса серии Б к содержимому счетчика 16 прибавляется единица, в результате формируется адрес следующей ячейки второй). Сброс в нуль триггера 9 модели ветви sf не вызывает начала периода моделирования, длин ветвей, так как триггер 9 с модели ветви по-прежнему в единичном состоянии. После появления единичного сигнала на -выходе задатчика 8 модели ветви sd номер d записьгоается во вторую ячейку памяти после чего в счетчике 16 формируется адрес следующей ячейки. Далее процесс продолжается аналогично, происходит запись в ячейки памяти номеров а, с , как описано выше. Таким образом, в результате работы устройства в ячейках блока памяти с номерами нуль, один, ..., четыре разместится такая последовательность номеров работ (,i ,а ,Я , С), которая и является искомой очередью. После завершения моделирования ветви SC начинается моделирование ветви СК,по окончании которого при поступлении ()-го импульса серии Б на выходе элемента И 20 появляется единичный сигнал, который через элемент ИЛИ 25 поступает в блок 3 управления. По этому сигналу завершени-я К-го узла последний блок останавливает работу устройства. Предлагаемое устройство позволяет организовать очередь по различным дисциплинам выбора работ. Например,

11

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

12827212

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

УСТРОЙСТВО ДНЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВ по авт.св. № 422002, отличающееся тем, что, с целью расширения класса решаемых . задач, в устройство введен блок памяти, в блок формирования топологии введены два Ч:четчика, сдвиговый регистр, два дополнительйьй элемента И и элемеш НЕ, причем первый вход первого дополнительного элемента И соединен с выходом первого элемента ИЛИ блока формирования топологии, с первьм входом сдвигового регистра и с входом первого счетчика, выходы которого подключены к информационным входам блока памяти, адресные входы которого соединены с выходами второго счетчика, управляющий вход блока памяти подклазчен к выходу первого дополнительного элемента И и входу элемента НЕ, ыход которого соединен с входом второг о счетчика и с первым входом второго дополнительного элемента И, выход которого подключен к второму входу сдвигового, регистра, выход которого соединен с вторыми входами первого и второго | дополнительных элементов И блока Фор мированйя топологии, третий вход первого дополнительного элемента И блока формирования топологии соединен с выходом третьего элемента И блока формирования топологии, выход блока памяти является выходом устройства.

b

JL

Фиг2

30

---

Z3

«ftla

Фмг.З

г«

Ф i

-o

Ю

Фиг.5