Если оказалось, что Т(т) > , то построение текущего плана прекращается ввиду его неперспективности и переходим на начало шага 3, т.е. выбирается новый вариант построения плана вьшолнения проекта. В
случае если Т(т)<Т, то выбирается очередной этап для вьшолнения, ему выделяются ресурсы и в момент завершения (т > т) какого-либо этапа проекта вычисляем Т(т). В процессе описанного построения плана реализации проекта возможна одна из альтернатив: либо для какого-либо т* окажется, что T{t)>Tq, либо будет построен новый план реализации проекта продолжительности Т < Т;. В этом случае значение Т, полагаем равным Т и переходим к анализу очередного варианта реализации проекта. Оптимальное решение будет определено либо когда Те станет равным либо когда анализ всех допустимых вариантов построения плана исчерпан. В качестве оптимального и в том и в другом случае выбирается план, соответствующий последнему значению верхней границы Те,
Пример. Решение задачи оптимизации времени выполнения проекта. Будем предполагать, что последовательность вьшолнения этапов проекта задана ориентированным ациклическим графом G(w, п) следующего вида:
Рис. 11.2
Пусть вершины графа соответствуют этапам выполняемого проекта, а дуги отражают технологическую последовательность их вьшолнения.
Не уменьшая общности, можно сказать, что продолжительность каждого этапа проекта совпадает с его номером, и для вьшолнения каж-304
дого этапа проекта необходим один исполнитель, т.е. а/ = 1 (/ = 1, 10), число исполнителей равно двум (Ь = 2). Вычислим продолжительности путей графа. В путь .Si входят этапы 1, 2, 3, 9, 10 и, следовательно, его длина равна 25. Аналогично 2 = 31, 5з = 33, 4 = 37. Следовательно, 5, = .4 = 37.
Определим сумму продолжительностей всех этапов проекта:
S =1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. /=1
(11.17)
Далее вычислим Т„ по формуле
i=\,n
= max37,-
(11.18)
Далее, следуя описанию метода ветвей и границ, вычислим верхнюю оценку Те, для чего определяется некоторое допустимое решение (допустимый план выполнения всех этапов проекта). Выберем в качестве этого решения следующую последовательность выполнения этапов, изображенную графически на диаграмме Ганга. Диаграмма Ганга представляет собой двумерную систему координат, в которой по горизонтальной оси фиксируется время, а по вертикальной- номер исполнителя (станка, прибора, машины и т.д.). Пронумерованные дуги на диаграмме Ганга отражают динамику выполнения этапов проекта (рис. 11.3).
4 7 8 |
1 2 6 1 | 5 1 i 1 3 9 10 |
| -\-!-!-► |
Рис. 11.3
Продолжительность выполнения проекта по этому плану (решению) равна 41. Следовательно, Т; = 41. Так как Г„ > Те, переходим к анализу следующего варианта выполнения проекта. Выберем, например, в каче-
стве исходных элементов для выполнения этап 6 и этап 7. Тогда в момент z=6 завершится выполнение этапа 6 и вычислим Т{т) при 7=6
7;""(r) = r+max
St,-
= 6 +max
25,31,27,31.у
= 6 + 31 = 37.
(11.19)
На диаграмме Ганта эта ситуация отразится следующим образом:
2 • 1
т = 6/
Рис. 11.4
Так как T(6)<Tg, следовательно выбираем следующий этап для вьшолнения. Пусть это будет этап 4. Тогда в момент времени г = 7 завершится вьшолнение этапа 7 и вновь вычислим Т(1)по предыдущей формуле
37 (7) = 7 + тах
25,30,27,30,у[. = 37.(11.20)
Отметим эту ситуацию на диаграмме Ганта:
Далее продолжаем анализ этого и других допустимых решений согласно следующей схеме: 306