7.2. Метод подъема

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

В задаче расстановки рабочих начальным решением будет какая-либо их расстановка по работам. Из множества вариантов начальной расстановки возьмем простейший вариант с равномерным распределением работников по работам k_ij = [K/N] для любых i и j, [] - целая часть числа. Далее оставшееся число работников K mod N распределяется по правилу один работник на работу с наибольшей трудоемкостью и, если их резерв не исчерпан, ищется следующая по трудоемкости работа, на которую ставится очередной работник. Процесс заканчивается, когда резерв работников исчерпан. В нашем примере после завершения процесса начальной расстановки сложится такая ситуация: k₀₁=1, k₀₂=2, k₁₃=1, k₂₄=2, k₃₄=2, k₁₄=1, k₄₅=1, а длительности полных путей составят

T(I₁) = t₀₁ + t₁₃ + t₃₅ = 1/1 + 2/1 + 4/2 = 5,

T(I₂) = t₀₁ + t₁₄ + t₄₅ = 1/1 + 2/1 + 1/1 = 4,

T(I₃) = t₀₂ + t₂₄ + t₄₅ = 2/2 + 3/2 + 1/1 = 3,5.

Путь I₁ является критическим путем. Далее организуется процесс восхождения от худшего к лучшему варианту. Для этого следует переместить одного работника с работы некритического пути на одну из работ критического пути. Если длительность критического пути уменьшилась, то процесс повторяется - работник перемещается на следующую работу этого пути, если – нет, то перемещается работник с другой работы некритического пути и т.д. Если ни одно из перемещений не приводит к улучшению результата, то алгоритм подъема завершает свою работу. Выбор работы критического пути, на которую перемещается работник с некритического пути, производится по критерию

.

Для I_кр= I₁= {(0, 1), (1, 3), (3, 5)}, максимум достигается для работы (1, 3). Согласно начальному распределению, кандидатами на перемещение работника могут быть только работы (0,2) и (2,4), поскольку на других работах некритических путей имеется только по одному работнику и резерв для перемещения отсутствует. Произведя подъем, получим следующее распределение работников: k₀₁=k₀₂=k₁₄=k₄₅=1, k₁₃=k₂₄= k₃₄=2, а длительности составят: T(I₁)=4, T(I₂)=4, T(I₃)=4,5. Полученный результат является уровнем останова подъема, так как никакое другое перемещение не улучшает этот результат. Не во всех случаях метод подъема достигает оптимального результата.