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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (1)926670 (61) Дополнительное к авт. свид-ву— (22) Заявлено 07.01.80 (21) 2882868/18-24 (511М Кп з

С 06 С 7/122 с присоединением заявки Нов (23) Приоритет—

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

СССР по делам нзооретеннй.н открытий

Опубликовано 070582. Бюллетень Мо17 (53) УАК 681. ззз (088. 8) Дата опубликования описания 27.08.82 (72) Авторы изобретения

A.Ã.Äîäoíoâ, В.В.Хаджинов, В.М.Шишмаре

Институт электродинамики AH Украинской (71) Заявитель (541 устРОЙстВО ДлЯ мОДелиРОВАниЯ экстРемАльных

ПУТЕЙ НА ГРАФЕ

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство для расчета сетевых графиков, содержащее л моделей ветвей, соединенных согласно топологии графа, генератор импульсов, вход и выход которого соединены соответствен5 но с управляющим выходом и управляющнм входом блока управления, и распределителей, соединенных последовательно, причем первый выход предыдущего распределителя соединен с- Repвым входом последующего распределителя, а первый вход первого распределителя соединен с первым выходом блока управления, второй выход которого подключен к первому входу формирователя временного, интервала и к первым входам моделей ветвей, вторые входы которых соединены с вторыми выходами соответствующих раояределителей, вторые входы которых подключены к первым выходам соответствующих моделей ветвей, третьи и четвертые входы которйх соединены с тре тьим и четвертым входами блока управления соответственно; Кроме этого, в устройстве имеются еще ряд связей .25 между моделями ветвей, распределителями, формирователем временного интервала и блоком управления )2) .

Данное устройство не позволяет решать задачу оптимизации распределе30 ния нескладируемых ресурсов в сетевом

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

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

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

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

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

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

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

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

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

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

92266 70 подключен к второму входу первого элемента ИЛИ, выход которого соединен с третьим выходом модели ветви.

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

Устройство содержит (фиг. 1) генератор 1 импульсов, блок 2 управления, модели ветвей З -3, управляемые рас— предели тели 4 „— 4 и, формиров атель 5 временного интервала, триггер б, элементы ИЛИ 7-10, элементы И 11 и 12, элемент НЕ 13.

Каждая из моделей ветви 3Ä, число 15 которых равно числу моделируемых работ сетевого графика, содержит счетчик 14, триггера 15 и 16, элементы И 17-21, элементы HF. 22-24 и диод 25, формирователи 26 и 27 времен- 20 ных интервалов, триггера 28 и 29, элементы И 30-34, элементы ИЛИ 35 и 36 и элемент HE 37.

Модели ветвей соединяются между собой полюсами: входным .38i и выходным 39, в соответствии с топологией моделируемого графа, и в каждой модели вход 40 соединен с шиной управления решением задачи о длиннейшем пути.

Каждая модель ветви предназначена для моделирования одной работы исследуемого сетевого графика. Счетчик 14 служит для формирования временного интервала, пропорционального заданной длительности работы, формирователь 26 временного интервала предназначен для моделирования величины резерва .времени соответствующей работы, формирователь 27 — для моделирования интенсивности потребления ресур- 40 са той же операции. Каждый формирователь временного интервала выполняется на основе счетчико-регистровых структур.

Управляемые распределители 4;, чис-45 ло которых равно числу моделей ветвей сетевого графика, предназначены для органиэации последовательного опроса моделей ветвей, сформировавших минимальные значения резерва времени моделируемых работ. В состав каждого управляемого распределителя входят входы 41-.43, триггеры 44 и 45, элементы И 46-49.

Формирователь 5 временного интер- 55 вала, выполненный аналогичным образом, как формирователи 26 и 27 моделей ветвей, предназначен для моделирования заданного ограничения ресурса R по фронту выполняемых работ.

