УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВОГО ГРАФИКА Советский патент 1974 года по МПК G06G7/48 

1

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

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

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

Известное устройство не позволяет определить вероятность реалиазции сети за время критического или любого другого пути.

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

Иа чертеже представлена блок-схема предлагаемого устройства.

Оно содержит основной счетчнк 1 импульсов, дополнительный счетчнк 2 нмпульсов, триггер 3 формирования временного интервала, схему «И 4, схему выделения 5 н схему индикацнн 6.

Счетчики 1 н 2 совместно с триггером 3 и схемой «И 4 образуют узел формирования

временного интервала, пропорционального нродолжительности выполнения работ.

Модели работ соединяются между собой полюсами 7 и 8 в соответствии с топологией рассчитываемого сетевого графика.

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

Импульсный сигнал, имитирующий начало работ сетевого графика,поданный па полюсы 7 блока моделирования работ, исходящих из начала графика, устанавливает триггеры 3 этих работ в единичное состояние. При этом открываются схемы «И 4, и импульсы тактового генератора, подключенного к полюсам 10, заполняют счетчики 1 и 2.

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

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

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

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

В устройстве, кроме того, содержится блок управления 11, имеющий N выходов 12, каждый из которых соответствует номеру модели работ в сетевом графике, и выход 13, включающий режим определения вероятности заданного пути сетевого графика. Блок моделирования работ состоит из N моделей работ 14, соединенных между собой в соответствии с топологией сети посредством наборного поля (на чертеже не показано). Задатчик вероятностей 15 предназпачеп для задапия вероятности выполнения данной работы. Первая схема «П 16 предназначена для выработки сигнала передачи информации с задатчика вероятностей 15 для работ, лежащих на критическом пути, вторая схема «П 17 - для выработки сигнала передачи информации с задатчика вероятиостей 15 для работ, лежащих на любом заданном с блока управления 11 пути. Общие входы 18 и 19 первой и второй схем «И 16 и 17 подключепы к выходу 12 блока управления 11. Другой вход 20 схемы «И 16 подключен к выходу схемы индикации 6, выделяющей работы, лежащей на критическом пути. Другой вход 21 схемы «П 17 подключен к выходу 13 блока управления 11. Схема «ИЛП 22 объединяет схемы «И 16 и 17. Блок умножения 23 предназначен для перемножения вероятностей заданного пути. Схема

«ИЛП 24 объединяет схемы «ПЛП 22 всех моделей работ 14.

Шины 25 предназначены для прохождения сигнала разрещения передачи информации с задатчика вероятностей 15 в блок умножения 23. Информационные шины 26 служат для передачи информации с задатчика вероятностей 15 в блок умножения 23. Управляющая щина 27, нодключенная к уиравляющему входу 28

блока умножения 23, предназначена для подачи сигнала умножения.

Задатчики вероятностей 15 устанавливаются по щипам 29 (щинам задания вероятности выполнения данной работы) в состояния, соответствующие вероятности (Pi) реализации данной работы.

Вероятность реализации любого пути сети равна произведению вероятностей реализации каждой из работ этого пути.

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

Затем начинается последовательный опрос номеров работ по выходам 12 блока управления 11. При совпадении сигнала номера работы па входе 18 схемы «И 16 и сигнала со схемы индикации о принадлежности данной работы критическому пути па входе 20 схемы «И 16 на выходе схемы «ИЛИ 22 появится

сигнал, который: через шину 25 поступит в задатчик вероятностей 15 и разрещит выдачу значения Pi в блок умножения 23; поступит на схему «ИЛИ 24, с выхода которой по управляющей щиие 27 поступит на вход 28 блока умножения 23 (этот сигнал является командой на умножение в блоке умножения).

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

Для определения вероятности реализации сети по любому заданному пути необходимо в блоке управления выделить работы заданпого пути. Затем подается сигнал на выходе 13

блока управлепия И, и начипается последовательпый опрос номеров работ заданного пути по выходам 12 блока управления 11. При совнадении сигнала номера работы на выходе схемы «И 17 и сигнала с выхода 13 блока

управления И па входе 21 схемы «И 17 на выходе схемы «ИЛИ 22 появится сигнал, который разрешит выдачу значения Pi в блок умножения 23 и выдает команды по умножении вероятностей.

Таким образом, после опроса всех работ в блоке умножения 23 сформируется произведепие вероятностей реализации работ заданного пути.

Предмет изобретения

Устройство для моделирования сетевого графика, содержащее блок управления, подключенный к блокам моделирования работ, 65 соединенным в соответствии с топологией сети,

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

Г