1990 ApproximationAlgsForSchedUnrelParMachines
- (Lenstra et al., 1990) ⇒ Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. (1990). “Approximation Algorithms for Scheduling Unrelated Parallel Machines.” In: Mathematical Programming, 46(1). doi:10.1007/BF01585745
Subject Headings: Scheduling Task, Approximation Algorithm, Linear Programming.
Notes
- A preliminary version of this paper appeared in the Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science (1987)
Cited By
Quotes
Key words
- Scheduling - Parallel Machines - Approximation Algorithm - Worst Case Analysis - Linear Programming - Integer Programming - Rounding
Abstract
We consider the following scheduling problem. There are [math]\displaystyle{ m }[/math] parallel machines and [math]\displaystyle{ n }[/math] independent jobs. Each job is to be assigned to one of the machines. The processing of job [math]\displaystyle{ j }[/math] on machine [math]\displaystyle{ i }[/math] requires time [math]\displaystyle{ p_{ij} }[/math]. The objective is to find a schedule that minimizes the makespan.
Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints.
In contrast to our main result, we prove that no polynomial algorithm can achieve a worst-case ratio3/2 unlessP = NP. We finally obtain a complexity classification for all special cases with a fixed number of processing times.,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1990 ApproximationAlgsForSchedUnrelParMachines | Éva Tardos Jan Karel Lenstra David B. Shmoys | Approximation Algorithms for Scheduling Unrelated Parallel Machines | Mathematical Programming Journal | 10.1007/BF01585745 | 1990 |