@inproceedings{3baf98ee1ac34cb284464b8ab8f5826b,

title = "An efficient PTAS for parallel machine scheduling with capacity constraints",

abstract = "In this paper, we consider the classical scheduling problem on parallel machines with capacity constraints. We are given m identical machines, where each machine k can process up to ck jobs. The goal is to assign the n ≤ ∑m k=1 ck independent jobs on the machines subject to the capacity constraints such that the makespan is minimized. This problem is a generalization of the c-partition problem where ck = c for each machine. The c-partition problem is strongly NP-hard for c ≥ 3 and the best known approximation algorithm of which has a performance ratio of 4/3 due to Babel et al. [2]. For the general problem where machines could have different capacities, the best known result is a 1.5- approximation algorithm with running time O(n log n + m2n) [14]. In this paper, we improve the previous result substantially by establishing an efficient polynomial time approximation scheme (EPTAS). The key idea is to establish a non-standard ILP (Integer Linear Programming) formulation for the scheduling problem, where a set of crucial constraints (called proportional constraints) is introduced. Such constraints, along with a greedy rounding technique, allow us to derive an integer solution from a relaxed fractional one without violating constraints.",

keywords = "Approximation algorithms, Capacity constraints, Integer programming, Scheduling",

author = "Lin Chen and Klaus Jansen and Wenchang Luo and Guochuan Zhang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; null ; Conference date: 16-12-2016 Through 18-12-2016",

year = "2016",

doi = "10.1007/978-3-319-48749-6_44",

language = "English",

isbn = "9783319487489",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "608--623",

editor = "Minming Li and Lusheng Wang and Chan, {T-H. Hubert}",

booktitle = "Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings",

}