Parallel task scheduling

Parallel task scheduling problem

The parallel task scheduling problem is an NP-hard optimization problem. A given set of $n$ parallel tasks, also called jobs, need to be scheduled on $m$ identical machines minimizing the latest completion time. In Veltman et al. and Drozdowski, this problem is denoted by $P|size_{j}|C_{\max }$ in the tree field notation introduced by Graham et al . The origins of this problem formulation can be traced back to 1960. There exists no polynomial time approximation algorithm with a ratio smaller than $3/2$ unless $P=NP$.

Definition

In this problem, we are given a set ${\mathcal {J}}$ of $n$ jobs as well as $m$ identical machines. Each job $j\in {\mathcal {J}}$ has a processing time $p_{j}\in \mathbb {N}$ and requires the simultaneous use of $q_{j}\in \mathbb {N}$ machines durng its execution. A schedule assigns each job $j\in {\mathcal {J}}$ to a starting time $s_{j}\in \mathbb {N} _{0}$ and a set $m_{j}\subseteq \{1,\dots ,m\}$ of $|m_{j}|=q_{j}$ machines to be processed on. A schedule is feasible if each processor executes at most one job at any given time. The objective of the problem denoted by $P|size_{j}|C_{\max }$ is to find a schedule with minimum length $C_{\max }=\max _{j\in {\mathcal {J}}}s_{j}+p_{j}$, also called the makespan of the schedule. A sufficient condition for the feasibility of a schedule is the following

$\sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\forall t\in \{s_{1},\dots ,s_{n}\}$.

If this property is satisfied for all starting times, a feasible schedule can be generated by assigning free machines to the jobs at each string time starting with time $t=0$. Furthermore, the number of machine intervals used by jobs and idle intervals at each time step can be bounded by $|{\mathcal {J}}|+1$. Here a machine interval is a set of consecutive machines of maximal cardinality such that all machines in this set are processing the same job. A machine interval is completely specified by the index of its first and last machine. Therefore, we can obtain a compact way of encoding the output with polynomial size.

Hardness

This problem is NP-hard even for a constant number of machines due to the fact that it contains the classic problem $P2||C_{\max }$. Furthermore, Du and Leung showed that this problem is strongly NP-hard when the number of machines is at least $m=5$ and that there exists a pseudo-polynomial time algorithm, which solves the problem exactly if the number of machines is at most $m=3$. Later Jansen and Rau showed that the problem is also strongly NP-hard when the number of machines is $m=4$. If the number of machines is not bounded by a constant, there can be no approximation algorithm with an approximation ratio smaller than $3/2$ unless $P=NP$ because this problem contains the bin packing problem as a subcase.

Differences between contiguous and non-contiguos jobs

Given an instance of the parallel task scheduling problem, the optimal makespan can differ depending on the constraint to the contiguity of the machines. If the jobs can be scheduled on non-contiguous machines, the optimal makespan can be smaller than in the case that they have to be scheduled on contiguous ones. The difference between contiguous and non-contiguous schedules has been first demonstrated in 1992 on an instance with $n=8$ tasks, $m=23$ processors, $C_{\max }^{nc}=17$, and $C_{\max }^{c}=18$. Błądek et al. studied this so called c/nc-differences and proved the following points:

• For a c/nc-difference to arrize, there must be at least three tasks with $size_{j}>1$.
• For a c/nc-difference to arise, there must be at least three tasks with $p_{j}>1$ .
• For a c/nc-difference to arise, the non-contiguous schedule length must be at least $C_{\max }^{nc}=4$
• For a c/nc-difference to arise, at least $m=4$ processors are required (and there exsits an instance with a c/nc-difference with $m=4$).
• To decide whether there is an c/nc-difference in a given instance is NP-complete.
• The maximal c/nc-difference $\sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)$ is at least $5/4$ and at most $2$.

Furthermore, they proposed the following two conjectures, which remain unproven:

• For a c/nc-difference to arise, at least $n=7$ tasks are required.
• $\sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4$