УСТРОЙСТВО для РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ Советский патент 1971 года по МПК G06G7/122 

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

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

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

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

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

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

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

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

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

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

счетчиком длительностей работ или резервов, а также для ввода работ или резервов работ и величин ресурсов на демонстрационное табло и счетчики ресурсов; нереключатель строк 4, унравляющий вводом работ или резервов работ на выбранную строку; логические схемы совнадений 5 для работ но датам, оиределяющие ввод работ в разрешенные даты; логические схемы совпадений 6 нереключателя строк для работ, оиределяющие ввод работ на разрешеные строки; унравляемый генератор 7 длительностей работ для ввода величины очередной длительности работы; переключатель сигналов 8, определяющий ввод на табло работ либо резервов работ (при вводе работ выдает сигнал на включение разделительного индикаторного элемента, обозначаюндего на табло носледнюю дату работы); индикаторный и запоминающий элемент 9 работы единичной длительности для визуального наблюдения за положением элемента работы в процессе решения задач; управляемый генератор дат 10 для ввода величины даты начала работ или резервов работ; ключи 11 установки величины ресурса для ввода на счетчики ресурсов величин ресурсов; блок команд 12 для управления сложением (при вводе) либо вычитанием (нри «стирании) вводимой на счетчики ресурсов величины; логические схемы отработки 13, управляющие нроцессом отработки рассогласования между счетчиком дат и счетчиком длительности работ или резервов; логическую схему 14 цикла отработки для реализации команд логической схемы отработки; тактовый генератор импульсов 15 для синхронизации работы блоков устройства; логические схемы совпадений 16 для ресурсов по датам, определяющие ввод величин ресурсов в счетчики ресурсов по разрешенным датам, соответствующим датам вводимой работы; счетчики ресурсов 17 для алгебраического суммирования расходуемых ресурсов по датам, имеющие индикаторные элементы, указывающие накопленные в них величииы; логические схемы совпадений 18 для резервов работ по датам, определяющие ввод резервов работ в разрещеиные даты; индикаторные и запоминающие элементы 19 резервов работ единичной длительности для визуального наблюдения за положением элемента резерва работы или разделительного сигнала меладу работами в процессе рещения задач; логические схемы совпадений 20 переключателя строк для резервов работ и разделительных сигналов между работами, определяющие ввод сигналов и резервов работ на разрешенные строки, и управляемый генератор 21 длительностей резервов работ для ввода величин резервов работ (здесь и далее под резервами работ понимаются резервы времени работы).

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

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

табло. В действигельности к выходу каждой ячейки счетчика дат нодсоединено четыре логические схемы, и, следовательно, каждых из этих схем столько же, сколько и ячеек (разрядов), в счетчике дат. Аналогично выходы

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

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

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

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

задач.

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

прохождения сигналов от логических схем 5 только на вторую строку, т. е. переключателем 4 подадим соответствующие сигналы на схемы 6 второй строки. С помощью управляемого генератора длительностей работ 7 введем нужную нам величину импульсов в счетчик длительностей работ 1. Одновременно переключателем будут произведены такие переключения, что сигналы, которые в будущем с него поступят, попадут только на логическую схему

