Устройство для расчета сетевыхграфиков

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ

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

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

Республик рп851417 (61) Дополнительное к авт. сеид-ву (22) Заявлено 051479 (21) 2842170/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 3007.81. бюллетень Н9 28

Дата опубликования описанию 300781 (я)м. к .з

G Об С 7/122

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

СССР по делам изобретений и открытий (53) УДК б81. 333 (088. 8) (72) Авторы изобретения

A.Ã.ÄoäoHoâ, В.В.Месяц, E.A.Ðàëäóãèí, В.В. и А.М.Щетинин (71) Заявитель

Институт электродинамики АН Украинской СС (54 ) YCTPOACTBO ДЛЯ РАСЧЕТА СЕТЕВИХ ГРАФИКОВ

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

Известно устройство для моделирования экстремальных путей на графике, содержащее модели ветвей, входной и выходной полюса каждой из которых соединены с соответствующими полюсами остальных моделей ветвей в соответствии с топологией заданного сетевого f5 графика, причем модель ветви состоит из счетчика, двух триггеров, элементов И, НЕ и диода (1) .

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

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

Недостаток такого устройства заключается в том, что оно только определяет суммарный 1потребляемый ресурс на заданный момент времени .. выполнения проекта, но не поэволяеъ

851417 решить задачу оптимального целочисленного распределения ограниченных ресурсов на сетевых графиках.

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

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

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

НЕ, выход которого является выходом модели ветви, выход первого элемен5

t0

Ю

$O

О

46

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

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

Устройство, состоит из генератора

1 импульсов, блока 2 управления, 3, -Зп моделей ветвей, формирователя

5 временного интервала, распределителей 41 -4

Каждая йз моделей ветвей 3,, число которых равно. числу моделируемых работ сетевого графика, содержит задатчик б частоты, формирователь 7 временного интервала, счетчик 8, триггеры 9-11, элементы И 12-19, элементы ИЛИ 20-21, элементы HE 2225. Задатчик частоты б представляет собой элемент, в котором опорная частота, подаваемая на вход, делится на частоты кратные 1,2... (n-1), п, а на выход элемента пропускается

851417 только одна частота, которая прямо пропорциональна задаваемой величине.

Формирователь временного интервала 7 выполняется на основе. счетчико-регистровых структур.

Модели ветвей соединяются между собой на наборном пале входными

264 и выходными 27, полюсами в соответствии с топологией моделируемого графика. В каждой модели полюса

28, 29 и 30 подключены соответственно к установочному, разрядному входу и разрядному выходу соответст вующей однотипной ячейки управляе мого распределителя.

Каждая Модель ветви 31 предназначена для моделирования одной работы исследуемого сетевого графика. Задатчик б частоты и формирователь 7 временного интервала служат для получения длительности t; моделируемой работы, счетчик 8 предназначен для хранения величины моделируемого ресурса г„, значение которого определяет задаваемую величину частоты в задатчике б. Достигается это путем параллельного соединения разрядных выходов счетчика 8 с соответствующими входами задатчика б частоты. Напри-мер, если в счетчике 8 хранится один импульс (пропорциональный единице ресурса), то на выход задатчика 6 пропускается наименьшая частота Г1

Г1= — n с, (1) где fo — частота следования опорных импульсов

n — емкость счетчика 8 определяющая максимальное значение ресурса, занятого выполнением одной работы.

Если же в счетчике 8 хранится число импульсов "k ", то выходная частота f определяется иэ .выражения

° f =К— (2)

Для моделирования (ij) работы в формирователь временного интервала 7 модели ветви 3 заносится величина М, определяющая объем выполняемой работы g - и в счетчик 8 заносится число

13 импульсов к, соответствующее величине моделируемого ресурса г;.. Количество импульсов в счетчике 8 опре- . деляет частоту Г« в задатчике 6. В дальнейшем, подавая на вход задатчика 6 частоты серию опорных импульсов, модель ветви сформирует временной интервал Т, пропорциональный длительности t" моделируемой работы (ij3

13

«.о со Г» — ° 14=ь .n — i с о к . 3

К где Ъ, С вЂ” период и частота следования опорных импульсов, М величина, пропорциональная объему выполняемой работы g,„. (задаваемая. числом импульсов в формирователе временного интервала 7);

