Improved algorithms for single machine scheduling with release dates and rejections

Cheng He, Joseph Y.T. Leung, Kangbok Lee, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.

Original languageEnglish (US)
Pages (from-to)41-55
Number of pages15
Journal4OR
Volume14
Issue number1
DOIs
StatePublished - Mar 1 2016

All Science Journal Classification (ASJC) codes

  • Management Information Systems
  • Theoretical Computer Science
  • Management Science and Operations Research
  • Computational Theory and Mathematics

Keywords

  • Approximation algorithm
  • Makespan
  • Rejection
  • Release date
  • Scheduling
  • Total rejection penalty

Fingerprint Dive into the research topics of 'Improved algorithms for single machine scheduling with release dates and rejections'. Together they form a unique fingerprint.

Cite this