Устройство для определения экстремальныхпутей

Вс, пи т» н нс, те (°

О Il&" Е А -Н И Е

ИЗОБРЕТЕН ИЯ

268035

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства №

Заявлено 28,VII I.1968 (№ 1265525/18-24) с присоединением заявки ¹

Кл. 42m, 7 48

Комитет по делам изобретеиий и открытий при Совете Министров

СССР

МПК G 06д 7/48

УДК 681.33.001.57 (088.8) Приоритет

Опубликовано 02.1V.1970. Бюллетень ¹ 13

Дата опубликования описания 1,Х.1970

Автор изобретения

И, С. Гурвич

Специальное конструкторское бюро вычислительных машин

Заявитель

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЬ1Х

ПУТЕЙ

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

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

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

Это учрощает устройство.

Устройство позволяет определять экстремальные пути(кратчайший или критический)

10 и расстояние между любой вершиной сетевого графика и начальной или конечной вершинами.

На фиг. 1 дано изображение работ и событий в сетевом графике; на фиг. 2 — схема мо15 дели работы; на фиг. 3 — схема модели события.

Стрелки 1 сетевого графика (см. фиг. 1), указывающие направленность:работы, соответствуют определенной работе, а вершины 2

20 H 3 — cOobtTHHM.

Каждая работа ij характеризуется длительностью t, (где т и j-события, между которыми находится работа 11).

Вершины, подобно вершине 2 выполняющие

25 функцию разветвления, назовем P-вершинами, а вершины, подобно вершине 3 выполняющие функцию сборки, С-вершинами.

Модель работы (см фиг. 2) состоит из постоянного или переменного резистора 4, вели80 чина сопротивления которого R» устанавли268035

3 вается пропорциональной длительности работы ц, и двух последовательно соедине 1ных диодов 5, задающих направленность работы в соответствии со стрелкой 1 в сетевом плане. Один конец резистора соединен с «o.tцом цепочки диодов. Это соединение является входом схемы, а другой конец резистора вместе с концом цепочки диодов присоединен к переключающим контактам б таким образом, что задействованным оказывается или резистор или диоды. Между общей точкой соединения диодов и общей шиной 7 включен газоразрядный индикатор 8. Общий контакт переключателя является выходом схемы.

В схеме модели события (см. фиг. 3) от общей точки 9 отходит ответвление 10 и два ответвления 11 через нормально разомкнутые контакты переключателей 12.

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

18, подключенных к общей шине 7. Кроме того, размыкающие контакты через контакты двух направлений кнопки 14 могут подключаться к шинам сравнения 15. Контакты т ретьего направления кнопки 14 замыкают шину питания 15 и шину 17 реле.

Устройство работает следующим образом.

Предварительно набирается модель, состоящая из моделей работ (по фиг. 2) и моделей событий (по фиг. 3) в топологическом соответствии с моделируемым сетевым графиком.

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

При этом, когда модель события имитирует

P-вершину, ответвление 10 используется как входное, а ответвления 11 — как выходные, и когда модель события имитирует С-вершину, ответвления 11 используются как входные, а ответвление 10 — как выходное.

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

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

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

Эта операция выполняется следующим образом. От источчика питания, напряжение которого выше напряжения загорания газоразрядных индикаторов (неоновых лампочек), «плюс» подключается к начальной вершине модели, а «минус» — к общей шине 7. Тогда положительчое напряжение беспрепятственно проходит на входы схемь совпадения С-вершины, пути кото рой от начала модели не проходят по другим С-вершинам. Обе лампочки

12 (на фиг. 3) такой С-вершины загораются, сигнализируя о ее местонахождении. В схеме найденной С-вершины нажимают на кнопку

l4. При этом замыкаются шина питания 16 и шина 17 реле; при этом на реле (или группу реле) 18 подается напряжение от источника питания 19. Реле срабатывает и переключает свои контакты б во всех схемах работ»одели и, кроме того, отключает «плюс» источника питания от начала модели. Кнопка 14. подключает входы найденной С-вершины к шинам сравнения 15, к котсрым следует подключить какую-либо схему сравнения 20 (например половину моста Уитстона). Общий вход 21 схемы сравнения следует подключить к начальной вершине модели. В зависимости от показаний схемы сравнения и того, какой путь (критический или наикратчайший) отыскивается, переключается верхний или нижний переключатель 12. Кнопка 14 отпускается.

Затем операция повторяется для каждой

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

Для того, чтобы горели индикаторы 8 тех работ, которые лежат на экстремальном пути из начала модели до любой вершины, необходимо в преобразованной модели подсоединить «плюс» источника питания к общей шине, а «минус» — к этой вершине.

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

Аналогично определяют расстояние от любой вершины графика до конечной вершины.

При этом роль С-вершины выполняют P-аершины, «плюс» источника питания подключается к общей шине 7, «минус» — к концу модели, общий вход 21 схемы сравнения — к концу модели, а для зажигания лампочек работ, которые лежат на оптимальном пути, из любой .вершины до конца модели в преобразованной модели подключают «плюс» источника питания к этой вершине, а «минус» — к общей шине.

268035 Риг >

«Риг Z, 21

Г - 20 С

7

I I

Л >19! !

Г--- I

> 18 Г

L ч иг 3

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

Редактор Л. А. Утехина Техред А. А. Камышникова Корректор С. А. Кузовенкова

Заказ 2668/1 Тираж 480 Подгиб>оное

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

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

Типография, пр. Сапунова, 2

Для измерения сопротивления из любой верпииы до конца модели подключают измериель сопротивлений между этой вершиной и

:онцом.

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

>1. Устройство для определения экстремаль1ых,путей при сетевом планировании, содеркащее модели работ, выполненные в виде по.ледовательно соединенных резистора, вели(ина которого пропорциональна длительности

>аботы, и нормально разомкнутого контакта

>еле, а также модели событий, соединенные

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

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