1outtreesumwc

[math]1 \mid outtree \mid \sum w_i C_i[/math]

Постановка задачи

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