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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

t_нов(i ,j) = t(i , j) - h(i , j) X ( 4.5 )

Величина h(i, j), равная тангенсу угла а наклона аппроксимирующей прямой в диапазоне a(i,j), b(i,j) (см. Рис. 4.3), показывает затраты на ускорение, то есть дополнительные ресурсы, необходимые для ускорения работы на единицу времени (день).

Рис.4.3. Зависимость времени работы от дополнительных затрат.

Под ресурсами можно понимать деньги, людей, технику. На Рисунке 4.3 видно, что используемая линейная зависимость время/затраты справедлива в некотором диапазоне; существует асимптота слева (затраты, при которых работа никогда не будет сделана) и справа: минимальное время выполнения работы при любых затратах. Ограничения затрат обозначены Х– (сколько можно вычесть) и Х+ (сколько можно добавить). Эти величины могут отличаться по модулю.

Дополнительные ресурсы можно привлечь извне, а можно перераспределить внутри проекта, перебросив с малонапряжённых работ на критические.

Далее приведён пример сетевого графика, соответствующего выполнению некоего проекта. Кругами обозначены события, стрелками – работы. Расположение кружков соответствует времени наступления событий, проекции стрелок на временную ось пропорциональны временам работ, резервы времени обозначены пунктиром.

Рис.4.4. Сетевой график до (А) и после оптимизации (Б).

Обычно оптимизацию плана комплекса работ проводят после нахождения критических работ, напряжённостей работ и ресурсов, которые можно перебросить с некритических работ на критические. В данном случае критический путь 1=>4=>6=>7=>10, соответственно новое время выполнения комплекса работ

t_{крит.нов.}= t_1нов+t_4нов+t_6нов +t_7нов +t_10нов. ( 4.6 )

В данной работе предлагается принципиально новая методика оптимизации сетевого графика, основанная на использовании итерационной градиентной процедуры (метод Ньютона или аналогичный), включённой в сервис “Поиск решения” (Solver) электронных таблиц Excel. Исходные данные, соответствующие сетевому графику Рис.4.4 А, и расчётные формулы размещаются в Таблице 4.2. t новое работ вычисляется по формуле (4.5), в данном примере h=0,1. Без дополнительных затрат tкрит=32. Целевая функция tкрит, её надоминимизировать, изменяя ячейки вектора Х. Ограничения:

X >= X-, X <= X+, SХ = 0,

то есть ресурсы перераспределяются внутри проекта, дополнительных затрат нет. В данном примере ограничения затрат X– = –50, X+ = 50. В реальных проектах ограничения и коэффициенты затрат на ускорение работ h устанавливаются экспертами для каждой работы отдельно, в таблице появляются ещё три столбика-вектора: h, X-, X+. Окно “Поиска решения” представлено на Рис.4.5.

Таблица 4.2.

Рис.4.5. Окно “Поиска решения”

В результате работы “Поиска решения” получим результат:

Таблица 4.3.

В результате максимальных вложений в критические работы путь

1=>4=>6=>7=>10 сократился до 12, но другие пути удлинились, и время выполнения проекта по пути 1=>2=>5=>7=>10 удлинилось до 35,31. Очевидно, в ограничения "Поиска решения" надо вводить недопустимость удлинения других путей по сравнению с критическим. Но даже в нашей простой задаче это приводит большому количеству ограничений, так как надо предусмотреть все возможные пути. Поэтому мы предлагаем принципиально новую технологию расчёта, основанную на понятии опорных событий, а не опорных работ, как обычно, и вычислении времён наступления событий.Опорные события – это события, непосредственно предшествующие данному событию, и связанные с ним стрелками-работами. В таблице 4.4 представлены результаты расчётов, а на Рисунке 4.4 Б соответствующий сетевой график.t новые событийвычисляются в последних четырех столбцах таблицы. Если имеется только одно опорное событие, то время наступления события складывается из времени наступления опорного события и времени соответствующей работы. Если опорных событий несколько, то время наступления события вычисляется по всем опорным событиям в трёх последних столбцах, и максимум по этим ячейкам принимается за t новое события.Если для каких-либо событий опорных событий больше, то и количество соответствующих столбцов должно быть больше.Дополнительные ограничения: время критического пути, вычисленное по формуле ( 4.6 ), должно быть больше или равно времён наступления конечного события 10, вычисленных в последних трёх ячейках соответствующей строки. Окно “Поиска решения” представлено на Рисунке 4.6, результаты расчётов – в Таблице 4.4. Полученный результат:tкрит=27,168 ,остальные пути, приводящие к событию 10, то есть к окончанию проекта, имеют ту же длину.

