Вычислительное устройство для решения задач сетевого планирования

 

O Il И C A Н И Е I 750503

Союз Советскик

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 04.04.78 (21) 2600771/18-24 с присоединением заявки №вЂ” (23) Приоритет— (51) М Кн

G 06 G 7/122

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

Опубликовано 23.07.80. Бюллетень № 27

Дата опубликования описания 27.07.80 (53) УДК 681.333 (088.8) па делам изобретений и открытий (72) Авторы изобретения

А. Г. Додонов, В. В. Хаджинов, В. М. Шишмарев и А. М. Щетинин

Институт электродинамики АН Украинской.ССР (7I ) Заявитель (54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОИСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

СЕТЕВОГО ПЛАНИРОВАНИЯ

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

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

15 с первым входом второго элемента И, два других входа которого подключены соответственно ко входу запуска блока моделей ветвей и единичному выходу триггера, выход второго элемента И подключен к третьему

20 входу формирователя временных интервалов модели ветви, а выход первого элемента И соединен со входом задатчика адреса конечного узла, выход которого подключен к четвертому входу формирователя времен750503 иых и те1> d;Iов модели ветви и через Tрегий элемсl>ò И, другой вход которого соединен с выходом третьих тактовых импульсов блока управления, соединен с выходом прерывания блока моделей ветвей, кроме того, схема задания функции узла состоит из счетчика и двух элементов И, первые входы которых соединены со вторым входом схемы задания функции узла, а второй вход первого элемента И вЂ” с первым входом схемы задания функции узла, выход которой соединен с выходом второго элемента И, второй вход которого через счетчик подключен к выходу первого элемента И, причем формирователь временных интервалов модели ветви содержит триггер, счетчики, элементы И и индикатор, соединенный первым входом с единичным входом триггера и третьим входом формирователя, вторым входом— с единичным выходом триггера и первым входом первого элемента И, и третьим входом — с выходом второго элемента И, входы которого соединены соответственно с первым и четвертым входами формирователя, причем второй вход первого элемента И соедиI>AH со вторым входом формирователя, а выход первого элемента И соединен со входами счетчиков, выход первого из которых подключен к выходу формирователя, а выход второго из счетчиков — — к нулевому входу триггера (1) — (4) .

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

Однако оно не позволяет определить

g)p0IlT работ на текущий момент времени и найти суммарный потребляемый ресурс на заданный момент времени. Г1од фронтом работ на текущий момент времени понимается совокупность работ, которые по сетевому графику. можно выполнять одновременно. Под потребляемым ресурсом на заданный момент времени понимается сумма величин ресурса тех работ, которые принадлежат заданному фронту.

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

Эта пель достигается тем, что в вычислительное устройство для решения задач сетевого планирования, содержащее блок ввода-вывода, вход и выход которого подключены соответственно к первым выходу и входу блока управления, второй вход которого соединен с выходом генератора импульсов, б >ок автоматического формирования топологии, первые вход и выход которого подклк>чены соответственно ко второму в»>ходу и третьему входу блока управления, вторые вход и выход блока автоматического формирования топологии соединены соот5

ic

15 эо

25 зо

SO

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

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

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

Вычислительное устройство состоит из блока 1 ввода-вывода, блока 2 управления, блока 3 моделей ветвей, генератора 4 импульсов, блока 5 автоматического формирования топологии, блока 6 вычисления ресурсов и счетчика в виде регистратора 7 ресурсов.

Каждая модель 8 ветви блока 3 моделей ветвей содержит формирователь 9 временных интервалов, триггер 10, задатчики адресов начального 1 и конечного 12 узлов, элементы 13, 14 и 15 И и предназначена для моделирования работы сетевого графика

Формирователь 9 временного интервала предназначен для моделирования заданного временного интервала и дополнительно для получения сигнала принадлежности модели 8 ветви заданному фронту.

750503 ления с полюса 30 последней ячейки 16 р распределителя.

Блок 2 управления предназначен для организации взаимосвязанной работы блоБлок 5 автоматического формирования топологии, соединенный с блоком 3 моделей ветвей, обеспечивает взаимодействие моделей 8 ветвей сетевого графика по временному принципу на основании адресов начального и конечного событий, занесенных в задатчики начального 11 и конечного 12 узлов модели 8 ветви.

Блок 6 ресурсов состоит из однотипных ячеек 16 управляемого распределителя и ячеек 17 стоимостно-ресурсных ограничений и предназначен для последовательного формирования временных интервалов потребляемого ресурса для работ, лежащих на фронте в заданный момент времени.

Однотипные ячейки 16 управляемого распределителя, число которых равно числу моделей ветвей сетевого графика, предназначены для организации последовательности опроса отдельных ячеек 17 стоимостноресурсных ограничений. В состав каждой ячейки 16 управляемого распределителя входят триггеры 18 и 19, элементы 20, 21, 22 и 23 И.

