Non-Approximability Results for Scheduling Problems with Minsum Criteria

Han Hoogeveen*, Petra Schuurman, Gerhard J. Woeginger

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We provide several non-approximability results for deterministic scheduling problems whose objective is to minimize the total job completion time. Unless P = N.P, none of the problems under consideration can be approximated in polynomial time within arbitrarily good precision. Most of our results are derived by APX-hardness proofs. We show that, whereas scheduling on unrelated machines with unit weights is polynomially solvable, the problem becomes APX-hard if release dates or weights are added. We further show APX-hardness for scheduling in flow shops, job shops, and open shops. We also investigate the problems of scheduling on parallel machines with precedence constraints and unit processing times, and two variants of the latter problem with unit communication delays; for these problems we provide lower bounds on the worst-case behavior of any polynomial-time approximation algorithm through the gap-reduction technique.

Original languageEnglish
Pages (from-to)157-168
Number of pages12
JournalINFORMS Journal on Computing
Volume13
Issue number2
DOIs
Publication statusPublished - 2001

Keywords

  • Approximation Algorithm
  • Approximation Scheme
  • Apx-hardness
  • Communication Delays
  • Flow Shop
  • Gap-Reduction
  • L-Reduction
  • Non-Approximability
  • Open Shop
  • Precedence Constraints
  • Scheduling
  • Unrelated Parallel Machines
  • Worst-Case Analysis

Fingerprint

Dive into the research topics of 'Non-Approximability Results for Scheduling Problems with Minsum Criteria'. Together they form a unique fingerprint.

Cite this