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

Практически во всех системах СПУ априори принимается, что распределение продолжительности работ обладает тремя свойст­вами: а) непрерывностью; б) унимодальностью, т.е. наличием единственного максимума у кривой распределения; в) двумя точ­ками пересечения кривой распределения с осью Ох, имеющими неотрицательные абсциссы.

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

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

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

Для определения числовых характеристик Ї (/, у), и ст2(/, у) этого распределения для работы (/, у) на основании опроса ответ­ственных исполнителей проекта и экспертов определяют три вре­менные оценки (рис. 14.10):

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

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

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

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

Т Л- + 4/„ в и, Л + 1П(І,Л . „А 1Ч

Следует отметить, что обычно специалистам сложно оценить наиболее вероятное время выполнения работы /„„(/, у). Поэтому в реальных проектах используется упрощенная (и менее точная) оценка средней продолжительности работы (/, у) на основании лишь двух задаваемых временных оценок г0(/, у) и /п(/, у): align=left> (14.23)

J (/, у) -2'o(U) + 3/n(/,y)

Зная I (/', у) и ст2(/, у), можно определять временные параметры сетевого графика и оценивать их надежность.

Так, при достаточно большом количестве работ, принадлежа­щих пути Ь, и выполнении некоторых весьма общих условий можно применить центральную предельную теорему Ляпунова, на основании которой можно утверждать, что общая продолжитель­ность пути I имеет нормальный закон распределения со средним значением 1 (£), равным сумме средних значений продолжитель­ности составляющих его работ I (/, у) и дисперсией а2(Ь), равной сумме соответствующих дисперсий а2(г, у):

(14.24)

(14.25)

Предположим, что сетевой график на рис.

(14.23) , и известны все дисперсии ст2(/, у), вычисленные по фор­муле (14.22).

Следует отметить, что и в этом случае временные параметры сетевого графика — длина критического пути, ранние и поздние сроки свершения событий, резервы времени событий и работ И Т.Д. — будут такие же, как и найденные в разд. 14.5. Но при этом необ­

ходимо учесть, что эти параметры, представленные в табл. 14.2 и

14.3, теперь будут являться Средними значениями соответствующих случайных величин: средней длиной критического пути I кр, сред­ним значением раннего срока наступления события 1 р(г), средним значением полного резерва времени работы Лп (/, у) и т.п.

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

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

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

рассмотрим анализ и оптимизацию календарных сетей, в которых заданы только оценки продолжительности работ.

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

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

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

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

■ (14.29)

кр ~ *кр

где ?(£тах) — продолжительность максимального пути, прохо­дящего через работу (г, у);

*кр — продолжительность (длина) критического пути;

I кр ~ продолжительность отрезка рассматриваемого пути, сов­падающего с критическим путем.

Формулу (14.29) можно легко привести к виду

(14.30)

'кр " кр

где Лп(/, у) — полный резерв времени работы (/, у).

Коэффициент напряженности Аг„(/, у) может изменяться в пре­делах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути).

14.4. Найти коэффициент напряженности работы (1, 4) для сетевого графика (рис. 14.6).

Решение. В разд. 14.5 мы установили, что длина критиче­ского пути 1^—61 (сутки), а максимальный путь, проходящий через работу (/, 4) — путь Ц 0-+1->4-*6-+9-+10-+11 — имеет про­должительность /(1тах)=/(14)=49 (суток). Максимальный путь Ц совпадает с критическим (см. рис. 14.6) на отрезке 6-+9-+10-+П продолжительностью /кр= 13+6+13=32 (сутки). Используя формулу^

(14.29) , найдем

49 - 32 17

ВД 4) =~-~ = — * 0,59.

61-32 29

Или иначе: зная полный резерв работы Яп(1, 4)= 12 (см рис. 14.3), по формуле (14.30) находим

АГ"аппроксимацию по прямой (см. рис. 14.12), можно легко найти изменение стоимости работы Лс (/, у) при сокращении ее продолжительности на величину

Ас (/, у)=[/!>(/, у)~/ (/, Л]Ш, у). (14.32)

Величина А(/, у), равная тангенсу угла а наклона аппроксими­рующей прямой (см. рис. 14.12), показывает затраты на ускорение

И Исследование операций в экономике

работы (/, у) (по сравнению с нормальной продолжительностью) на единицу времени:

/»(/, у) = 18 а =£та|М2^тМ. (14.33)

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

С = 5>(/,у), (14.34)

и

уменьшится на величину

С = 1Ас(/,у) = 1:[А(/,у)-/(/,у)]А(/,У). (14.35)

и и

Для проведения частной оптимизации сетевого графика кроме продолжительности работ / (/, у), необходимо знать их граничные значения а (/, у) и Ь (/, у), а также показатели затрат на ускорение работ Л (/, у), вычисляемые по формуле (14.33). Продолжитель­ность каждой работы / (/, у) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного ре­зерва времени Яс (/,/).

^ 14.15. Провести частную оптимизацию сетевого графика (рис. 14.6). Граничные значения продолжительностей работ а (/,у) и Ь (/,у), их стоимости с(/, у), коэффициенты затрат на ускорение работ Л (/,у) приведены в табл. 14.4.

Решение. Свободные резервы времени работ Д.