К величина, пропорциональная количеству ресурсов

z;, занятых выполнением

5 (i j ) работы (задаваемая числом импульсов в счет чике 8 и определяющая выходную частоту f задатчика б частоты).

Управляемый распределитель, состоящий иэ однотипных ячеек 4,, число которых равно числу моделей ветвей сетевого графика, предназначен для

) организации последовательного опроса моделей ветвей, принадлежащих одно15 му критическому пути. В состав каждой ячейки 4 управляемого распределителя входят триггеры 31 и 32, элементы И 33-36.

Формирователь 5 временного интер2О вала построен по аналогии с формирователями 7 моделей ветвей и предназначен для моделирования заданного ограничения ресурсов R, занятого выполнением всего 1троекта.

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

Блок 1 управления предназначен для организации взаимосвязанной работы блоков устройства и для выработки серий тактовых импульсов ГИ1, ГИ2 (ГИ1, ГИ2, ГИЗ), сдвинутых отно сительно друг друга. В состав блока

2 управления входят триггеры 37 и

38, элементы И 39-45, элемент

ИЛИ 46, элементы НЕ 47 и 48 и элементы задержки 49-54.

40 Устройство работает следукхцим образом.

В формирователе 7 временных интервалов моделей ветвей заносится число импульсов, пропорциональное

4S объему выполняемой работы 9 . Триг«о геры 9-11 находятся первоначально в нулевом состоянии, а.на полюсах 26 и 27 действует запрещенный потенциал.

В счетчик 8 каждой модели заносится число импульсов, соответствующее начальному распределению ресурса которое получается путем предварительного решения задачи минимального. потока.

После начального установа каждой э5 модели ветви триггеры 31 и 32 распределителей 4 устанавливаются в нулевое состояние, а в формирователь 5 временного интервала заносится число .импульсов, определякщее ограничение

Щ используемого ресурса,R, занятого выполнением всего проекта. В блоке 2 (фиг.2) триггеры 37 и 38 устанавливаются в нулевое состояние.

В некоторйй момент времени сиг-. ф нал "Пуск", поступающий на полюс 55

851417 блока 2, проходит на вход генератора

1 импульсов и включает его. При этом импульсы с выхода генератора 1 проходят в фнок 2 на входы элементов И "39 и 40. Сигнал "Пуск" также поступает на вход триггера 37 и через элемент ИЛИ 46 на вход триггера

38 и устанавливает их в единичные состояния

Единичное состояние триггера 38 выдает разрешение определения дерева критических путей через полюс 56 на нход элемента И 17 всех моделей ветвей 3, а также на вход элемента

И 39 в блоке 2 (фиг.2). При этом импульсы с выхода генератора 1 проходят через элемент И 39 на входы эле- !5 ментов 49 и 50 задержек. Элементы

49 и 50 задержки предназначены для выработки серии импульсов ГИ1 и ГИ2, которые получаются путем соответствующего сдвига серии импульсов, поступающей нз генератора 1. Единичное состояние триггера 37 через элемент

HE 47 рыдает разрешающий сигнал в начальный узел моделируемой сети (полюс 57). 25

Кроме того, триггер 37 разрешает прохождение серии импульсов ГИ1 и

ГИ2 через элементы И 41 и 42 на полюса 58 и 59 блока 2 управления. Тактовые импульсы ГИ1 и ГИ2 с полюсов

58 и 59 поступают на входы всех моделей ветвей. Но начинают отсчитывать импульсы ГИ1 только те модели ветвей

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

ГИ1 проходят через элемент И 14 на вход задатчика частоты 6, последний делит частоту и на своем выходе формирует новую частоту, которая апре- 40 деляется количеством импульсов, хранящихся в счетчике 8.

Формирователь 7 временного интервала отсчитывает импульсы с выхода задатчика б частоты. При появлении на выходе формирователя 7 импульса переполнения через элементы И 15 и

ИЛИ 20, триггеры 9 и 10 устанавливаются в единичное состояние. Сигнал с нулевого выхода триггера 10 поступает на один иэ нходов элемента И 17, на второй вход которого поступает сигнал определения дерева критических путей. Сигнал с выхода этого элемента И поступает на вход схемы совпадения, которая образуется соединением выходов элементов НЕ 22 через полюса 27 моделей ветвей, сходящихся в одной иэ вершин графика.