Данная задача и технология её решения являются нелинейными. Это может привести к появлению различных планов Х, в том числе неоптимальных, и зависимости результатов от начальных значений Х.

Рис. 4.6. Окно “Поиска решения”

В частности, коэффициент ускорения h для всего проекта (0,0315) оказался втрое меньше h для каждой работы в отдельности (0,1). Этот результат был получен последовательным изменением SХ в параметрах “Поиска решения”. Соответствующий график представлен на Рисунке 4.7.

Рис.4.7. Изменение продолжительности проекта t в зависимости от дополнительных ресурсов SХ

Таблица 4.4.

Таблица 4.5.

Возможна другая постановка задачи: вычислить и минимизировать количество дополнительных ресурсов SХ для достижения заданной величины tкрит.В этом случае целевой ячейкой “Поиска решения” становится SХ, и устанавливается ограничение t крит. В примере, приведённом в Таблице 4.5 , установлено tкрит=20. Расчёты показали, что это достижимо при дополнительном вложении 237,17 единиц ресурсов. Интересно, что сохраняется линейная зависимость t(SХ), что видно на Рисунке 4.8 .

Рис.4.8. Изменение продолжительности проекта t в зависимости

от дополнительных ресурсов SХ .

УПРАЖНЕНИЯ

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

4.1. Сделать деревянный ящик (работу выполняет один чело­век). Разместить доски в соответствии с размерами ящика (15 мин); разрезать доски (12 мин); склеить части ящика (40 мин); прибить к крышке ящика петли (8 мин); подождать, пока ящик высохнет, и вытереть его (15 мин); петли (с крышкой) прибить к ящику (10 мин).

4.2. Заменить колесо машины (работу выполняют два чело­века). Достать из багажника домкрат и инструменты (40 с); снять диск с колеса (30 с); освободить колесо (50 с); поставить домкрат под машину (26 с); поднять машину (20 с); из багажника взять запасное колесо (25 с); снять гайки и колесо (20 с); установить запасное колесо на ось (10 с); завинтить (не сильно) гайки на оси (15 с); опустить машину и собрать домкрат (25 с); поставить дом­крат обратно в багажник (10 с); завинтить гайки на оси до конца (12 с); положить плохое колесо и инструменты в багажник (40 с); поставить на место диск колеса (10 с).

4.3. Придумайте проекты и нарисуйте для них сетевые графики:

.а) строительство особняка; б) открытие мастерской (ювелирной и т.д);

в) полёт на Марс; г) экспедиция на полюс; г) ремонт квартиры;

д) подготовка к сессии, и т.п.

Рис. 4.9. Сетевой график

4.4. Для сетевого графика (Рис. 4.9) найти все полные пути, критический путь; рассчитать ранние и поздние сроки свершения событий, начала и окончания работ; определить резервы времени полных путей и событий, резервы времени (полные, частные ре­зервы первого вида, свободные и независимые) работ и коэффи­циенты напряженности работ.

4.5. Как изменится срок выполнения проекта ( Рис. 4.9), резервы времени работ и событий, коэффициенты напряженности работ, если увеличить продолжительность работы t(9, 10) на ве­личину: a) R_n(9, 10); б) R₁(9, 10); в) R_c(9, 10); г) R_н(9, 10)?

4.6. Как изменится срок выполнения проекта ( Рис. 4.9), резервы времени работ и событий, коэффициенты напряженности работ, если продолжительность каждой работы t(i, j)увеличить на величину: : a) R_n(9, 10); б) R₁(9, 10);

