Патент ссср 333568

 

333568

О П И С А Й И Е

ИЗОБРЕТЕНИЯ

Сааре Советских

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

Республик

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

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

Заявлено 23.VI.1970 (№ 1451959/18-24) с присоединением заявки №

Приоритет

Опубликовано 21.III.1972. Бюллетень № 11

Дата опубликования описания 20ЛЧ.1972

М. Кл. G 06g 7/48

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

СССР

УДК 681,333:66.012(088.8) Автор изобретения

3. 3. Трайнин

Заявитель

УСТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО ПЛАНА

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

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

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

Все известные устройства обладают низкой разрешающей способностью:и требуют большого объема оборудования.

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

Это позволяет расширить класс решаемых задач.

На чертеже приведена функциональная схе-. ма устройства, где: 1 — модель сетевого графика, 2 — модель минимального разреза; 8—

10 блок управления; 4 — сравнивающее устрой. ство; 5 — суммирующи"; б — конденсатор; 7 — 14 — ключи; 15, 1б — регулируемые источники напряжения; 17 — ограничитель уровня напряжения; 18 — 21 — диоды;

15 22 —; 28 — трансформатор тока; 24, 25 —; 2б — 29 — схемы совпаденйя; 80 †- схема разделения; 81 — дифференцирующий усилитель; 82 — распредел итель импульсов. на (и+3) выхода, 88 — 8б со20 ответственно; й, (и+1), (и+2), (и+3) — выходы распределителя импульсов; 87 — генератор импульсов.

Модель 1 работы (ij ) сетевого графика выполнена в виде четырехвходового суммирую25 щего усилителя 5 с диодом 18 в цепи обратной связи. На первый:вход суммирующего усилителя 5 включен запоминающий конденсатор б. Второй вход через ключ 7 соединен с выходом усилителя-инвертора, моделирующе30 го событие т, из которого исходит рассматри333568

3 ваемая работа (ij). На третий вход суммирующего усилителя 5 включен регулируемый источник напряжения 15, напряжение которого устанавливается пропорциональным максимальной длительности работы (ij): (J). е„=1т, „.

На выходе суммирую щего усилителя 5 включен ограничитель 17 уровня напряжения, величина напряжения которого устанавливается пропорциональной минимальному времени выполнения работы (ц):

Модель 2 минимального разреза содержит отключаемые элементы, каждый из которых содержит источник тока 22, параллельно которому включены диод 20 и цепь, состоящая из последовательно соединенных диода 21 и трансформатора тока 28. Эти отключаемые элементы соединены .согласно топологии сетевого графика. Токи источника тока 22 устанавливаются прапорщ ональными затратам средств на сокраше@ие.на единицу времени соответствующей" работь : .

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

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

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

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

Устройство позволяет получить оптимальный план сетевого графика в случае, когда затраты средств С;; на сокращение на единицу времени каждой работы (Ц) являются величинами постоянными, т. е. 1 = COaSt.

dt

Длительность каждой работы 1ц лежит в пределах т1л 4 ц 4 Уаах °

На первом этапе происходит выявление критических ветвей в модели 1 сетевото графика. При этом триггер 25 находится в состоянии «О». Открыт ключ 18, и вход дифференцирующего усилителя 81 подключен к конечной точке сетевого графика К„.

На каждом такте генератора импульсов 87 сигналы с выходов распределителя импульсов

32 поступают на входы соответствующих элементов устройства. Так, на к-м такте с вы5

55 б0 б5 хода 88 распределителя импульсов сигнал поступает на первый вход схемы совпадения 26, на первичную обмотку трансформатора тока

28 и на четвертый вход суммирующего усилителя 5 модели работы (ij)

При поступлении импульса напряжения Ье на четвертый вход суммирующего усилителя

5 на его выходе напряжение возрастет также на величину Ье. Если рассматриваемая работа лежит на критическом пути, напряжение между начальной и конечной точками сетевого графика также возрастет на величину Ле.

При этом на выходе дифференцирующего усилителя 81 появится импульс, поступающий на вторые входы всех схем совпадения 26. Этот импульс пройдет через ту схему сов падения, на первый вход которой поступил сигнал с выхода распределителя импульсов 82. Соответствующий тритгер 24 установится в состояние «1» и замкнет ключ 11 в соогветствующей ветви модели 2 минимального разреза. Ключ

