Preemptive scheduling of jobs with agreeable due dates on a single machine to minimize total tardiness

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

Abstract

We consider the problem of scheduling n preemptive jobs on a single machine to minimize total tardiness, subject to agreeable due dates, i.e., a later release date corresponds to a later due date. We prove that the problem is N P-hard in the ordinary sense by showing that it is N P-hard, and deriving a pseudo-polynomial algorithm for it.
Original languageEnglish
Pages (from-to)368-374
Number of pages7
JournalOperations Research Letters
Volume37
Issue number5
DOIs
Publication statusPublished - 1 Sep 2009

Keywords

  • Preemptive scheduling
  • Single machine
  • Total tardiness

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Applied Mathematics
  • Industrial and Manufacturing Engineering
  • Software

Cite this