Minimizing total completion time subject to job release dates and preemption penalties

Research output: Journal article publicationJournal articleAcademic researchpeer-review

21 Citations (Scopus)

Abstract

Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.
Original languageEnglish
Pages (from-to)313-327
Number of pages15
JournalJournal of Scheduling
Volume7
Issue number4
DOIs
Publication statusPublished - 1 Jul 2004

Keywords

  • Preemption penalty
  • Preemptive scheduling
  • Setup time

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Cite this