Устройство для моделирования сетевого графика

«»сео-,.

«втентио-;, библ,-,,.;, ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ нц 424!82

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

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

Республик (61) Зависимое от авт. свидетельства (22) Заявлено 25.07.72 (21) 1816285/18-24 (51) М. Кл. Ci 06@ 7/48 с присоединением заявки №

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

Совета Министров СССР ао делам изооретений и открытий (32) Приоритет

Опубликовано 15.04.74. Бюллетень № 14

Дата опубликования описания 24.09.74 (53) УДК 681.333(088.8) (72) Авторы изобретения

В. И. Волошин, Л. С. Горшкова и Р. Б. Хусид (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

СЕТЕВОГО ГРАФИКА

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

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

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

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

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

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

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

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

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

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

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

424182

65

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

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

10, заполняют счетчики 1 и 2.

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

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

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

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

В устройстве, кроме того, содержится блок управления 11, имеющий iV выходов 12, каждыи из которых соответствует номеру модели работ в сетевом графике, и выход 13, включающий режим определения вероятности заданного пути сетевого графика. Ьлок моделирования работ состоит из iV моделей работ 14, соединенных между собой в соответствии с топологией сети посредством наборного поля (на чертеже не показано). Задатчик вероятностей 15 предназначен для задания вероятности выполнения данной работы. Первая схема «И» 16 предназначена для выработки сигнала передачи информации с задатчика вероятностеи 15 для работ, лежащих на критическом пути, вторая схема «И» 17 — для выработки сигнала передачи информации с задатчика вероятностей 15 для работ, лежащих на любом заданном с блока управления ll пути. Общие входы 18 и 19 первой и второй схем

«И» 16 и 17 подключены к выходу 12 блока управления 11. Другой вход 20 схемы «И» 16 подключен к выходу схемы индикации 6, выделяющей работы, лежащей на критическом пути. Другой вход 21 схемы «И» 17 подключен к выходу 13 блока управления 11. Схема

«ИЛИ» 22 объединяет схемы «И» 16 и 17.

Влок умножения 23 предназначен для перемножения вероятностей заданного пути. Схема

4

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

Шины 25 предназначены для прохождения сигнала разрешения передачи информации с задатчика вероятностей 15 в блок умножения

23. Информационные шины 26 служат для передачи информации с задатчика вероятностей

15 в блок умножения 23. Управляющая шина

27, подключенная к управляющему входу 28 блока умножения 23, предназначена для подачи сигнала умножения.

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

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

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

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

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

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

Для определения вероятности реализации сети по любому заданному пути необходимо в блоке управления выделить работы заданного пути. Затем подается сигнал на выходе 13 блока управления 11, и начинается последовательный опрос номеров работ заданного пути по выходам 12 блока управления 11. При совпадении сигнала номера работы на выходе схемы «И» 17 и сигнала с выхода 13 блока управления 11 на входе 21 схемы «И» 17 на выходе схемы «ИЛИ» 22 появится сигнал, который разрешит выдачу значения Р; в блок умножения 23 и выдает команды по умножении вероятностей.

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

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

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

Составитель E. Тимохина

Техред Т. Курилко

Редактор Е. Семанова

Корректор Т. Хворова

Заказ 2454/13 Изд. № 1470 Тираж 624 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, )К-35, Раушская наб., д, 4, 5

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