Модель дуги для оптимизации сетевого графика по времени-стоимости Советский патент 1974 года по МПК G06F15/173 

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

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

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

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

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

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

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

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

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

Модель дуги для оптимизации сетевого графика по времени-стои, мости содержит модель I дуги для построения максимального потока и фиксации разреза, модель 2 дуги для определения критического пути, ключи 3 и 4, схему 5 сравнения, блок б задания минимального времени, . злемент 7 И, ключ 8, генератор . 9 случайных временных интервалов, первый и второй полюсы 10 и II соответственно, вход 12 задания скорости изменения стоимости, вход 13 задания времени выполнения работы, вход l4 задания минимального Д1апустимого времени выполнения работы 14, вход 15 запуска генератора и импульсный вход 16. .

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

Сначала необходимое количество моделей дуг для оптимизации сетевого графика по времени-стоимости соединяют полюсами 10 и II согласно топологии исследуемого сетевого графика. Затем на входы 12, 13 и l4 подают последовательности импульсов. Если один из параметров дуги (скорость изменения стоимости или время выполнения работы) является случайной величиной, то значение его задается с помощью генератора 9 после установки ключа 8 в соответствующее положение и подачи на вход запуска генератора одиночного импульса. После задания параметров дуг модели дуги для оптимизации сетевого графика по времени-стоимости готовы к работе.

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

Таким образом, максимальное

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

и далее процесс повторяется.

В том случае, когда на втором шаге время в модели 2 дуги для определения критического пути становится равным времени, записанному в блоке б задания минимального времени, т.е. времени, раньше которого работа по тем или иным причинам не может быть выполнена, на выходе схемы 5 сравнения появляется сигнал, запрещающий работу элемента М 7 и устанавливающий в модели I дуги для построения максимального потока и фиксации разреза максимальный код, (что по алгоритму Форда-Фалкерсона соответствует С оо).

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

ЭТИХ путей равными содержимому блока задания минимального времени.

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

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

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