Каждая отдельная ячейка 17 стоимостноресурсных ограничений, число которых равно числу моделей ветвей, предназначена для задания стоимостно-ресурсных ограничений, накладываемых на выполняемую работу, и представляет собой формирователь временного интервала, содержащий счетчики 24 и 25 импульсов, триггер 26, элемент 27 И.

Величины стоимости выполнения каждой работы или интенсивности потребления однородного ресурса изображаются пропорциональным количеством импульсов и заносятся в счетчики 24 ячеек 17 стоимостноресурсного ограничения.

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

Регистратор 7 ресурса может быть выполнен различным образом. В простейшем случае — это счетчик импульсов достаточной емкости, в который при определении каждого текущего ресурса в конкретный момент времени импульсы ГИ1 поступают из блока 2 управления через плюс 28, начиная с момента появления сигнала из блока 2 на полюсе 29 первой ячейки 161 управляемого распределителя блока 6 ресурсов и до момента появления сигнала в блоке 2 управS о

1$

zo

25 зо

45 то ков устройства и для выработки первой и второй серии тактовых импульсов (ГИ1 и

ГИ2) соответственно с полюсов 28 и 31 на входы блока 3 моделей ветвей, блока 5 автоматического формирования топологии и блока 6 ресурсов.

Вычислительное устройство работает следующим бразом.

Предварительно из блока 1 ввода-вывода производится ввод исходных данных. При этом в формирователь 9 временного интервала записывается число им пульсов, пропорциональное длительности моделируемой работы, в задатчик 11 адреса начального узла — число импульсов, пропорциональное номеру узла, из которого выходит данная работа, в задатчик 12 адреса конечного узла — число импульсов, пропорциональное номеру узла, в который входит данная работа, в счетчик 24 ячейки 17 стоимостноресурсного ограничения записывается число импульсов, пропорциональное интенсивности потребления одного из видов ресурсов. Все триггеры устройства устанавливаются в нулевое состояние.

Для запуска всех моделей ветвей, исходящих из начального узла, устройство управления разрешает прохождение импульсов ГИ2 (полюс 31) на входы всех задатчиков 1! адресов начальных узлов всех моделей 8 ветвей и в блок 5 автоматического формирования топологии. При этом в момент переполнения задатчиков 11 адресов начальных узлов, в одном из которых записан адрес начального узла, из блока 5 автоматического формирования топологии (полюс 35) приходит сигнал о выполнении всех работ, входящих в событие, из которого выходит данная ветвь. Пройдя элемент 13 И, сигнал переполнения с задатчика 11 включает через полюс 32 формирователь 9 временного интервала. Выходной сигнал блока

5 автоматического формирования топологии запрещает поступление (полюс 31) импульсов второй серии и разрешает прохождение импульсов первой серии (полюс 28) на вход формирователей временных интервалов.

Включенные формирователи 9 временных интервалов начинают отсчитывать поступление импульсов ГИ1. Через время, пропорциональное длительности работы, на выходе формирователя 9 появляется сигнал переполнения, который поступает на полюс ЗЗ. По сигналу с полюса 33 запрещается серия импульсов ГИ1 и разрешается серия ГИ2, которая поступает в задатчики 11 адресов начальных узлов всех моделей 8 ветвей и в задатчики 12 адресов конечных узлов только тех моделей ветвей, у. которых сформирован временной интервал. Отсчитав число импульсов, равное номеру события, в которое входит данная модель 8 ветви, задатчик 12 выдает сигнал переполнения, который через элемент 15 И поступает в

750503

2$

4$ блок 5 автоматического формирования топологии и фиксируется там как номер конечного узла выбранной модели 8 ветви.

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

В каждой модели 8 ветви в процессе решения имеются сигналы о начале и окончании ее выполнения, что позволяет при определении фронта работ и при определеIIHH стоимостно-ресурсных ограничений получать на выходе формирователя 9 модели 8 ветви через полюс 34 на одном из входов элемента 20 И соответствующей ячейки 16„ управляемого распределителя следующие логические сигналы: признак принадлежности рассматриваемой работы фронту работ на текущий момент времени; признак принадлежности рассматриваемой работы множеству невыполненных работ.

Управляемый распределитель, состоящий из однотипных ячеек 16 „, число которых равно числу моделей 8 ветвей сетевого графика, предназначен для организации последовательности опроса отдельных ячеек 17 стоимостно-ресурсных ограничений при определении суммарного ресурса только тех моделей ветвей, которые содержат заданный признак, пропуская без затрат времени молели ветвей, не имеющие этот признак.

Происходит это следующим образом.

