Complexity and inapproximability results for parallel task scheduling and strip packing (Q5915576)

In the parallel task scheduling problem a set \(J\) of jobs needs to be processed on a group of \(m\) machines; each job \(j\) has processing time \(p_j \in \mathbb{N}\) and it needs the simultaneous use of \(q_j \in \mathbb{N}\) machines. The goal is to to schedule the jobs on the machines so that each machine processes at most one job at any given moment and each job is processed on the required number of machines; the goal is to minimize the makespan, or completion time, of the last job. The problem is known to be NP-hard for the case when the number \(m\) of machines is at least 5, and when the number of machines is at most 3 there is a pseudo-polynomial time algorithm for it. The complexity of the case when the number of machines is 4 was a long-standing question, that was finally answered in this paper as the authors prove that the problem when \(m = 4\) is NP-hard. The NP-hardness proof uses a reduction from the 3-partition problem, which is known to be NP-hard. In the 3-partition problem, a list \(I\) of \(3z\) positive numbers is given whose total sum is \(zD\), a multiple of \(z\), and in which each number \(i\) has value larger than \(D/4\) and smaller than \(D/2\). The problem is to determine whether the set of numbers can be partitioned into \(z\) sets such that the sum of values in each set is equal to \(D\). The reduction from the 3-partition problem to the parallel task scheduling problem is very technical and it relies on a clever idea of using a set of structure jobs. Structure jobs are jobs such that in any optimal schedule these jobs leave \(z\) idle gaps of length \(D\) in the schedule. Hence, constructing a schedule for the jobs of minimum makespan implies also a solution for the 3-partition problem. In the above reduction, the considered schedules place the jobs on adjacent machines. This allows the authors to obtain a lower bound for the complexity of a related problem: the strip packing problem. In this problem a group of rectangles has to be packed in a strip of integer width and minimum height so that the rectangles do not overlap. Note that a job can be represented as a rectangle if the job is scheduled on a group of consecutive machines. The authors show that there is no pseudo-polynomial time algorithm for the strip packing problem with approximation ratio smaller than \(5/4\) unless \(\mathrm{P} = \mathrm{NP}\).