Устройство для расчета сетевыхгРАфиКОВ Советский патент 1981 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ РАСЧЕТА СЕТЕВЫХ ГРАФИКОВ

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств или оперативного решения задач оптимального распределения целочисленного ограниченного ресурса на сетевых графиках. Известно устройство для моделирования экстремальных путей на графике, содержащее модели ветвей, входно и выходной полюса каждой из которых соединены с соответствующими полюсам остальных моделей ветвей в соответст вии с топологией заданного сетевого графика, причем модель ветви состоит из счетчика, двух триггеров, элементов И, НЕ и диода l . Недостатком этого устройства явля ется то, что оно определяет только длиннейший и кратчайший путь на графе но, не позволяет решать зада чу оптимсшьиого целовычисленного распределения ограниченных ресурсов на сетевых графиках. Наиболее близким по технической сущности к предлагаемому является устройство для расчета сетсГвых графиков г содержсццее модели ветвей, сг стоящие из счетчиков, триггеров, элементов И, ИЛИ, НЕ, входной и выходной полюса каждой из которых соединены с соответствующими полюсами остальных моделей ветвей в соответствии с топологией заданного сетевого графика, генератор импульсов, входом и выходом соединенный с блоком управления, управляеЬвлй распределитель., состоящий из однотипных ячеек, каждая из которых состоит из двух триггеров и четырех элементов И, причем ячейки управляемого распределителя соединены последовательно, при этом первый выход предыдущей ячейки соединен с первым входом последующей ячейки, а первый вход 1первой ячейки управляемого распределителя и первый выход последней ячейки соединены соответственно с первыми выходами и входом блока управления, второй и третий выходы которого подключены соответственно ко вторым входам однотипных ячеек управляемого распределителя и к первым полюсам моделей ветвей С2. Недостаток такого устройства заключается в том, что оно только определяет суммарный потребляемый ресурс на заданный момент времени выполнения проекта, но не позволяетрешить задачу оптимального целочисленного распределения ограниченных ресурсов на сетевых графиках.

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

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

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

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

Устройство.сострит из генератора 1 Импульсов, блока 2 управления, 3, -Зп моделей ветвей, формирователя 5 временного интервала, распределителей 4 -4f,.

