Оптимизация сетевого графика

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

сокращения длительности критического пути;
выравнивания коэффициентов напряженности работ;
рационального использования всех видов ресурсов.

Сокращение продолжительности работ, находящихся на критическом пути, достигается за счет:

перераспределения всех видов ресурсов из зон менее напряженных в зоны, объединяющие наиболее напряженные работы. К ресурсам относятся:

а) временные – при использовании ресурсов времени некритических работ;

б) трудовые;

в) материальные;

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

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

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

Поэтому выделяют задачу:

частной оптимизации, когда минимизируют время выполнения комплекса работ при заданной его стоимости (например: строительство «под ключ»); или минимизируют стоимость комплекса работ при заданном времени выполнения проекта;
комплексной оптимизации, когда определяют оптимальное соотношение стоимости и сроков выполнения проекта.

Условные обозначения:

A(i,j) – минимально возможное время выполнения работы;

b(i,j) – нормальная продолжительность работы;

С_min(i,j) – стоимость работы при нормальной ее продолжительности;

С_max(i,j) – стоимость работы при минимальной продолжительности работы.

тогда

Изменение стоимости работы при сокращении ее продолжительности определяется:

где h(i,j) – дополнительные затраты, связанные с ускорением выполнения работы.

Частная оптимизация

При использовании метода «время-стоимость» предполагают, что снижение сроков выполнения работ пропорционально возрастанию их стоимости.

Наиболее часто используется следующий алгоритм оптимизации:

продолжительность каждой работы, имеющий свободный резерв времени Rc(i,j), увеличивает до тех пор, пока не будет почерпан резерв Rc(i,j) или пока не будет достигнуто верхнее значение продолжительности работы b(i,j);
рассчитывают уменьшение (увеличение) стоимости проекта:

Для проведения оптимизации кроме продолжения работ t(i,j) необходимо знать их граничные значения a(i,j), b(i,j), а также показатели затрат на ускорение работ k(i,j). При этом продолжительность каждой работы t(i,j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние ожидаемые сроки наступления всех событий сети, т.е. на величину Rc(i,j).

Условные обозначения:

A(i,j) – минимально возможное время выполнения работы;

b(i,j) – нормальная продолжительность работы;

Сmin(i,j) – стоимость работы при нормальной ее продолжительности;

Сmax(i,j) – стоимость работы при минимальной продолжительности работы.

Тогда

Изменение стоимости работы при сокращении ее продолжительности определяется:

где h(i,j) – дополнительные затраты, связанные с ускорением выполнения работы.

Например:

провести частичную оптимизацию сетевого графика (включаются только работы, имеющие резервы)

№ п/п	Работа	Продолжительность работы, сутки	Свободный резервR_c(i,j).	Стоимость работV(i,j).	h(i,j)	Уменьшение стоимости проекта	Продолжительность работы после оптимизации
	(0,5)							5∙8=40	14=9+5
	(1,4)							4∙4=16	10=6+4
	(1,3)							1∙12=12	5=4+1
	(2,7)							4∙6=24	7=3+4
	Итого

Первоначальная стоимость равна сумме стоимости всех работ, включая работы не имеющие резервов: С=1216(у.е.), в т.ч. стоимость работ, имеющих резервы, равна 694 у.е.

Тогда возможное изменение стоимости проекта при использовании свободного резерва составит 293 у.е., и стоимость после частной оптимизации составит:

Построим новый сетевой график после частной оптимизации.

После оптимизации появились новые критические пути t_kp=61 (сутки):

Всего 28 путей из 64.

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

Итак, в результате оптимизации проект может быть выполнен в срок 61 сутки при минимальной его стоимости 923 у.е.

Комплексная оптимизация

Если необходимо в процессе оптимизации сократить сроки выполнения проекта, то стоимость работ возрастает. В таким случае определяют оптимальное соотношение между стоимостью проекта С и продолжительностью его выполнения t=t_kp. Для этого необходимо:

1. Найти все полные пути сетевого упорядоченного графика и выделить критический путь;

2. Определить максимально возможные величины уменьшения продолжительности работ;

3. Из работ критического пути выбирают работу, имеющую наименьший коэффициент затрат на ускорение k(i,j);

4. Сокращают продолжительность работы, определенной в п.3, на величину

5. Определить увеличение стоимости выполнения проекта и новую стоимость

6. Определяют новые длины всех полных путей, выделяют новые критические пути;

7. Реализуют указанный алгоритм с п.2 по п.6 до тех пор, пока не будут исчерпаны все резервы;

8. Строят график зависимости стоимости проекта C(t) от продолжительности его выполнения.

Например:

С помощью графика возможно определить:

минимальную стоимость проекта при любом возможном сроке его выполнения;
предельную продолжительность выполнения проекта при заданной его стоимости;
дополнительные затраты, связанные с сокращением сроков выполнения проекта (сокращение срока выполнения проекта с 40 до 30 дней потребует дополнительных затрат 20 у.е. (200-180=20))

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

продолжительность каждой работы должна находиться в пределах:

продолжительность любого полного пути не должна превышать установленного срока выполнения проекта.

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

максимальное использование ресурсов:

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