3. ФОРМАЛЬНАЯ ЗАПИСЬ (АЛГОРИТМ) ЗАДАЧИ СЕТЕВОГО ПЛАНИРОВАНИЯ

Описанный выше графический способ построения и анализа плана работ пригоден только в случае, когда планируемый комплекс не слишком сложен (по количеству работ и логических связей). На практике часто встречаются комплексы работ, состоящие из огромного числа звеньев (порядка тысяч и более), сложным образом опирающихся друг на друга. Естественно, что в таких случаях вычерчивание сетевого графика вручную — тяжелое и неблагодарное занятие, так как основное преимущество сетевого графика — его наглядность — при этом теряется. Для анализа и усовершенствования плана работ в таких случаях обычно привлекают ЭЦВМ.

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

Опишем один из возможных алгоритмов, которые могут быть применены для этой цели. Прежде всего, выполняется упорядочение структурной таблицы (см. § 2), для чего работы разделяются на ранги, по признаку числа и рангов работ, на которые они опираются. Это — сравнительно простая задача, и на ней мы останавливаться не будем. Предположим, что упорядочение комплекса работ выполнено, и структурно-временная таблица представлена, например, в виде табл. 3.1.

Таблица 3.1

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

Для этого обозначим — минимально возможный срок начала работы (время отсчитывается от начала процесса), — минимально возможный срок ее окончания. Очевидно

где — время выполнения работы .

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

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

Продемонстрируем, как это делается на материале табл. 3.1. Вычислим величины и для всех работ комплекса.

Для работ первого ранга имеем:

Работа опирается на работы она может начаться в момент когда окончится наиболее поздно кончающаяся из работ

Момент окончания работы

Аналогично, для работ и т. д.:

(3.5)

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

Чтобы найти критические работы (а стало быть, и критический путь), нужно сделать следующее; прежде всего найти работу для которой время окончания максимально; эта работа, конечно, будет критической. Затем найти среди формул (3.5) ту, которой определяется момент начала этой работы Величина представлена в виде максимума каких-то моментов нужно найти тот из них, на котором достигается максимум (если таких моментов несколько, взять любой из них). Та работа при которой достигается этот максимум, будет второй от конца работой на критическом пути. Далее точно так же определяется третья и т. д. работы на критическом пути. Таким образом, критической будет работа с самым поздним сроком окончания и все работы, на времени окончания которых достигается максимум в выражении, определяющем срок начала очередной критической работы. Конечно, максимум в каких-нибудь из формул (3.5) может достигаться не на одной, а на нескольких работах; соответственно на каждом шагу мы можем получить не один, а несколько критических путей.

Продемонстрируем алгоритм построения критического пути на материале той же структурно-временной табл. 3.1. Для этого, очевидно, надо задаться в этой таблице конкретными значениями времен (табл. 3.2).

Таблица 3.2

Имеем:

Время выполнения всего комплекса работ есть максимальное из всех времен

Найдем критические работы, начиная с последней Так как максимум в формуле (3.14) достигается для данная работа является критической. Она опирается на работы и ад Какая же из них является критической? Очевидно, а», так как максимум в формуле (3 13) приходится на Переходим к формуле (3 12) — в ней максимум приходится на значит, работа — критическая. Далее, аналогичным способом, просматривая максимумы в формулах (3.11) — (3.7), находим одну за другой все критические работы. Перечисленные в естественном порядке, они будут:

Таким образом, критический путь найден чисто формальным способом, без построения сетевого графика В табл 3.2 подчеркнуты все критические работы.

Совершенно аналогичным формальным способом могут быть определены и некритические дуги, и соответствующие им резервы