Формулировка гипотезы (точно): «Для любого задания расписания с фиксированным числом машин $m$ и требованием пермутационного порядка (или просто с предшествованиями-«перестановками») его можно свести к задаче минимизации суммарного штрафа и решить полиномиально, если граф зависимостей задач (precedence graph) является деревом».
Краткий ответ: гипотеза в этой общей форме неверна. Ниже — разбор, контрпример и краткие положительные и отрицательные результаты.
1) Модель, которую я беру для контр-примера
- $m$ — фиксированное число одинаковых машин (в контрпримере возьмём $m=2$).
- Набор задач $J=\{1,\dots ,n\}$ с обработками $p_j\in {\mathbb{Z}}_{>0}$.
- Предшествования заданы ориентированным ацикличным графом; в контрпримере граф — дерево (конкретно: ин-дерево — все листья предшествуют корню).
- Цель: минимизировать время завершения последней задачи (makespan) $C_{\max }$.
2) Контрпример (сведение из Partition)
Пусть дана задача Partition: даны числа $a_1,\dots ,a_k$ суммарно $2B$. Нужно решить, можно ли разбить их на два подмножества с суммой $B$.
Построим инстанс расписания:
- Для $i=1,\dots ,k$ создаём задачу $A_i$ с $p_{A_i}=a_i$.
- Создаём корневую задачу $R$ с $p_R=1$.
- Предшествования: для каждого $i$ требуется $A_i\to R$ (т. е. все $A_i$ — предки $R$). Граф предшествований — дерево (звезда с корнем $R$).
- Машин $m=2$.
Любой расписание должно выполнить все $A_i$ на двух машинах (в параллель), затем (после завершения всех $A_i$) выполнить $R$. Пусть нагрузки (суммы времён) на две машины при выполнении $A_i$ равны $L_1$ и $L_2$; пусть $L=\max (L_1,L_2)$. Тогда
$$C_{\max }=\max (L,L+p_R)=L+p_R,$$ поскольку $R$ стартует только после завершения всех $A_i$. Поскольку $p_R=1$, существует расписание с $C_{\max }\le B+1$ тогда и только тогда, когда существует разбиение $a_i$ на два подмножества с максимальной суммы не более $B$, т. е. решение Partition. Следовательно задача ${\mathrm{P}}_2\mid \mathrm{prec}(\text{дерево})\mid C_{\max }$ NP‑трудна (по крайней мере так же трудна, как Partition). Таким образом не может быть общего полиномиального алгоритма для всех таких задач, если P$\ne$NP.
(Замечание: выбор $p_R=0$ тоже возможен в формулировках, допускающих нулевые времена; тогда $C_{\max }=L$ и редукция ещё проще.)
3) Выводы и обсуждение
- Контрпример показывает: даже при фиксированном $m$ (уже при $m=2$) и при том что граф предшествований — дерево, минимизация $C_{\max }$ остаётся NP‑трудной (по крайней мере слабонапряжённо через Partition). Следовательно утверждение «всегда сводится и решается полиномиально» — неверно.
- Причина: «дерево» предшествований не исключает комбинаторики распределения задач по машинам; балансировка нагрузок (Partition) остаётся подзадачей.
4) Положительные частные результаты (которые требуют дополнительных ограничений)
- Если все времена $p_j=1$ (единичные времена), то задача ${\mathrm{P}}_m\mid \mathrm{prec}(\text{дерево})\mid C_{\max }$ разрешима полиномиально (классический алгоритм Hu — level‑scheduling: размещать по уровням ориентированного дерева), получаем оптимальную длину равную высоте дерева в смысле уровней занятости.
- Для других целей или дополнительных ограничений (например, $m=1$ — одно машинное расписание, или только цепочки предшествований, или специальная структура весов/штрафов) возможны полиномиальные алгоритмы, но это сильно зависит от конкретной цели (ΣC_j, Σw_jC_j, L_max, число просроченных задач и т.п.).
- Напротив, многие стандартные объективы (минимизация Σw_jC_j, ΣU_j, L_max и т.д.) остаются NP‑трудными при довольно слабых допущениях на структуру графа.
5) Итог
Гипотеза в общей формулировке ложна. При дополнительных сильных ограничениях (единичные времена, специальные структуры целей) дерево предшествований даёт полиномиальные алгоритмы, но в общем случае даже для $m=2$ и дерева задача оптимизации (например, минимизация $C_{\max }$) остается NP‑трудной (контрпример через Partition).
Если нужно, могу:
- привести формальную и детальную редукцию с полным доказательством корректности и анализом сложности, или
- перечислить точные известные положительные и отрицательные теоремы по отдельным комбинациям обозначений (Graham‑style нотация) и дать ссылки на литературу.