12-12-2012, 05:56 PM
Minimum Makespan Scheduling with Low Rank Processing Times
Minimum Makespan.pdf (Size: 401.53 KB / Downloads: 33)
Abstract
We investigate approximation algorithms for the classical minimum makespan scheduling problem, focusing on
instances where the rank of the matrix describing the processing times of the jobs is bounded. A bounded rank matrix
arises naturally when the processing time of a job on machine depends upon a bounded set of resources. A bounded
rank matrix also shows up when jobs have varying degrees of parallelizability, and the machines have multiple cores.
We are interested in studying the tractability of the problem as a function of the (positive) rank of the processingtime
matrix. At one extreme is the case of unit rank, also known as related machines, which admits a PTAS [7], and
at the other extreme is the full rank case (unrelated machines), which is NP-hard to approximate within a factor better
than 3=2 [8].
Our main technical contribution is in showing that the approximability of the problem is not smooth with the rank
of the matrix. From the inapproximability side, we show that the problem becomes APX-hard, even for rank four
matrices. For rank seven matrices, we prove that it is hard to approximate to a factor 3=2, matching the inapproximability
result for general unrelated machines. From the algorithmic side, we obtain a quasi-polynomial approximation
scheme (i.e., a (1 + ") approximation in time npoly(1=";log n)) for the rank two case. This implies that the problem is
not APX-hard in this case, unless NP has quasi-polynomial algorithms. Our algorithm is a subtle dynamic program
which runs in polynomial time in some interesting special cases. The classification of the three dimensional problem
remains open.
Introduction
The makespan minimization problem is a classic and well-studied problem. In this problem, we are given a collection
of n jobs andmmachines, and the processing time incurred by scheduling job j on machine i is given by pi;j 0. The
goal is to find an assignment of jobs to machines, that minimizes the total processing time assigned to any machine
(i.e., the makespan). This is also the time to complete processing all jobs. Makespan minimization is one of the
problems originally shown to be NP-Hard by Garey and Johnson [5]. The problem is NP-Hard even on two identical
machines (through a reduction from the subset-sum problem). Since then most work focused on obtaining efficient
approximation algorithms, and our work also concerns with precisely this line of study.
A well understood special case for this problem is the one of identical machines where the processing time of job j is
pj on each of themmachines. As mentioned earlier, the hardness reduction in [5] shows that an FPTAS is not possible
(unless P=NP). In a seminal result Hochbaum and Shmoys [6] show an (1 + )-approximation algorithm which runs
in polynomial time for constant . The algorithm was later extended to the case of related machines [7] where each
machine may have a different speed, and the processing time of job j on machine i is pi;j = pi s