11 самоблокируется с помощью реле либо другим .способом.

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

На (и+2)-м такте сигнал с выхода 85 распределителя импульсов 32 поступает на счетный вход триггера 25, который перебрасывается в состояние «1». При этом ключ 13 запирается, а через открытый ключ 12 вход дифференцирующего усилителя 31 подсоединяется к конечной точке К, модели 2 минимального разреза.

На (n+3)-м такте сигнал с выхода 86 блока 82 проходит через схему совпадения 27 и сбрасывает триггер 24 в состояние «0».

На втором этапе работы устройства в модели минимального разреза среди выбранных на первом этапе ветвей выявляются экстремальные ветви, принадлежащие минимальному разрезу. Это достигается с помощью трансформатора тока 28, распределителя импульсов 82 и ди фференцирующего усилителя 31, выявляющих экстремальные каналы способом, ацисанным выше. Необходимо отметить, что в этом случае возмущающей величиной является не приращение напряжения Ле, а приращение тока — Л1, уменьшающее величину тока в ветвях на Л1. При этом, если рассматриваемая ветвь принадлежит минимальному разрезу, уменьшение тока в ней на .величину Л1 вызовет уменьшение суммарного тока через модель 2 минимального разреза на такую же величину. Это изменение выходной величины передается на вход дифференцирующего усилителя 31, на выходе которого появится импульс, сигнализирующий об экстремальности опрашиваемой ветви, Этот импульс

333568

5 0

25 через соответствующую схему совпадения 26 установит триггер 24 в состояние «1», Таким образом, на втором этапе устанавливаются в состояние «1» триггеры ветвей, принадлежащих минимальному разрезу. При этом будут замкнуты ключи 8 на первых входах суммирующих усилителей 5 в соответствующих моделях сетевого графика.

На (и+1)-м такте генератора импульсов 37 с выхода 84 распределителя импульсов 82 сигнал через схему совпадения 29 отпирает ключ 9, соединяющий выход сравнивающего устройства 4 с шиной, объединяющей ключи8.

Этот же сигнал отпирает ключ 18 через схему разделения 30, На первый вход сравнивающего устройства 4 включен регулируемый источник напряжения 16, моделирующий заданное время выполнения комплекса работ.

Второй вход сравнивающего устройства 4 соединен с конечной точкой К, модели 1 сетевого графика, направление которой пропорционально текущему минимальному времени выполнения комплекса работ (Т критическому). Разность этих двух напряжений через ключ 9 и ключи 8 поступает на первые входы соответствующих суммирующих усилителей 5 и заряжает конденсаторы 6, Поскольку это напряжение противофазно напряжениям регулируемых источников напряжения 15, напряжение на выходах соответствующих усилителей

5 понижается. Это соответствует сокращению длительностей выбранных критических работ, При этом уменьшается напряжение конечной точки К, модели 1 сетевого графика, а поскольку через схему разделения 80 открывается ключ 18, дифференцирующий усилитель 31 преобразует изменение этого напряжения в управляющий сигнал, который запирает ключ 14 на выходе генератора импульсов 87.

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

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

Контроль за сокращением операций до величины не ниже Т осуществляется с помощью ограничителей 17 уровня напряжения.

На (n+2)-м такте триггер 25 вновь установится в состояние «0», а ключи 9 и 12 закроются.

На (а+3)-м такте импульс через схему совпадения 28 запрет ключи 7, соединяющие вто30

60 рые входы суммирующих усилителей 5 с событиями, из которых исходят рассматриваемые работы. При этом обнаруживаются работы, сокращенные до величины Tm,„. Любой суммирующий усилитель 5, у которого разность напряжений на конденсаторе б и регулируемом источнике напряжения 15 окажется больше напряжения ограничителя 17 уровня напряжений, выйдет пз линейного режима, так как при этом запирается диод 18 в цепи обратной связи. Сигналы с выходов таких суммирующих усилителей запрут ключи 10.

Эти ключи самоблокируются и шунтируют соответствующие ветви модели 2 минимального разреза. Таким образом, работы, длительность которых сократилась до Т„„„, исключаются из дальнейшего рассмотрения.

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

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

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

333568

Составитель Г. Сорокин

Техред 3. Гараненко Корректор Е. Михеева

Редактор Б. Нанкина

Заказ 1001/6 Изд. № 399 Тираж 448 Подписное

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

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

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