Стоимость первоначального варианта сетевого графика или плана по формуле (14.34) равна сумме стоимостей всех работ (включая работы, не имеющие резервов и не включенные в табл. 14.4):

О694+50+45+...+35+Ю=1216 (усл.руб.).

Стоимость нового плана равна С-ДС=1216-293=923 (усл.руб.), г.е. уменьшилась почти на 25%. Новый оптизированный сетевой рафик представлен на рис. 14.13. Нетрудно убедиться в том, что Появились новые критические пути длиной 'кр =61 (сутки), на­пример: 0-+1-*3-*4-*7-+10-+П; 0->3-+5->8-*9->11', 0-+1-*3-*4~* 0-+3-*5-+6-*8-*9->11 и т.д.

Таблица 14.4

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

2. Стоимости с (/, у) остальных работ: с (0,1)=50; с (0,3)=45; с (1,2)=82; с (3,4)=55; с (3,3)=72; с(5,6)=30; с(6,7)=26; с (6,9)=75; с (6,8)=42; с(9,10)=35; с(10,1Г)= 10 (усл.руб.).

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

и

Рис. 14.13

Можно показать, что в этом варианте сетевого графика из 64 полных путей 28 — критические. Если бы верхние границы про­должительностей работ дали возможность полностью использо­вать резерв времени всех работ, представленных в табл. 14.4, то в новом плане все полные пути были бы критические.

Итак, в результате оптимизации сети мы пришли к плану, по­зволяющему выполнить комплекс работ в срок 7кр=61 (сутки) при минимальной его стоимости С — 923 (усл.руб.).

В реальных условиях выполнения проекта может потребоваться ускорение его выполнения, что, естественно, отразится на стои­мости проекта: она увеличится. Поэтому необходимо определить оптимальное соотношение между стоимостью проекта С и про­должительностью его выполнения t = /кр, представленное, напри­мер, в виде функции С = С{().

Для оптимизации сетей и, в частности, для нахождения функ­ции С(/) могут быть использованы эвристические методы, т.е. мето- ■ ды, учитывающие индивидуальные особенности сетевых графиков! к 14.6. Оптимизировать сетевой график, изображенный на рис. 14.14, в котором указаны максимально возможные продолжительности работ (в сутках). Необходимые для оптимизации исходные данные представлены в табл. 14.5.

Решение. Исходный для оптимизации план (см. рис. 14.14) имеет максимальную продолжительность работ /(/, /)=Ь(1, у) и со­ответственно минимальную стоимость С=300 (усл.руб.). Найдем все полные пути сетевого графика.

12 Исследование операций в экономике

Их четыре:

Ь\ 0-¥ 1-+3-+5-+6-+7-+8 продолжительностью /(Х])=89 (суток);

Хг 0-> 1->3->4-+6-> 7-*8 продолжительностью (‘кр=/ (Ь})=99 (суток);

Хз 0-»/-».?-> 7->2-> 7-+8 продолжительностью t (Х4)=50 (суток).

Для удобства дальнейших расчетов представим эти пути графи­чески в виде цепочек работ (рис. 14.15), в которых цифры над стрелками показывают коэффициенты затрат на ускорение работ Л О, У), а под стрелками — максимально возможные величины уменьшения продолжительности работ Л?(/, ]) — Ь (/, ;)-а (/,

Рис. 14.15

рения работы (3,4} с учетом формул (14.34) и (14.35) возрастет до 300+2-10=320 (усл.руб.). Итак, на I шаге:

С = 300 + 2-(99-/), где 89 комплекса, например, 540 (уел. руб.) предельная продолжительность проекта составит 55 (суток). С помощью функции С (/) можно оценить дополнительные затраты, связанные с сокращением сроков завершения комплекса. Так, со-

С

600

гоимость юекта, л. руб.

400

200

Продолжительность проекта, сутки

кращение продолжительности проекта с 79 до 55 суток потребует дополнительных затрат 540-375=165 (уел. руб.)>

Итак, мы рассмотрели один из возможных эвристических ал­горитмов оптимизации сетевого графика (см. рис. 14.14). Можно было использовать и другие алгоритмы. Например, взять в каче­стве первоначального план, имеющий не максимальные, а мини­мальные значения продолжительности работ / (/, у) = а (/, у) и со­ответственно максимальную стоимость проекта. А затем последо­вательно увеличивать продолжительность выполнения комплекса работ путем увеличения продолжительности работ, расположен­ных на некритических, а затем и на критическом(ских) пути в порядке убывания коэффициентов затрат Л (/,у). ,

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

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

УПРАЖНЕНИЯ

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

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

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

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

14.10. Как изменится срок выполнения проекта (см. рис. 14.17), резервы времени работ и событий, коэффициенты напряженности работ, если увеличить продолжительность работы г (9, 10) на ве­личину: а) ЛП(Я 10)', б) Я\(Я 10); в) /^(9, 10); г) Л„(Я 10)1

14.11. Как изменится срок выполнения проекта (см. рис. 14.17), резервы времени работ и событий, коэффициенты напряженности работ, если продолжительность каждой работы /(/, у) увеличить на величину: а) Лп(і, у); б) Л^і, у); в) Л^і, у); г) Л„(/, у)? Для случаев б), в) и г) найти все критические пути сетевого графика.

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

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

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

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

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

……….