Задача (случайный пример). Есть набор задач $J=\{1,\dots ,n\}$, одинаковые машины $M$ числа $m$. Каждая задача $j$ имеет длительность $p_j\in \{1,2,4\}$. Даны ограничения:
- предшествования (частичный порядок) задаются ориентированным ацикличным графом (DAG) $D=(J,E_{prec})$: если $(i\to j)\in E_{prec}$, то $j$ нельзя начать до завершения $i$;
- конфликтные пары (нельзя выполнять одновременно) задаются неориентированным графом $G=(J,E_{conf})$: если $\{i,j\}\in E_{conf}$, то их исполнения не должны пересекаться по времени.
Цель: минимизировать makespan $C_{\max }$ — время завершения всех задач.
Связь с теорией графов.
- Предшествования — это DAG $D$ (частичный порядок). Антайны (maximal antichains) в этом порядке соответствуют множествам задач, которые теоретически могут выполняться одновременно, если нет конфликтов.
- Конфликты — это граф $G$; в любой момент можно запустить лишь такое подмножество задач, которое является независимым множеством в $G$ и не содержит задач с неудовлетворёнными предшественниками.
- Модель с дизъюнктивными рёбрами: для каждой конфликтной пары $\{i,j\}$ добавляется дизъюнктивное условие «либо $i$ перед $j$, либо $j$ перед $i$» — классическая дисъюнктивная модель для цехового расписания.
Формулировка точного алгоритма (time-indexed ILP).
Пусть верхняя грань срока $T$ (возможно суммарный объём). Вводим бинарные переменные
$$x_{j,t}=\{\begin{array}{ll}1,& \text{если задача}j\text{стартует в момент}t,\\ 0,& \text{иначе}\end{array}$$ с $t=0,\dots ,T-p_j$. Ограничения:
1) каждая задача стартует ровно один раз:
$$\forall j:\sum _{t=0}^{T-p_j}{x}_{j,t}=1.$$ 2) машина в любой момент обслуживает не более $m$ задач:
$$\forall \tau \in \{0,\dots ,T-1\}:\sum _j\sum _{t:t\le \tau <t+p_j}{x}_{j,t}\le m.$$ 3) предшествования:
$$\forall (i\to j)\in E_{prec}:\sum _{t}t{x}_{i,t}+p_i\le \sum _{t}t{x}_{j,t}.$$ 4) конфликты (запрещение перекрытия для каждой пары):
$$\forall \{i,j\}\in E_{conf}:\sum _{t,u:\text{интервалы}[t,t+p_i),[u,u+p_j)\text{пересекаются}}{x}_{i,t}{x}_{j,u}=0,$$ или линеаризовать через дополнительные бинарные переменные порядка. Цель: минимизировать $T$ (либо минимизировать последнее завершение через переменные начала).
Этот ILP даёт оптимальное решение, но размер и решаемость резко растут с $T$ и $n$.
Альтернативный точный метод (перебор/DP по состояниям).
Определим DP по подмножествам завершённых задач: $F(S)$ — минимальное время, за которое можно выполнить подмножество $S$. Начальное $F(\varnothing )=0$. Переход: из состояния $S$ можно одновременно запустить любое множество $A\subseteq J\setminus S$, такое что
- все задачи в $A$ имеют все предшественники в $S$ (т.е. $A$ — допустимое расширение),
- $A$ независимо в $G$,
- $|A|\le m$.
Тогда
$$F(S\cup A)=\min \{\max (F(S),F(S)+\underset{j\in A}{\max }{p}_j)\}=F(S)+\underset{j\in A}{\max }{p}_j.$$ Ищем $F(J)$. Этот DP требует перебора подмножеств допустимых $A$ и всех $S$, в худшем случае экспоненциально: время порядка $O^{\ast }(2^n)$ (символ $O^{\ast }(\cdot )$ опускает полиномиальные множители).
Эвристики и приближения.
- List-scheduling (topological order / LPT): сортировать задачи по приоритету (например, по длительности или раннему возможному старту) и размещать на первой свободной машине при соблюдении предшествований и конфликтов. Быстро, но не всегда оптимально.
- Для общего случая без предшествований list-scheduling даёт гарантированный коэффициент приближения $\le 2-\frac{1}{m}$ относительно оптимального $C_{\max }$ (классическая оценка Грэма).
- Можно использовать B&B + релаксации (LP), или итеративно выбирать максимум независимого множества в $G$ из допустимых задач для заполнения слота (требует решение MWIS — тоже NP-трудная подзадача).
Сложность и NP-полнота.
- Общая задача (идентичные машины, предшествования, конфликты) является NP-трудной; точное решение в общем случае требует экспоненциального времени (и ILP решается экспоненциально в худшем случае).
- Уже частные случаи NP-полны:
- задача идентичных машин без предшествований $P||C_{\max }$ содержит Partition/3-Partition и потому NP-трудна (сильная NP-полнота для общего $m$ и длительностей).
- задача с единичными длительностями и предшествованиями $P|prec,p_j=1|C_{\max }$ NP-полна для $m\ge 2$ (классический результат).
- задача с конфликтным графом сводится к проблемам раскраски/пакетирования (capacity coloring) и потому NP-трудна в общем случае.
- Полиномиально разрешимые случаи:
- $m=1$ — просто топологическая сортировка, полиномиально.
- если предшествования образуют цепь (total order) — однопроходная последовательность.
- некоторые параметризованные случаи: при очень малом $n$ или малой ширине частичного порядка (малый максимум размера антайна) можно применять DP по состояниям с приемлемой сложностью; также допустимы FPT-алгоритмы при параметре «ширина» или «treewidth» соответствующих графов.
Краткая инструкция для практического решения.
- Для $n\lesssim 40$: используйте DP по подмножествам или time-indexed ILP в современном солвере (CP-SAT).
- Для средних $n$: B&B с эвристическим упорядочиванием (topological + LPT) и отсекающими оценками (нижняя граница по сумме длительностей и по длине критического пути).
- Для больших $n$: приближённые и жадные алгоритмы, локальный поиск, расписание по уровням (антайнки), либо сведение к специальной задаче с последующим применением эвристик на конфликтном графе.
Если хотите, могу сгенерировать конкретный случай (конкретные $n,m,p_j$, списки рёбер $E_{prec},E_{conf}$) и показать пошагово поиск оптимального расписания на небольшом примере.