On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

Leah Epstein, John Noga, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

54 Citations (Scopus)

Abstract

We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs. We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.
Original languageEnglish
Pages (from-to)415-420
JournalOperations research letters
Volume30
Issue number6
DOIs
Publication statusPublished - 2002

Keywords

  • IR-74863
  • On-line algorithm
  • Scheduling
  • Worst-case bounds
  • METIS-208618
  • Competitive Analysis

Fingerprint Dive into the research topics of 'On-line scheduling of unit time jobs with rejection: Minimizing the total completion time'. Together they form a unique fingerprint.

  • Cite this