Г1редварительно триггеры 18 и 19 установлены в нулевое состояние. При сигнале наличия признаков из формирователя 9 временного интервала модели 8 ветви через полюс 34 на входы элементов 20 И соответствующих ячеек 16 подаются разрешающие сигналы, которые, пройдя их, устанавливают в единичное состояние триггеры 18, такое, что на их нулевых выходах, соединенных со входами элементов 21 И, появляются запрещенные поте!щиалы, а на единичных выходах, соединенных со входами элементов 22 И,— разрешающие потенциалы, При этом блок 2 управления вырабатывает сигнал, постуггающий на полюс 29, первой ячейки 16 управляемого распределителя.

Этот сигнал, пройдя элемент 22 И, устанавливает триггер 29 ячейки 17, cTQHMocTHQресурсного ограничения и триггер 19 ячейки 16, управляемого распределителя в единичное состояние (если триггер 18 этой ячейки находится в единичном состоянии), тем сам 1 1 м I!!1. ая рHзреl(lзlolци Й !Iоте111(иа. входа э!(. i;(I!i 20 И и подавая разре-!!!!!с(1((!й, . (,! I;I, i па эг!с.(!сllT 23 И.

Для определения текущего ресурса блок

2 управления запрещает поступление импульсов второй серии, что останавливает процесс формирования топологии и разрешает поступление импульсов ГИ1 в регистратор 7 ресурса и в ячейки 17 стоимостноресурсных ограничений. Одиночный импульс блока 2 управления с полюса 36 поступает в формирователи 9 временных интервалов моделей 3 ветвей, если ветвь принадлежит фронту, то он появляется на выходе полюса 34; через элемент 20 И и устанавливает триггер 18 соответствующей ячейки 16, распределителя в единичное состояние.

Сигнал, поступивший из блока 2 управления с полюса 29, разрешает последовательное формирование временных интервалов ячейки 17 стоимостно-ресурсных ограничений.

Таким образом, счетчик 24 ячейки 17„, соединенный с ячейкой 16i;, отсчитывает величину интенсивности потребления pecvpca

После появления на выходе счетчика 24 импульс переполнения через элемент 23 И устанавливает три!!ep 19 в нулевое состояние, разрешая прохождение сигнала со входа ячейки 16; на ее выход через элемент 21 И.

Сигнал с поноса 29 первой ячейки 16 управляемого распределителя передается от ячейки к ячейке, пропуская те ячейки, на вход элементов 20 И которых не были поданы разреша!ощие импульсы с моделей 8 ветвей. Это в свою очередь соответствует передаче в регистратор 7 ресурса содержимого ячеек 17i стоимостно-ресурсных ограничений тех моделей ветвей, которые принадлежат фронту выполняемых работ.

При появлении сигнала на выходе управляемого распределителя (полюс 30, элемента 21 И ячейки 16 . распределителя), что соответствует опросу всех моделей ветвей, принадлежащих фронту, блок 2 управления прекращает поступление импульсов в регистратор 7 ресурса и в ячейки 17„стоимостно-ресурсных ограничений. В результате этого в регистраторе 7 ресурса содержится число импульсов, пропорциональное суммарной интенсивности потребления ресурса на заданный момент времени.

Эта интенсивность сохраняется до тех пор, пока какая-либо работа не будет закончена. Поэтому при определении графика потребления ресурсов, после изменения состояния какой-либо модели ветви (либо окончена, либо только начата), процесс определения суммарной интенсивности потребляемого ресурса в устройстве повторяется аналогично описанному выше.

Из блока 2 управления во все блоки ма!пины обеспечивается поступление не<)() ((); I 1! (l bIX (- HI Hd;IOB i:!I PII I, I (!(!H H IIJ)(,2i)H1! !1т(! l !1о(О !(ста нова.:" (>т 1) . . ", !(:", " (ж(; !((I()! :; ÇË!I Н!.

750503

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

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

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке № 2579790/18-24, кл. G 06 F 7/38, 1978.

2. Авторское свидетельство СССР по заявке № 2581765/18-24, кл. G 06 F 7/06, 1978.

3. Авторское свидетельство СССР по заявке № 2383712/18-24, кл. G 06 F 15/20, 1976.

4. Авторское свидетельство СССР № 473455, кл. G 06 G 7/122, 1975 (прототип).

750503

Редактор В. Зарванскаи

Заказ 44á7/!9

СостаBèòñëь И. Загорбиннна

Текред К. Шу фрич Корректор Г. Решетник

Тираж 751 Подписное

IjHHHIIH Государственного комитета СССР по дел а м изобретений и открытий

J J 3035, Москва, Ж--35, Раушская наб., д. 4/5

Филиал ППП <<Патент», r, Ужгород, ул. Проектная, 4