An efficient PTAS for parallel machine scheduling with capacity constraints

Lin Chen, Klaus Jansen, Wenchang Luo, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

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.

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Proceedings
EditorsMinming Li, Lusheng Wang, T-H. Hubert Chan
PublisherSpringer-Verlag
Pages608-623
Number of pages16
ISBN (Print)9783319487489
DOIs
StatePublished - 2016
Event10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016 - Hong Kong, China
Duration: Dec 16 2016Dec 18 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10043 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2016
CountryChina
CityHong Kong
Period12/16/1612/18/16

Keywords

  • Approximation algorithms
  • Capacity constraints
  • Integer programming
  • Scheduling

Fingerprint Dive into the research topics of 'An efficient PTAS for parallel machine scheduling with capacity constraints'. Together they form a unique fingerprint.

Cite this