Устройство для решения задач сетевого планирования и управления

ОПИСАН И Е ИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ союз Советских Социалистических РеспубликЗависимое от авт, свидетельства М 1262356/18-24) Заявлено 01.Ч 11.1968 (с присоединением заявкПриоритетОпубликовано 06.1,1971Дата опубликования оп МПК С 06 д 748 Комитет по делам обретеиий и открыти ри Совете Мииистрав СССР1 С.СС.2 ГИАЯ Автор зобретения О. Б. Тка витель СТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯИзобретение относится к области аналоговой вычислительной техники.Известны устройства для решения задач сетевого планирования и управления.Однако в известных устройствах нет возможности учитывать ограничения на одновременный расход ресурсов. Такие устройства могут решать задачи только по времени ограниченного объема, так как наборное поле ограничено, кроме того, позволяют наблюдать промежуточные решения, т. е. оценивать складывающуюсяя ситуацию.Предложенное устройство отличается тем, что с целью определения временных параметров работ, а также нахождения распределения ресурсов и длительности критического пути для комплекса работ в нем выход управляемого генератора дат соединен со входом счетчика дат и входом счетчика длительностей работ или резервов, выходы управляемого генератора длительностей работ и управляемого генератора резервов соединены со входом счетчика длительностей работ или резервов, причем выходы счетчика длительностей работ или резервов и счетчика дат соединены со входами логических схем совпадений отработки, выходы которых соединены со входом тактового генератора, а выход последнего соединен со входом счетчика отработки, первый выход которого соединен со входом счетчика дат, а между вторым - его выходом и выходом счетчика дат включены логические схемы совпадений для работ, резервов, ресурсов и строк, выходы которых подключены к сигнальным и запоминающим элементам табло и счетчикам ресурсов.На фиг. 1 изображена блок-схема предлагаемого универсального вычислительного устройства.Ы На фиг. 2 приведена сетевая модель в традиционной форме, которая является основой задачи приведенного примера.На фиг, 3 приведены этапы решения исходной задачи на предлагаемом устройстве с учс том ресурсов типа исполнители при заданном ограничении на расход ресурсов и при отсутствии ресурсов. Над изображением каждой из работ в этих линейных графиках указаны коды работ. Суммарная интенсивность Я 20 приведена под каждым из графиков. Текущеевремя 1 изображено под нижним графиком в виде отдельной строки.Предлагаемое устройство содержит (см.фиг. 1) счетчик 1 длительностей работ или рс зервов, служащий для промежуточного запоминания этих величин; счетчик дат 2 для промежуточного запоминания даты начала работы или резерва работы; счетчик отработки 3, используемый как генератор для отработки 30 рассогласования между счетчиками дат исчетчиком длительностей работ или резервов, а также для ввода работ или резервов работ и величин ресурсов на демонстрационное табло и счетчики ресурсов; переключатель строк 4, управляющий вводом работ или резервов работ на выбранную строку; логические схемы совпадений б для работ по датам, определяющие ввод работ в разрешенные даты; логические схемы совпадений 6 переключателя строк для работ, определяющие ввод работ на разрешеные строки; управляемый генератор 7 длительностей работ для ввода величины очередной длительности работы; переключатель сигналов 8, определяющий ввод на табло работ либо резервов работ (при вводе работ выдает сигнал на включение разделительного индикаторного элемента, обозначающего па табло последнюю дату работы); индикаторный и запоминающий элемент 9 работы единичной длительности для визуального наблюдения за положением элемента работы в процессе решения задач; управляемый генератор дат 10 для ввода величины даты начала работ или резервов работ; ключи 11 установки величины ресурса для ввода на счетчики ресурсов величин ресурсов; блок команд 12 для управления сложением (при вводе) либо вычитанием (при стирании) вводимой на счетчики ресурсов величины; логические схемы отработки 13, управляющие процессом отработки рассогласования между счетчиком дат и счетчиком длительности работ или резервов; логическую схему 14 цикла отработки для реализации команд логической схемы отработки; тактовый генератор импульсов 1 б для синхронизации работы блоков устройства; логические схемы совпадений 1 б для ресурсов по датам, определяющие ввод величин ресурсов в счетчики ресурсов по разрешенным датам, соответствующим датам вводимой работы; счетчики ресурсов 17 для алгебраического суммирования расходуемых ресурсов по датам, имеющие индикаторные элементы, указывающие накопленные в них величины; логические схемы совпадений 18 для резервов работ по датам, определяющие ввод резервов работ в разрешенные даты; индикаторные и запоминающие элементы 19 резервов работ единичной длительности для визуального наблюдения за положением элемента резерва работы или разделительного сигнала между работами в процессе решсния задач; логические схемы совпадений 20 переключателя строк для резервов работ и разделительных сигналов между работами, определяющие ввод сигчалов и резервов работ на разрешенные строки, и управляемый генератор 21 длительностей резервов работ для ввода величин резервов работ (здесь и далее под резервами работ понимаются резервы времени работы),Счетчики длительностей работ пли резервов, дат и отработки выполнены таким образом, что в каждом из них может быть возбуждена одна ячейка. При работе это возбуждение ячеек или, точнее, двоичная единица переме 5 10 15 20 25 30 35 40 45 5 О 55 бО 65 4щается от начальных к конечным ячейкам. Аналогом счетчиков может быть шаговый искатель. Число ячеек в счетчиках длительностей рабог или резервов и даты равно числу индикаторных элементов в строках демонстрационного табло.На фиг. изображены только такие логические схемы совпадений, логические схемы совпадений для резервов работ по датам, логические схемы совпадений для работ по датам и логические схемы совпадений для ресурсов по да гам, которые соответствуют первой ячейке счетчика дат или (что то же) первым индикаторным элементам на демонстрационном табло. Ы действигельности к выходу каждой ячейки счетчика дат подсоединено четыре логические схемы, и, следовательно, каждых из этих схем столько же, сколько и ячеек (разрядов), в счетчике дат. Аналогично выходы все ячеек счетчика длительностей работ или резервов подсоединены ко входам соответствующих логических схем совпадений.Число логических схем совпадений переключателя строк для работ и число схем совпадений переключателя строк для резервов работ равно произведению числа индикаторных элементов в строке на число строек.В устройстве все работы вводятся с помогцью одних и тех же управляемых генераторов дат и длительностей работ, а логика сети контролируется на демонстрационном табло. Здесь нет никаких машинных ограничений, определяющих положение работ по времени, что позволяет решать более широкий класс задач.Допустим, что работу длительностью в 5 единиц времени необходимо ввести в отрезок с 11-й по 15-ю единицу времени на вторую строку, а интенсивность ее составляет два человека в единицу времени. Пусть каждая единица времени является днем. Положим, что счетчики 1, 2 и 3 находятся в начальном положении, т. е. в них возбуждена начальная ячейка. Переключателем 4 создадим условия прохождения сигналов от логических схем б только на вторую строку, т. е, переключателем 4 подадим соответсгвующие сигналы на схемы б второй строки, С помощью управляемого генератора длительностей работ 7 введем нужную нам величину импульсов в счетчик длительностей работ 1, Одновременно переключателем будут произведены такие переключения, что сигналы, которые в будущем с него поступят, попадут только на логическую схему б, а через нее на индикаторные и запоминающие элементы 9 верхней подстроки второй строки. С помощью управляемого генератора дат 10 введем дату начала, т. е. 11 импульсов нли единиц времени в счетчики 1 и 2. Ключами 11 установим требуемое количество ресурса, т. е, замкнем два из них, а с помощью блока 12 определим ввод ресурса. В этот момент установившееся между счетчиками 1 и 2 рассогласование, выявленное схемой И, откроет вентиль 14. Импульсы от генератора 1 б постуТаблара данных А Работы РО ПО Р П 1 П Ч 22 - 23 23 - 24 22 - 24 И П П 1 П 1 пят на счеткик 3. Сигнал от первой ячейки счетчика пройдет через переключатель 8 и через схему совпадений 5 на 1-й сигнальный элемент 9 второй строки, где запомнится. Сигналы, проходящие через ключи 11, пройдут на схему совпадений 5 на 11-й сигнальный элемент 9 второй строки, где запомнятся. Сигналы, проходящие через ключи 11, пройдут на схему совпадений 1 б и далее в счетчики ресурсов 17. В дальнейшем импульсом от счетчика 3 двоичная единица в сцетчике 2 отработки даты переместится в 12-ю ячейку, и цикл повторится,При отработке последнего 15-го отрезка времени счетчики 1 и 2 окажутся в одинаковых состояниях. От схем совпадения 13 поступит предварительный запрещающий сигнал на схему 14 и сигнал на переключатель 8, где последний вызовет такие переключения. что последний сигнал на вторую строку поступит уже через схемы 5 и 18, т. е. в верхнюю и никцюю подстройки. Причем сигнал на индикаторный и запоминающий элемент 19 второй строки пройдет через логическую схему 20, открытую переключателем 4 только для второй строки. Этим будет введен разделительный сигнал мекду работами. Затем вводится величина ресурса, поступит второй запрещающий сигнал из счетчика 3 на схему 14 и последняя блокируется. Если в дальнейшем нужно вводить работы по этой же строке, то никаких переключений не требуется, в противном случае схему ввода необходимо вернуть в исходное положение,Если бы в предыдущем примере потребовалось ввести не работу, а резерв работы, то длительность резерва была бы введена с помощью управляемого генератора 21 оезервов работ, и были высвечены элементы 19 с 11-й по 15-ю единицу времени,Рассмотрим теперь принцип решения задач на предлагаемом устройстве. Поскольку прохождение сигналов при вводе в устройство работы или резерва времени работы было рассмотрено выше весьма подообно, ниже мы не будем называть всех цепей, по которым следуют сигналы в сходных случаях.Пусть задан сетевой график (см. фиг. 2) и задано ограничение на расход ресурсов по всем ,В распоряжении оператора имеется таблица данных А, в которой заполнены только столбцы а, б и в. Таким образом, исходная информация по работам задана. где РН - раннее начало работы; РО - раннее окончание работы; 5 10 15 20 25 30 35 40 45 50 55 60 65 ПО - позднее окончание работьцР - резерв времени работы.Для упрощения последующих пояснений работы в столбце а расположены в порядке возрастания вторых индексов кодов работ. В общем случае упопядочение работ це обязательно.В начале оператор рассматривает первук работу 22 - 23 и, учитывая ее зпачонцо длительности 1 ц=П 1 и величину интецсивцост д=17, вводит эти данные в устройство следующим образом. Поскольку первая работа должна начаться в первый отрезок времени выполнения работ, т. е. в первую дату, генератором 10 оператор вводит дату, равную единице, генератором 7 - длительность работы, равную трем единицам, ключом 11 - интенсивность, равную шести единицам (см, таблицу данных А), а переключателем строк устанавливает пеовую (цли любую другую) строку. Начинается процесс отработки введенных величин. От тактового генератора 15 импульсы отработки поступают ца счетчик 3, с помощью которого первая работа вводится ца первую строку, где занимает тои первых индикаторных и запоминающих элемента 9 и, для фиксации окончания работы, третий элемент 19.После этого оператор может заполнить первую строку столбцов г и д таблицы данных А. РН этой работы равно, очевидно, 1, а РО равно 1 П. Значения этого РН и РО, а также всех госледующих, опеоатор может прочитать на табло по расположенной там сетке дат.Далее оператор рассматривает следующую по порядку работу 23 - 24. Очевидно, что работа 23 - 24 должна следовать за работой 22 - 23, а для работы 22 - 23 РО известно (цз таблицы данных А) и равно П 1, Допустим, что состояния всех счетчиков 1, 2 ц 3 после ввода каждой работы соответствуют исходному. В действительности это может иметь место по желанию оператора и не является обязательным. Тогда оператор вводит генератором 10 дату, равную 1 Ъ, так как последующая работа 23 - 24 может нацаться после работы 22 - 23 в дате РО (22 - 23)+1=Л, генератором 7 вводит длительность работы, равную П 1, а ключом 11 - интенсивность, равную П. Допустим, что переключателем строк оператор устанавливает вторую строку (или любую другую).Импульсами отработки эти величины вводятся ца табло и образуют картину, приведенную на фиг, 3, б. На счетццках ресурсов устанавливаются значения, показанные ца этой же фигуре.Рассматривая этот график, оператор может заполнить вторую строку столбцов г и д таблицы данных, так как из графика, видимого на табло, очевидно, что РН для работы 23 - 24 равно Л 7, а РО равно 1 Ч.Далее оператор рассматривает следующую по порядку работу 22 - 24, Казалось бы генератором 10 рц может стацовцть для цео датП 1Ч 1ЧП 1 П 1ЧП 1Ч 1 П О П О начала, равную 1, но в этом случае будет нарушено ограничение на расход ресурсов, Гсли оператор не заметил этого сразу, то после ввода работы 22 - 24 на табло, он может ее стереть, установив в бло 1(е 12 ключ в положение вычесть. Тогда при повторном вводе этих же данных информация на элементах 9 и в счетчиках 17, соответствующая работе 22 - 24, будет ликвидирована, Рассматривая наиболее раннее возможное время ее начал, он заметит, что работа 22 - 24 может быть начата в дату 17, которую он и введет генератором 10. Генератором 7 оператор вновь введет ее длительность, ключом 11 - интенсивность, а переключателем 4 - третью строку.Результирующая картина показана на фиг, 3, в, Под этим графиком показано результирующее распределение ресурсов, соответствующее по(азаниям счетчиков 17, Таким образом оператор установил ранние начала и окончания работ и записал в графы г и д, а тем самым и длительность критического пути, равную 1 Г единицам. Рассматривая график позиции (фиг, 3, в), он может установить, что только работа 23 - 24 имеет резерв времени, равный 11, так как ее перемещение не приведет к нарушению ограничений. Все это он отражает в таблице данных и получает ее в окончательном виде (таблица данных Б). Приведенное в таблице данных Б решение соответствует, как это легко показать, оптимальному решению,Получить подобное или какое-либо другое решение исходной задачи на противопоставляемом устройстве не представляется возможным. 15 го 25 3 О 35 40 45 Используя рассмотренную методику можно вычислить поздние начала работ, зависимые резервы времени работ, определить подкритические пути и т. д. Если необходимо получить решение задачи без учета ресурсов, то используя эту же методику, моя(но вычислить только временные характеристики работ и всего комплекса. Результат подобного решения приведен на фиг, З,г,Предмет изобретенияУстройство для решения задач сетевого планирсвания и управления, например, с учетом ограниченных ресурсов типа исполнители содержащее управляемый генератор длительностей работ, управляемый генератор длитель ностей резервов работ, управляемый генератор дат, тактовый генератор, счетчик длительностей работ или резервов, счетчик дат, счетчик отработки, табло для индикации и запоминания информации, логические схемы и переключатели, отлыназощееся тем, что, с целью определения временных параметров работ, а также нахождения распределения ресурсов и длительности критического пути для комплекса работ, в нем выход управляемого генератора дат соединен со входом счетчика дат и входом счетчика длительностей работ или резервов, выходы управляемого генератора длительностей работ и управляемого генератора резервов соединены со входом счетчика длительностей работ или резервов, причем выходы счетчика длительностей работ или резервов и счетчика дат соединены со входами логических схем совпадений отработки, выходы которых соединены со входом тактового генератора, а выход последнего соединен со входом счетчика отработки, первый выход которого соединен со входом счетчика дат, а между вторым его выходом и выходом счетчика дат включены логические схемы совпадений для работ, резервов, ресурсов и строк, выходы которых подключены к сигнальным и запоминающим элементам табло и счетчикам ресурсов,292165 1=УХЫХГ КЛЯТ фие 3 Составитель Е, В. Тимохинатехина Техред А. А. Камышникова Корректор О, С, Зайцев Редактор Л. Изд.166 Заказ 329/2 Тираж 473 Подписное ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 4/5 ипография, пр. Сапунова,