Модель дуги для оптимизации сетевого графика по времени стоимости

(11), 441567ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(61) Зависимое от авт. свидетельства -1 с (212678863/1 ено 07.07соединениеритет -22) 3 М Кл.9 06 15/2 эая асударственный комитетСовета Министров СССРво делам изобретенийи открытий(72) А зобретения рдена ТрУдового Красного Знаменинс титут сковскизическ ерно 1) Заявит(54) МОДЕ)Ь ДУГИ ДЛЯ ОПТИМИЗАЦИИ СЕТЕВО ГРАФИКА ПО ВРЕугЕНИ-СТОИМОСТИ Изобретение относится к области вычислительной техники.Известны модели дуги для оптимизации сетевого гра ика по времени-стоимости, содержащие модель дуги для построения максимального потока и фиксации разреза и модель дуги для определения критического пути, первые и вторые полюсы которых через одноименные го ключи соединены соответственно с первым и вторым полюсом модели дуги для оптимизации сетевого графика по времени-стоимости. Вход запуска генератора модели 15 дуги через последовательно включенные генератор случайных временных интервалов и соответствующий ключ соединен с первыми управляющими входами модели дуги ао для построения максимального потока и фиксации разреза и модели дуги для определения критического пути, которые подключены соответственно к входу задания скорости изменения стоимости и входу задания времени выполнения работы модели дуги для оптимизации сетевого графика по времени-стоимости. Второй управляющий вход модели дги для построения максимального потока и фиксации разреза подключен к первому выходу модели дуги для определения критического пути.Однако такие модели дуги нв позволяют решать задачи оптимизации сетевых графиков по врвменистоимости.Предлагаемая модель дуги отличается от известных тем, что она содержит блок задания минимального времени, подключенный к входу задания мийимального допустимого времени выполнения работы, схему сравнения, входы которой подключены к выходу блока задания минимального времени и второму выходу модели дуги для определения критического пути, а выход схемы сравнения соединей с третьим управляющим входом модели дуги для построения максимального потока и10 20 25 Зо З 5 10 45 50 55 фиксации разреза, и элемент "Ифф,входы которого подключены к выходусхемы сравнения, импульсному входумодели дуги для оптимизации сетевого графика по времени-стоимостии выходу модели дуги для построения максимального потока и фиксацииразреза, а выход элемента "фф соединен с вторым управляющим входоммодели дуги для определения критического путиНа чертеже показана блок-схема модели дуги для оптимизации сетевого графика по времени-стоимосМодель дуги для оптимизации сетевого графика по времени-стоимости содержит модель 1 дуги для построения максимального потокаи фиксации разреза, модель 2 дуги для определения критического пути, ключи 5 и Ю, схему 5 сравнения, блок 6 задания мйнимального времейи, элемент 7 "И", ключ 8, генератор 9 случайных временных интервалов первый и второй полюсы 10 и 11 соответственно, вход 12 задания скорости изменения стоимости, вход 15 задания времени выполнения работы, вход 1 Ф задания минимального допустимого времени выполнения работы 14, вход 15 запуска генератора и ймпульсный вход 16.Модель дуги для оптимизации сетевого графика по времени-стоимости работает следующим образом.Сначала необходимое количество моделей дуг для оптимизации сетевого графика по вре лени-стоимости соединяют полюсами 10 и 11 согласно топологии исследуемого сетевого графика. Затем на входы 12, 15 и 14 подают последовательности импульсов, Если один из параметров дуги (скорость изменения стоимости или время выполнения работы) является случайной величиной, то значение его задается с помощью генератора 9 после установки ключа 8 в соответствующее положение и подачи на вход запуска генератора одиночного импульса, После задания параметров дуг модели дуги для оптимизации сетевого графика по времени-стоимости готовы к работе.Один такт вычислительного процесса (получение одноИ точки на оптимальной кривои) состоит из следующих шагов, Ключ 5 находится в состоянии а и работает модель 2 дуги для определения критического пути, которая определяет на сетевом графике дерево критическихпутей. Затем проводится сравнениевремей в модели дуги для определения критического пути и блоказадания минимального времени. Если эти времена не равны, то наэлемент И" 7 поступает разрешающии потенциал. Ключ 5 переключается в состояние б и уже работаютмодели дуг для построения максимального потока и фиксации разреза, причем тех, которые принадлежат дереву критических путеИ,определенных моделью дуги для определения критического пути, и которые строят максимальный поток иопределяют и фиксируют дуги, принадлежащие разрезу. Если дайнаядуга принадлежит разрезу, на выходе модели дуги для построениямаксимального потока и фиксацииразреза появляется разрешающиИпотенциал для элемент И" 7. Далее подается импульс на входыэлементов фИ" 7 всех моделей дугпо импульсному входу 16, и в моде-,лях дуг для определения критического пути время выполнения даннойработы уменьшается на единицу вовсех дугах, принадлежащих разрезу.Таким образом, максимальноевремя выполнения разработки уменьшается на единицу, т.е, уменьшение времени выполйенйя работы происходит на тех разрезах сетевогографика, лежащих на критическихпутях, йа которых возрастаниестоимости минимально. На этомпервый такт оптимизации закончен,и далее процесс повторяется.В том случае, когда на второмшаге время в модели 2 дуги для определения критического пути становится равныл времени, записанномув блоке 6 задания мийимальноговремени, т.е. времени, раньше которого работа по тем йли инымпричинам не может быть выполнена,на выходе схемы 5 сравнения появляется сигнал запрещающий работуэлемента "И" 7 и устанавливающиИв модели 1 дуги для построениямаксимального потока и фиксацииразреза максимальный код, (что поалгоритму Форда-Фалкерсойа соответствует С = со),Процедура построения оптимального сетевого графика может продолжаться по заданному числу шаговдо заданного времени Т директивноили до тех пор, пока все пути неокажутся критическими и времена4415675этих путей равными содержимомублока задания минимального времени. ПРЕДМЕТ ИЗОБРЕТЕНИЯМодель дуги для оптимизации сетевого графика по времени-стоимости, содержащая модель дуги для построения максимального потока и фиксации разреза и модель дуги для определения критического пути, первые и вторые полюсы которых через одноименные ключи соединены соответственно с первым и вторым полюсом модели дуги для оптимизации сетевого графика по времени- стоимости, вход запуска генератора которой через последовательно включенные генератор случайных временных интервалов и соответствующий ключ соединен с первыми управляющими входами модели дуги для построения максимального потока и фиксации разреза и модели дуги для определения критического пути, которые подключены соответствейно к входу задания скорости изменения стоимости и входу задания времени выполнения работы модели дуги для оптимизации сетевого 5 0 35 20 25, 30 6гра ри ка по времени-стоимости, второй управляющий вход модели дуги для построения максимального потока и фиксации разреза подключен к первому выходу модели дуги для определения критического пути, о т л и ч а ю щ а я с я тем, что, с целью расширения класса решаемых задач, она содержит блок задания минимального времени, подключенный к входу задания мийимального допустимого времени выполнения работы, схему сравнения, входы которой подключены к выходу блока задания минимального времени и второму выходу модели дуги для определения критического пути, а выход схемы сравнения соединей с третьим управляющим входом модели дуги для построения максимального потока и фиксации разреза, и элемент И, входы которого йодключвны к вйходу схемы сравнения, импульсному входу модели дуги для оптимизации сетевого графика по времени-стоимостии выходу модели дуги для построения максимального потока и фиксации разреза, а выход элемента ф 1 И 1 соединен с вторым управляющим входом модели дуги для определения критического пути.441567 Составитель ГеСОРОКИНредТ.РНбаЛОВВ екредА.ЗбарСКИй 1 п гппспо атеит, Москва, Г 59, 1 йсрежковская паб 1 рсдприятие 6 У изд, м(011 И 111111 1 ос у да рствеи ногопо делам изМосква, 1130 Тпраяг 629 комигета Совеа Иггппстров бретепий и открытий5, аушская наб., 4