333568

333568 О П И С А Й И Е ИЗОБРЕТЕНИЯ Саве Саеетских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ т, свидетельстваависимое о Кл. 70 ( 1451959/18-2 аявлено с присоединением заявкиКомитет по делам обретений и атнрцти.11.1972. Бюллетень1 и Сосете й 1 инистро ата опубликования описания в Трайнин зооретеш аявител ТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО ПЛАНА СЕТЕВОГО ГРАФИКАИзобретение относится к области вычислительной техники,Известны устройства для построения оптимального плана сетевого графика, содержащие соединенные между собой модель сетевого графика на основе суммирующего усилителя с диодом в цепи обратной связи и конденсатором на одном из входов, модель минимального разреза на отключаемых элементах,выполненных в виде параллельно соединенных 10источников тока, диодов и трансформаторагока, триггеры, управляемые ключи, схемысовпадения и регулируемые источники напряжения.Все известные устройства обладают низкой 15разрешающей способностью:и требуют большого объема оборудования.Предлагаемое устройство отличается от известных тем, что оно содержит сравнивающееустройство, дифференцирующий усилитель и 20распределитель импульсов, причем выходымоделей сетевого графика и минимальногоразреза через соответствующие управляемыеключи соединены с дифференцпрующим усилителем, выход которого через управляемый 25ключ присоединен ко входу распределителяимпульсов, первичной обмоткой трансформатора тока, вторым входом суммирующего усилителя и счетным входом триггера; выходсравнивающего устройства через управляемый 30 ключ соедттнен с первым входом суммирующего усилителя, а его входы подключены к вы. ходу модели сетевого графика и выходу регулируемого источника напряжения,Это позволяет расширить класс решаемых задач.На чертеже приведена функциональная схема устройства, где: 1 - модель сетевого графика, 2 - модель минимального разреза; 3 - блок управления; 4 - сравнивающее устрой ство; 5 - суммирующий усилитель; б - конденсатор; 7 - 14 - ключи; 15, 1 б - регулируемые источники напряжения; 17 - ограничитель уровня напряжения; 18 - 21 - диоды;22 - источник тока; 28 - трансформатор тока; 24, 25 - триггеры; 2 б - 29 - схемы совпаденйя; Ю всхема разделения; 31 - диф. ференцирующий усилитель; 82 - распредел и- тель импульсов.на (и+3) выхода, 38 - Зб соответственно; й, (и+1), (и+2), (и+3) - выходы распределителя импульсов; 87 - генера. тор импульсов,Модель 1 работы (гу) сетевого графика выполнена в виде четырехвходового суммирующего усилителя 5 с диодом 18 в цепи обратной связи. На первый .вход суммирующего усилителя 5 включен запоминающий конденсатор б. Второй вход через ключ 7 соединен с выходом усилителя-инвертора, моделирующего событие г, из которого исходит рассмагри3ваемая работа (ц). На третий вход суммирующего усилителя 5 включен регулируемый источник напряжения 15, напряжение которого устанавливается пропорциональным максимальной длительности работы (Ц):И),е=Й Т;На выходе суммирующего усилителя 5 включен ограничитель 17 уровня напряжения, величина напряжения которого устанавливается пропорциональной минимальному времени выполнения работы (ц):Модель 2 минимального разреза содержит отключаемые элементы, каждый из которых содержит источник тока 22, параллельно которому включены диод 20 и цепь, состоящая из последовательно соединенных диода 21 и трансформатора тока 23. Эти отключаемые элементы соединены согласно топологии сетевого графика. Токи источника тока 22 устанавливаются прапорщональными затратам средств на сокрашеие. на единицу времени соогветствуюЩей"ряботьУстройство работает следующим образом.С помощью блока управления 3 в модели 1 сетевого графика выявляются критические операции, т, е. работы, лежащие на критическом пути (или путях).В модели 2 минимального разреза замыкаются ключи на выходах тех ветвей, которым соответствуют критических операции в сетевом графике.При этом создается возможность для протекания тока и выявления среди выбранных ветвей подмножества, принадлежащего минимальному разрезу. Затем с помощью сравнивающего устройства 4 происходит сокращение длительностей тех критических работ сетевого графика, которым соответствуют ветви в блоке 2, принадлежащие. минимальному разрезу.Устройство позволяет получить оптимальный план сетевого графика в случае, когда затраты средств С на сокращение на единицу времени каждой работы (Ц) являются величинами постоянными, т. е.1 =СОПЗ 1.Длительность каждой работы 1 ц лежит в пределахТтул ( ц (ТйцйНа перовом этапе происходит выявление критических ветвей в модели 1 сетевото графика, При этом триггер 25 находится в состоянии О. Открыт ключ 13, и вход дифференцирующего усилителя 31 подключен к конечной точке сетевого графика К.На каждом такте генератора импульсов 37 сигналы с выходов распределителя импульсов 32 поступают на входы соответствующих элементов устройства. Так, на к-м такте с вы 5 10 15 20 25 30 35 40 45 50 55 60 б 5 хода 33 распределителя импульсов сигнал поступает на первый вход схемы совпадения 2 б, на первичную обмотку трансформатора тока 23 и на четвертый вход суммирующего усилителя 5 модели работы (ц).При поступлении импульса напряжения Ье на четвертый вход суммирующего усилителя 5 на его выходе напряжение возрастет также на величину Ье. Если рассматриваемая работа лежит на критическом пути, напряжение между начальной и конечной точками сетевого графика также возрастет на величину Ле. При этом на выходе дифференцирующего усилителя 31 появится импульс, поступающий на вторые входы всех схем совпадения 2 б, Этот импульс пройдет через ту схему совпадения, на первый вход которой поступил сигнал с выхода распределителя импульсов 32. Соответствующий тритгер 24 установится в состояние 1 и замкнет ключ 11 в соогветствующей ветви модели 2 минимального разреза, Ключ 11 самоблокируется с помощью реле либо другим способом.Таким образом, на первом этапе будут выявлены критические операции сетевого графика и соответствующие им ветви в модели 2 минимального разреза. Эти ветви образуют цепь для протекания тока от начальной точки Н, к конечной К, модели 2, что позволяет, моделируя задачу о максимальном потоке, обнаружить среди этих ветвей подмножество, принадлежащее минимальному разрезу.На (и+2)-м такте сигнал с выхода 35 распределителя импульсов 32 поступает на счетный вход тритгера 25, который перебрасывается в состояние 1. При этом ключ 13 запирается, а через открытый ключ 12 вход дифференцирующего усилителя 31 подсоединяется к конечной точке К, модели 2 минимального разреза,На (а+3)-м такте сигнал с выхода 3 б блока 32 проходит через схему совпадения 27 и сбрасывает триггер 24 в состояние 0.На втором этапе работы устройства в модели минимального разреза среди выбранных на первом этапе ветвей выявляются экстремальные ветви, принадлежащие минимальному разрезу, Это достигается с помощью трансформатора тока 23, распределителя импульсов 32 и дифференцирующего усилителя 31, выявляющих экстремальные каналы способом, ацисанным выше. Необходимо отметить, что в этом случае возмущающей величиной является не приращение напряжения Ле, а приращение тока - Л 1, уменьшающее величину тока в ветвях на Л 1. При этом, если рас. сматриваемая ветвь принадлежит минимальному разрезу, уменьшение тока в ней на величину Ы вызовет уменьшение суммарного тока через модель 2 минимального разреза на такую же величину. Это изменение выходной величины передается на вход дифференцирующего усилителя 31, на выходе которого появится импульс, сигнализирующий об экстремальности опрашиваемой ветви, Этот импульс5 10 15 20 25 через соответствующую схему совпадения 26 установит триггер 24 в состояние 1, Таким образом, на втором этапе устанавливаются 1 в состояние 1 триггеры ветвей, принадлежащих минимальному разрезу. При этом будут замкнуты ключи 8 на первых входах суммирующих усилителей б в соответствующих моделях сетевого графика,На (и+1)-м такте генератора импульсов 37 с выхода 34 распределителя импульсов 32 сигнал через схему совпадения 29 отпирает ключ 9, соединяющий выход сравнивающего устройства 4 с шиной, объединяющей ключи 8. Этот же сигнал отпирает ключ 13 через схему разделения 30,На первый вход сравнивающего устройства 4 включен регулируемый источник напряжения 16, моделирующий заданное время выполнения комплекса работ.Второй вход сравнивающего устройства 4 соединен с конечной точкой К, модели 1 сетевого графика, направление которой пропорционально текущему минимальному времени выполнения комплекса работ (Т критическому). Разность этих двух напряжений через ключ 9 и ключи 8 поступает на первые входы соответствующих суммирующих усилителей б и заряжает конденсаторы 6, Поскольку это напряжение противофазно напряжениям регулируемых источников напряжения 1 б, напряжение на выходах соответствующих усилителей б понижается. Это соответствует сокращению длительностей выбранных критических работ, При этом уменьшается напряжение конечной точки К, модели 1 сетевого графика, а поскольку через схему разделения 30 открывается ключ 13, дифференцирующий усилитель 31 преобразует изменение этого напряжения в управляющий сигнал, который запирает ключ 14 на выходе генератора импульсов 37.Как только прекратится изменение напряжения конечной точки модели 1 сетевогс графика, т, е. как только сокращаемые работы уходят с критического пути, ключ 14 отпирается, Выбранные работы не могут сокращаться до величины, при которой время выполнения комплекса работы Т (Т критическое) окажется меньше заданного времени Т так как при равенстве этих времен напряжение на выходе сравнивающего устройства 4 равно нулю.Контроль за сокращением операций до величины не ниже Тпосуществляется с помощью ограничителей 17 уровня напряжения,На (а+2)-м такте триггер 2 б вновь установится в состояние 0, а ключи 9 и 12 закроются,На (а+3)-м такте импульс через схему совпадения 28 запрет ключи 7, соединяющие вто 30 35 40 45 50 55 60 рые входы суммирующих усилителей б с со. бытиями, из которых исходят рассматриваемые работы. При этом обнаруживаются работы, сокращенные до величины Т,ш. Любой суммирующий усилитель б, у которого разность напряжений на конденсаторе 6 и регулируемом источнике напряжения 1 б окажется больше напряжения ограничителя 17 уровня напряжений, выйдет пз линейного режима, так как при этом запирается диод 18 в цепи обратной связи. Сигналы с выходов таких суммирующих усилителей запрут ключи 10. Эти ключи самоблокируются и шунтируют соответствующие ветви модели 2 минимального разреза, Таким образом, работы, длительность которых сократилась до Т, исключаются из дальнейшего рассмотрения.Описанный процесс оптимизации в два этапа повторяется до тех пор, пока время выполнения комплекса операций не станет равным заданному. Напряжение на выходе сравнивающего устройства 4 будет равно нулю, При этом на выходах суммирующих усилителей б при запертых ключах 7 фиксируются напряжения, пропооциональные искомым длительностям работ, а с помощью триггеров 24 индицируются критические операции полученного оптимального плана,Предмет изобретенияУстройство для построения оптимального плана сетевого графика, содержащее соединенные между собой модель сетевого графика на основе суммирующего усилителя с диодом в цепи обратной связи и конденсатором на одном из входов, модель минимального разреза на отключаемых элементах, выполненных в виде параллельно соединенных источника тока, диодов и трансформатора тока, триггеры, управляемые ключи, схемы совпадения и регулируемые источники напряжения, отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит сравнивающее устройство, дифференцирующий усилитель и распределитель импульсов, причем выходы моделей сетевого графика и минимального разреза через соответствующие управляемые ключи соединены с дифференцирующим усилителем, выход которого через управляемый ключ присоединен ко входу распределителя импульсов, выходы которого соединены со входами схем совпадения, первичной обмоткой трансформатора тока, вторым входом суммирующего усилителя и счетным входом триггера;,выход сравнивающего устройства через управляемый ключ соединен с первым входом суммирующего усилителя, а его входы подключены к выходу модели сетевого графика и выходу регулируемого истоЧнпка напряжения.333568 Составитель Г. СорокиТехред 3. Хараненко ректор Е. Михеева едактор Б, Нанкина ипография, пр. Сапунова, 2 Заказ 10016 Изд,399 Тираж 448 Подписное1 НИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5