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

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

Иллюстрации

Показать все

Реферат

 

ОПИСАН И Е

ИЗОБРЕТЕН ИЯ

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

292l65

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

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

Республик

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

Заявлено 01.Vill.1968 (№ 1262356/18-24) МПК С 06K 7/48 с присоединением заявки ¹

Приоритет

Опубликовано 06.1.1971. Бюллетень ¹ 4

Дата опубликования описания 26.II.1971

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

СССР

УДК 681.333(088,8) ГСЕСС. 2Г1-1ДЯ

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

О. Б. Ткалич

Заявитель

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО

ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ

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

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

Однако в известных устройствах нет возможности учитывать ограничения на одновременный расход ресурсов. Такие устройства могут решать задачи только по времени ограниченного объема, так как наборное поле ограничено, кроме "îãî, .позво.ляют наб.людать промежуточные решения, т. е. оценивать складывающу.юся ситуацию.

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

На фиг. 1 изображена блок-схема предлагаемого универсального вычислительного устройства.

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

На фиг. 3 приведены этапы решения исходной задачи на предлагаемом устройстве с учетом ресурсов типа «исполнители» при заданном ограничении на расход ресурсов и при отсутствии ресурсов. Над изображением каждой из работ в этих линейных графиках указаны коды работ. Суммарная интенсивность Q

2г приведена под каждым из графиков. Текущее время t изображено под нижним графиком в виде отдельной строки.

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

3р рассогласования между счетчиками дат и

292165 счетчиком длительностей работ или резервов, а также для ввода работ или резервов работ и всличин ресурсов на демонстрационное табло и счетчики ресурсов; переключатель строк

4, управляющий вводом работ или резервов работ на выбранную строку; логические схемы совпадений б для работ по датам, определгпощие ввод работ в разрешенные даты; логические схемы совпадений б переключателя строк для работ, определяющие ввод рабо" на разрешеные строки; управляемый генератор 7 длительностей работ для ввода величины очередной длительности работы; переключатель сигналов 8, определяющий ввод на табло работ либо резервов работ (при вводе работ выдает сигнал на включение разделительного индикаторного элемента, обозначающего па табло последнюю дату работы); индикаторный и запоминающий элемент 9 работы единичной длительности для визуального наблюдения за положением элемента работы в процессе решения задач; управляемый генератор дат 10 для ввода величины даты начала работ или резервов работ; ключи 11 установки величины ресурса для ввода на счетчики ресурсов величин ресурсов; блок команд 12 для управления сложением (при вводе) либо вычитанием (при

«стирании») вводимой на счетчики ресурсов величины; логические схемы отработки 18, управляющие процессом отработки рассогласования между счетчиком дат и счетчиком длительности работ или резервов; логическую схему. 14 цикла отработки для реализации команд логической схемы отработки; тактовый генератор импульсов 15 для синхронизации работы блоков устройства; логические схемы совпадений 1б для ресурсов по датам, определяющие ввод величин ресурсов в счетчики ресурсов по разрешенным датам, соответствующим датам вводимой работы; счетчики ресурсов 17 для алгебраического суммирования расходуемых ресурсов по датам, имеющие индикаторные элементы, указывающие накопленные в них величины; логические схемы совпадений

18 для резервов работ по датам, определяющие ввод резервов работ в разрешенные даты; индикаторные и запоминающие элементы 19 резервов работ единичной длительности для визуального наблюдения за положением элемента резерва работы или разделительного сигнала между работами в процессе решсния задач; логические схемы совпадений 20 переключателя строк для резервов работ и разделительных сигналов между работами, определяющие ввод сигчалов и резервов работ на разрешенные строки, и управляемый генератор 21 длительностей резервов работ для ввода величин резервов работ (здесь и далее под резервами работ понимаются резервы времени работы), Счетчики длительностей работ пли резервов, дат и отработки выполнены таким образом, что в каждом из них может быть возбуждена одна ячейка. При работе это возбуждение ячеек или, точнее, двоичная единица переме5

55 бО

4 щается от начальных к конечным ячейкам.

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

