Multiprocessor Scheduling

Input

Set $T$ of tasks, number $m \in \mathbb{Z}^{+}$ of processors, length $\ell(t) \in \mathbb{Z}^{+}$ for each $t \in T$, and a deadline $D \in \mathbb{Z}^{+}$.

Question

Is there a $m$-processor schedule for $T$ that meets the overall deadline $D$, i.e. a function $\sigma : T \rightarrow \mathbb{Z}_{0}^{+}$ such that, for all $u \geq 0$, the number of tasks $t \in T$ for which $\sigma(t) \leq u < \sigma(t) + \ell(t)$ is no more than $m$ and such that, for all $t \in T$, $\sigma(t) + \ell(t) \leq D$?

Classes

• NP-complete

Comments

Remains NP-complete for $m = 2$, but can be solved in pseudo-polynomial time for any fixed $m$. NP-complete in the strong sense for $m$ arbitrary ([problem:3-partition] is a special case). If all tasks have the same length, then this problem is trivial to solve in polynomial time, even for different speed processors.

Proofs

NP-complete

Transformation from Partition.

Reducible from

• Partition