An O (n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

In this paper, we study the problem of scheduling n equal-length preemptive jobs on a single machine to minimize total tardiness, subject to release dates. The complexity status of this problem has remained open to date. We provide an O(n2) time algorithm to solve the problem.
Original languageEnglish
Pages (from-to)343-364
Number of pages22
JournalJournal of Scheduling
Volume9
Issue number4
DOIs
Publication statusPublished - 1 Jan 2006

Keywords

  • Equal-length jobs
  • Preemptive scheduling
  • Release date
  • Single machine
  • Total tardiness

ASJC Scopus subject areas

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

Cite this