Устройство для моделирования экстремальных путей на графе Советский патент 1982 года по МПК G06G7/122 

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

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

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

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

соединенных согласно топологии графа, генератор импульсов, вход и выход которого соединены соответственно с у правляющим выходом и управляющим входом блока управления, h распределителей, соединенных последовательно, причем первый выход предыдущего распределителя соединен с йервым входом последующего распредели10теля, а первый вход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу фо.рмирователя временного 1нтервала и к

15 первым входам моделей ветвей, вторые BXojQj которых соединены с вторыми выходами соответствующих распредели-. телей, вторые входы которых подключены к первым выходам соответствую20щих моделей ветвей, третьи и четвертые входы которых соединены с третьим и четвертым входами 15лока управления соответственно. Кроме зтого, в устройстве имеются еще ряд связей

.25 между моделями ветвей, распределителями, фopVlIиpoвaтeлeм временного интервала и блоком управления 2 .

Данное устройство не позволяет решать задачу оптимизации распределе30ния нескладируемых ресурсов в сетевом графике. Такая задача возникает при планировании и управлении сооружением сложных комплексов работ по сетевым методам. Цель изобретения - расширение функциональных возможностей данного устройства за счет возможности решения задачи оптимизации распределения нескладируемых ресурсов в сетевом графике. Указанная цель достигается тем, что в устройство, содержащее п моделей ветвей, соединенных согласно топологии графа, генератор импульсов, ( вход и выход которого соединены соответственно с, управляющим выходом и управляющим входом блока управления, п распределителей, соединенных последовательно, причем первый выход предыдущего распределителя соединен с первым входом последующего распределителя, а первый вход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу формирователя временного интервала и к первым входам моделей ветвей, вторые входы ко торых соединены с вторыми выходами соответствующих распределителей, вторые входы которых подключены к первым выходам соответствующих моделей ветвей, третьи и четвертые входы которых соединены с третьим и четвертым выходами блока управления соответственно, введены элементы И, элементы ИЛИ и триггер, единичный выход которого подключен к первым входам первого и второго элементов ИЛИ, выход первого элемента ИЛИ сое динен с первым входом блока управления и с пятыми входами моделей ветвей, вторые выходы которых подключены к соответствующим входам первого элемента И, выход которого соединен с вторым входом первого эл мента ИЛИ и через элемент НЕ с первы входом второго элемента И, выход ко торого подключен к второму входу бл ка управления, к шестым входам моде лей ветвей и к нулевому входу триггера, нулевой выход которого соединен с седьмыми входами моделей нетвей, третьи выходы которых подключ ны к третьим входам соответствующих распределителей и к соответствующим входам третьего элемента ИЛИ, -выход которого соединен с третьим входом блока управления, четвертый вход ко торого подключен к выходу второго элемента ИЛИ, второй вход которого соединен с первым выходом п-го распределителя, первый выход блока управления подключен к второму вход формирователя временного интервала, выход которого соединен с единичным входом триггера, четвертые выходы м делей ветвей подключены к соответствующим входам четвертого элемента . ИЛИ, выход которого -подключен к второму входу второго элемента И. Кроме этого, каждая модель ветви содержит счетчик, два формирователя временного интервала, четыре триггера, два элемента ИЛИ, десять элементов И и четыре элемента НЕ, первый и второй входы модели ветви подключены соответственно к первому и второму входам первого формирователя временного интервала, выход которого соединен с первым входом первого элемента И, выход которого подключен к единичному входу первого триггера, единичный выход которого соединен с первым выходом модели ветви, с первым входом второго элемента И и с первым входом третьего элемента И, выход которого подключен к входу счетчика, выход которого соединен с (четвертым выходом модели ветви, с нулевым входом первого триггера и с первым входом четвертого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с первым входом пятого элемента И и с единичным входом третьего триггера, нулевой выход которого подключен к первому входу шестого элемента И и к первому входу седьмого элемента И, выход которого через первый элемент НЕ соединен с выходным полюсом модели ветви и через второй элемент НЕ с вторыми входами четвертого и пятого элементов И и с первым входом восьмого элемента И, выход которого соединен с нулевым входом второ.го триггера, выход пятого элемента И . через третий элемент НЕ соединен с входным полюсом модели ветви, с вторым входом третьего элемента И, с первым входом девятого элемента И, с вторым входом шестого элемента И и через четвертый элемент НЕ с первым входом десятого элемента И, выход шестого элемента И и третий вход модели ветви подключены соответственно к первому и второму входам второго формирователя временного интервала, выход которого соединен с первым входом первого элемента ИЛИ и с единичным входом четвертого триггера, единичный и нулевой выходы которого подключены соответственно ко вторым входам девятого и десятого элементов И, выходы которых соединены с входами второго элемента ИЛИ, выход которого подключен к второму выходу модели ветви, нулевой выход первого триггера соединен с третьим входом пятого элемента И, пятый, седьмой и шестой входы модели ветви подключены соответственно к третьему входу третьего элемента И, к второму входу первого элемента И и к второму входу второго элемента И, выход КОТОРОГО подключен к второму входу первого элемента ИЛИ, выход которого соедин с третьим выходом модели ветви. На фиг.1 изображена блок-схема предлагаемого устройства; на фиг.2 схема блока управления; на фиг.З схема формирователя временного инте вала. Устройство содержит (фиг.1) гене ратор 1 импульсов, блок 2 управлени модели ветвей З.-Зп, управляемые ра пределители 4;,-4п, формирователь 5 временного интервала, триггер 6, эл менты ИЛИ 7-10, элементы И.11 и 12, элемент НЕ 13. Каждая из моделей ветви 3; , числ которых равно числу моделируемых работ сетевого графика, содержит счетчик 14, триггера 15 и 16, элеме ты И 17-21, элементы НЕ 22-24 и диод 25, формирователи 26 и 27 времен ных интервалов, триггера 28 и 29, э менты И 30-34, элементы ИЛИ 35 и 36 и элемент НЕ 37.. Модели ветвей соединяются между собой полюсами: входным -38i, и выход ным 39j в соответствии с топологией моделируемого графа, и в каждой модели вход 40 соединен с шиной управ ления решением задачи о длиннейшем пути. Каждая модель ветви предназначена для моделирования одной работы исследуемого сетевого графика. Счет чик 14 служит для формирования временного интервала, пропорционального заданной длительности работы, форми рователь 26 временного интервала пре назначен для моделирования величины резерва .времени соответствующей рабо ты, формирователь 27 - для моделиров ния интенсивности потребления ресурса той же операции. Каждый формирователь временного интервала выполняется на основе счетчико-регистровых структур. Управляемые распределители 4, чи ло которых равно числу моделей ветвей сетевого графика, предназначены для организации последовательного опроса моделей ветвей, сформировавши минимальные значения резерва времени моделируемых работ. В состав каждого управляемого распределителя вхо дят входы 41-.43, триггеры 44 и 45, элементы И 46-49. Формирователь 5 временного интер-Всша, выполненный аналогичным образом, как формирователи 26 и 27 моделей ветвей, предназначен для моделирования заданного ограничения ресурса R по фронту выполняемых работ Блок 2 управления предназначен для осуществления первоначального запуска всего устройства, для органи зации взаимосвязанной работы блоков устройства и для выработки первой, второй и третьей серии тактовых импульсов (ГИ1, ГИ2 и ГИЗ сдвинутых относительно друг друга) соответственно с выходов 50-52 на одноименные входы всех моделей ветвей 3, Блок 2 управления может быть выполнен различным образом. Один из его вариантов (фиг.2), где блок 2 управления состоит из триггеров 53-55, элементов 56 и 57 задержки, элементов ИЛИ 58-60, элементов И 61-63, входов блока 64-68, выхода 69. Формирователь 5 временного интервала ограничения состоит из C4eT4HV ка 70 импульсов, триггера 71, элемента Vi 12. По входу 73 в счетчик 70 производится предварительная запись числа импульсов, дополняющая заданную величину ограничения ресурса R до полной емкости счетчика. Устройство работает следующим образом. В счетчик 14 модели ветви предварительно заносится число импульсов, дополняющее длину ветвидо полной емкости счетчика. Триггеры 15, 16, 28, 29 находятся первоначально в нулевом состоянии, и на полюсах 38 и 39 действует запре(1ценный потенцигш. Затем в формирователи 26 и 27 временных интервалов заносится число импульсов, соответственно пропорциональное величине il.j , определяющей резерв времени модешируемой работы, и величине используемого ресурса 1 , той же работы. Например, в формирователь 26 модели ветви заносится число импульсов М N - а Т ,j , где N - полная емкость формирователя, а в формирователь 27 - число импульсов L N - .. После начального установа каждой модели ветви триггер 6 и триггеры 44 и 45 однотипных ячеек управляемого распределителя 4; устанавливаются в нулевое состояние, а в формирователь 5 временного интервала заноситсЯдЧИСло импульсов К N - R, определяющее ограничение используемого ресурса по фронту выполняемых работ. В некоторый момент времени по сигналу Пуск подается разрешающий сигнал в начальный уэея моделируемой сети, кроме этого, сигнал Пуск, поступающий на вход 64 блока 2 управления (фиг.2), проходит НЗ вход генератора 1 импульсов и включает его. При этом импульсы с выхода генератора 1 проходят в блок 2 управления на входы элемента И 61 и элементов 56 и 57 задержки. Элементы 56 и 57 задержки предназначены для выработки серии импульсов ГИ2 и ГИЗ, которые получаются путем соответствующего сдвига серии ГИ1, поступающей из генератора 1. Сигнал Пуск с входа 64 также проходит через элемент ИЛИ 58 и устанавливает триггер 53 в единичное состояние. Последнее состояние триггера 53 выдает разрешение на вход элемента И 61, и импульсы ГИ1 проходят через этот элемент И на выход 50 блока управления. Вслед за этим тактовые импульсы ГИ1 с выхода 50 блока управления поступают на входы всех моделей ветвей, но начинаиот моделировать временной интер вал ,j формирователи 26 только тех моделей ветвей 3,, на входном полюсе 38; которых присутствует разрешаю щий сигнал. В данном случае происходит определение тех моделей ветвей, на входе 38;; которых присутствует разрешающий сигнал и величина резерва времени .At j принимает мини мальное значение. Так, когда будет сформирован один или несколько временных интервалов формирователями 26, то импульсный сигнал с выхода формирователя 26 поступит через эле мент ИЛИ 36 на вход 41; соответству ющей я Гейки управляемого распредели теля 4, и установит триггер 44 в единичное состояние. Сигнал с выхода 41; поступает также через элемен ИЛИ В на вход 65 в блок 2 управлени Сигнал с входа 65 проходит через элемент ИЛИ 59 и сбрасывает триггер 53 в нулевое состояние, в результат чего запрещается прохождение импуль сов ГИ1 на выходе 50. Кроме этого сигнал с входа 65 поступает на вход триггера 54 и устанавливает его в единичное состояние. Единичное состояние триггера 54 выдает разрешение на выходе 69, а также разрешает прохождение импульсов ГИ2 с выхода элемента 56 задержки через элемент И 62 на выход 51. По сигналу с выхо да 69, поступающего на управляемый вход (вход 69) первого управляемого распределителя 4 , последний начинает последовательно опрашивать модели ветвей, у которых сформированы минимальные значения резерва времени моделируемых работ. Происходит это следующим образом Предварительно триггеры 44 и 45 устанавливаются в нулевое состояние При появлении сигнала на выходе 41 через элемент И 46 устанавливается в единичное состояние триггер 44 распределителя 4;. Вследствие этого на нулевом его выходе, соединенном со входом элемента И 47, появляется запрещенный потенциал, а на единичном выходе - разрешающий потенциал. С появлением на выходе 69 разрешающего сигнала из блока 2 управления, который через элемент И 48 устанавливает триггер 45 управляемого распределителя 4 в единичное состоя- ние (если триггер 44 этой ячейки находился в единичном состоянии). Тем самым снимается разрешающий потенциал со входа элемента И 46 и подает- ; ся разрешающий потенциал на элемент И 49. Кроме того, сигнал с выхода элемента И 48 через выход 43 поступает на вход формирователя 27 временного интервала соответствующей модели ветви. При этом импульсы ГИ2 с выхода 51 моделируют временной интервал Z;, , величина которого параллельно отсчитывается в общем формирователе 5, так как на одном входе его присутствует разрешающий сигнал с выхода 6.9 блока управления, а на второй поступают импульсы ГИ2. После того, как сформирован моделируемый интервал, на выходе формирователя 27 модели ветви появляется импульсный сигнал, который, установив триггер 29 в единичное состояние (если триггер 6 ограничения находится в нулевом состоянии, полюс 74), выдает разрешение через выход 42 на второй вход элемента И 49 управляемого распределителя 4. Этот сигнал проходит через элемент И 49 и устанавливает триггер 44 в нулевое состояние. Нулевое состояние триггера 44 выдает разрешение на прохождение сигнала с управляющего входа 69 распределителя на ее выход 75 через элемент И 47.. . Сигнал с выхода 69/ первого распределителя 4 передается 6т распределителя к распределителю, пропуская те распределители, на входах элементов И 46 которых нет разрешения из моделей ветвей 3. Так будут просматриваться все модели ветвей и моделироваться значения Z,; для тех моделей, у которых величина резерва времени работы Дии является минимальной. Когда будут сформированы все временные интервалы моделируемых ресурсов и суммарная их величин а не превышает ограничения R, то импульс -движения проходит через-все распре-,, делители и появится на выходе 75 последнего распределителя 4 п. Этот, сигнал проходит через элемент ИЛИ 10 на вход 66 блока 2 управления. Сигнал с входа 79 проходит через элемент ИЛИ 60, сбрасывает триггер 54 в нулевое состояние, запрещая серию импульсов ГИ2 на выходе 51 и разрешение на выходе 69. Кроме того, сигнал с входа 66 проходит через элемент ИЛИ 58 и устанавливает триггер 53 в единичное состояние, разрешая тем самым появление импульсов ГИ1 на выходе 50. Это соответствует дальнейшему моделированию величин ti.,i /т.е. определяются следуюище модели ветвей с минимальным значением резерва времени из оставшихся моделируемых работ на данньй момент времени, Для моделей ветвей, сформировавших временной интервал минимального резерва времени, вновь моделируются величины ресурсов Z; j путем подачи пульсов ГИ2 на выход 51 и разрешающ го сигнала на вход 69 управляемого распределителя и формирователя 5 временного интервала. Как только формирователь 5 сформирует величину ограничения R, на выходе появляется единичный сигнал, который устанавливает триггер 6 в единичное состояние. Сигнал с выхода триггера 6 поступает через элемент ИЛИ 10 на вход 66 в блок 2 управления и запре щает поступление импульсов ГИ2 на выходе 51. Кроме того, этот же сигнал поступает через элемент ИЛИ 9 н вход 67-блока 2 и во все модели вет вей на вход элемента И 18. В блоке сигнал с входа 67 сбрасывает через элементы ИЛИ 59 и 60 триггеры 53 и в нулевые состояния, запрещая тем с мым серии ГИ1 и ГИ2 и устанавливает триггер 55 в единичное состояние. В результате появляется разрешение . на входе элемента И 63 и серия импульсов ГИЗ с выхода элемента 57 за держки проходит на выход 52 блока 2 Поступление импульсов ГИЗ с выхода 52 в модели ветвей 3 соответствует моделированию временных интервалов для тех моделей, которые вошли во фронт выполняемых работ. Если формирователь 5 временного интервала ограничения R не выдает сигнал переполнения, но будут промоделированы все временные интервалы J, для моделей ветвей на входном полюсе 38; которых присутствует сигнал разрешения, то процесс моделирования интервалов будет включен сигналом с выхода элемента И 11. На выходе элемента И 11 появляется разрешающий сигнсш в том случае, если на всех входах 76 имеются разрешаю.щиё потенциалы, которые приходят от моделей ветвей, не принимавших участия в моделировании через элементы НЕ 37, И 32 и ИЛИ 35, либо от модели ветви, на входе 38 которой присутствует сигнал разрешения и она сформировала временной интервал Z, . через элементы И 31, ИЛИ 35. При подаче импульсов ГИЗ на входы 52 всех моделей ветвей моделирование .временных значений t,- осуществляют счетчики 14 лишь тех моделей ветвей которые отсчитали свою величину ресурса , не превысив ограничения R, т.е. триггер 29 модели с единичного выхода выдает разрешение на вход элемента И 18, на остальных вхо дах которого присутствуют разрешающие сигналы с входа 67, входа 38 и серии импульсов ГИЗ. При этом сигнал Пуск, поданный в начальный , распространяясь по сени, задерживается в каждой модели на величину, пропорциональную времени выполнения моделируемой работы j . При появлении на выходе счетчика 14 импульса переполнения триггеры 15 и 16 устанавливаются в единичное состояние . Сигнал с нулевого выхода триггера 16 поступает на один из.входов элемента И 19, на второй вход которого поступает разрешение с входа 40 управления решением задачи о длиннейшем пути. Сигнал с выхода этого элемента поступает на вход схемы совпадения, которая образуется соединением элементов НЕ 23 полюсами 39 моделей ветвей, сходящихся в одной из вершин моделируемого сетевого графика. На полюсе 39 появляется разрешающий потенциал только тогда, когда все триггеры 16 моделей ветвей, входящих в одну вершину, устанавливается в единичное состояние, что соответствует изменению фронта выполняемых работ и необходимо производить перераспределение ресурса. На основании сказанного следует, что если какой-либо -счетчик 14 сформирует моделируемый интервал t;; и при этой в узле реализуется логическая операция выделения максимальной из входящих величин ветвей (логическая функция И), то сигнал переполнения с выхода счетчика пройдет через выход 77, элемент ИЛИ 7 на вход элемента И 12. На втором входе И 12 имеется разрешающий сигнал с выхода элемента НЕ 13, так как фронт выполняемлх работ Изменился и на выходе элемента И 11 появляется запрещенный сигнал. Сигнал с выхода элемента И 12 устанавливает триггер 6 вновь в нулевое состояние и поступает через вход 68 в блок 2. Сигнал с входа 68 сбрасырает триггер 55 в нулевое сост Уяние и запрещает серию импульсов ГИЗ. При этом сигнал с выхода счетчика 14 в модели ветви 3 устанавливает триггер 29 своей модели ветви в нулевое состояние. В результате модель вет-. ви 3 отключается из пр9Цесса моделирования. Как следует из условий задачи, работы сетевого графика, которые начаты, нельзя останавливать и прерывать их выполнение. Поэтому, прежде чем произвести перераспределение ресурса необходимо принять во внимание интенсивности моделей ветвей, ив окончивших моделирование величины ti . Для выполнения приведенного условия сигнал с выхода элемента И 12 поступает на входы 68 всех моделей и проходит через элемент И 34 только тех моделей, которые не окончили уже начатый моделируемый интервал t (т.е. триггер 29 у которых находится в единичном состоянии). В результате в указаниых моделях ветвей 3; сигнгш с выхода И 34 проходит через элемент ИЛИ 36 на выход 41; и , устанавливает триггер 44 соответству юдея ячейки управляемого распределителя в единичное состояние. Кроме того, с выхода 41 сигнал поступает через элемент ИЛИ 8 на вход 65 в блок 2. По этому сигналу устанавливается триггер 54 в единичное состояние, которое выдает разрешение на выход 69 и пропускает импульсы ГИ2 через элементы И 62 на выход 51 В данном случае блок 2 организует мо делирование величин ресурса уже начатых работ и отсчет этих значений в формирователе 5 временного интервала ограничения. В результате этого перед тем, ка начнется вьщеление моделей ветвей с минимальным резервом времени, будут величины ресурсов мо делей, принадлежащих фронту. Так процесс перераспределения ресурса сменяется процессом моделирования длительностей t; (распространения си гнала Пуск по моделируемой сети) до тех пор, пока не будет сформирован конечный узел сетевого графика. При этом величина сутчмарного ресурса фронта на протяжении всего проце са решения не превышает заданного ограничения R. Количество импульсов ГИЗ, поступающих на выход 52 из бло ка 2 управления, определяют время выполнения всего проекта с ограниче нием R на используемый ресурс. В устройстве обеспечивается поступление необходимых сигналов управления и предварительного установ (не показаны). Рассмотрим краткую постановку за дачи оптимизации распределения нескладируемых ресурсов в сетевом гра фике. Пусть задан связанный ориентированный граф G(X,U) без Контуров, у которого имеются только одна начальная XjH одна конечная Х вершины. Граф G соответствует комплексу взаимосвязанных работ, которые необходи мо выполнить при реализации проекта Узел (событие) сетевого графика фиксирует свершение всех работ, входящих в него, и начало всех работ, исходящих из этого узла. Ветвь сетевого графика соответствует отдельной работе (операции), время выполнения t;. которой определяет длительность рассматриваемой ветви. Если работа (ij) начинается в момент времени 1, и заканчивается я то требуемые для ее момент проведения ресурсы нескладируемого типа можно записать как функцию времени в виде . l,W Z,j(i(t-i.)(t-t), (О где 6 (t) -функция единичного скачка; -время начала и конца работы (ij); -интенсивность потребления ресурса, необходимого для выполнения работы (i j ) . Причем весь сетевой график в каждый момент времени описывается суммарным потребляемым ресурсом для данного фронта работ . Н,, где Zj.(tj - интенсивность потребления ресурса в момент t для всего графика. Совокупность работ, которые по сетевому графику можно выполнять одновременно, называется фронтом работ l-4t). Задача оптимизации сетевого графика при ограниченных ресурсах заключается в такой организации выполнения проекта, чтобы величина суммарного потребляемого ресурса для каждого фронта F не превышала заданного ограничения R. Т.е. при реализации проекта, исходя из важности выполняемых работ (принадлежности критическому пути), и, не превышая заданного ограничения, без задержек включать в процесс выполнения одни работы и передвигать сроки начала других работ.(Задача определения критического пути и временного расчета сетевого графика может быть решена на предлагаемом устройстве). В предлагаемом устройстве для моделирования экстремальных путей на графе для определения длиннейшего пути в заданном графе строится модель сети. Длительность Кс1ждой ветви графа моделируется временным интервалом, а в каждом узле реализуется логическая операция выделения максимальной из входящих величин ветвей (логическая функция И). При этом модели ветвей соединяются между собой в соответствии с топологией сетевого графика. Для определениядлиннейшего пути подается сигнал Пуск в начальный узел модели, который, распространяясь по сети, задерживается в каждой модели ветви на величину, пропорциональную времени моделируемой работы. Временная задержка сигнала Пуск с момента его поступления в начальный узел до момента появления в конечном узле

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

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

Сущность этого метода состоит в

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

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

Использование приведенного правила для распределения ресурсов на устройстве эквивалентно заданию некоторой функции предпочтения, котора минимизирует функционал М где F(t} - множество работ, принад лежащих фронту; - резерв времени работы - величина ресурсов, необ ходимая для выполнения боты (ij). Для того, чтобы вычислить резер времени операции, необходимо внача определить число т. т - t i где Т . - время выполнения всего комплекса; , - позднее время начала ра ты (ij) , которое не изм няет ход выполнения про екта . Тогда резерв работы определяется по формуле 3 L-L,-- или (ij)eFCt) (5) где-.Ь,- Т,L maxL(ij)eFCt) Теперь легко получить распределение суммарного ресурса по фронту при заданном ограничении R. Перераспределение ресурсных значений пр исходит каждый раз, когда оканчивается какая-либо операция. При этом данный момент в работу включаются по порядку сначала те операции, которые имеют наименьшую величину резерва времени до тех пор, пока суммерное значение ресурса не превысит ограничения R. Зная распределение ресурса на данный момент времени, легко определить следующий момент перераспределения и включить в работу соответствующие операции. Таким образом, с момента начала выполнения проекта можно последовательно получить распределение ресурса по всем фронтам, значение которого не превышает допустимого ограничения.

Приведенный метод позволяет орга1низовать оптимизацию распределения ,нескладируемых ресурсов в сетевом Графике на предлагаемом устройстве.

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

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

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

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

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

через первый элемент НЕ соединен с выходным полюсом модели ветви и через второй элемент НЕ с вторыми входами четвертого и пятого элементов И и с первым входом восьмого

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

5 третьего элемента И, с первым входом девятого элемента И, с вторым входом шестого элемента И и через четвертый элемент НЕ с первым входом десятого элемента И, выход шестого

0 элемента И и третий вход модели ветви подключены соответственно к первому и второму входам второго формирователя временного интервала, выход которого соединен с первым входом

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

му входу первого элемента ИЛИ, выход

которого соединен с третьим выходом . модели ветви.

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

5 1. Авторское свидетельство СССР 305484, кл,С Об G 7/34, 1970.

2. Авторское свидетельство СССР по заявке 2842170/18-24, кл.С Об G 7/122, 1979 (прототип).