При этом на полюсе 27 появится разрешакщий потенциал толька тогда, фф когда триггер 10 моделей ветвей, входящих в одну вершину, установятся в единичное состояние. Если же йа выходном полюсе 27 модели нетви еще не появился разрешающий сигнал, то д элемент НЕ 23 дает разрешающий сиг— нал на элемент И 15 и 16. На нторой вход элемента И 16 через полюс 59 поступают сдвинутые импульсы ГИ2 из блока 2 управления, т.е. все установившиеся в единичное состояние до появления .на полюсе 27 разрешающего потенциала триггеры 9 будут установлены в нулевое состояние выходным сигналом элементов И 16 через элементы ИЛИ 21.

Триггеры 9, которые установились в единичное состояние с появлением сигнала на полюсе 27., остаются в единичном состоянии, так как в этот момент снимается разрешающий потенциал со входа элемента И 16.

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

Импульсы ГИ1 и ГИ2 поступают на полюса 58 59 блока управления 2 до тех пор, пока не сформируется конечный узел моделируемого сетевого графика. При этом число импульсов ГИ1 будет определять величину критического пути. Когда это произойдет, то сигнал с конечного узла сетевого графика поступает на полюс 60 блока

2, где устанавливает триггеры 38 .в нулевое состояние. Последнее состояние триггера 38 выдает запрещающий сигнал на полюс 56 определения дерева критических путей и разрешающий сигнал на полюс 61 для выделения одного критического пути.

Кроме .того, триггер 38 запрещает прохождение импульсов с выхода генератора 1 через элемент И 39 и разрешает их прохождение через элемент

И 40 на входы элементов 51-53 задержек. Элементы 51-53 задержки предназначены для заработка серии импульсон ГИ1, ГИ2, ГИЗ, которые получаются путем соответствующего сдвига серии импульсов поступающих из генератора 1. В результате вместо импульсов ГИ1 и ГИ2 (полюсы 58 и 59) подаются импульсы ГИ1, ГИ2, ГИЗ на полюсы 62-64, которые поступают с выходов элемента задержек. 51-53 через элементы И 43-45.

Конечный узел моделируемого сетевого графика представляет собой схему совпадения, которая образуется соединением выходов элементов НЕ 22 через .полюса 27 моделей ветвей сходящихся в конечном узле. Кроме того, в указанную схему совладения подключен выход элемента HE 48 блока 2, который в процессе определения дерева критических нулей не влиял на результат моделирования..

При определении одного критического пути нулевое состояние триггера 38 через время задержки, вырабатываемое элементом 54 задержки, выда851417

10 ет разрешающий сигнал через элемент

НЕ 48 в конечный узел сетевого графика (полюс 60).

Сигнал, постунйвший в конечный узел сетевого графика, проходит во всех моделях ветвей 3, заканчивающихся в последнем узле, через элемент НЕ 23 и поступает на один из входов элемента И 12, на втором входе которого присутствует разрешение с полюса 61. Но на выходе элемента И 12 появляется разрешающий сигнал только в той модели ветви, у которой триггер 9 находится в единичном состоянии, т.е. если ветвь сформировала свой временной интер-, вал Т последней в конечном узле. сетевого графика. С выхода элемента И 12 разрешение поступает через элемент

НЕ 24 на входной полюс рассмотренной модели ветви 3 и далее в следующие модели 3, .которые соединены выходными полюсами 27 с этим вход-. ным полюсом.

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

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

Это выполняется для определения связанности начального и конечного узлов сетевого графика по дереву критических путей.

В дальнейшем определяется множество моделей ветвей 3, принадлежащих одному критическому пути. С этой целью первый импульс ГИ1 поступает на полюс 62, первого распределителя 4 .

Распределитель 4„ предназначен для выделения из дерева дальнейших путей модели ветвей, принадлежащих одному критическому пути. Происходит это следующим образом. Предварительно триггеры 31 и 32 устанавливаются в нулевое состояние. При появлениИ сигнала разрешения определения одного критического пути (полюс 61) на выходе элемента И 19 появляется сигнал принадлежности модели ветви дереву критических путей в том случае, если триггер 9 находится в единичном состоянии. Сигнал с выхода элемента