На фиг. изображены только такие логические схемы cýâïàäåíèé, логические схемы совпадений для резервов работ по датам, логические схемы совпадений для работ по датам и логические схемы совпадений для ресурсов по да гам, которые соответствуют первой ячейке счетчика дат или (что то же) первым индикатор ым элементам на демонстрационном табло. Ы действигельности к выходу каждой ячейки счетчика дат подсоединено четыре логические схемы, и, следовательно, каждых из этих схем столько же, сколько и ячеек (разрядов), в счетчике дат. Аналогично выходы все ячеек счетчика длительностей работ или резервов подсоединены ко входам соответствующих логических схем совпадений.

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

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

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

Допустим, что работу длительностью в 5 единиц времени необходимо ввести в отрезок с

11-й по 15-ю единицу времени на вторую строку, а интенсивность ее составляет два человека в единицу времени. Пусть каждая единица времени является днем. Положим, что счетчики 1, 2 и 3 находятся в начальном положении, т. е. в них возбуждена начальная ячейка. Переключателем 4 создадим условия прохождения сигналов от логических схем 5 только на вторую строку, т. е. переключателем

4 подадим соответсгвующие сигналы на схемы б второй строки, С помощью управляемого генератора длительностей работ 7 введем нужную нам величину импульсов в счетчик длительностей работ 1. Одновременно переключателем будут произведены такие переключения, что сигналы, которые в будущем с него поступят, попадут только на логическую схему б, а через нее на индикаторные и запоминающие элементы 9 верхней подстроки второй строки. С помощью управляемого генератора даr 10 введем дату начала, т. е. 11 импульсов нли единиц времени в счетчики 1 и 2. Ключами 11 установим требуемое количество ресурса, т. е. замкнем два из них, а с помощью блока 12 определим ввод ресурса. В этот момент установившееся между счетчиками 1 и 2 рассогласование, выявленное схемой И, откроет вентиль 14. Импульсы от генератора 15 посту292165

Таблара данных А

Работы

PO ПО P

Ш

Ш

22 — 23

23 — 24

22 — 24

VI

11

1Ц пят на счеткик 8. Сигнал от первой ячейки счетчика пройдет через переключатель 8 и через схему совпадений 5 на !1-й сигнальный элемент 9 второй строки, где «запомнится».

Сигналы, проходящие через ключи 11, пройдут на схему совпадений 5 на 11-й сигнальный элемент 9 второй строки, где «запомнятся».

Сигналы, проходящие через ключи 11, пройдут на схему совпадений 1б и далее в счетчики ресурсов 17. В дальнейшем импульсом от счетчика 8 двоичная единица в счетчике 2 отработки даты переместится в 12-ю ячейку, и цикл повторится.

При отработке последнего 15-ro отрезка времени счетчики 1 и 2 окажутся в одинаковых состояниях. От схем совпадения 18 поступит предварительный запрещающий сигнал на схему 14 и сигнал на переключатель 8, где последний вызовет такие переключения. что последний сигнал на вторую строку поступит уже через схемы 5 и 18, т. е. в верхнюю и ни>кшою подстройки. Причем сигнал на индикаторный и запоминающий элемент 19 второй строки пройдет через логическую схему 20, открытую переключателем 4 только для второй строки.

Этим будет введен разделительный сигнал между работами. Затем вводится величина ресурса, поступит второй запрещающий сигнал из счетчика 8 на схему 14 и последняя блокируется. Если в дальнейшем нужно вводить работы по этой же строке, то никаких переключений не требуется, в противном случае схему ввода необходимо вернуть в исходное поло>кение.

Если бы в предыдущем примере потребовалось ввести не работу, а резерв работы, то длительность резерва была бы введена с помощью управляемого генератора 21 резервов работ, и были высвечены элементы 19 с 11-й по 15-ю единицу времени.

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

Пусть задан сетевой график (см. фиг. 2) и задано ограничение на расход ресурсов по всем t.

В распоряжении оператора имеется таблица данных А, в которой заполнены только столбцы а, б и в. Таким образом, исходная информация по работам задана. где PH — раннее начало работы;

PO — раннее окончание работы;

l0

ПΠ— позднее окончание работы;

Р— резерв времени работы.

Для упрощения последующих пoHCIICIIIII работы в столбце а расположень; в порядке возрастания вторых индексов кодов работ. В общем случае упорядочение работ не обязательно.

