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

Союз Советскнх Социалистических Республнк(51)М. К .з 6 Об С 7/122 Государственный комитет СССР по делам изобретений и открытий(72) Авторы изобретения А,Г,Додонов, В.В.Месяц, Е,А.Ралдугин, В.В.и А.М.Цетинин 1) Заявитель ИнститУт электродинамики АН Украинской 54) УСТРОЙСТВО ДЛЯ РАСЧЕТА СЕТЕВИХ ГРАФИКОВ Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств или оперативного решения задач оптимального распределения целочисленного ограниченного ресурса на сетевых графиках.Известно устройство для моделирования экстремальных путей на графике, содержащее модели ветвей, входной и выходной полюса каждой из которых соединены с соответствующими полюсами остальных моделей ветвей в соответствии с топологией заданного сетевого графика, причем модель ветви состоит иэ счетчика, двух триггеров, элементов И, НЕ и диода 1 .Недостатком этого устройства является то, что оно определяет только длиннейший и кратчайший путв на графе но, .не позволяет решать задачу оптимального целовычисленного распределения ограниченных ресурсов на сетевых графиках.Наиболее близким по технической сущности к предлагаемому является устройство для расчета сетевых графиков, содержащее модели ветвей, сс стоящие из счетчиков, триггеров,элементов И, ИЛИ, НЕ, входной и выходной полюса каждой иэ которых соединены с соответствующими полюсамиостальных моделей ветвей в соответствии с топологией заданного сетевогографика, генератор импульсов, входоми выходом соединенный с блоком управ.ления, управляемый распределительсостоящий иэ однотипных ячеек, кажО дая иэ которых состоит из двух триггеров и четырех элементов И, причем ячейки управляемого распределителя соединены последовательно,при этом первый выход предыдущей15 ячейки соединен с первым входом последующей ячейки, а первый входпервой ячейки управляемого распределителя и первый выход последней ячейки соединены соответственно с первы 20 ми выходами и входом блока управления, второй и третий выходы которо го подключены соответственно ко вторым входам однотипных ячеек управляемого распределителя и к первым25 полюсам моделей ветвей 2,Недостаток такого устройства заключается в том, что оно толькоопределяет сумларный употребляемыйресурс на заданный момент времени38 выполнения проекта, но не поэволяеъ851417 та 2 дтсл Составитель К.Яицковная Техред А Савка Корректор В. Синицкая Ред е Заказ 6361/70ВНИИ ПодписноСР 113035,ППП "Патентф, г. Ужгород ли ная, 4 Тираж Государственно делам изобретени сква, Ж, Раунда5комити открыкая на та ССтийеф дерешить задачу оптимального целочисленного распределения ограниченныхресурсов на сетевых графиках,Цель изобретения - созданиеустройства для расчета сетевых графикав с учетом распределения целочисленных нескладируемых ресурсов.Указанная цель достигается тем,что в устройство, содержащее о, модели ветвей, соединенные согласнотопологии сетевого графика, генератор импульсов, вход и выход которогосоединены соответственно с упраьбиющим выходом и управляющим входом блока управления,п распределителей,.соединенных последовательно, причем первый выход предыдущего распределителясоединен с первым входом последующего распределителя, а первый входпервого распределителя .и первый выходв-го распределителя соединены соответственно с первыми выходом и вхо-"дом блока управления, второй и третийвыходы которого подключены соответственно ко вторым входам распределителей и к первым полюсам моделей ветвей, введен. формирователь временногоинтервала, выход которого соединен совторым входом блока управления, четвертый, пятый и шестой выходы которого подключены соответственно ко второму, третьему и четвертому полюсамвсех моделей ветвей, пятые полюсыкоторых соединены с первым входомформирователя временного интервалаи подключены к седьмому выходу блокауправления, второй вход формирователя временного интервала соединен спервым выходом и-го распределителя ис шестыми полюсами всех моделей ветвей, седьмые полюсы которых подключены к восьмому выходу блока управления и ко входному полюсу устройства, выходной полюс которого соединенс девятым выходом блока управления,восьмой и девятый полюсы каждоймодели ветви подключены соответственно к установочному входу и второму выходу соответствующего распределителя, десятые полюсы моделей ветвей соединены со вторым выходом блока управления.Кроме этого, каждая модель ветвисодержит восемь элементов И, тритриггера, два элемента ИЛИ, четыреэлемента НЕ, счетчик, задатчик частоты и формирователь временного интервала, единичный выход первоготриггера подключен к первым входампервого, второго и третьего элементов И и к единичному входу второготриггера, нулевой выход которого со"единен с первым входом четвертогоэлемента И, второй вход которогоподключен к первому полису моделиветви, выход четвертого элемента Исоединен со входом первого элементаНЕ, выход которого является выходоммодели ветви, выход первого элемен 5 1 О 15 Ю 25 30 35 40 О 46 6 та НЕ соединен со входом второгоэлемента НЕ, выход которого подключен ко второму входу второго элемента И и к первым входам пятого и шестого элементов И, второй вход шестого элемента И соединен с третьимполюсом модели ветви, второй полюскоторой подключен к первому входуседьмого элемента И, выход которогосоединен с одним входом задатчикачастоты, другие входы которого подключейы к выходам счетчика, входкоторого подключен к выходу третьегоэлемента И, второй вход которого соединен с шестым полюсом модели ветви,.седьмой полюс которой подключен черезтретий: элемент НЕ к первому входувосьмого элемента И, выход которогосоединен с первым входом первого элемента ИЛИ, выход которого подключенк единичному входу первого триггера,.нулевой вход которого соединен с выходом второго элемента ИЛИ первыйвход которого подключен к выходушестого элемента И, второй вход .второго элемента ИЛИ соединен с девятымполюсом модели ветви и с единичнымвходом третьего триггера, единичныйвыход которого подключен ко второмувходу восьмого элемента И, третийвход которого подключен к четвертомуполюсу модели ветви, пятый полюскоторой соединен со вторым входомпервого элемента И и с третьим входом второго элемента И, выход которого через четвертый элемент НЕ подключен ко второму входу седьмогоэлемента И и ко входному полюсу модели ветви, восьмой и десятый полюсыкоторой соединены соответственно свыходом первого элемента И и с нулевым входом третьего триггера, выходзадатчика частоты через формировательвременного интервала подключен ковторому входу пятого элемента И,выход которого соединен со вторымвходом первого элемента ИЛИ.На фиг. 1 изображена блок-схемапредлагаемого устройства, нафиг. 2 - схема блока управления, нафиг. 3 - времяресурсная характеристика отдельной работы.Устройство, состоит из генератора1 Импульсов, блока 2 управления,3, -Зп моделей ветвей, формирователя5 временного интервала, распределителей 4 -4.Каждая йз моделей ветвей 3число которых равно. числу моделируемых работ сетевого графика, содержитзадатчик б частоты, формирователь 7временногоинтервала, счетчик 8,триггеры 9-11, элементы И 12-19,элементы ИЛИ 20-21, элементы НЕ 2225. Задатчик частоты б представляетсобой элемент, в котором опорнаячастота, подаваемая на вход, делитсяна частотц кратные 1,2 (о), п,а на выход элемента пропускаетсятолько одна частота, которая прямо пропорциональна задаваемой величине.формирователь временного интервала 7 выполняется на основе. счетчико-регистровых структур.Модели ветвей соединяются междусобой на наборном пале входными 264 и выходными 27, полюсами в соответствии с топологией моделируемого графика. В каждой модели полюса 28, 29 и 30 подключены соответственно к установочному, разрядному входу и разрядному выходу соответст вующей однотипной ячейки управляе" мого распределителя.. Каждая модель ветви З предназначена для моделирования одной работы исследуемого сетевого графика. Задатчик б частоты и формирователь 7 временного интервала служат для получения длительности с; моделируемой работы, счетчик 8 предназначен для хранения величины моделируемого ресурса г, значение которого определяет задаваемую величину частоты в задатчике б. Достигается это путем параллельного соединения разрядных выходов счетчика 8 с соответствующими входами задатчика б частоты. Например, если в счетчике 8 хранится один импульс (пропорциональный единице ресурса), то на выход задатчика б пропускается наименьшая частота Го(1)где Го - частота следования опорныхимпульсови - емкость счетчика 8 определяющая максимальное значение ресурса, занятого выполнением одной работы.Если же в счетчике 8 хранится число импульсов "К ", то выходная частота Г определяется иэ .выраженияЕ =К - (2)Для моделирования (1) работы вформирователь временного интервала 7модели ветви 3 заносится величина М,определяющая объем выполняемой работы 9" и в счетчик 8 заносится числоимпульсов к, соответствующее величине моделируемого ресурса г; , Количество импульсов в счетчике 8 опре- .деляет частотув задатчике б, Вдальнейшем, подавая на вход задатчика б частоты серию опорных импульсов, модель ветви сформирует временной интервал Т, пропорциональный длительности г" моделируемой работы(13)оо МТ. - М:.п - ,о и 3Кгде Ъ,- период и частота следования опорных импульсов,М величина, пропорциональная объему выполняемойработы 9,. (задаваемаячислом импульсов в формирователе временногоинтервала 7);К величина, пропорциональная количеству ресурсовг; , занятых выполнением5 (1) работы (задаваемаячислом импульсов в счетчике 8 и определяющаявыходную частоту Узадатчика б частоты), , Управляемый распределитель, состоящий иэ однотипных ячеек 4 числокоторых равно числу моделей ветвейсетевого графика, предназначен для1организации последовательного опросамоделей ветвей, принадлежащих одно му критическому пути, В состав каждой ячейки 4 управляемого распределителя входят триггеры 31 и 32, элементы И 33-36.формирователь 5 временного интер О вала построен по аналогии с формирователями 7 моделей ветвей и предназначен для моделирования заданногоограничения ресурсов В, занятого выполнением всего 1 троекта.Блок 2 управления в предлагаемомустройстве представляет собой управ- .ляющий автомат с жесткой логикой,для построения которого можно применить методы синтеза конечных автома О тов, описанных в литературеБлок 1 управления предназначендля организации взаимосвязанной работы блоков устройства и для выработки серий тактовых импульсов ГИ 1,ГИ 2 (ГИ 1, ГИ 2, ГИЗ), сдвинутых относительно друг друга. В состав блока2 управления входят триггеры 37 и38, элементы И 39-45, элементИЛИ 46, элементы НЕ 47 и 48 и элементы задержки 49-54.40 Устройство работаетследувхцим образом.В формирователе 7 временных интервалов моделей ветвей заноситсячисло импульсов, пропорциональное 4 объему выполняемой работы 9 . Триггеры 9-11 находятся первоначально внулевом состоянии, а.на полюсах 26и 27 действует запрещенный потенциал.В счетчик 8 каждой модели заноситсячисло импульсов, соответствующееначальному распределению ресурсакоторое получается путем предварительного решения задачи минимального.потока.После начального установа каждой э 5 модели ветви триггеры 31 и 32 распределителей 4 устанавливаются в нулевое состояние, а в формирователь 5временного интервала заносится число.импульсов, определякщее ограничение Щ используемого ресурса,й, занятоговыполнением всего проекта. В блоке2 (фиг.2) триггеры 37 и 38 устанавливаются в нулевое состояние.В некоторый Юмеит времени сиг-. у нал фПуск", поступающий на полюс 55блока 2, проходит на вход генератора1 импульсов и включает его. Приэтом импульсы с выхода генератора 1проходят в фнок 2 на входы элементов И 39 и 40. Сигнал "Пуск" такжепоступает на вход триггера 37 и через элемент ИЛИ 46 на вход триггера38 и устанавливает их в единичныесостоянияЕдиничное состояние триггера 38выдает разрешение определения деревакритических путей через полюс 56 на 1 Онход элемента И 17 всех моделей ветвей 3, а также на вход элементаИ 39 в блоке 2 (фиг,2). При этом импульсы с выхода генератора 1 проходят через элемент И 39 на входы элементов 49 и 50 задержек, Элементы49 и 50 задержки предназначены длявыработки серии импульсов ГИ 1 и ГИ 2,которые получаются путем соответствующего сдвига серии импульсов, по Оступающей нз генератора 1. Единичноесостояние триггера 37 через элементНЕ 47 выдает разрешающий сигнал вначальный узел моделируемой сети (полюс 57). 25Кроме того, триггер 37 разрешаетпрохождение серии импульсов ГИ 1 иГИ 2 через элементы И 41 и 42 на полюса 58 и 59 блока 2 управления. Тактовые импульсы ГИ 1 и ГИ 2 с полюсов58 и 59 поступают на входы всех моделей ветвей. Но начинают отсчитыватьимпульсы ГИ 1 только те модели ветвей3, на входном полюсе 26 которыхприсутствует разрешающий сигнал (впервый момент это будут модели,.выходящие из начального узла). ИмпульсыГИ 1 проходят через элемент И 14 навход задатчика частоты 6, последнийделит частоту и на своем выходе формирует новую частоту, которая апределяется количеством импульсов, хранящихся в счетчике 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 моделей ветвей сходящихся в конечном узле. Кроме того,в указанную схему совладения подключен выход элемента НЕ 48 блока 2,который в процессе определения дерева критических нулей не влиял нарезультат моделированияПри определении одного критического пути нулевое состояние триггера 38 через время задержки, вырабатываемое элементом 54 задержки, выдает разрешающий сигнал через элемент .НЕ 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, элемент И ЗЗ и устанавливает триггер 31распределителя 4 в единичное. состояние. Вследствие этого на нулевомего выходе, соединенном со входомэлемента И 34, появляется запрещающий потенциал, а на единичном выхо"де - разрешающий потенциал. С появлением на полюсе 62 первого импулькса ГИ 1, который через элемент И 35датанавливает триггер 32 распределителя 4, в единичное состояние (еслитриггер 31 этой ячейки уже находилсяв единичном состоянии), снимаетсяразрешающий потенциал со входа элемента И 33 и подается разрешающийпотенциал на элемент И 36. Кроме тогоФэтот импульс ГИ 1 с выхода элементаИ 35 проходит на разрядный выходячейки (полюс 30) и далее поступаетв соответствующую модель ветви, гдеустанавливает в единичное состоя 1 ф ние триггер 11 и в нулевое триггер 9.Новое состояние триггера 9 запрещает прохождение сигнала с: выходаполюса 27 через элемент И 12 навходной полюс 26, что равносильно15 отключению соответствующей моделиветви от дерева критических путей.Если при этом между конечным узлом(полюс 60) и начальным узлом (полюс67) сетевого графика связанность31 нарушена, то в начальном. узле (по.люс 57 блока управления) появляетсязапрещенный сигнал, который проходитво всех моделях ветвей 3 через элемент НЕ 25 и дает разрешение на входэлемента И 18. Вслед за этим импульсГИ 2 с полюса 63 блока 2 управленияпоступает во все модели ветвей наследующий вход элемента И 18, проходит через указанный элемент тольков той модели ветви, у которой триггер30 11 находится в единичном состоянии,т,е. только в выбранной модели. Сигнал с выхода элемента И 18 поступаетчерез элемент ИЛИ 20 на единичный. вход триггера 9 и возвращает его в3 единичное состояние. Если же связность между начальным и конечнымузлом сетевого графика не была нарушена в момент сброса триггера 9 вноль,.то на полюсе 57 блока 2 управ-,ц ления присутствует разрешающий сигнал, который через инвертор НЕ 25в каждой модели ветви 3 дает запрещение для прохождения импульса ГИ 2через элемент И 18, в итоге триггер9 остается в нулевом состоянии, т.е.рассматриваемая модель ветви исключается из дерева критических путей.Далее импульс ГИМ с полюса 64 блока2 управления поступает на полюс 29модели ветви 3, где сбрасываетсяф триггер 11 в нулевое состояние,и на вход 29 распределителя 4, гдепроходит через элемент И 36 и устанавливает триггер 31 в нулевое состояние, нулевое состояние которого35 выдает разрешение иа прохождениеимпульсов ГИ 1 фсо входа распределителя 4 на его выход (полюс 65) че- .рез элемент И 34.Сигнал с полюса 65, распределите 4 ля 4 передается от ячейки к ячейке,обходя те ячейки, на входах элементов И 33 которых нет разрешения изМоделей ветвей 3. Это соответствуетпоследовательному отключению моделей .ветвей 3, принадлежащий деревугде41 1 вр После просмотра всех моделей, принадлежащих дереву указанных путей,остаются только те ветви, которыеобразуют единственный критичесКийпуть. Направив в эти ветви дополни- .тельно единицу ресурсов с , котораявызывает. соответствующее сокращениемоделируемой длительности Я , Сокращение с;4 каждой ветни уменьшаетЩ длительность всего критического пути. Затем определяем следующий длиннейший путь, величина которого равна либо меньше пути полученногона предыдущем шаге, и распределяемследукщую единицу ресурса,ного графика .равна нулю, при выполнении ограниченийХ.ай, а го, (8)ъО, Д 1 "Ое - целое, . (10)объем работ операции(3)7- количество ресурса,занятого выполнениемработы (13)",гпростаиваемое количество ресурсов во нремя выполнения работы(13)ьвремя простоя. при выполнении операции(13)г - общее количество ресурса, выделяемогодля ныполнения намеченного комплекса работ;Х ,2;- нижний и верхний предел изменения ресурса.Пусть в сетеном графике, состоящемиз работ с подающей нремяресурснойхарактеристикой (фиг.З), распределен.оптимальным образом однородный нескладируеьвй ресурс величиной г. Тогда распределение г +количестваресурса на данном граФике такжеоптимально, если дополнительная единица ресурса направляется по критическому пути.Поскольку рассматривается нескладируеьый ресурс, то его дополнитель,ная единицами должна быть направленапо одному пути иэ множества 1., которые проходят иэ начального узла н конечный. Максимальный эффект, т.е.сокращение срока выполнения всегокомплекса работ, будет достигнут вслучае направления единичного ресурса Я по критическому пути.Представляя в задаче оптимальногораспределения ресурсов в сети искомые переменные г", как сумму некоторых дискретных величии , видим,что довольно сложная, н общем случаенелинейная задача сводится к простому решению.Поскольку задача оптимального целочисленного распределения базируется на методе последовательного наращивания используемого ресурса, тодля правильного ее решения необходимо иметь решения частной задачи, а. именно задачи минимального потока иего распределения по дугам графа.Таким образом, для успешного решенияраспределительной задачи необходимопрежде всего найти минимальный потокв заданной сети.После определения минимального потока для исследуемого графика, вели-.чина потока в каждой ветви будет. ОП.ределять начальное распределение ресурса соответствующей работы. Знаяобъем работы д; и начальные ресурсыг;., выделенныд для выполнения, можно определить начальную длительностьс рассматриваемой операции.Для определения критического путив заданном графике строится модельсети, Длительность каждой ветви графа моделируется временным интервалом,а в каждом узле реализуется логическая операция выделения максимальнойиэ входящих величин ветвей (логическая функция И). При этом моделиветвей 3 соединяются между собой всоответствии с топологией сетевогографика., Для определения, критического 15 (длиннейшего) пути подается сигнал.выпуск" в начальный узел модели, распространяясь по сети, задерживаетсяв каждой модели ветви 3 на величину,пропорциональную времени моделируе мой работы. Временная задержка сигнала "Пускф с момента его поступления в начальный узел до моментапоянления в конечном узле будет пропорциональна величине длиннейшего 25 пути, а модели ветвей, которые окан"чивались в каждом уэле последними,будут определять множество ветвей,.принадлежащих дереву длиннейшихпутей.Построив дерево критических путейна сетевом графике,-можно перейти. к добавлению следующей-.единицы ресурса Й . Поскольку расйрределениересурсбн базируется на основаниипервого закона сетей, необходимвыбрать единственный критическийпуть, в ветви которого мы направляем распределяеьую на данном шагеединицу ресурсов.С этой целью в устройство должна 40 быть введена операция выбора одногокритического пути из имеющегосядерева длиннейших путей. Эта операция строится по методу последовательного опроса всех моделей ветвей, 45 обраэущих полученное подмножество,Каждая ветвь, принадлежащая деревуразрывается последовательно одна эадругой, и исследуется влияние этогофактора на сохранение критического 50 пут"Так, если величина критическогопути на каждом шаге буде либо оставаться прежней, либо уменьшается,то следует ожидать последовательного уменьшения длин критических путей.Очевидно, после использования всего.ресурса, ограниченного значением й,получается минимально возможный дляданных условий критический путь;соответствующий минимальному срокувыполнения всего комплекса работ,а следовательно, полученное приэтом распределение целочисленногоресурса по отдельным работам будет.оптимальным.Использование предлагаемого устройства и приведенного материалапозволяет решить сложную многовариантную задачу и имеет большое прак"тическое значение в сетевом планировании и управлении.,По сравнению с известными устройствами, построенными на диодно-логических цепях, предлагаемое позволяетсущественно повысить точность рас-.пределения ограниченных ресурсовна сетевых графиках, а также дает возможность автоматизироватьпроцесс ввода и обработки информации, непосредственно использоватьрезультаты оптимизации сетевогографика при ограниченных ресурсахв системах СПУ, Цифровая формапредставления информации упрощаетстыковку предлагаемого устройствав комплексе технических средствсистем СПУ.Формула изобретения1. Устройство для расчета сетевых графиков, содержащее и модели ветвей, соединенные согласно топологии сетевого графика, генератор импульсов, вход и выходкоторого соединены соответственно с управляющим выходом и управляющим входом блока управления, и распределителей, соединенных последовательно, причем первый выход предыдущего распределителя соединен с первым входом последующего распределителя, а первый вход первого распределителя и первый выход и-го распределителя соединены соответственно с первыми выходом и входом блока управления, второй и третий выходы которого подключены соответственно ко вторым входам распределителей и к первым полюсам моделей ветвей, о т л и ч а ю щ е е - с я тем, что, с целью расширения функциональных возможностей эа счет возможности решения задачи оптимального целочисленного распределения ограниченных ресурсов, в него введен формирователь временного. интервала, выход которого соединен со вторым входом блока управления, четвертый,пятый и шестой выходы которого подключены соответственно ко второму,третьему и четвертому полюсам моделей ветвей, пятые полюсы которых соединены с первым входом формирователя временного интервала и седьмымвыходом блока управления, второйвходформирователя временного интервала соединен с первым выходом и-гораспределителя и с шестыми полюсамимоделей ветвей, седьмые полюсы кото О рых подключены к восьмому выходублока управления и ко входному полюсу устройства, выходной полюс которого соединен с девятым выходомблока управления, эосьмой и девятый 15 полюсы каждой модели ветвей подключены соответственно к установочномувходу и второму выходу соответствующего распределителя, десятые полюсымоделей ветвей соединены со вторым р эыходом блока управления.2. Устройство по п.1, о т л ич а ю щ е е с я тем, что каждая модель ветви содержит восемь элементов И, три триггера, два элементаИЛИ, четыре элемента ЯЕ, счетчик,задатчик частоты и формировательвременного интервала, единичный выход первого триггера подключен кпервым входам первого, второго итретьего элементов И и к единичному ЗО входу второго триггера, нулевой выход которого соединен с первым вхоцом четвертого элемента И, второйвход которого подключен к первомуполюсу модели ветви, выход четверто го элемента соединен со входом первого элемента НЕ, выход которого является выходом модели ветви, выходпервого элемента НЕ соединен со входом второго элемента НЕ, выход кото О рого подключен ко второму входувторого элемента И и к первым входампятого и шестого элементов И, второйвход шестого элемента И соединен стретьим полюсом модели ветвей, вто.рой полюс которой подключен к первому входу седьмого элемента И, выходкоторого соединен с одним входомзадатчика частоты, другие входы которого подключены к выходам счетчика,вход которого подключен к выходутретьего элемента И, второй входкоторого соединен с шестым полюсом.модели ветви, седьмой полюс которой .подключен через третий элемент НЕ кпервому входу восьмого элемента И, Ы выход которого соединен с первымвходом первого элемента ИЛИ,. выходкоторого подключен к единичному входу первого триггера, нулевой входкоторого соединен с выходом второго р элемента ИЛИ, первый вход которогоподключен к выходу шестого элемента И, второй вход второго элементаИЛИ соединен с девятым полюсом модели ветви и с единичным входом третьд его триггера, единичный выход кото0 Врого подключен ко второму входу восьмого элемента И, третий вход которого подключен к четвертому полюсу модели ветви, пятый полюс которой соединен со вторым входом первого элемента И и с третьим входом второго элемента И, выход которого через четвертый элемент НЕподключен ко второму входу седьмого элемента Ии ко входному полюсу модели ветви, восьмой и десятый полюсы которой соединены соответственно с . выходомпервого элемента И и с нулевым входом третьего триггера,выход задатчика частоты череэ формирователь временного интервала подключен ко второму входу пятого элемента И, выход которого соединен. со вторым входом первого элемента ИЛИ.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР9305484, кл. С Об С 7/34, 1970.2, Авторское свидетельство СССРпо заявке В 2579670/18-24,кл. С 06 6 7/122, 1978 (прототип).