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

 

(11), 44I567

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДБТВЛЬСТВУ (61} Зависимое от авт. свидетельства— (22) Заявлено 07.07. 7I i (21}I678863/IBB4 (51) М Кл.

9 0+ I5/20 с присоединением заявки—

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

Совета Мииистров СССР во делам изобретений и открытий (32) Приоритет— (5З) УдК 68I.333:

° ° °

6.0I2

088.8) Опубликовано30.08.74 Бюллетень N- 32

Дата опубликования описаниЖ. I2. 74 (72) Автор изобретения

А.А. Илюхин

Московский ордена ТрУдового Красного Знамени инженернофизический институт (71) Заявитель (54) МОДЕПЬ ДУГИ ЛЛЯ ОПТИМИЗАЦИИ СЕТЕВОГО

ГРАФИКА ПО ВРЕМЕНИ-СТОИМОСТИ

Изобретение относится к области вычислительной техники.

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

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

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

Однако такие модели дуги нв

10 ПОЗВОЛЯЮТ Решать задачи оптимизации сетевых графиков по врвменистоимости.

Предлагаемая модель дуги отличается от известных тем, что

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

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

20

Зо

З5

j0

55 фиксации разреза, и элемент "И", входы которого подключены к выходу схемы сравнения, импульсному входу модели дуги для оптимизации сетевого графика по времени-стоимости и выходу модели дуги для построения максимального потока и фиксации разреза, а выход элемента "И" соединен с вторым управляющим входом модели дуги для определения критического пути

На чертеже показана блок-схема модели дуги для оптимизации сетевого графика по времени-стоимосTM

Модель Дуги для опТМММ за Ции сетевого графика по времени-стоимости содержит модель I дуги для построения максимального потока и фиксации разреза, модель 2 дуги для определения критического пути, ключи 3 и 4, схему 5 сравнения, блок б задания мйнимального времейи, элемент 7 "И", ключ 8, генератор

9 случайных временных интервалов,, первый и второй полюсы IQ и П соответственно, вход I2 задания скорости изменения стоимости, вход

I3 задания времени выполнения работы, вход I4 задания минимального дапустимого времени выполнения работы I4, вход 75 запуска генЕратора и ймпульсный вход Тб.

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

Сначала необходимое количество моделей дуг для оптимизации сетевого графика по времени-стоимости соединяют полюсами IO и П согласно топологии исследуемого сетевого графика. Затем на входы I2

I3 и I4 подают последовательности импульсов, Если один из параметров дуги (скорость изменения стоимости или время выполнения работы} является случайной величиной, то значение его задается с помощью генератора 9 после установки ключа 8 в соответствующее положение и подачи на вход запуска генератора одиночного импульса. После задания параметров дуг модели дуги для оптимизации сетевого графика по времени-стоимости готовы к работе.

Один такт вычислительного процесса (получение одноИ точки на оптимальной кривои) состоит из следующих шагов. Ключ 3 находится в состоянии а и работает модель

2 дуги для определения критического пути, которая определяет на сетевом графике дерево критических путей. Затем проводится сравнение времей в модели дуги для определения критического пути и блока задания минимального времени. Если эти времена не равны, то на элемент И" 7 поступает разрешающии потенциал. Ключ 3 переключается в состояние б и уже работают модели дуг для построения максимального потока и фиксации разреза, причем тех, которые принадлежат дереву критических путей, определенных моделью дуги для определения критического пути, и которые строят максимальный поток и определяют и фиксируют дуги, принадлежащие разрезу. Если дайная дуга принадлежит разрезу, на выходе модели дуги для построения максимального потока и фиксации разреза появляется разреша ющиИ потенциал для элемент И" 7. Далее подается импульс на входы элементов "И" 7 всех моделей дуг по импульсному входу IG, и в моде-, лях дуг для определения критического пути время выполнения данной работы уменьшается на единицу во всех дугах, принадлежащих разрезу.

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

В том случае, когда на втором шаге время в модели 2 дуги для определения критического пути становится равным времени, записанному в блоке 6 задания мийимального времени, т.е. времени, раньше которого работа по тем йли иным причинам не может быть выполнена, на выходе схемы 5 сравнения появляется сигнал запрещающий работу элемента "И" 7 и устанавливающиИ в модели I дуги для построения максимального потока и фиксации разреза максимальный код, (что по алгоритму Форда-I àëêåðñoéà соо=ветствует С = со).

Процедура построения оптимального сетевого графика может продолжаться по заданному числу шагов до заданного времени Т директивно или до тех пор, пока все пути не окажутся критическими и времена

44I567

5 этих путей равными содержимому блока задания минимального времени.

ПРЕДМЕТ ИЗОБРЕТЕНИЯ

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

5 0

f5

25, 30

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

44I567

Составитель Г«СОРОКИН

РедактоД,РыбЯЯОЗВ 1 ехред Д, 3бЯРСКИЙ

3а каз ЗИУ изд. м(0 Т»раяг 62 1 II» 0lllc»0L

I Il !HI!i III I осу»а рствеи »ого коми гета Сове а Игг»»строя ССС!

»о делам из»брате»ий и открытий

Москва, 113035, Раушская »аб., 4

11рсд»риятие «Г!атент», Москва, Г-59, 13«режковская»аб., 24