И 19 проходит через полюс 28, элемент И 33 и устанавливает триггер 31 распределителя 4 в единичное. состояние. Вследствие этого на нулевом его выходе, соединенном со входом элемента И 34, появляется запрещающий потенциал, а на единичном выходе - разрешающий потенциал. С появлением на полюсе 62 первого импульк са ГИ1, который через элемент И 35 станавливает триггер 32 распределителя 4, в единичное состояние (если триггер 31 этой ячейки уже находился в единичном состоянии), снимается разрешающий потенциал со входа элемента И 33 и подается разрешающий потенциал на элемент И 36. Кроме того

II

I этот импульс ГИ1 с выхода элемента

И 35 проходит на.разрядный выход ячейки (полюс 30) и далее поступает в соответствующую модель ветви, где устанавливает в единичное состояние триггер 11 и в нулевое триггер 9.

Новое состояние триггера 9 запрещает прохождение сигнала с: выхода полюса 27 через элемент И 12 на входной полюс 26, что равносильно

15 отключению соответствующей модели ветви от дерева критических путей.

Если при этом между конечным узлом (полюс 60) и начальным узлом (полюс

67) сетевого графика связанность

З) нарушена, то в начальном. узле (по.люс 57 блока управления) появляется запрещенный сигнал, который проходит во всех моделях ветвей 3 через элемент НЕ 25 и дает разрешение на вход элемента И 18. Вслед за этим импульс

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

30 11 находится в единичном состоянии, т.е. только в выбранной модели. Сигнал с выхода элемента И 18 поступает через элемент ИЛИ 20 на единичный . вход триггера 9 и возвращает его в

3S единичное состояние. Если же связность между начальным и конечным узлом сетевого графика не была нарушена в момент сброса триггера 9 в ноль,.то на полюсе 57 блока 2 управ-, ц ления присутствует разрешающий сигнал, который через инвертор НЕ 25 в каждой модели ветви 3 дает запрещение для прохождения импульса ГИ2

I через элемент И 18, в итоге триггер

9 остается в нулевом состоянии, т.е. рассматриваемая модель ветви исключается из дерева критических путей.

Далее импульс ГИ3 с полюса 64 блока

2 управления поступает на полюс 29 модели ветви 3, где сбрасывается ® триггер 11 в нулевое состояние, и на вход 29 распределителя 4, где проходит через элемент И 36 и устанавливает триггер 31 в нулевое состояние, нулевое состояние которого

35 выдает разрешение иа прохождение импульсов ГИ1 со входа распределителя 4 на его выход (полюс 65) че- . . рез элемент И 34.

Сигнал с полюса 65, распределите 4 ля 4 передается от ячейки к ячейке, обходя те ячейки, на входах элементов И 33 которых нет разрешения из моделей ветвей 3. Это соответствует последовательному отключению моделей .ветвей 3, принадлежащий дереву

851417

12 критических путей и проверке сохранения связанности начального и конечного узлов сетевого графика.

После опроса всех моделей ветвей

3, принадлежащий дереву критических путеи, на выходе и-го распределителя (полюс 65н) появляется сигнал, поступающий на полюс 66 блока 2 управления. Этот сигнал проходит через элемент ИЛИ 46 и устанавливает триггер 38 в единичное состояние. В результате блок управления прекращает подачу импульсов ГИ1, ГИ2 и ГИЗ" на соответствующие полюса 62, 63 и

64 и разрешает подачу импульсов ГИ1 и ГИ2 на полюса 58 и 59, а также разрешающий сигнал снимается с полюса 61 и подается на полюс 56. Причем импульс с выхода 65я n-ro распределителя поступает на вход формирователя 5 временного интервала и через полюс 66 на вход элемента И 13 всех моделей ветвей 3.

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

Затем на модели сетевого графика вновь определяется дерево критических путей с учетом нового распределения ресурсов н снова распределяется следующая единица ресурса. Так процесс распределения ресурса повторяется до тех пор, пока на выходе формирователя 5 временного интервала (полюс 67) не появится импульс переполнения, который поступает в блок 2 управления и сбрасывает триггер в нулевое состояние, что указывает на распределение нсего:имеющегося ресурса R. После распределения всего ресурса R будет получен минимально возможный критический срок выполнения сетевого графика, а распределение целочисленного ресурса, по от« дельным работам, хранящегося н счетчике 8 каждой модели ветви 3, будет оптимально.

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

