Лекция 21. Анализ и оптимизация сетевого графика

План.

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

21.2. Сетевое планирование в условиях неопределенности.

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

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

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

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

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

- параллельное выполнение работ критического пути;

- просмотр топологии сети, изменение состава работ и структуры сети.

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

Сетевое планирование в условиях неопределенности

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

Практически во всех системах СПУ априори принимается, что распределение продолжительности работ обладает тремя свойствами:

а) непрерывностью;

б) унимодальностью, то есть наличием единственного максимума у кривой распределения;

в) двумя точками пересечения кривой распределения с осью Ox, имеющими неотрицательные абсциссы.

Установлено, что распределение продолжительности работ обладает положительной асимметрией, то есть максимум кривой смещен влево относительно медианы (линии делящей площадь под кривой на две равные части). Распределение, как правило, более круто поднимается при удалении от минимального значения t и полого опускается при приближении к максимальному значению t.

Простейшим распределением с подобными свойствами является известное в математической статистике -распределение. Анализ большого количества статистических данных (хронометраж времени реализации отдельных работ, нормативные данные и т.д.) показывают, что -распределение можно использовать в качестве априорного для всех работ (рис. 21.1).

Рисунок 21.1 - -распределение вероятностей продолжительности работ

Для определения числовых характеристик и этого распределения для работы (i,j) на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки:

а) оптимистическую оценку - продолжительность работы (i,j) при самых благоприятных условиях;

б) пессимистическую оценку - продолжительность работы (i,j) при самых неблагоприятных условиях;

в) наиболее вероятную оценку - продолжительность работы (i,j) при нормальных условиях.

Предположение о -распределении продолжительности работы (i,j) позволяет получить оценки ее числовых характеристик:

;

.

Обычно специалистам сложно оценить наиболее вероятное время выполнения работы . Поэтому в реальных проектах используется упрощенная (и менее точная) оценка средней продолжительности работы (i,j) на основании лишь двух задаваемых временных оценок и :

.

Зная и , можно определять временные параметры сетевого графика и оценивать их надежность.

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

;

.

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

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

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

Полагая случайной величиной, имеющей нормальный закон распределения, получим

,

где Ф(z) – значение интеграла вероятностей Лапласа, ; - среднее квадратическое отклонение длины критического пути: , а , определяются по приведенным выше формулам.

Если вероятность мала (меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходимо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т.п. Если значительна (больше 0,65), то с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.

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