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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

424I79

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

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

Республик (61) Зависимое от авт. свидетельства 292165 (22) Заявлено 05.10.71 (21) 1702200/18-24 (51) М. Кл. С 06@ 7/48 с присоединением заявки ¹

Государственный комитет

Совета Министров СССР по делам изаоретений и открытий (32) Приоритет

Опубликовано 15.04.74. Бюллетень № 14

Дата опубликования описания 24.09.74 (53) УДК 681.333(088.8) (72) Автор изобретения

О. Б. Ткалич (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО

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

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

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

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

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

На фиг. 1 приведена с åìà устройства; на фиг. 2 — сетевой график; »а фиг. 3 — графики расхода ресурсов.

Предлагаемое устройство содержит счетчик

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

8 сигналов, индикаторный и запоминающий элемент 9 работы единичной длительности, управляемый генератор 10 дат, ключи 11 установки величины ресурса, блок команд 12, логические схемы 13 отработки, логическую схему 14 цикла отработки, тактовый генератор 15

25 импульсов, анализатор 16 знака расходов ресурсов, логическую схему 17 управления ввода величины интенсивности очередной работы, логическую схему 18 управления вводом импульсов, логическую схему 19 совпадений для

30 ресурсов по датам, счетчики 20 ресурсов, ло424179

1 1И

VI

II

III

28 — 29

29 — 30

28 — 30

III

III

60

65 гическую схему 21 управления вводом величины накопленной интенсивности, логические схемы 22 управления вводом параметров работы на индикаторные и запоминающие элементы, индикаторный элемент 23, логические схемы 24 совпадений для резервов работ по датам, индикаторные и запоминающие элементы 25 резервов работ единичной длительносчи, логические схемы 2б совпадений переключателя строк для резервов работ и разделительных сигналов и управляемый генератор

27 длительностей резервов работ.

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

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

Дополнительно введенный в устройство анализатор знака расхода ресурсов Л q служит для суммирования накопленной величины интенсивности Q „(/) и величины интенсивности расхода ресурсов q,, в контролируемой дате /.

При сопоставлении величины Q„(t) =Q „(t)+

+q, и ограничения на расход ресурсов Q (t) определяется знак Лд=Я,(/) — Q (/).

Процесс решения задач на предложенном устройстве осуществляется следующим образом.

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

Q,=VI.

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

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

Работа 1; д; PH PO ПО P а б I в I г j д I e лс

В таблице данных А введены обозначения;

PH — раннее начало работы;

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

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

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

tö — длительность работы;

q, — интенсивность расхода ресурсов.

Оператор рассматривает полную работу

28 — 29 и учитывая ее значение длительности

t.; =111 и величину интенсивности оц=VI, вводит эти данные в устройство следующим образом.

Поскольку первая работа должна начаться в 1-й отрезок времени выполнения работ, т. е. в 1-ую дату, генератором 10 (см. фиг. 1) оператор вводит дату, равную единице, генератором 7 вводит длительность работы, равную трем единицам. Ключем 11 вводит интенсивность, равную шести единицам. Переключателем 4 строк устанавливает первую (или любую другую) строку. Начинается процесс отработки введенных величин. От тактового генератора 15 импульсы отработки поступают на счетчик 3, с помощью которого первая работа вводится на первую сторону, где занимает три первых индикаторных и запоминающих элемента 9 и для фиксации даты окончания работы — третий элемент 25.

После этого оператор может заполнить первую строку столбцов (г) и (д) таблицы данных А. PH этой работы равно I, à PO равно

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

Эта ситуация приведена на фиг. За, где показано также расходование ресурсов Q»(t), соответствующее заполнению счетчиков 20 для дат 1, Il, 111.

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

28 — 29, а для работы 28 — 29 PO известно (из таблицы данных А) и равно III. Допустим, что состояния всех счетчиков 1 — 3 после ввода каждой работы соответствуют исходному.

Тогда оператор вводит генератором 10 дату, равную IV, так как последующая работа

29 — 30 может начаться после работы 28 — 29 в дате PO (28 — 29) + I = IV, генератором 7 вводит длительность работы, равную 111, а ключем 11 — интенсивность, равную II. Переключателем 4 строк оператор устанавливает вторую строку (или любую другую), Импульсами отработки эти величины вводятся на табло (см. фиг. Зб).

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

29 — 30 равно IV, à PO IV.

Далее оператор рассматривает следующую по порядку работу 28 — 30. Поскольку эта работа начинается в первой дате, то генерато ром 10 оператор устанавливает дату, равную

1, а генератором 7 — длительность, равную V, 424179

VI

II

lII

28 — 29

29 — 30

28 -г0

111

111

11

IV

III

V II I

V I I I

III

VI

V I I I

«Проба» включения операции в расписание в этой дате оканчивается тем, что анализатор

16 выдает импульс «сдвига» на счетчики 1 и 2.

Таким образом, следующая «про ба» будет осуществляться во II-ой дате. Но как в I-ой, так и во 11-ой, а также и в 111-ей дате знак расхода ресурса Лд будет отрицателен, В каждом из этих случаев осуществляется только проверка знака Лд, по ци ца счетчики ресурсов 20, пи иа индикаторные элементы 9 и 25 информация ие вводится, так как схемы 17 и

22 находятся в таких состояниях, когда указанная запись невозможна. В четвертой же дате знак Aq положителен, ца схемы 22 поступит первый разрешающий сигнал. Однако схемы 22 откроются только вторым разрешающим сигналом от первого разряда счетчика 3.

Сигналами от последующих разрядов счетчика 3 введены величины интенсивности в счетчики 20, длительность работы ца элементы 9 и разделительный сигнал на VIII элемент 25.

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

Под этим графиком показано итоговое распределение ресурсов, соответствующее показаниям счетчиков 20. Таким образом, оператор устанавливает ранние начала и окончания работ и записывает в графы (г) и (д), а тем самым и длительность критического пути, равную VIII единицам. Из графика следует, что только работа 29 — 30 имеет резерв времени, равный 11, так как это ее перемещение ие приведет к нарушению ограничений. Все это оператор отражает в таблице и получает ее в окончательном виде (таблица данных Б).

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

Работа 1; q; PH PO ПО P а б ) в 1 г д е ж

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

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

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

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

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

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

Л д позволяет резко увеличить производительность устройства.

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

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

424179

А(8 иг. 2

Составитель В. Озеров

Техред Т. Курилко

Корректор В. Брыксина

Редактор Е. Семанова

Заказ 2454/10 Изд. № 1470 Тираж 624 Подписное

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

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

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