3.2. Общий алгоритм решения задачи

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

,

где n - число работ, после чего начинается пошаговое уменьшение (форсирование) времени выполнение отдельных работ и всего комплекса работ таким образом, чтобы удорожание на каждом шаге было минимально возможным. Общая структура алгоритма приведена на рис. 5.

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

Г раф:

Пути:

Сечения:

Рис. 6.

Таблица 4.

Параметры	Работы
	1	2	3	4	5
Di	12	13	5	21	9
di	2	10	2	13	6
CDi	25	16	8	32	20
Cdi	45	34	20	40	26

На рис. 7 приведены данные табл. 3 в виде зависимостей (3.3).

Для реализации алгоритма структуру сетевого графика представляют с помощью двух логических матриц: матрицы путей Р и матрицы минимальных сечений S. Путь – это множество последовательных работ, соединяющих первый и последний узлы сетевого графика. Минимальное сечение – это минимальное множество работ, удаление (размыкание) которых из графа рассоединяет начальный и конечный узлы сетевого графика. Сечение является минимальным в том смысле, что замыкание любой одной работы образует хотя бы один путь, связывающий начальный и конечный узлы.

Сечения приведены на рис. 6. Следует особо обратить внимание на то, что работы сечения, которые опираются только на предшествующие им работы того же сечения не принадлежат минимальному сечению. В примере (рис. 6) это работа а₃ в третьем минимальном сечении, в самом деле, если эта работа замкнута, то между начальной и конечной точкой сетевого графика нет ни одного замкнутого пути.

Матрица путей составляется следующим образом. Она имеет п столбцов по числу работ сетевого графика и т строк по числу путей.

Аналогичным образом составляется матрица минимальных сечений. В ней имеется также п столбцов и  строк по числу минимальных сечений.

В нашем примере (см. рис. 6) матрицы имеют следующий вид:

(3.9)

Алгоритм оптимизации начинается с определения вектора времен выполнения работ всех путей сетевого графика

(3.10)

Далее определяется время выполнения сетевого графика Т_СГ как наибольшее из _к

(3.11)

множество критических путей в виде логического вектора V:

(3.12)

Далее рассчитываются стоимости выполнения всех работ по формуле (3.3) и суммарная стоимость С_СГ

(3.13)

В нашем примере рассчитаем по формулам (3.4), (3.5) коэффициенты уравнение (3.3) (исходные данные в таблице 4) результаты в таблице 5.

Таблица 5

Коэффициенты	Работы
	1	2	3	4	5
аi	49	94	28	53	38
bi	2	6	4	1	2

На первом шаге оптимизации по формуле (16) рассчитаем:

откуда (17)

по формуле (3.3) С =25+16+8+32+20=101.

Здесь верхний индекс указывает номер шага оптимизации. Результат расчета представлен в виде первой (нижней) точки на графике зависимости (рис. 8)

Основная идея алгоритма состоит в выборе на каждом шаге наилучшего способа сокращения длительности выполнения сетевого графика, т.е. выбора минимального сечения для которого удорожание критических работ минимально. Совершенно очевидно, что вкладывая дополнительные средства в сокращение времени выполнения некритических работ просто бессмысленно, так как эти работы имеют резервы времени, и следовательно, нужно сокращать только критические работы. Но на критических путях обычно имеется по несколько работ. Какие же сокращать в первую очередь? Для минимального сечения можно дать другое определение, более ясно отражающее сущность метода оптимизации: это минимальное множество работ одновременное сокращение времени выполнения которых наверняка приводит к уменьшению времени выполнения сетевого графика. Фактически же следует сокращать только критические работы минимального сечения.

Для каждой работы показателем скорости удорожания является коэффициент b_i или угол наклона прямой (см. рис. 7). Чем меньше b_i (угол наклона), тем меньше удорожание на единицу сокращения времени.

Как показано стрелками в первой точке (рис. 8) рассматриваемого примера, если сокращать некритические работы а₂, а₃, а₅, то будет происходить удорожание без сокращения времени сетевого графика, следовательно, нужно сокращать время одной из двух критических работ а₁ или а₄; b₄<b₁, поэтому в первую очередь следует сокращать время выполнения работы а₄ (стрелки, показывающие изменение времени и затрат на рис. 8, параллельны зависимостям c_i=a_i - b_it_i, 3.1).

В общем случае суммарное удорожание работ j-го минимального сечения В_j на единицу сокращения времени выполнения сетевого графика равна

, (3.14)

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

. (3.15)

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

Если время выполнения сетевого графика можно сократить и найдено минимальное сечение с наименьшим удорожанием, то встает вопрос на сколько это время можно сократить. Время выполнения сетевого графика можно уменьшать до тех пор пока длительность одной из сокращаемых работ ни достигнет своего минимального значения (t_i=d_i) или появится новый критический путь. Сокращение времени δ определяется как меньшая величина минимального резерва времени на некритическом пути и минимально возможным уменьшением времени сокращаемых работ до нижней границы ОДР d_i:

(3.16)

здесь минимум по k берется по некритическим путям (kV) на которых нет сокращаемых работ, минимум по i берется по всем уменьшаемым работам, т.е. критическим работам минимального сечения с . Далее вычисляются новые значения времени сетевого графика

Т_СГ=Т_СГ – δ,