Блок 2 управления предназначен для осуществления первоначального запуска всего устройства, для организации взаимосвязанной работы блоков устройства и для выработки первой, второй и третьей серии тактовых им- 65 пульсов (ГИ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 производится предварительная запись числа импульсов, дополняющая заданную величину ограничения ресурса R до полной емкости счетчика.

Устройство работает следующим образом.

В счетчик 14 модели ветви предварительно заносится число импульсов, дополняющее длину ветви до полной емкости счетчика. Триггеры 15, 16, 28, 29 находятся первоначально в нулевом состоянии, и на полюсах 38 и 39 действует запрещенный потенциал. Затем в формирователи 26 и 27 временных интервалов заносится число импульсов, соответственно пропорциональное величине л ., определяющей резерв времени моделируемой работы, и величине используемого ресурса Z той же ра6оты. Например, в формирователь

26 модели ветви заносится число импульсов М = N — ь 7„, где N — полная емкость формирователя, а в формирователь 27 — число импульсов Ь = N — Z< .

После начального установа каждой модели ветви триггер б и триггеры 44 и 45 однотипных ячеек управляемого распределителя 4; устанавливаются в нулевое состояние, а в формирователь

5 временного интервала заносится число импульсов К = N — R, определяющее ограничение используемого ресурса по фронту выполняемых работ.

B некоторый момент времени по сигналу "Пуск" подается разрешающий сигнал в начальный узел моделируемой сети, кроме этого, сигнал "Пуск", поступающий на вход 64 блока 2 управления (фиг.2), проходит на вход генератора 1 импульсов и включает его. При этом импульсы с выхода генератора 1 проходят в блок 2 управления на входы элемента И 61 и элементов 56 и 57 задержки. Элементы

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

Сигнал "Пуск" с входа 64 также проходит через элемент ИЛИ 56 и 926670 устанавливает триггер 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„, последний начинает последовательно опрашивать модели ветвей, у которых сформированы минимальные значения резерва времени моделируемых работ.

Происходит это следующим образом.

Предварительно триггеры 44 и 45 устанавливаются в нулевое состояние.

При появлении сигнала на выходе 41„. через элемент И 46 устанавливается в единичное состояние триггер 44 распределителя 4; . Вследствие этого на нулевом его выходе, соединенном со входом элемента И 47, появляется запрещенный потенциал, а на единичном выходе — разрешающий потенциал.

С появлением на выходе 69< разрешающего сигнала из блока 2 управления, который через элемент И 48 устанавливает триггер 45 управляемого распределителя 4„ в единичное состояь ние (если триггер 44 этой ячейки наI ходился в еди ничном состоянии) . Тем самым снимается разрешающий потенциал со входа элемента И 46 и подает- „ ся разрешающий потенциал на элемент

И 49. Кроме того, сигнал с выхода элемента И 48 через выход 43 поступает на вход формирователя 27 временного интервала соответствующей модели ветви. При этом импульсы

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

Сигнал с выхода 69; первого распределителя 4; передается дт распределителя к распределителю, пропуская те распределители, на входах элементов И 46 которых нет разрешения из моделей ветвей 3. Так будут просматриваться все модели ветвей и моделироваться значения Z, для тех моделей, у которых величйна резерва времени работы Ь, является минимальной.

Когда будут сформированы все временные интервалы моделируемых ресурсов Z и суммарная их величина не

1) 5 превышает ограничения R, то импульс

-движения проходит через -все распределители и появится на выходе 75п последн его р аспредели теля 4 q. Э то т

5О сигнал проходит через элемент ИЛИ 10 на вход 66 блока 2 управления. Сигнал с входа 79 проходит через элемент ИЛИ 60, сбрасывает триггер 54 в нулевое состояние, запрещая серию импульсов ГИ2 на выходе 51 и разрешение на выходе 69. Кроме того, сигнал с входа 66 проходит через элемент ИЛИ 58 и устанавливает триггер

53 в единичное состояние, разрешая тем самым появление импульсов ГИ1 на О выходе 50. Это соответствует дальнейшему моделированию величин Ь,,>,т.е. определяются следующие модели ветвей с минимальным значением резерва времени из оставшихся моделируемых

65 работ на данный момент времени. его присутствует разрешающий сигнал с выхода 69 блока управления, а на второй поступают импульсы ГИ2.

