Вычислительное устройство для решения задач сетевого планирования Советский патент 1980 года по МПК G06G7/122 

(54) ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯ

I

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

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

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

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

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

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

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

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

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

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

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

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

Вычислительное устройство состоит из блока 1 ввода-вывода, блока 2 управления,

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

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

5 Формирователь 9 временного интервала предназначен для моделирования заданного временного интервала и дополнительно для получения сигнала принадлежности модели 8 ветви заданному фронту. Блок 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первой ячейки-16 управляемого распределителя блока 6 ресурсов и до момента появления сигнала в блоке 2 управления с полюса 30 последней ячейки 16,1. распределителя. Блок 2 управления предназначен для организации взаимосвязанной работы блоков устройства и для выработки первой и второй серии тактовых импульсов (ГИ1 и ГИ2) соответственно с полюсов 28 и 31 на входы блока 3 .моделей ветвей, блока 5 автоматического формирования топологии и блока 6 ресурсов. Вычислительное устройство работает следующим бразом. Предварительно из блока 1 ввода-вывода производится ввод исходных данных. При этом в формирователь 9 временного интервала записывается число импульсов, пропорциональное длительности моделируемой работы, в задатчик 11 адреса начального узла - число импульсов, пропорциональное номеру узла, из которого выходит данная работа, в задатчик 12 адреса конечного узла - число импульсов, пропорциональное номеру узла, в который входит данная работа, в счетчик 24 ячейки 17 стоимостноресурсного ограничения записывается число импульсов, пропорциональное интенсивности потребления одного из видов ресурсов. Все триггеры устройства устанавливаются в нулевое состояние. Для запуска всех моделей ветвей, исходящих из начального узла, устройство управления разрёщает прохождение импульсов ГИ2 (полюс 31) на входы всех задатчиков 11 адресов начальных узлов всех моделей 8 ветвей и в блок 5 автоматического формирования топологии. При этом в момент переполнения задатчиков И адресов начальных узлов, в одном из которых записан адрес начального узла, из блока 5 автоматического формирования топологии (полюс 35) приходит сигнал о выполнении всех работ, входящих в событие, из которого выходит данная ветвь. Пройдя элемент 13 И, сигнал переполнения с задатчика 11 включает через полюс 32 формирователь 9 временного интервала. Выходной сигнал блока 5 автоматического формирования топологии запрещает поступление (полюс 31) импульсов второй серии и разрёщает прохождение импульсов первой серии (полюс 28) на вход формирователей временных интервалов. Включенные формирователи 9 временных интервалов начинают отсчитывать поступление импульсов ГИ1. Через время, пропорциональное длительности работы на выходе формирователя 9 появляется сигнал переполнения, который поступает на полюс 33. По сигналу с полюса 33 запрещается серия импульсов ГИ1 и разрещается серия ГИ2, которая поступает в задатчики 11 адресов начальных узлов всех моделей 8 ветвей и в задатчики 12 адресов конечных узлов только тех моделей ветвей, у которых сформирован временной интервал. Отсчитав число импульсов, равное номеру события, в которое входит данная модель 8 ветви, задатчик 12 выдает сигнал переполнения, который через элемент 15 И поступает в

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

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

признак принадлежности рассматриваемой работы фронту работ на текущий момент времени;

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

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

Происходит это следующим образом. Предварительно триггеры 18 и 19 установлены в нулевое состояние. При сигнале наличия признаков из формирователя 9 временного интервала модели 8 ветви через полюс 34 на входы элементов 20 И соответствующих ячеек 16 подаются разрешающие сигналы, которые, пройдя их, устанавливают в единичное состояние триггеры 18, такое, что на их нулевых выходах, соединенных со входами элементов 21 И, появляются запрещенные потенциалы, а на единичных выходах, соединенных со входами э..пементов 22 И,- разрешающие потенциалы. При этом блок 2 управления вырабатывает сигнал, поступающий на полюс 29, первой ячейки 16-( управляемого распределителя. Этот сигнал, пройдя элемент 22 И, устанавливает триггер 29 ячейки 17 стоимостноресурсного ограничения и триггер 19 ячейки IGi управляемого распределителя в единичное состояние (если триггер 18 этой ячейки на.ходится в единичном состоянии), тем caMiiiM снимая разрешающий потенциал С ) входа чломеита 20 И и подавая разре ii;ii(;;:iiiH .u .ua,i на э, смент 23 И.

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

Таким образом, счетчик 24 ячейки 17i, соединенный с ячейкой 161, отсчитывает величину интенсивности потребления ре0 сурса.

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

Сигнал с полюса 29 первой ячейки 16i

управляемого распределителя передается

от ячейки к ячейке, пропуская те ячейки,

на вход элементов 20 И которых не были

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

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

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

Из блока 2 управления во все блоки машины обеспечивается г ост 1ление необходимых сигна:1ов управ.н-мия и HJKMьаритглыюго установ.а. KOTDPI-IC чертеже е 1С).;азап1: ;. Предложенное устройство, дискретное по принципу действия, позволяет дополнительно к временным задачам сетевого планирования и управления решать задачу определения фронта работ на текущий момент времени и задачу определения суммарного потребляемого ресурса на заданный момент времени. Кроме того, это же дает возможность легко автоматизировать процесс сбора этой информации и передачи ее в цифровую вычислительную машину, так как работа специализированного устройства возможна в комплексе с цифровой машиной. Формула изобретения 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 (прототип).