Optimal algorithms for single-machine scheduling with rejection to minimize the makespan

Lingfa Lu, Chi To Ng, Liqi Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)

Abstract

In this paper we consider the single-machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial-time algorithm for the off-line problem when split is allowed. Second, for the on-line problem with arbitrary arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio 2. Finally, for the on-line problem with at most two distinct arrival times, we provide a determined on-line algorithm with the best-possible competitive ratio (51)/2≈1.618.
Original languageEnglish
Pages (from-to)153-158
Number of pages6
JournalInternational Journal of Production Economics
Volume130
Issue number2
DOIs
Publication statusPublished - 1 Apr 2011

Keywords

  • Competitive ratio
  • On-line algorithm
  • Rejection penalty
  • Scheduling

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Business, Management and Accounting(all)
  • Management Science and Operations Research
  • Economics and Econometrics

Cite this