8.5. Оптимизационные задачи сетевого планирования по стоимости

Под стоимостью выполнения работы будем подразумевать лишь прямые затраты. Пусть для каждой работы имеются следующие данные: d_ij – минимальная продолжительность (срочный режим выполнения), которой соответствуют наибольшие затраты – C_ij и нормальная (небольшая) продолжительность – D_ij , которой соответствуют наименьшие затраты – c_ij. Предположим, что затраты на выполнение отдельных работ находятся в обратной зависимости от продолжительности их выполнения:

. (8.5.1)

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

а) Оптимизация проекта при нефиксированной величине критического пути

Пусть задан сетевой график проекта и известны продолжительность каждой работы и стоимость ее выполнения в нормальном (D_ij ,c_ij) и срочном (d_ij,C_ij) режиме работы. Если все работы выполняются в нормальном режиме, то критический срок будет наибольшим, а стоимость выполнения проекта – наименьшей. Необходимо сократить критический срок до некоторого минимально возможного значения при наименьшем возрастании стоимости выполнения проекта.

Алгоритм оптимизации комплекса работ по стоимости

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

Общий шаг. 1. Среди критических работ найти работу, для которой КДЗ наименьший. Если эта работа является общей для всех критических путей или, если критический путь один, то она и подлежит сокращению. Если же найденная работа не является для критических путей общей, однако, пути имеют одну или несколько общих работ, то на каждом из них найти работу с наименьшим КДЗ, просуммировать КДЗ этих работ и сравнить с КДЗ той из общих работ, для которой он наименьший. Если сумма КДЗ работ не больше КДЗ общей работы критических путей, то все эти работы подлежат сокращению. Если же, наоборот, сумма КДЗ работ больше КДЗ общей работы, то сокращению подлежит общая для критических путей работа. Если критические пути не имеют общих работ, то на каждом из них находится работа с наименьшим КДЗ.

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

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

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

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

Рис. 8.5.1

Таблица 8.5.1

Работа Параметры	(1,2)	(1,3)	(1,4)	(2,4)	(3,4)	(4,5)
Dij	6	7	2	4	4	4
dij	3	2	1	3	3	2
cij	90	50	42	30	70	60
Cij	180	100	50	40	82	90

Решение.

По формуле (8.5.1) определим коэффициенты дополнительных затрат для каждой работы (КДЗ) h_ij и занесем в таблицу 8.5.2:

Таблица 8.5.2

Работа КДЗ	(1,2)	(1,3)	(1,4)	(2,4)	(3,4)	(4,5)
hij	30	10	8	10	12	15

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

Рис. 8.5.2

Таким образом,

Критический путь определяют работы: (1,3), (3,4), (4,5).

Затраты на реализацию данного комплекса работ составят:

Среди критических работ определяем, что

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

Рис. 8.5.3

В данном случае

Критический путь определяют работы: (1,2), (2,4), (4,5).

Затраты на реализацию комплекса работ составят:

Среди критических работ определяем, что

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

3

Рис. 8.5.4

В данном случае

Критический путь определяют работы: (1,2), (2,4), (4,5).

Затраты на реализацию комплекса работ составят:

Среди критических работ определяем, что

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

Рис. 8.5.5

В данном случае

Критический путь определяют работы: (1,2), (2,4), (4,5).

Затраты на реализацию комплекса работ составят:

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

2

3

3

0

3

3

1

4

5

8

0

0

2

6

6

2

8

0

0

0

2

3

4

2

2

0

Рис 8.5.6

В данном случае

Получены два критических пути: (1,2), (2,4), (4,5) и (1,3), (3,4), (4,5).

Затраты на реализацию комплекса работ составят:

Среди критических работ КДЗ является наименьшим у работ (1,3) и (2,4): Работа (4,5) является общей для обоих критических путей. Так как , то сокращению подлежала бы продолжительность общей работы (4,5), но ее сокращать более нельзя. При сокращении продолжительности работы (3,4) t_кр не изменится, а стоимость проекта возрастет.

Вывод. Таким образом, можно сократить срок выполнения всего проекта до 8 ед. времени, при этом стоимость выполнения проекта увеличится с 342 ден. ед. до 522 ден. ед.

б) Минимизация стоимости проекта при фиксированной его продолжительности

Пусть задан сетевой график проекта . Известны продолжительности выполнения работ и их стоимость в срочном режиме (d_ij,C_ij). Для них определены критическое время t_кр и стоимость выполнения проекта С. Стоимость при этом является максимальной. Предполагается, что коэффициенты дополнительных затрат для каждой работы известны. Ставится задача минимизации стоимости проекта при фиксированном сроке выполнения проекта за счет увеличения времени выполнения отдельных работ. Критическое время t_кр может быть меньше заданного срока или равно ему. Если = t_кр, то оптимизация возможна только за счет резервов некритических работ, если > t_кр, то за счет всех работ проекта. После оптимизации все работы будут критическими, так как их продолжительности будут достигать наибольших возможных значений. Ни одно событие, ни одна работа не будут иметь резерва. Такой план можно назвать безрезервным. Ранние и поздние сроки свершения событий здесь совпадают, а времена начала и окончания работ совпадают со сроками свершения событий. Поэтому за неизвестные переменные задачи можно принять сроки свершения событий t_i. Тогда продолжительность работы в оптимальном плане составит: . Стоимость работы за время ее выполнения будет определяться формулой:

.

Математическая модель задачи следующая:

(8.5.2)

(8.5.3)

(8.5.4)

. (8.5.5)

Пример 8.5.2. Задан сетевой график (рис. 8.5.7) комплекса работ.

3

1

5

2

4

Рис. 8.5.7

Известны продолжительности выполнения работ , стоимости выполнения в срочном режиме , КДЗ – (таблица 8.5.3).

Определено критическое время выполнения комплекса работ:

Таблица 8.5.3

Работа Параметры	(1,2)	(1,3)	(2,4)	(3,4)	(3,5)	(4,5)
dij	3	4	6	4	2	1
Cij	55	70	45	90	30	50
hij	4	7	5	9	2	6

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

Решение.

Заметим, что стоимость выполнения комплекса работ в срочном режиме составляет

Математическая модель задачи, на основании (8.5.2) – (8.5.5), имеет вид:

После решения задачи на ПЭВМ симплекс-методом получим:

Продолжительность выполнения работ после проведения оптимизации составит:

Вывод. При увеличении срока выполнения комплекса работ с 10 до 13 ед. времени, стоимость уменьшается с 340 до 275 ден. ед. При этом, продолжительность выполнения работы (2,4) увеличивается с 6 до 9 ед. времени, работы (3,4) – с 4 до 8, работы (3.5) – с 2 до 9.