Рассмотрим постановку и общий подход решения.

Задан связанный ориентиронанный граф С(Х,LI) без контуров, у которого имеются одна начальная хо и одна конечная х„ нершины. Граф С соответ- . ствует комйлексу взаимосвязанных работ, которые необходимо выполнить при реализации проекта.

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

Если операция (i ) характеризуется объемом работы g; „ то используя количество ресурсов z„, можно выполнить рассматриваемую работу за вре-. мя я

Исходя из этого, для каждой работы

20 (I J ) может быть получена зависимость . которая показывает, что скорость выполнения операции прямо пропорциональна количеству ресурса участвующего н выполнении этой операции

25 .йл (4)

4 при условии

7„.4 min . 4 л md% 7

Если допустить, что ресурсы предЗО ставлены целыми числами, то времяресурсная характеристика должна быть ступенчатой (фиг.3).

Задача оптимального распределения однородного нескладируемого целочисЗ5 ленного ресурса в сетевом графике заключается н таком назначении ресурса на каждую работу выполняемого проекта, чтобы величина суммарного потребляемого ресурса не пренышала за Я данного ограничения R, а длина критического пути была бы наименьшей.

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

Минимизировать ;- (ф ";,) (;; - .;,„,) )

4 1 при условии выполнения:

1) первого закона сетей

$O- " z, если j =н (Z; +2„ t,>) Å(7„" -Z„-. )= О, если Фнк

-2, если, =к (Ь)

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

2) второго закона сетей

40 бх 7„

" Ф"(ч (- -+st..)=o 7! т.е. алгебраическая сумма продолжительностей. выполнения операций и простоев по ним s любом цикле сете15

851417

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

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

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

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

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

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

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

„р эыходом блока управления.

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

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

ЗО входу второго триггера, нулевой выход которого соединен с первым вхоцом четвертого элемента И, второй вход которого подключен к первому полюсу модели ветви, выход четверто35 ro элемента соединен со входом первого элемента НЕ, выход которого является выходом модели ветви, выход первого элемента НЕ соединен со входом второго элемента НЕ, выход котощ рого подключен ко второму входу второго элемента И и к первым входам пятого и шестого элементов И, второй вход шестого элемента И соединен с третьим полюсом модели ветвей, вто.рой полюс которой подключен к первому входу седьмого элемента И, выход которого соединен с одним входом задатчика частоты, другие входы которого подключены к выходам счетчика, вход которого подключен к выходу третьего элемента И, второй вход которого соединен с шестым полюсом. модели ветви, седьмой полюс которой . подключен через третий элемент НЕ к первому входу восьмого элемента И, Ы выход которого соединен с первым входом первого элемента ИЛИ,. выход которого подключен к единичному входу первого триггера, нулевой вход которого соединен с выходом второго уу элемента ИЛИ, первый вход которого подключен к выходу шестого элемента И, второй вход второго элемента

ИЛИ соединен с девятым полюсом модели ветви и с единичным входом третьего триггера, единичный выход кото851417

30 рого подключен ко второму входу восьмого элемента И, третий вход которого подключен к четвертому полюсу модели ветви, пятый полюс которой соединен со вторым входом первого элемента И и с третьим входом второго элемента И, выход которого через четвертый элемент НЕ подключен ко второму входу седьмого элемента И и ко входному полюсу модели ветви, восьмой и десятый полюсы которой соединены соответственно с выходом первого элемента И и с нулевым входом третьего триггера, выход задатчика частоты череэ формирователь временного интервала подключен ко второму входу пятого элемента И, выход которого соединен. со вторым входом первого элемента ИЛИ.

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

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

9305484, кл. С 06 С 7/34, 1970 °

2. Авторское свидетельство СССР по заявке 9 2579670/18-24, кл. С 06 6 7/122, 1978 (прототип).

851417

Фиг. 2

4 тах 4/ 67гл

z<> .2д mug

Zij mi e

Составитель A Яицков

Редактор Н.Безродная Техред й. Савка Корректор В Синицкая

Заказ 6361/70 Тираж 745 Подписное

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

113035, Москва, ж-35, Рауюская наб., д. 4/5

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