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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(23) Приоритет -Государственный комитет СССР по делам изобретенийДата опубликования описания 27.08.82(72) Авторы изобретен и А.Г.Додонов, В.В.Хаджинов, В.М.Шишмаре Институт электродинамики АН Украинской(541 устРОЙстВО ДлЯ мОДелиРОВАниЯ экстРемАльных ПУТЕЙ НА ГРАФЕ15 25 30 Изобретение относится к вычислительной технике и преимущественно может быть использовано при построении специализированных вычислительных устройств для оперативного решения Задач оптимального распределения нескладируемых ресурсов на сетевых графиках.Известно устройство для моделирования экстремальных путей на графе,содержащее модели ветвей, входную и выходную, полюса каждой из которых соединены с соответствующими полюсами остальных моделей ветвей в соответствии с топологией заданного сетевого графика, причем модель ветви состоит из счетчика, двух триггеров, элементов И, НЕ и диода 1 .НЕдостатком этого устройства является то, что оно определяет только длиннейший и. кратчайший путь на графе, но не позволяет решить задачу оптимального целочисленного распределения ресурсов на сетевых графиках.Наиболее близким по технической сущности к предлагаемому является устройство для расчета сетевых графиков, содержащее л моделей ветвей,соединенных согласно топологии графа, генератор импульсов, вход и вы" ход которого соединены соответственно с управляющим выходом и управляющим входом блока управления, и распределителей, соединенных последовательно, причем первый выход предыдущего распределителя соединен с йервым входом последующего распределителя, а первый вход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу формирователя временного, интервала и к первым входам моделей ветвей, вторые входы которых соединены с вторыми выходами соответствующих раоюределителей, вторые входы которых подключены к первым выходам соответствующих моделей ветвей, третьи и четвертые входы которйх соединены с третьим и четвертым входами блока управления соответственно; Кроме этого, в устройстве имеются еще ряд связей между моделями ветвей, распределителями, формирователем временного интервала и блоком управления 2 .Данное устройство не позволяет решать задачу оптимизации распределения нескладируемых ресурсов в сетевомРедакт лиал ППП "Патент", г.ужгород, ул.Проектная,4 каз 6805 ВНИИПИ Го по дела 1 13035, Мосраж 731 дарстве изобрет а, ЖногонийРауш оми отк кая Подписноета СССРтийаб д.4/5графике. Такая задача возникает припланировании и управлении сооружением сложных комплексов работ по сетевым м.тодам,Цель изобретения - расширениефункциональных возможностей данногоустройства за счет возможности решения задачи оптимизации распределения нескладируемых ресурсов в сетевом графике.Указанная цель достигается тем, 10что в устройство, содержащее и моделей ветвей, соединенных согласно топологии графа, генератор импульсов,вход и выход которого соединенысоответственно с управляющим выходом и управляющим входом блокауправления, и распределителей, соединенных последовательно, причемпервый выход предыдущего распределителя соединен с первым входом последующего распределителя, а первыйвход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу формирователявременного интервала и к первым входам моделей ветвей, вторые входы которых соединены с вторыми выходамисоответствующих распределителей,вторые входы которых подключены кпервым выходам соответствующих моде- З 0лей ветвей, третьи и четвертые входы которых соединены с третьим ичетвертым выходами блока управлениясоответственно, введены элементы И,элементы ИЛИ и триггер, единичный 35выход которого подключен к первымвходам первого и второго элементовИЛИ, выход первого элемента ИЛИ соединен с первым входом блока управления и с пятыми входами моделейветвей, вторые выходы которых подключены к соответствующим входам:первого элемента И, выход которогосоединен с вторым входом первого элемента ИЛИ и через элемент НЕ с первымвходом второго элемента И, выход которого подключен к второму входу блока управления, к шестым входам моделей ветвей и к нулевому входу триггера, нулевой выход которого соединен с седьмыми входами моделей ветвей, третьи выходы которых подключены к третьим входам соответствующихраспределителей и к соответствующимвходам третьего элемента ИЛИ, выходкоторого соединен с третьим входом 55блока управления, четвертый вход которого подключен к выходу второгоэлемента ИЛИ, второй вход которогосоединен с первым выходом и-го распределителя, первый выход блока 60управления подключен к второму входуформирователя временного интервала,выход которого соединен с единичнымивходом триггера, четвертые выходы мгделей ветвей подключены к соответствующим входам четвертого элемента . ИЛИ, выход которого подключен к второму входу второго элемента И.Кроме этого, каждая модель ветви содержит счетчик, два. формирователя временного интервала, четыре триггера, два элемента ИЛИ, десять элементов И и четыре элемента НЕ, первый и второй входы модели ветви подключены соответственно к первому и второму входам первого формирователя временного интервала, выход которого соединен с первым входом первого элемента И, выход которого подключен к единичному входу первого триггера, единичный выход которого соединен с первым выходом модели ветви, с первым входом второго элемента И и с первым входом третьего элемента И, выход которого подключен к входу счетчика, выход которого соединен с четвертым выходом модели ветви, с нулевым входом первого триггера и с первым входом четвертого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с первым входом пятого элемента И и с единичным входом третьего триггера, нулевой выход которого подключен к первому входу шестого элемента И и к первому входу седьмого элемента И, выход которого через первый элемент НЕ соединен с выходным полюсом модели ветви и через второй элемент НЕ с вторыми входами четвертого и пятого элементов И и с первым входом восьмого элемента И, выход которого соединен с нулевым входом второго триггера, выход пятого элемента И . через третий элемент НЕ соединен с входным полюсом модели ветви, с вторым входом третьего элемента И, с первым входом девятого элемента И, с вторым входом шестого элемента И и через четвертый элемент НЕ с первым входом десятого элемента И, выход шестого элемента И и третий вход модели ветви подключены соответственно к первому и второму входам второго формирователя временного интервала, выход которого соединен с первым входом первого элемента ИЛИ и с единичным входом четвертого триггера, единичный и нулевой выходы которого подключены соответственно ко вторым входам девятого и десятого элементов И, выходы которых соединены с входами второго элемента ИЛИ, выход которого подключен к второму выходу модели ветви, нулевой выход первого триггера соединен с третьим входом пятого элемента И, пятый, седьмой и шестой входы модели ветви подключены соответственно к третьему входу третьего элемента И, к второму входУ первого элемента И и к второму входу второго элемента И, выход котооогоподключен к второму входу первого элемента ИЛИ, выход которого соединен с третьим выходом модели ветви.На Фиг.1 изображена блок-схема предлагаемого устройства; на фиг.2 схема блока управления, на Фиг.З схема формирователя временного интервалаа.Устройство содержит (фиг.1) генератор 1 импульсов, блок 2 управления, модели ветвей 3.-3 р, управляемые распределители 4 - 4 П, формирователь 5 временного интервала, триггер б, элементы ИЛИ 7-10, элементы И.11 и 12, элемент НЕ 13.Каждая из моделей ветви 3, число 15 которых равно числу моделируемых работ сетевого графика, содержит счетчик 14, триггера 15 и 16, элементы И 17-21, элементы НЕ 22-24 и диод 25, Формирователи 26 и 27 времен р ных интервалов, триггера 28 и 29, элементы И 30-34, элементы ИЛИ 35 и 36 и элемент НЕ 37.Модели ветвей соединяются между собой полюсами: входным 38 и выходным 39, в соответствии с топологией моделируемого графа, и в каждой модели вход 40 соединен с шиной управления решением задачи о длиннейшем пути.Каждая модель ветви предназначена для моделирования одной работы исследуемого сетевого графика. Счетчик 14 служит для формирования временного интервала, пропорционального заданной длительности работы, формирователь 26 временного интервала предназначен для моделирования величины резерва, времени соответствующей работы, формирователь 27 - для моделирования интенсивности потребления ресур са той же операции. Каждый формирователь временного интервала выполняется на основе счетчико-регистровых структур.Управляемые распределители 4;, число которых равно числу моделей ветвей сетевого графика, предназначены для органиэации последовательного опроса моделей ветвей, сформировавших минимальные значения резерва времени моделируемых работ. В состав каждого управляемого распределителя входят входы 41-.43, триггеры 44 и 45, элементы И 46-49.Формирователь 5 временного интер 55 вала, выполненный аналогичным образом, как формирователи 26 и 27 моделей ветвей, предназначен для моделирования заданного ограничения ресурса к по фронту выполняемых работ.Блок 2 управления предназначен для осуществления первоначального запуска всего устройства, для организации взаимосвязанной работы блоков устройства и для выработки первой, второй и третьей серии тактовых им пульсов (ГИ 1, ГИ 2 и ГИЗ сдвинутыхотносительно друг друга) соответственно с выходов 50-52 на одноименныевходы всех моделей ветвей 3. Блок2 управления может быть выполнен различным образом. Один из его вариантов (фиг.2), где блок 2 управлениясостоит из триггеров 53-55, элементов 56 и 57 задержки, элементов ИЛИ58-60, элементов И 61-63, входов блока 64-68, выхода 69,Формирователь 5 временного интервала ограничения состоит из счетчикка 70 импульсов, триггера 71, элемента И 72.По входу 73 в счетчик 70 производится предварительная запись числаимпульсов, дополняющая заданную величину ограничения ресурса Й до полной емкости счетчика.Устройство работает следующимобразом.В счетчик 14 модели ветви предварительно заносится число импульсов,дополняющее длину ветви до полнойемкости счетчика. Триггеры 15, 16, 28,29 находятся первоначально в нулевомсостоянии, и на полюсах 38 и 39 действует запрещенный потенциал. Затемв формирователи 26 и 27 временных интервалов заносится число импульсов,соответственно пропорциональное величине д,1, определяющей резерв времени моделируемой работы, и величинеиспользуемого ресурса г,; той жеработы. Например, в формирователь26 модели ветви заносится число импульсов М = И - ь 7 , где И - полнаяемкость формирователя, а в формирователь 27 - число импульсов Ь = ИПосле начального установа каждоймодели ветви триггер б и триггеры 44и 45 однотипных ячеек управляемогораспределителя 4; устанавливаются внулевое состояние, а в формирователь5 временного интервала заносится число импульсов К = Х - й, определяющееограничение используемого ресурсапо фронту выполняемых работ. В некоторый момент времени по сигналу "Пуск" подается разрешающий сигнал в начальный узел моделируемой сети, кроме этого, сигнал "Пуск", поступающий на вход 64 блока 2 управления (фиг,2), проходит на вход генератора 1 импульсов и включает его. При этом импульсы с выхода генератора 1 проходят в блок 2 управления на входы элемента И 61 и элементов 56 и 57 задержки. Элементы 56 и 57 задержки предназначены для выработки серии импульсов ГИ 2 и ГИЗ, которые получаются путем соответствующего сдвига серии ГИ 1, поступающей из генератора 1.Сигнал "Пуск" с входа 64 также проходит через элемент ИЛИ 58 иустанавливает триггер 53 в единичное состояние. Последнее состояние триггера 53 выдает разрешение на вход элемента И 61, и импульсы ГИ 1 проходят через этот элемент И на выход 50 блока управления. Вслед за этим тактовые импульсы ГИ 1 с выхода 50 блока управления поступают на входы всех моделей ветвей, но начинают моделировать временной интервал ь, Формирователи 26 только тех моделей ветвей 3 на входном полюсе 38, которых присутствует разрешающий сигнал. В данном случае происходит определение тех моделей ветвей, на входе 38 которых присутствует разрешающий сигнал и величина резерва времени.ь принимает минимальное значение. Так, когда будет сформирован один или несколько временных интервалов формирователями 26, то импульсный сигнал с выхода Формирователя 26 поступит через элемент ИЛИ 36 на вход 41 соответствующей ячейки управляемого распределителя 4, и установит триггер 44 в единичное состояние. Сигнал с выхода 41, поступает также через элемент ИЛИ 8 на вход 65 в блок 2 управления. Сигнал с входа 65 проходит через элемент ИЛИ 59 и сбрасывает триггер 53 в нулевое состояние, в результате чего запрещается прохождение импульсов ГИ 1 на выходе 50. Кроме этого сигнал с входа 65 поступает на вход триггера 54 и устанавливает его в единичное состояние. Единичное состояние триггера 54 выдает разрешение на выходе 69, а также разрешает прохождение импульсов ГИ 2 с выхода элемента 56 задержки через элемент И 62 на выход 51. По сигналу с выхода 69, поступающего на управляемый вход (вход 69 ) первого управляемого распределителя 4, последний начинает последовательно опрашивать модели ветвей, у которых сформированы минимальные значения резерва времени моделируемых работ.1Происходит это следующим образом.Предварительно триггеры 44 и 45 устанавливаются в нулевое состояние. При появлении сигнала на выходе 41 через элемент И 46 устанавливается в единичное состояние триггер 44 распределителя 4; . Вследствие этого на нулевом его выходе, соединенном со входом элемента И 47, появляется запрещенный потенциал, а на единичном выходе - разрешающий потенциал. С появлением на выходе 69 разрешающего сигнала из блока 2 управления, который через элемент И 48 устанавливает триггер 45 управляемого распределителя 4 в единичное состоя ь ние (если триггер 44 этой ячейки находился в единичном состоянии), Темсамым снимается разрешающий потенциал со входа элемента И 46 и подает-ся разрешающий потенциал на элементИ 49. Кроме того, сигнал с выходаэлемента И 48 через выход 43 поступает на вход формирователя 27 временного интервала соответствующей модели ветви. При этом импульсы ГИ 2 с выхода 51 моделируют временной интервал 2 , величина которого параллельно отсчитывается в общем формирователе 5, так как на одном входе 10 Сигнал с выхода 69; первого распределителя 4; передается дт распределителя к распределителю, пропуская те распределители, на входах элементов И 46 которых нет разрешения из моделей ветвей 3. Так будут просматриваться все модели ветвей и моделироваться значения 2, для тех моделей, у которых величйна резерва времени работы Ь, является минимальной.Когда будут сформированы все временные интервалы моделируемых ресурсов 2 и суммарная их величина не11превышает ограничения К, то импульс-движения проходит через .все распределители и появится на выходе 75последнего распределителя 4 и. Этот 5 О сигнал проходит через элемент ИЛИ 10на вход 66 блока 2 управления. Сигнал с входа 79 проходит через элемент ИЛИ 60, сбрасывает триггер 54 внулевое состояние, запрещая серию импульсов ГИ 2 на выходе 51 и разрешение на выходе 69. Кроме того, сигнал с входа 66 проходит через элемент ИЛИ 58 и устанавливает триггер53 в единичное состояние, разрешаятем самым появление импульсов ГИ 1 на О выходе 50. Это соответствует дальнейшему моделированию величин Ьт.е.определяются следующие модели ветвей с минимальным значением резервавремени из оставшихся моделируемых 65 работ на данный момент времени. его присутствует разрешающий сигналс выхода 69 блока управления, а навторой поступают импульсы ГИ 2, 15 После того, как сформирован моделируемый интервал, на выходе формирователя 27 модели ветви появляетсяимпульсный сигнал, который, установив триггер 29 в единичное состоя ние (если триггер 6 ограничения находится в нулевом состоянии, полюс 74),выдает разрешение через выход 42 навторой вход элемента И 49 управляемого распределителя 41, Этот сигналпроходит через элемент И 49 и устанавливает триггер 44 в нулевое состояние. Нулевое состояние триггера 44выдает разрешение на прохождение сигнала с управляющего входа 69 распределителя на ее выход 75 через элемент И 47.Сигнал с выхода элемента И 12 устанавливает триггер 6 вновь в нулевое состояние и поступает через вход 68 в блок 2. Сигнал с входа 68 сбрасывает триггер 55 в нулевое состояние и запрещает серию импульсов ГИЗ. При этом сигнал с выхода счетчика 14 в модели ветви 3 устанавливает триггер 29 своей модели ветви в нулевое состояние. В результате модель ветви 3 отключается из пррцесса моделирования.Как следует из условий задачи, работы сетевого графика, которые начаты, нельзя останавливать и прерывать их выполнение. Поэтому, прежде чем произвести перераспределение ресурса необходимо принять во внимание интенсивности 2 моделей ветвей, не окончивших моделирование величины й ,. Для выполнения приведенного ус 11ловия сигнал с выхода элемента И 12 поступает на входы 68 всех моделей и проходит через элемент И 34 только 1тех моделей, которые не окончили уже начатый моделируемый интервал й Для моделей ветвей, сформировавших временной интервал минимального резерва времени, вновь моделируются величины ресурсов 2,; путем подачи импульсов ГИ 2 на выход 51 и разрешающего сигнала на вход 69 управляемого распределителя и формирователя 5 временного интервала. Как только Формирователь 5 сформирует величину ограничения Й, на выходе появляется единичный сигнал, который уста навливает триггер 6 в единичное состояние. Сигнал с выхода триггера 6 поступает через элемент ИЛИ 10 на вход 66 в блок 2 управления и запрещает поступление импульсов ГИ 2 на 15 выходе 51. Кроме того, этот же сигнал поступает через элемент ИЛИ 9 на вход 67 блока 2 и во все модели ветвей на вход элемента И 18. В блоке 2 сигнал с входа 67 сбрасывает через элементы ИЛИ 59 и 60 триггеры 53 и 54 в нулевые состояния, запрещая тем самым серии ГИ 1 и ГИ 2 и устанавливает триггер 55 в единичное состояние. В результате появляется разрешение на входе элемента И 63 и серия импульсов ГИЗ с выхода элемента 57 задержки проходит на выход 52 блока 2. Поступление импульсов ГИЗ с выхода 52 в модели ветвей 3 соответствует моделированию временных интервалов С,; для тех моделей, которые вошли во Фронт выполняемых работ.1Если формирователь. 5 временного интервала ограничения й не выдает 35 сигнал переполнения, но будут промоделированы все временные интервалы 2 для моделей ветвей на входном полюсе 38 которых присутствует сигнал разрешения, то процесс моделиро вания интервалов й будет включен сигналом с выхода элемента И 11. На выходе элемента И 11 появляется разрешающий сигнал в том случае, если на всеХ входах 76 имеются разрешаю .щие потенциалы, которые приходят от моделей ветвей, не принимавших участия в моделировании через элементы НЕ 37, И 32 и ИЛИ 35, либо от модели ветви, на входе 38 которой присутствует сигнал разрешения и она сформировала временной интервал 2, через элементы И 31, ИЛИ 35.При подаче импульсов ГИЗ на входы 52 всех моделей ветвей моделирование .временных значений С; осуществляют счетчики 14 лишь тех моделей ветвей, которые отсчитали свою величину ресурса 2; , не превысив ограничения К, т.е. трйггер 29 модели с единичного выхода выдает разрешение на вход элемента И 18, на остальных входах которого присутствуют разрешающие сигналы с входа 67, входа 38 и серии импульсов ГИЗ. При этом сигнал "Пуск", поданный в начальный Ы Ъзел, распространяясь по семи, задерживается в каждой модели на величину, пропорциональную времени выполнения моделируемой работы С .При появлении на выходе счетчика 14 импульса переполнения триггеры 15 и 16 устанавливаются в единичное состояние. Сигйал с нулевого выхода триггера 16 поступает на один из входов элемента И 19, на второй входкоторого поступает разрешение с входа 40 управления решением задачи о длиннейшем пути. Сигнал с выхода этого элемента поступает на вход схемы совпадения, которая образуется соединением элементов НЕ 23 полюсами 39 моделей ветвей, сходящихся в одной иэ вершин моделируемого сетевого графика.На полюсе 39 появляется разрешающий потенциал только тогда, когда все триггеры 16 моделей ветвей, входящих в одну вершину, устанавливаются в единичное состояние, что соответствует изменению фронта выполняемых работ и необходимо производить перераспределение ресурса. На основании сказанного следует, что если какой-либо счетчик 14 сформирует моделируемый интервал г; и при этюя вузле реализуется логическая операциявыделения максимальной из входящихвеличин ветвей (логическая функция"И"), то сигнал переполнения с выхо"да счетчика пройдет через выход 77,элемент ИЛИ 7 на вход элемента И 12.На втором входе И 12 имеется раэрешающий сигнал с выхода элемента НЕ13, так как фронт выполняемых работизменился и на выходе элемента И 11появляется запрещенный сигнал.т,е. триггер 29 у которых находится в единичном состоянии), В результате в указанных моделях ветвей 3 сигнал с выхода И 34 проходит че- рез элемент ИЛИ 36 на выход 41; и . устанавливает триггер 44 соответствующей ячейки управляемого распределителя в единичное состояние. Кроме того, с выхода 41 сигнал поступает через элемент ИЛИ 8 на вход 65 в блок 2. По этому сигналу устанав О ливается триггер 54 в единичное состояние, которое выдает разрешение на выход 69 и пропускает импульсы ГИ 2 через элементы И 62 на выход 51, В данном случае блок 2 организует мо делирование величин ресурса 2, уже начатых работ и отсчет этих значений в формирователе 5 временного интервала ограничения.В результате этого перед тем, как начнется выделение моделей ветвей с минимальным резервом времени, будут учтены величины ресурсов 2; моделей, принадлежащих фронту. Так процесс перераспределения ресурса сменяется процессом моделирования длительностей 1; (распространения сигнала "Пуск" по моделируемой сети) до тех пор, пока не будет сформирован конечный узел сетевого графика. При этом величина суммарного ресурса фронта на протяжении всего процесса решения не превышает заданного ограничения К. Количество импульсов ГИЗ, поступающих на выход 52 из блока 2 управления, определяют время выполнения всего проекта с ограничением К на используемый ресурс.В устройстве обеспечивается поступление необходимых сигналов уп равления и предварительного установа (не показаны) .Рассмотрим краткую постановку задачи оптимизации распределения нескладируемых ресурсов в сетевом графике.Пусть задан связанный ориентированный граф С(Х,П) без контуров, у которого имеются только одна начальная Хи одна конечная Хвершины. Граф ( соответствует комплексу взаимосвязанных работ, которые необходимо выполнить при реализации проекта. Узел (событие) сетевого графика фиксирует свершение всех работ, входящих в него, и начало всех работ, исходящих из этого узла. Ветвь сетевого графика соответствует отдельной работе (операции), время выполнениякоторой определяет длительность ф4рассматриваемой ветви.Если работа (13) начинается в монмент времени 1 и заканчивается ъ момент 1 . то требуемые для еепроведения ресурсы нескладируемого 63 типа можно записать как функцию времени в видегде о (й) функция единичного скачка;время начала иконца работы (1);2;интенсивность потребления ресурса, необходимогодля выполнения работы (11) . Причем весь сетевой график в каждый момент времени описывается суммарным потребляемым ресурсом для данного фронта работ(2)11 ЕС ( Сгде 2(Г 1 - интенсивность потребления ресурса в моментС для всего графика. Совокупность работ, которые по сетевому графику можно выполнять одновременно, называется фронтом работ Е (т.),Задача оптимизации сетевого графика при ограниченных ресурсах заключается в такой организации выполнения проекта, чтобы величина суммарного потребляемого ресурса для каждого фронта Е не превышала заданного ограничения К. Т.е. при реализации проекта, исходя из важности выполняемых работ (принадлежности критическому пути), и, не превышая заданного ограничения, без задержек включать в процесс выполнения одни работы и передвигать сроки начала других работ. (Задача определения критического пути и временного расчета сетевого графика может быть решена на предлагаемом устройстве).В предлагаемом устройстве для моделирования экстремальных путей на графе для определения длиннейшего пути в заданном графе строится модель сети. Длительность каждой ветви графа моделируется временным интервалом, а в каждом узле реализуется логическая операция выделения максимальной из входящих величин ветвей (логическая функция "И"). При этом модели ветвей соединяются между собой в соответствии с топологией сетевого графика. Для определения- длиннейшего пути подается сигнал "Пуск" в начальный узел модели, который, распространяясь по сети, задерживается в каждой модели ветви на величину, пропорциональную времени моделируемой работы. Временная задержка сигнала "Пуск" с момента его поступления в начальный узел до момента появления в конечном узлепропорциональна величине длиннейшего пути, а модели ветвей, которые оканчивались в каждом узле последними, определяют множество ветвей, принадлежащих дереву длиннейших путей.для решения задачи оптимизации сетевого графика может быть применен известный метод распределения величин ресурса по фронту.Сущность этого метода состоит в 10 том, что при распределении использу- ется простое правило, позволяющее соответствующим образом организовать процесс выполнения проекта, которое заключается в том, что в пер вую очередь выполняются операции с меньшим резервом времени. Здесь под резервом времени работы понимается максимальное увеличение продолжительности работы, не приводящее к увеличению длины критического пути.Использование приведенного правила для распределения ресурсов на, устройстве эквивалентно заданию некоторой функции предпочтения, которая 25 минимизирует функционал Мгде Е(й) - множество работ, принадлежащих фронту;лЬ 1 - резерв времени работыЖ)Е - величина ресурсов, необходимая для выполнения работы (ц) .Для того, чтобы вычислить резерв времени операции, необходимо вначале определить числоТ" = Т40 где Т . - время выполнения всегокомплек са;й, - позднее время начала работы (11) , которое не изменяет ход выполнения проекта.Тогда резерв работы ь, определяется по формуле50Л 7;= Е-Еили (1 ) Е Е (й) (5)где 1,= Т,1. = вах 1,(Ц)6 Г(С)Теперь легко получить распределение суммарного ресурса по фронту при заданном ограничении Й. Перераспределение ресурсных значений происходит каждый раз, когда оканчивается какая-либо операция. При этом в данный момент в работу включаются по порядку сначала те операции, которые имеют наименьшую величину резерва времени до тех пор, пока сум марное значение ресурса не превысит ограничения К, Зная распределение ресурса на данный момент времени, легко определить следующий момент перераспределения и включить в рабо-ту соответствующие операцииТаким образом, с момента начала выполнения проекта можно последовательно получить распределение ресурса по всем фронтам, значение которого не превышает допустимого ограничения.Приведенный метод позволяет организовать оптимизацию распределения нескладируемых ресурсов в сетевом графике на предлагаемом устройстве.По сравнению с известными устройствами предлагаемое исключает имеющиеся недостатки, а именно позволяет повысить точность решения задачи, автоматизировать процесс сбора и обработки информации, использовать результаты оптимизации сетевого гра. фика с ограниченными ресурсами в анализе СПУ.Формула изобретения1. Устройство для моделирования экстремальных путей на графе, содер. - жащее и моделей ветвей, соединенных согласно топологии графа, генератор импульсов, вход и выход которого соединены соответственно с управляющим выходом и управляющим входом блока управления, п распределителей, причем первый выход предыдушего распределителя соединен с первым входом последующего распределителя, а первый вход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу формирователя временного интервала и к первым входам моделей ветвей, вторые входы которых соединены с вторыми выходами соответствующих распределителей,овторые входы которых подключены к первым выходам соответствующих моделей ветвей, третьи и четвертые входы которых соединены с третьим и четвертым выходами блока управления соответственно, о т л и. ч а ю щ е е с я тем, что, с целью расширенйя функциональных возможностей за счет возможности решения задачи оптиМизации распределения нескладируемых ресурсов, в него введены элементы И, элементы ИЛИ и триггер, единичный выход которого подключен к первым входам первого и второго элементов ИЛИ, выход первого элемента ИЛИ соединен с первым входом блока управления и с пятыми входами моделей ветвей, вторые выходы которых подключены к соответствующим входам первого элемента И, выход которого соединен с вторым входом первого элемента ИЛИи через элемент НЕ с первым входом второго элемента И, выход которого подключен к второму входу блока управления, к шестым входам моделей ветвей и к нулевому входу триггера, нулевой выход которого соединен с седьмыми входами моделей ветвей, третьи выходы которых подключены к третьим входам соответствующих распределителей и к соответствующим входам третьего элемента ИЛИ, выход которого соединен с третьим входом блока управления, четвертый вход которого подключен к выходу второго элемента ИЛИ, второй вход которого соединен с первым выходом п-го распределителя, первый выход блока уп-, ранления подключен к второму входу формирователя временного интервала, выход которого соединен с единичным входом триггера, четвертые выходы моделей ветвей подключены к соответствующим входам четвертого элемента ИЛИ, выход которого подключен к второму входу второго элемента И.2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что каждая модель ветви содержит счетчик, два формирователя нременного интервала, четыре триггера, два элемента ИЛИ, десять элементов И и четыре элемента НЕ, первый и второй входы модели ветви подключены соответственно к первому и второму входам первого формирователя временного интервала, выход которого соединен с первым входом первого элемента И, выход которого подключен к единичному входу первого триггера, единичный выход которого соединен с первым выходом модели ветви, с первым входом второго элемента Й и с первым входом третьего элемента И, выход которого подключен к входу счетчика, выход которого соединен с четвертым выходом модели ветви, с нулевым входом первого триггера и с первым входом четвертого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с первым входом пятогоэлемента И и с единичным входом третьего триггера, нулевой выход которого подключен. к первому входу шестого элемента Й и к первому входуседьмого элемента И, выход которогочерез первый элемент НЕ сОедиНен свыходным полюсом модели ветви ичерез второй элемент НЕ с вторымивходами четвертого и пятого элементов И и с первым входом восьмого10 элемента И, выход которого соединенс нулевым входом нторого триггера,выход пятого элемента И через третийэлемент НЕ соединен с нходным полюсом модели ветви, с вторым входом15 третьего элемента И, с первым входомдевятого элемента И, с вторым входом шестого элемента И и через четвертый элемент НЕ с перным входомдесятого элемента И, выход шестогоэлемента И и третий вход модели ветви подключены соответственно к первому и второму входам второго формирователя временного интервала, выходкоторого соединен с первым входом25 первого элемента ИЛИ и с единичнымвходом четвертого триггера, единичныйи нулевой выходы которого подключенысоответственно к вторым входам девятого и десятого элементов И, выхоЗО ды которых соединены с входами второго элемента ИЛИ, выход которого подключен к второму выходу модели ветви,нулевой выход первого триггера соединен с третьим входом пятого элементаИ, пятый, седьмой и шестой входы модели ветви подключены соответственнок третьему входу третьего элементаИ, к второму входу первого элементаИ и к второму входу второго элементаИ, выход которого подключен к нторо"4 О му входу первого элемента ИЛИ, выходкоторого соединен с третьим выходом. модели ветви.Источники информации,принятые во внимание при экспертизе45 1. Авторское свидетельство СССР9 305484, кл.С 06 С 7/34, 1970.2. Авторское свидетельство СССРпо заявке Р 2842170/18-24,кл.С 06 С 7/122, 1979 (прототип).