в) R_c(9, 10); г) R_н(9, 10)? Для случаев б), в) и г) найти все критические пути сетевого графика.

4.7.В таблице 4.6 указаны оценки времени выполнения работ сетевого графика, данные ответственными исполнителями и экс­пертами.

Таблица 4.6

Необходимо: а) построить сетевой график; б) определить сред­ние (ожидаемые) значения продолжительности работ; в) опреде­лить критический путь и его длину. Полагая, что продолжитель­ность критического пути распределена по нормальному закону, найти: а) вероятность того, что срок выполнения комплекса работ не превысит 17 суток; б) максимальное значение продолжитель­ности выполнения проекта, которое можно гарантировать с на­дежностью 0,95.

4.8.По данным таблицы 4.7 необходимо: 1) построить сетевой график; 2) определить критический путь и стоимость проекта при минимально возможных значениях продолжительности всех ра­бот; 3) найти минимальную стоимость проекта при том же сроке его завершения; 4) рассчитать и построить оптимальную зависи­мость стоимости проекта от продолжительности его выполнения, используя в качестве первоначального варианта сетевого графика:

а) план с максимальными значениями продолжительности всех работ и соответственно минимальной стоимостью проекта;

б) план, полученный в результате выполнения п.З.

Таблица 4.7

4.9. Сократите время выполнения проектов, сетевые графики которых представлены на Рисунке 4.10 без привлечения дополнительных ресурсов (SХ=0). Для всех работ h=0,1, X- = -60, X+ = 65. Вычислите h_T =DTпроекта/SХ. Сколько надо затратить ресурсов, чтобы уменьшить время выполнения каждого проекта до 50? Составьте соответствующие планы X,DT .

Рис.4.10. Сетевые графики

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

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

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

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

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

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

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

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

Рис.4.11. b-распределение

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

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

Зная t (i, j)и s²(i, j), можно определять временные параметры сетевого графика и оценивать их надежность.

Так, при достаточно большом количестве работ, принадлежа­щих пути L, и выполнении некоторых весьма общих условий можно применить центральную предельную теорему Ляпунова, на основании которой можно утверждать, что общая продолжитель­ность пути Lимеет нормальный закон распределения со средним значением t (L),равным сумме средних значений продолжитель­ности составляющих его работ t(i, j)и дисперсией s²(L),равной сумме соответствующих дисперсий s²(i, j):

s_кр — среднее квадратическое отклонение длины критического пути:

a tcp кр, s²_кр определяются по формулам (4.7) и (4.8).

Если вероятность Р(t_кр < Т)мала (например, меньше 0,3), то опасность срыва заданного срока выполнения комплекса велика, необходи­мо принятие дополнительных мер (перераспределение ресурсов по сети, пересмотр состава работ и событий и т.п. — об этом речь пойдет дальше). Если Р(t_кр< Т)значительна (например, более 0,8), то, очевидно, с достаточной степенью надежности можно прогнозировать выполнение проекта в установленный срок.

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

где z_b — нормированное отклонение случайной величины, опре­деляемое с помощью функции Лапласа Ф(zb)= b

T=61+z(0,95)*4,1=61+l,96*4,1=69, т.е. с на­дежностью 0,95 срок выполнения проекта не превысит 69 суток.

Следует отметить, что для данной сети мы можем найти лишь весьма приближенные оценки Р(t_кр< Т)и Т, ибо на основании теоремы Ляпунова вывод о нормальном законе распределения случайной величины t_кр правомерен лишь для достаточно большо­го числа критических работ, а в рассматриваемой сети их всего 6.

Однако приведенный метод расчета имеет принципиальные недостатки оценки параметров даже сложных сетей с большим количеством работ. Дело в том, что на практике нередки случаи, когда дисперсии s²(L) длин некритических (но близких к крити­ческому) путей существенно больше, чем s²_кр. Поэтому при из­менении ряда условий в данном конкретном комплексе работ возможен переход к новым критическим путям, которые в расчете не учитываются.

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

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

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