новые значения уменьшаемых работ

t_i=t_i - δ,

значения с_i по формуле (3.3) и С_СГ по формуле (3.13).

Для перехода к следующему шагу оптимизации остается определить изменяется ли множество критических путей и в зависимости от этого переход в блок-схеме алгоритма происходит к блоку 3 либо к блоку 4 (рис.5). При уменьшении длительности выполнения сетевого графика количество критических путей может увеличиться, если в меньшей из величин окажется , то k-й путь тоже станет критическим. Критический путь после уменьшения длительности выполнения работ может стать некритическим, если в минимальном сечении окажется две или более одновременно сокращаемые работы этого пути.

Если

, (3.17)

где k – номер критического пути,

j – номер сокращаемого минимального сечения,

то k-й путь становится некритическим. Иначе множество критических путей остается неизмененным и новый шаг оптимизации начинается с выбора нового минимального сечения (блок 5, рис 5.5), так как на предыдущем шаге в минимальном сечении появилась критическая работа, которую нельзя дальше уменьшить (t_i=d_i).

Рассмотрим применение описанного алгоритма к нашему примеру (рис. 6, 7, 8).

На первом шаге

Так как критический путь один величины совпадают. Как указывалось b₄<b₁, поэтому в первую очередь будем сокращать сечение j=2 (либо j=4) и работу а₄.

На какую величину δ можно сократить работу а₄? По формуле (3.13)

Таким образом, работу а₄ можно уменьшить на 7 единиц времени и при этом она не достигнет своего минимального значения d₄=13. Появляется новый критический путь k=3. Новые значения (точка 2 на рис. 8).

Второй шаг. Критические пути первой и третий. Пересечение минимальных сечений и критических путей (см. рис. 6) дают следующие значения коэффициентов удорожание:

откуда

сокращаемая работа а₁.

Сокращение времени :

Критическим путем теперь становится и второй путь k=2, т.е. после этого шага все пути и все работы сетевого графика становятся критическими. Новые значения (точка 3 на рис. 8):

Рис. 7

Третий шаг. Значение коэффициентов удорожания:

откуда

,

сокращаются работы а₄ и а_5.

Так как все пути критические, формула (3.16) упрощается.

.

Следовательно, работа а₄ достигает своего минимального времени выполнения t₄=d₄=13. Критические пути остаются прежними.

Новые значения (точка 4 на рис. 8):

Четвертый шаг. Так как критическая работа а₄ достигла своего наименьшего времени, минимальные сечения 2 и 4 , в которые входит эта работа, должны быть исключены из рассмотрения. Коэффициенты удержания остальных двух сечений равны

т.е. сокращаются работы а₁ и а₅.

Сокращение времени :

.

Так как обе работы а₁ и а₅ находятся на третьем пути

и третий путь становится некритическим. Остальные величины будут соответственно равны (точка на рис. 8):

Пятый шаг. Теперь и критическая работа а₅ достигла нижней границы времени, поэтому сокращать можно только работы первого минимального сечения:

т.е. сокращаются работы а₁ и а₂. Появился некритический путь к=3, но сокращаемая работа а₁ лежит на этом пути, поэтому  рассчитывается по упрощенной формуле:

Значения времен и стоимостей для точки 6 (рис. 8) таковы:

Пятый шаг оптимизации оказался последним, так как достигла нижней границы времени выполнения работа а₂ и не осталось ни одного минимального сечения, работы которого можно было бы сократить. В самом деле все работы второго критического пути (а₂ и а₅) достигли своей нижней временной границы 0и, следовательно, время выполнения сетевого графика уже нельзя уменьшить. Окончательные результаты расчета представлены на рис. 8 и табл. 6.

Таблица 6

№ п/п	Работы					ТСГ ССГ	1 2 3	Номера критических путей	Номер сокращаемого миним. сечения	Номер сокращаеьых работ	Сокращен. времени СГ
	t1 c1	t2 c2	t3 c3	t4 c4	t5 c5
1	12 25	13 16	5 8	21 32	9 20	33 101	33 22 26	1	2	4	7
2	12 25	13 16	5 8	14 39	9 20	26 108	26 22 26	1,3	1	1	4
3	8 33	13 16	5 8	14 39	9 20	22 116	22 22 22	1,2,3	2	4,5	1
4	8 33	13 16	5 8	13 40	8 22	21 119	21 21 21	1,2,3	3	1,5	2
5	6 37	13 16	5 8	13 40	6 26	19 127	19 19 17	1,2	1	1,2	3
6	3 43	10 34	5 8	13 40	6 26	16 151	16 16 14	1,2	-	-	-

В качестве оптимального примем решение в точке 3, для которой Т_СГ=22, С_СГ=116. Это решение является компромиссным между нормальным – наиболее длительным режимом (Т_СГ=33, С_СГ=101) и форсированным – наиболее дорогостоящим режимом (Т_СГ=16, С_СГ=151).

Сравнение этих режимов показывает, что нормальный режим всего на 13% дешевле и в полтора раза длительней, форсированный режим при сокращении длительности на 27% требует увеличения затрат на 30%. Окончательное решение остается за руководителем комплекса работ.

Для выбранного нами режима на рис. 9 приведен календарный план; составление его не представляет труда, так как все пути и все работы сетевого графика являются критическими.