В начале оператор рассматривает первук работу 22 — 23 и, учигывая ее зпачонпо длительности гц — III и величину интенсивност а;; =IV, вводит эти данные в устройство следующим образом. Поскольку первая работа должна начаться в первый отрезок времени выполнения работ, т. е. в первую дату, генератором 10 оператор вводит дату, равную единице, генератором 7 — длительность работы, равную трем единицам, ключом 11 — интенсивность, равную шести единицам (см. таблицу данных А), а переключателем строк устанавливает первую (или любую другую) строку. Начинается процесс отработки введенных величин. От тактового генератора 15 импульсы отработки поступают на счетчик 8, с помощью которого первая работа вводится на первую строку, где занимает три первых индикаторных и запоминающих элемента 9 и, для фиксации окончания работы, третий элемент 19.

После этого оператор может заполнить первую строку столбцов г и д таблицы данных А.

PH этой работы равно, очевидно, 1, а РО равно 1П. Значения этого PH «PO, а также всех последующих, оператор может прочитать на табло по расположенной там сетке дат.

Далее оператор рассматривает следующую по порядку работу 23 — 24. Очевидно, что работа 28 — 24 должна следовать за работой 22—

28, а для работы 22 — 23 PO известно (из таблицы данных А) и равно III, Допустим, что состояния всех счетчиков 1, 2 и 3 после ввода каждой работы соответствуют ис. одному. В действительности это может иметь место по желанию оператора и не является обязательным. Тогда оператор вводит генератором 10 дату, равную IV, так как последующая работа 28 — 24 может начаться после работы 22—

28 в дате PO (22 — 23)+1=IV, генератором 7 вводит длительность работы, равную III, а ключом 11 — интенсивность, равную II. Допустим, что переключателем строк оператор устанавливает вторую строку (или любую другую) .

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

Рассматривая этот график, оператор может заполнить вторую строку столбцов г и д таблицы данных, так как из графика. видимого на табло, очевидно, что PH для работы 23 — 24 равно IV, à PO равно VI.

Далее оператор рассматривает следующую

rо порядку работу 22 — 24. Казалось бы геноDBTopo 10 оп может ста повить Л,IH Ilcc дату

292165

Таблица данных Б

Работы

22 — 23

23 — 24

22 — 24

II I

III

VI

II

IV

Ш

VI

ЧШ

Ш

V I II

VIII

0 начала, равную 1, но в этом случае будет нарушено ограничение на расход ресурсов. Если оператор не заметил этого сразу, то после ввода работы 22 — 24 на табло, он может ее стереть, установив в блоке 12 ключ в положение «вычесть». Тогда при повторном вводе этих же данных информация на элементах 9 и в счетчиках 17, соответствующая работе

22 — 24, будет ликвидирована, Рассматривая наиболее раннее возможное время ее начал, он заметит, что работа 22 — 24 может быть начата в дату IV, которую он и введет генератором 10. Генератором 7 оператор вновь введет ее длительность, ключом 11 — интенсивность, а переключателем 4 — третью строку.

Результирующая картина показана на фиг.

3, в. Под этим графиком показано результирующее распределение ресурсов, соответствующее показаниям счетчиков 17. Таким образом оператор установил ранние начала и окончания работ и записал в графы г и д, а тем самым и длительность критического пути, равную IV единицам. Рассматривая график позиции (фиг. 3, в), он может установить, что только работа 28 — 24 имеет резерв времени, равный 11, так как ее перемещение не приведет к нарушению ограничений. Все это он отражает в таблице данных и получает ее в окончательном виде (таблица данных Б).

Приведенное в таблице данных Б решение соответствует, как это легко показать, оптимальному решению.

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

Используя рассмотренную методику можно вычислить поздние начала работ, зависимые резервы времени работ, определить подкритические пути и т. д. Если необходимо получить решение задачи без учета ресурсов, то используя эту же методику, можно вычислить только временные характеристики работ и всего комплекса. Результат подобного решения приведен на фиг. З,г, Предмет изобретения

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

4Ьг З

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

Редактор Л. А. Утехина Техред А. А. Камышникова Корректор О. С. Зайцева

Изд. № 166 Заказ 329/2 Тираж 473 Подписное

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

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

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