5, а через нее на индикаторные и запоминающие элементы 9 верхней подстроки второй строки. С номощью унравляемого генератора дат }0 введем дату начала, т. е. 11 импульсов или единиц времени в счетчики 1 и 2. Ключами // установим требуемое количество ресурса, т. е. замкнем два из них, а с помощью блока 12 определим ввод ресурса. В этот момент установившееся счетчиками 1 и 2 рассогласование, выявленное схемой 13, откроет ПЯТ на счеткик 3. Сигнал от первой ячейки счетчика пройдет через переключатель 8 и через схему совпадений 5 на 11-й сигнальный элемент 9 второй строки, где «запомнится. Снгналы, проходящие через ключи //, пройдут на схему совпадений 5 на 11-й сигнальный элемент 9 второй строки, где «запомнятся. Сигналы, проходящие через ключи 11, пройдут на схему совпаденнй 16 и далее в счетчикн ресурсов 17. В дальнейшем импульсом от счетчика 5 двоичная единица в счетчике 2 отработки даты переместится в 12-ю ячейку, и цикл повторится. При отработке последнего 15-го отрезка времени счетчики 1 и 2 окажутся в одинаковых состояниях. От схем совпадения 13 поступит предварительный запрещающий сигнал на схему 14 и сигнал на переключатель 8, где последний вызовет такие переключения, что последний сигнал на вторую строку поступит уже через схемы 5 и 18, т. е. в верхнюю и нижнюю подстройки. Причем сигнал на индикаторный и запоминающий элемент 19 второй строки пройдет через логическую схему 20, открытую переключателем 4 только для второй строки. Этим будет введен разделительный сигнал между работами. Затем вводится величина ресурса, поступит второй запрещающий сигнал из счетчика 3 на схему 14 и последняя блокируется. Если в дальнейшем нужно вводить работы по этой же строке, то никаких переключений не требуется, в противном случае схему ввода необходимо вернуть в исходное положение. Если бы в предыдущем примере потребовалось ввести не работу, а резерв работы, то длительность резерва была бы введена с помощью управляемого генератора 21 резервов работ, и были высвечены элементы 19 с 11-й по 15-ю единицу времени. Рассмотрим теперь припцип решения задач на предлагаемом устройстве. Поскольку прохождение сигналов при вводе в устройство работы или резерва времени работы было рассмотрено выще весьма подробно, ниже мы не будем называть всех цепей, по которым еледуют сигналы в сходных случаях. Пусть задан сетевой график (см. фиг. 2) и задано ограничение на расход ресурсов по всем t. В распоряжении оператора имеется таблица данных А, в которой заполнены только столбцы и; б и в. Таким образом, исходная информация но работам задана. Таблица данных А ПО - позднее окончание работы; Р - резерв времени работы. Для упрощения последующих пояснений работы в столбце а расположены в порядке возрастания вторых индексов колов работ. В обшем случае упорядочение работ ч обязательно. В начале оператор рассматривает первун работу 22-23 и, учигывая ее значение длительности tij in и величину интенсивности IV, вводит эти данные в устройство следующим образом. Поскольку первая работа должна начаться в первый отрезок времени выполнения работ, т. е. в первую дату, генератором 10 оператор вводпт дату, равную единице, генератором 7 - длительность работы, равную трем единицам, ключом 11 - интенсивность, равную шести единицам (см. таблицу данных Л), а переключателем строк устанавливает первую (пли любую другую) строку. Пачинается процесс отработки введенных величин. От тактового генератора /5 импульсы отработки поступают на счетчик 3, с помощью которого первая работа вводится на первую строку, где занимает три первых инднкатсрных и запоминающих элемента 9 и, для фиксации окончания работы, третий элемент 19. После этого оператор может занолнпть первую строку столбцов гид таблицы данных А. РН этой работы равно, очевидно, /, а РО равно ///. Значения этого РН и РО, а также всех последующих, оператор может прочитать на табло по расположенной там сетке дат. Далее оператор рассматривает следующую по порядку работу 23-24. Очевидно, что работа 23-24 должна следовать за работой 22- 23, а для работы 22-23 РО известно (из таблицы данных Л) и равно ///. Допустим, что состояния всех счетчиков /, 2 и 3 после ввода каждой работы соответствуют исходному. В действительности это может иметь место по желанию оператора и не является обязательным. Тогда оператор вводпт генератором 10 дату, равную /V, так как последующая работа 23-24 может начаться после работы 22- 23 в дате РО (22-23) + V, генератором 7 вводит длительность работы, равную ///, а ключом // - интенсивность, равную //. Допустим, что переключателем строк оператор устанавливает вторую строку (или любую другую) . Импульсами отработки эти величины вводятся на табло и образуют картину, приведенную на фиг. 3, б. На счетчиках ресурсов устанавливаются значения, показанные на этой же фигуре. Рассматривая этот график, оператор может заполнить вторую строку столбцов гид таблицы данных, так как из графика, видимого на табло, очевидно, что РН для работы 23-24 равно IV, а РО равно VI. Далее оператор рассматривает следующую по порядку работу 22-24. Казалось бы гененачала, равную 1, но в этом случае будет нарушено ограничение на расход ресурсов. Если онератор не заметил этого сразу, то после ввода работы 22-24 на табло, он может ее стереть, установив в блоке 12 ключ в положение «вычесть. Тогда при повторном вводе этих же данных информация на элементах 9 и в счетчиках 17, соответствующая работе 22-24, будет ликвидирована. Рассматривая наиболее раннее возможное время ее начал, он заметит, что работа 22-24 может быть начата в дату IV, которую он и введет генератором 10. Генератором 7 оператор вновь введет ее длительность, ключом 11 - интенсивность, а переключателем 4 - третью строку. Результирующая картина иоказана на фиг. 3,8. Под этим графиком показано результирующее распределение ресурсов, соответствующее показаниям счетчиков 17. Таким образом оператор установил ранние начала и окончания работ и записал в графы г и д, а тем самым и длительность критического пути, равную IV единицам. Рассматривая график позиции (фиг. 3,0), он может установить, что только работа 23-24 имеет резерв времени, равный //, так как ее перемещение не приведет к нарушению ограничений. Все это он отражает в таблице данных и получает ее в окончательном виде (таблица данных Б).

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

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

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

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

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

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

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

Jlj ume/ tf oi№t: t

22