15 После того, как сформирован моделируемый интервал, на выходе формирователя 27 модели ветви появляется импульсный сигнал, который, установив триггер 29 в единичное состоя2р ние (если триггер б ограничения находится в нулевом состоянии, полюс 74), выдает разрешение через выход 42 на второй вход элемента И 49 управляемого распределителя 41. Этот сигнал проходит через элемент И 49 и устанавливает триггер 44 в нулевое состояние. Нулевое состояние триггера 44 выдает разрешение на прохождение сигнала с управляющего входа 69 распределителя на ее выход 75 через элемент И 47.

926670

Сигнал с выхода элемента И 12 устанавливает триггер 6 вновь в нулевое состояние и поступает через вход

68 в блок 2. Сигнал с входа 68 сбрасывает триггер 55 в нулевое сост1 1яние и запрещает серию импульсов ГИЗ.

При этом сигнал с выхода счетчика 14 в модели ветви 3 устанавливает триггер 29 своей модели ветви в нулевое состояние. В результате модель ветви 3 отключается из пррцесса моделирования.

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

Для выполнения приведенного ус1 1 ловия сигнал с выхода элемента И 12 поступает на входы 68 всех моделей и проходит через элемент И 34 только

1 тех моделей, которые не окончили уже начатый моделируемый интервал t

Для моделей ветвей, сформировавших временной интервал минимального резерва времени, вновь моделируются величины ресурсов 2,; путем подачи импульсов ГИ2 на выход 51 и разрешающего сигнала на вход 69„ управляемого распределителя и формирователя 5 временного интервала. Как только

Формирователь 5 сформирует величину ограничения R, на выходе появляется единичный сигнал, который уста- 10 навливает триггер б в единичное состояние. Сигнал с выхода триггера 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 соответствует моделированию временных интервалов

t для тех моделей, которые вошли во фронт выполняемых работ.

Если формирователь. 5 временного интервала ограничения R не выдает 35 сигнал переполнения, но будут промоделированы все временные интервалы

Z,>, для моделей ветвей на входном полюсе "-81 которых присутствует сигнал разрешения, то процесс моделиро- 40 вания интервалов й;; будет включен сигналом с выхода элемента И 11. На выходе элемента H 11 появляется разрешающий сигнал в том случае, если на всех входах 76 имеются разрешаю- 45 .щие потенциалы, которые приходят от моделей ветвей, не принимавших участия в моделировании через элементы

НЕ 37, И 32 и ИЛИ 35, либо от модели ветви, на входе 38 которой присутствует сигнал разрешения и она сформировала временной интервал Z, через элементы И 31, ИЛИ 35.

При подаче импульсов ГИЗ на входы

52 всех моделей ветвей моделирование .временных значений 1; осуществляют счетчики 14 лишь тех моделей ветвей, которые отсчитали свою величину ресурса Z, не превысив ограничения

R, т.е. трйггер 29 модели с единичного выхода выдает разрешение на вход элемента И 18, на остальных вхо-. дах которого присутствуют разрешающие сигналы с входа 67, входа 38 и серии импульсов ГИЗ. При этом сигнал "Пуск", поданный в начальный Ы

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

При появлении на выходе счетчика

14 импульса переполнения триггеры 15 и 16 устанавливаются в единичное состояние. Сигйал с нулевого выхода триггера 16 поступает на один из входов элемента И 19, на второй .вход которого поступает разрешение с входа 40 управления решением задачи о длиннейшем пути. Сигнал с выхода этого элемента поступает на вход схемы совпадения, которая образуется соединением элементов НЕ 23 полюсами 39 моделей ветвей, сходящихся в одной иэ вершин моделируемого сетевого графика.

На полюсе 39 появляется разрешающий потенциал только тогда, когда все триггеры 16 моделей ветвей, входящих в одну вершину, устанавливаются в единичное состояние, что соответствует изменению фронта выполняемых работ и необходимо производить перераспределение ресурса. На основании сказанного следует, что если какой-либо счетчик 14 сформирует моделируемый интервал t и при это1я в . узле реализуется логическая операция выделения максимальной из входящих величин ветвей (логическая функция

"И"), то сигнал переполнения с выхода счетчика пройдет через выход 77, элемент HJIH 7 на вход элемента И 12.

