МОДЕЛЬ СЕТЕВОГО ГРАФИКА Советский патент 1968 года по МПК G06G7/122 

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

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

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

Модель одного ребра сетевого графика состоит из регулируемой линии задержки 1, на которой с помощью переключателя 2 устанавливается величина физического параметра, например, время выполнения работы в сетевом графике, вентиля-формирователя 3, который при разомкнутом положении ключа 4 выполняет функции усилителя-формирователя, статического триггера 5 с индикационной лампочкой 6, дополнительной линии задержки 7 и диода 8.

Линия задержки 1 через переключатель 2 подключена к импульсному входу вентиля 3, выход которого соединен со входом дополнительной линии задержки 7 и катодом диода 8. Выход линии задержки 7 и анод диода подключены соответственно к нулевому и единичному входам триггера 5, нулевой выход которого связан с потенциальным входом вентиля 3 через ключ 4.

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

Разомкнутому положению ключа соответствует I режим: определение «критического» пути.

Положительный импульс, поданный на вход ребра P₁, появляется на выходе линии задержки (ЛЗ₁) 1 через время и, пройдя через формирователь 3, попадает на вход линии задержки (ЛЗ₂) 7. Одновременно он появляется в точке С (узел сети), т.е. на единичных входах триггеров 5 всех ребер, входящих в узел С, переводя триггеры 5 в состояние «1». Через время импульс появляется на выходе линии задержки 7 и переводит триггер 5 ребра P₁ в состояние «0». При этом триггеры 5 остальных ребер остаются в состоянии «1».

Если после этого импульс попадает в точку С из ребра Р_к, то триггер 5 ребра Р_к оказывается в состоянии «0», а триггеры 5 остальных ребер, в том числе и ребра Р₁ - в состоянии «1». Таким образом, лишь последний импульс, попавший в точку С, является определяющим, и ребро, по которому он пришел, фиксируется триггером 5, который находится в состоянии «0», в то время как триггеры 5 остальных ребер находятся в состоянии «1».

Сеть работает следующим образом.

На вход сети подается контрольный импульс, который распространяется по сети, и в каждом узле появляется столько импульсов, сколько различных путей ведет из начала сети в этот узел. После этого в каждом узле одно из входящих в него ребер оказывается в состоянии «0», а остальные - в состоянии «1». Ребра, находящиеся в состоянии «0», образуют дерево (на фиг. 2 оно выделено жирными линиями), которое зафиксировано триггерами 5. Та ветвь дерева, которая идет из начала в конец сети, представляет собой критический путь. Остальные ветви указывают пути наибольшей продолжительности до соответствующих узлов сети.

Замкнутое положение ключа 4 соответствует II режиму работы узла: определению кратчайшего пути.

В исходном состоянии триггеры 5 устанавливаются на «0»; таким образом, вентили 3 открыты по потенциальному входу. Положительный импульс, поданный на вход ребра Р₁, появляется на выходе линии задержки (ЛЗ₁) 1 через время и, пройдя через вентиль 3, попадает на вход линии задержки (ЛЗ₂) 7. Одновременно он появляется в точке С (узел сети), т.е. на единичных входах триггеров 5 всех ребер, входящих в узел С, переводя триггеры 5 в состояние «1». Через время импульс появляется на выходе линии задержки 7 и переводит триггер 5 ребра P₁ в состояние «0». Триггеры 5 остальных ребер, входящих в узел С, остаются в состоянии «1», перекрывая вентили 3 по потенциальным входам. После этого не может произойти никаких изменений в состояниях триггеров 5 ребер, входящих в узел С, так как ребро P₁ является единственным «открытым» ребром. Таким образом, первый импульс, пришедший в точку С, оставит триггер 5 того ребра, по которому он пришел, в состоянии «0», а триггеры 5 остальных ребер переведет в состояние «1».

Работа всей сети происходит следующим образом. На вход 9 сети (фиг. 2) подается контрольный импульс. Как и в I режиме, после переходного процесса в каждом узле одно из входящих в него ребер оказывается в состоянии «0», а остальные - в состоянии «1». Ребра, находящиеся в состоянии «0», образуют дерево, зафиксированное триггерами 5. Та из ветвей дерева, которая проходит из начала в конец сети, представляет собой кратчайший путь. Остальные ветви указывают пути наименьшей продолжительности до соответствующих узлов. Отметим, что в сетевом графике может быть два или несколько критических (или кратчайших) путей.

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

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