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

Задачи оптимизации:

1. Сокращение стоимости проекта за счет перераспределения ресурсов;

2. Выравнивание коэффициентов напряженности для снижения вероятности срыва выполнения в заданные сроки;

3.Сокращение продолжительности критического пути за счет пересмотра продолжительности работ или пересмотра сетевого графика.

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

Методы решения задач в оптимизации:

1.Перераспределение ресурсов (временных, трудовых, энергетических, материальных) между работами: из зон менее напряженных в зоны, объединяющие наиболее напряженные работы;

2. Сокращение трудоемкости части работ критического пути за счет передачи на другие пути, имеющие резервы времени;

3. Параллельное выполнение критических работ;

4. Пересмотр (изменение) топологии сетей, состава работ и структуры сети.

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

 

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

Стоимость»

Для оптимизации сетевого графика используется частная оптимизация (уменьшение стоимости проекта). При использовании метода «время - стоимость» предполагают, что уменьшение продолжительности работ пропорционально возрастанию ее стоимости. Каждая работа (i, j) характеризуется продолжительностью t (i, j), которая может находиться в пределах

 , где

a (i, j) - минимальная возможная продолжительность работы (i, j);

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

t (i, j) - наиболее вероятная продолжительность работы (i, j).

При этом стоимость C (i, j) работы (i, j) заключена в границах:

С_max - минимальная стоимость работы, оптимистическая оценка стоимости работы, стоимость при минимальных сроках выполнения работы;

C_min - максимальная стоимость работы, пессимистическая оценка стоимости работы, стоимость при максимальных сроках выполнения работы.

Далее при оптимизации вычисляют:

h (i, j) - коэффициент увеличения затрат от ускорения работы (i, j);

C (i, j) - наиболее вероятная стоимость проекта

Таким образом, увеличение продолжительности работ может привести к уменьшению стоимости проекта, но продолжительность каждой работы целесообразно увеличить на такую величину, чтобы не изменить ранние сроки наступления всех событий сети. Это означает с одной стороны - продолжительность каждой работы можно увеличить на свободный резерв времени, с другой - эта продолжительность не должна превышать предельно допустимую продолжительность b (i, j).

Оптимальную продолжительность работы можно найти на основе соотношения:

 или

где ;.

В этом случае стоимость выполнения работы находят по формуле:

Оптимизированный проект имеет суммарную стоимость:

 

Коэффициенты напряженности

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

 

Где t (L_max) - продолжительность отрезка максимального пути, проходящего через данную работу;

t ^' _кр – продолжительность отрезка максимального пути, совпадающего с критическим путем;

t _кр – продолжительность критического пути.

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам:

К_н(i, j)>0,8 – критическая зона;

0,6≤К_н≤0,8 – подкритическая зона;

К_н<0,6 – резервная зона.

Чем ближе коэффициент напряженности К_н(i, j) к 1, тем сложнее выполнить данную работу в установленные сроки. Чем ближе К_н(i, j) к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.

 

 

СЕТЕВОЕ ПЛАНИРОВАНИЕ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ

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

При определении временных параметров сетевого графика до сих пор предполагалось, что время выполнения каждой работы точно известно. Допустим, продолжительность работы t (i, j) заранее неизвестна, т.е. является случайной величиной и задается законом распределения. Следовательно, характеризуется своими числовыми характеристиками:

(i, j) – среднее значение или математическое ожидание;

σ² (i, j) – дисперсия (мера отклонения от среднего значения).

В этих условиях полагаем:

§ закон распределения непрерывный;

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

§ закон распределения имеет две точки пересечения с осью абсцисс;

§ закон распределения обладает положительной асимметрией (максимум кривой смещен влево относительно медианы).

Этим свойством удовлятворяет β – распределение.

Для определения числовых характеристик (i, j) и σ² (i, j) на основе экспертных оценок задают величины:

1. t_onm (i, j)= a (i, j) – оптимистическая оценка, т. е. продолжительность работы при благоприятных условиях;

2. t_nec (i, j)= b (i, j) – пессиместическая оценка, т.е. продолжительность работы при неблагоприятных условиях;

3. t _нв (i, j)= { t (i, j) } – наиболее вероятная оценка.

В этом случае для β – распределения можно получить соотношения:

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

На основании этой теоремы можно утверждать, что продолжительность пути имеет нормальный закон распределения со средним значением  и дисперсией

где

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

1. Оценка вероятности того, что срок выполнения проекта t _кр не превзойдет заданного директивного срока T находится по формуле:

2. Обратная задача: определение максимального срока выполнения проекта T, который возможен с заданной надежностью β.

z_β – нормированное отклонение случайной величины, определяемой функцией Лапласа 𝜱 (z_β)= β.

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

Содержание лабораторного практикума

1. Выбрать сетевой график согласно выданному варианту;

2. Провести проверку соответствия сетевого графика требованиям;

3. Упорядочить сетевой интерфейс;

4. Определить критический путь (критические пути) сетевого графика методом простого перебора и графическим методом;

5. Расчитать временные характеристики событий и работ сетевого графика;

6. Провести оптимизацию сетевого графика по методу «Время – Стоимость»

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

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

 

Требования к выполнению лабораторных работ

1. Вариант работы выдается студенту преподавателем.

2.Лабораторная работа должна содержать:

· Титульный лист;

· Содержание лабораторной работы;

· Выполненные задания с подробными расчетами и формулами;

· Заключение;

· Список использованных источников.

3. Лабораторная работа сдается на бумажном носителе.

 

Варианты заданий

1.

 

 

2.