На втором входе H 12 имеется раэрешающий сигнал с выхода элемента НЕ

13, так как фронт выполняемых работ изменился и на выходе элемента И 11 появляется запрещенный сигнал.

926670

12 (т,е. триггер 29 у которых находится в единичном состоянии). В результате в указанных моделях ветвей

3; сигнал с выхода И 34 проходит че- рез элемент ИЛИ 36 на выход 41; и . устанавливает триггер 44 соответствующей ячейки управляемого распределителя в единичное состояние. Кроме того, с выхода 41 сигнал поступает через элемент ИЛИ 8 на вход 65 в блок 2. По этому сигналу устанав- 10 ливается триггер 54 в единичное состояние, которое выдает разрешение на выход 69 и пропускает импульсы

ГИ2 через элементы И 62 на выход 51.

В данном случае блок 2 организует мо- 15 делирование величин ресурса Z уже начатых работ и отсчет этих значений в формирователе 5 временного интервала ограничения.

В результате этого перед тем, как начнется выделение моделей ветвей с минимальным резервом времени, будут учтены величины ресурсов 2; моделей, принадлежащих фронту. Так процесс перераспределения ресурса сменяется процессом моделирования длительностей 1; (распространения сигнала "Пуск" по моделируемой сети) до тех пор, пока не будет сформирован конечный узел сетевого графика.

При этом величина суммарного ресурса фронта на протяжении всего процесса решения не превышает заданного ограничения R. Количество импульсов

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

В устройстве обеспечивается поступление необходимых сигналов уп- 40 равления и предварительного установа (не показаны) .

Рассмотрим краткую постановку задачи оптимизации распределения нескладируемых ресурсов в сетевом гра- 45 фике.

Пусть задан связанный ориентированный граф G(Х,П) без контуров, у которого имеются только одна начальная Х и одна конечная Х „ вершины.

Граф С соответствует комплексу взаимосвязанных работ, которые необходимо выполнить при реализации проекта.

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

4 Р рассматриваемой ветви .

Если работа (i j ) начинается в мон мент времени 1 и заканчивается зц 1 момент t,, то требуемые для ее проведения ресурсы нескладируемого 43 типа можно записать как функцию времени в виде н

11 1

Z (t) =,б (2)

11СС С где 7 (t ) — интенсивность потребления ресурса в момент для всего графика.

Совокупность работ, которые по сетевому графику можно выполнять одновременно, называется фронтом работ

Е(t) .

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

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

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

его поступления в начальный узел до момента появления в конечном узле где о (t) функция единичного скачка; время начала и конца работы (ij);

2; ° 3 интенсивность потребления ресурса, необходимого для выполнения работы (i) )

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

926670

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

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

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

Использование приведенного правила для распределения ресурсов на, устройстве эквивалентно заданию некоторой функции предпочтения, которая 25 минимизирует функционал М

М =,C Е .ь""ñ .. И» Ч где F(t) — множество работ, принадлежащих фронту; л резерв времени работы (i j);

Z — величина ресурсов, необ43 ходимая для выполнения ра- 35 боты (ij) .

Для того, чтобы вычислить резерв времени операции, необходимо вначале определить число

Т; ° = Т (4) 4О

41 где Т . — время выполнения всего комплек ca, t".. — позднее время начала работы (ij) которое не изменяет ход выполнения проек та.

Тогда резерв работы ь, определяется по формуле

Й; = L-Е„или (ij)EF(t) (5) где L Т, L = maxL(ij)eF(t)

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

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

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

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

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

926670

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

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

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

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

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

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

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

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

И и к второму входу второго элемента

И, выход которого подключен к нторо4О му входу первого элемента ИЛИ, выход которого соединен с третьим выходом . модели ветви.

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

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

9 305484, кл.G G 7/34, 1970.

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

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

Редактор М.Ткач Техред Т.Маточка Корректор М.ДеМчик

Заказ 6805 Тираж 731 Подписное

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

1 13035, Москва, Ж-7Ь, Раушская наб., д.4/5

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