Каждая из моделей ветвей 3 , число которых равно числу моделируемых работ сетевого графика, содержит задатчик б частоты, формирователь 7 временного интервала, счетчик 8, триггеры 9-11, элементы и 12-19, элементы ИЛИ 20-21, элементы НЕ 2225. Задатчик частоты б представляет собой элемент, в котором опорная частота, подаваемая на вход, делится на частоты кратные 1,2... (п-1), п. а на выход элемента пропускается только одна частота, которая прямо пропорциональна задаваемой величине Формирователь временного интервала выполняется на основе, счетчико-реги стровых структур. Модели ветвей соединяются между собой на наборном поле входными 264 и выходными 27, полюсами в соответствии с топологией моделируемо го графика. В каждой модели полюса 28, 29 и 30 подключены соответственно к установочному, разрядному ,входу и разрядному выходу соответст вующей однотипной ячейки управляемого распределителя. Каждая модель ветви 3 предназна чена для моделирования одной работы исследуемого сетевого графика. Задат чик 6 частоты и формирователь 7 временного интервала служат для получения длительности t; моделируемой работы,-счетчик 8 предназначен для хранения величины моделируемого ресурса Z--., значение которого определя ет задаваемую величину частоты в задатчике 6. Достигается это путем параллельного соединения разрядных выходов счетчика 8 с соответствующим входс ми задатчика б частоты. Например, если в счетчике 8 хранится один импульс (пропорциональный единице ресурса), то на выход задатчика б пропускается наименьшая частота f f{j - частота следования опорных импульсов; п - емкость счетчика 8 определяющая максимальное значение ресурса, занятого выпол нением одной работы. Если же в счетчике 8 хранится чис ло импульсов К, то выходная частота f.. определяется из .выражения ..-.i Дпя моделирования (i j) работы в формирователь временного интервала 7 модели ветви 3 заносится величина М определяющая объем выполняемой работы g-i и в счетчик 8 заносится число импульсов It , соответствующее величине моделируемого ресурса . Количество импульсов в счетчике 8 определяет частоту Тц в задатчике 6. В дашьнейшем, подавая на вход задатчика 6 частоты серию опорных импульсов, модель ветви сформирует временной интервал Т, пропорциональный дли тельности t-- моделируемой работы период и частота .следогде о 0 вания опорных импульсов величина, пропорциональ ная .объему выполняемой работы д.. (задаваемая числом ийпульсов в .формирователе временного интервала 7) ; К - величина, пропорционгшьная количеству ресурсов гл , занятых выполнением (ij) работы (задаваемая числом импульсов в счетчике 8 и определяющая выходную частоту f задатчика 6 частохы), Управляемый распределитель,состоящий из однотипных ячеек 4 , число которых равно числу моделей ветвей сетевого графика, предназначен для организации последовательного опроса моделей ветвей, принадлежгидих одному критическому пути. В состав каждой ячейки 4 управляемого распределителя входят триггеры 31 и 32, эле-, менты И 33-36. Формирователь 5 временного интервала построен по аналогии с формирователями 7 моделей ветвей и предназначен для моделирования заданного ограничения ресурсов R, занятого выполнением всего Ъроекта. Блок 2 управления в предлагаемом устройстве представляет собой управляющий автомат с жесткой логикой, для построения которого можно применить методы синтеза конечных автоматов, описанных в литературе. Блок 1 управления предназначен для организации взаимосвязанной работы блоков устройства и д.пя выработки серий тактовых иМпульсов ГИ1, ГИ2 (ГИ1, ГИ2, ГИЗ), сдвинутых относительно друг друга. В состав блока 2 управления входят триггеры 37 и 38, элементы И 39-45, элемент ИЛИ 46, элементы НЕ 47 и 48 и элементы задержки 49-54. Устройство работает следукадим образом. . В формирователе 7 временных интервалов моделей ветвей заносится число импульсов, пропорциональное объему выполняемой работы g;j . Триггеры 9-11 находятся первоначально в нулевом состоянии, а.на полюсах 26 и 27 действует запр ценный потенциал. В счетчик 8 каждой модели заносится число импульсов, соответствующее начальному распределению ресурса которое получается путем предварительного решения задачи и1инимальногопотока. . После начального установа каждой модели ветви триггеры 31 и 32 распределителей 4 устанавливаются в нулевое состояние, а в формирователь 5 временного интервала заносится число импульсов, определякадее ограничение используемого ресурса ,R, з1анятого выполнением всего проекта. В блоке 2 (фиг.2) триггеры 37 и 38 устанавиваются в нулевое состояние. В некоторый номент времени сиг-г нал Пуск, поступающий на полюс 55

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

Единичное состояние триггера 38 выдает разрешение определения дерева критических путей через полюс 56 на вход элемента И 17 всех моделей ветвей 3, а также на вход элемента И 39 в блоке 2 (фиг.2). При этом импульсы с выхода генератора 1 прохо ,дят через элемент И 39на входы элементов 49 и 50 задержек. Элементы 49 и 50 задержки предназначены для выработки серии импульсов ГИ1 и ГИ2, которые получаются путем соответствующего сдвига серии импульсов, поступающей из генератора 1. Единичное состояние триггера J7 через элемент НЕ 47 выдает разрешающий сигнал в начальный узел моделируемой сети (полюс 57) , .

Кроме того, триггер 37 разрешает .прохождение серии импульсов ГИ1 и ГИ2 через элементы И 41 и 42 на полюса 58 и 59 блока 2 управления. Тактовые импульсы ГИ1 и ГИ2 с полюсов 58 и 59 поступают на входы всех моделей ветвей. Но начинают отсчитывать импульсы ГИ1 только те модели ветвей 3 , на входном полюсе 26. которых присутствует разрешающий сигнал (в первый момент это будут модели,. выходящие из начального узла). Импульсы ГИ1 проходят через элемент И 14 на вход задатчика частоты 6, последний делит частоту и на своем выходе формирует новую частоту, которая определяется количеством импульсов, хранящихся в счетчике 8,

Формирователь 7 временного интервала отсчитывает импульсы с выхода задатчика 6 частоты. При появлении на выходе формирователя 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, элемент И 33 и устанавливает триггер 31 распределителя 4 в единичное, состояние. Вследствие этого на нулевом его выходе, соединенном со входом элемента И 34, появляется запрещающий потенциал, а на единичном выходе - разрешающий потенциал. С появлением на полюсе 62 первого импульса ГИ1, который через элемент И 35 v :тaнaвливaeт триггер 32 распредели-.

теля 4 в единичное состояние (если триггер 31 этой ячейки уже находился в единичном состоянии), снимается разрешающий потенциал со входа элемента И 33 и подается разрешакишй потенциал на элемент И 36. Кроме того, этот импульс ГИ1с выхода элемента И 35 проходит на разрядный выход ячейки (полюс 30) и далее поступает в соответствующую модель ветви, где устанавливает в единичное состоя0ние триггер 11 ив нулевое триггер 9.

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

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

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

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

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

5 рассматриваемая модель ветви исключается из дерева критических путей. Далее импульс ГИЗ с. полюса 6 блока 2 управления поступает на полюс 29 модели ветви 3, где сбрасывается

0 триггер 11 в нулевое состояние, и на вход 2-9 распределителя 4, где проходит через элемент и 36 и устанавливает триггер 31 в нулевое состояние, нулевое состояние которого

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

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

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

После опроса всех моделей ветвей 3, пр надлвжащий дереву критических путей, на выходе п-го распределителя (полюс 65/) появляется сигнал, поступающий на полюс 66 блока 2 управления. Этот сигнал проходит через элемент ИЛИ 46 и устанавливает триггер 38 в единичное состояние. в результате блок управления прекращает подачу импульсов ГИг, ГИ2 и ГИЗ на соответствующие полюса 62, 63 и 64 и разрешает подачу импульсов ГИ1 и ГИ2 на полюса 58 и 59, а также разрешающий сигнал снимается с полюса 61 и подается на полюс 56. Причем импульс с выхода 65 п-го распределителя поступает на вход формирователя 5 временного интервала и через полюс 66 на йход элемента И 13 всех моделей ветвей 3.

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

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

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

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

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

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

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

Если операция (ij) характеризуется объемом работы , то используя количество ресурсов , можнб выполнить рассматриваемую работу за время у j .

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

. .iii

(М

при условии

V-j j max

Z;

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

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

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

Минимизировать ,

.s(-.t,.).(.,i..,,

.)()

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

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

0 -fZ,ecAMJ H

()-f (.T -ianpl It2, если j к

(6)

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

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

)°

т.е. алгебраическая сумма продолжительностей. выполнения операций и 5 простоев по ним в любом цикле сетевого графика -равна нулю, при выполнении ограничений ijmin -«а о , ijnp. -13 - целое, -объем работ операции - . (ij); -количество ресурса, занятого выполнением работы (i j)V -простаиваемое количе ство ресурсов во вре мя выполнения работы -время простоя при вы полнении операции Z - общее количество ресурса , выделяемого для выполнения намеченного комплекса ра бот; ижний и верхний предел изменения ресурс Пусть в сетевом графике, состояще из работ с подагацей времяресурсной характеристикой (фиг.З.), распределен оптимальным образом однородный нескладируемый ресурс величиной z. Тог да распределение z -)- g количества ресурса на данном графике также оптимально, если дополнительная единица ресурса направляется по критическому пути. Поскольку рассматривается нескладируёмый ресурс, то его дополнитель|Ная единица € должна быть направлена по одному пути из множества L, которые проходят из начального узла в ко нечный. Максимальный эффект, т.е. сокращение срока выполнения всего комплекса работ, будет достигнут в случае направления единичного ресурса по критическому пути. Представляя в задаче оптимашьного распределения ресурсов в сети искомые переменные , как сумму некоторых дискретных величин f , видим, что довольно сложная, в общем случае нелинейная задача сводится к простому решению. Поскольку задача оптимального целочисленного распределения базируется на методе последовательного наращивания используемого ресурса, то для правильного ее решения необходимо иметь решения частной задачи, а именно задачи минимального потока и его распределения по дугам графа. Таким образом, для успешного решения распределительной задачи необходимо прежде всего найти минимальный поток в заданной сети. После определения минимального по тока для исследуемого графика, величина потока в каждой ветви будет, определять начальное распределение ресурса соответствующей работы. Зная объем работы и начальные ресурсы Z;. , выделенные для выполнения, можно определить начальную длительность рассматриваемой операции. , Для определения критического пути в заданном графике строится модель сети. Длительность каядой ветви графа моделируется временным интервалом а в каздом узле реализуется логическая операция выделения максимальной из входящи с величин ветвей (логическая функция И). При этом модели ветвей 3 соединяются между собой в соответствии с топологией сетевого графика. Для определения, критического (длиннейшего) пути подается сигнал . Пуск в начальный узел модели, распространяясь по сети, Зсшерживается в каждой модели ветви.3 на величину, пропорциональную времени моделируемой работы. Временная задержка сигнала Пуск с момента его поступления в начальный узел до момента появления -в конечном узле будет пропорциональна величине длиннейшего пути, а модели ветвей, которане оканчивались в каждом узле последними, будут определять множество ветвей, принадлежащих дереву длиннейших путей. -. Построив дерево критических путей на сетевом графике, можно перейти к добавлению следующёй единицы ресурса S. . Поскольку распределение ресурсов базируется на основа«ии первого закона сетей, необходимо выбрать единственный критический , путь, в ветви которого мы направляем распределяемою на данном шаге единицу ресурсов. С этой целью в устройство должна быть введена операция выбора одного критического пути из имеющегося дерева длиннейших путей. Эта операция строится по методу последовательного опроса, всех моделей ветвей, образущих полученное подмножество. Каждая ветвь, принсщлежащая дереву разрывается последовательно одна за , другой, и исследуется влияни этого фактора на сохранение критического пути. После просмотра всех моделей, принадлежащих дереву указанных путей, остаются только те ветви, которле Образуют единственный кpитичeckий путь. Направив в эти ветви дополнительно единицу ресурсов f , которая вызывает соответствующее сокращение моделируемой длительности t;j . Сокращение каждой ветви уменьшает длительность всего критического пути. Затем определяем следующий длиннейший путь, величина которого равна либо меньше пути/ полученного на предыдущем шаге, и распределяем следующую единицу ресурса. Так, если величина критического пути на каждом шаге буде либо оставаться прежнеп, либо уменьшается то следует -ожидать последовательного уменьшения длин критических путе Очевидно, после использования всего ресурса, ограниченного значением R получается -минимально возможный для данных условий критический путь,соответйтвующий минимальному сроку выполнения всего комплекса работ, а следовательно, полученное при этом распределение целочисленного ресурса по отдельным работам будет оптимальным. Использование предлагаемого устройства и приведенного материала позволяет решить сложную многовариантную задачу и имеет большое практическое значение в сетевом планиро вании и управлении.. По сравнению с известными устрой ствами, построенными на диОдно-логи ческих цепях, предлагаемое позволяе существенно повысить точность распределения ограниченных ресурсов на сетевых графиках, а также дает возможность автоматизировать процесс ввода и обработки информации, непосредственно использовать результаты оптимизации сетевого графика при ограниченных ресурсах в системах СПУ. Цифровая форма . представления информации упрощает стыковку предлагаемого устройства в комплексе технических средств систем СПУ. Формула изобретения 1. Устройство для расчета сетевы графиков, содержащее п модели ветвей, соединенные согласно топологи сетевого графика, генератор импульсов, вход и выходкоторого соедине ны соответственно с управляющим выходом и управляющим входом блока управления, п распределителей, соединенных последовательно, причем первый выход предыдущего распредел теля соединен с первым входом посл дующего распределителя, а первый в первого распределителя и первьлй вы ход п-гр распределителя соединены соответственно с первыми выходом и входом блока управления, второй и третий выходы которого подключены соответственно ко вторым входам ра пределителей и к первым полюсам мо делей ветвей, отличающее с я тем, что, с целью расширения функциональных возможностей за сче возможности решения задачи оптймгш ного целочисленного распределения ограниченных ресурсов, в него введ формирователь временного.интервала выход KOTOfSoro соединен со вторым входом блока управления, четвертый пятый и шестой выходы которого подключены соответственно ко второму, третьему.и четвертому полюсам моделей ветвей, пятые полюсы которых соединены с первым входом формирователя временного интервала и седьмым выходом блока управления, второй входформирователя временного интервала соединен с первым выходом п-го распределителя и с шестыми полюсами моделей ветвей, седьмые полюсы которых подключены к восьмому выходу блока управления и ко входному полюсу устройства, выходной полюс которого соединен с девятым выходом блока управления, восьмой и девятый ПО.ЛЮСЫ каждой модели ветвей подключены соответственно к установочному входу и второму выходу соответствующего распределителя, десятые полюсы моделей ветвей соединены со вторымвыходом блока управления. 2. Устройство ПОП.1, ОТЛИчающееср тем, что каждая, модель ветви содержит восемь элементов И, три триггера, два элемента ИЛИ, четыре элемента ЛЕ, счетчик, задатчик частоты и формирователь временного интервала, единичный выход первого триггера подключен к первым входам первого, второго и третьего элементов И и к единичному входу второго триггера, нулевой выход которого соединен с первым вхоцом четвертого элемента И, второй вход которого подключен к первому полюсу модели ветви, выход четвертого элемента соединен со входом первого элемента НЕ, выход которого является выходом модели ветви, выход первого элемента НЕ соединен со входом второго элемента НЕ, выход которого подключен ко второму входу второго элемента И и к первым входам пятого и шестого элементов И, второй вход шестого элемента И соединен с третьим полюсом модели ветвей, второй полюс которой подключен к первому входу седьмого элемента И, выход которого соединен с одним входом задатчика частоты, другие входы которого подключены к выходам счетчика, вход которого под1 лючен к выходу третьего элемента И, второй вход которого соединен с шестым полюсом модели ветви, седьмой полюс которой . подключен через третий элемент НЕ к первому входу восьмого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход которого подключен к единичному входу первого триггера, нулевой вход которого соединен с выходом второго элемента ИЛИ, первый вход которого подключен к выходу шестого элемента И, второй вход второго элемента ИЛИ соединен с девятым полюсом модели ветви и с единичным входом третьего триггера, единичный выход которого подключен ко второму входу восьмого элемента И, третий вход которого подключен к четвертому полюсу модели ветви, пятый полюс которой соединен со вторым входом первого элемента И и с третьим входом второго элемента И, выход которого через четвертый элемент НЕподключен ко второму входу седьмого элемента И и ко входному полюсу модели ветви, восьмой и десятый полюсы которой соединены соответственно с выходомпервого элемента И и с нулевым входом третьего триггера, выход задатчика частоты через формирователь временного интервала подключей ко второму/входу пятого элемента И, выход которого соединен, со вторым входом первого элемента ИЛИ.

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

кл. G 06 G 7/122, 1978 (прототип).

til.

j.rnax

iu

ij mtn -