ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES.

Michael R. Garey, Robert E. Tarjan, Gordon T. Wilfong

Research output: Contribution to journalArticle

256 Scopus citations

Abstract

We consider one-processor scheduling problems having the following form: Tasks T//1,T//2,. . . ,T//N are given, with each T//i having a specified length l//i and a preferred starting time a//i (or, equivalently, a preferred completion time b//i). The tasks are to be scheduled nonpreemptively (i. e. , a task cannot be split) on a single processor to begin as close to their preferred starting times as possible. We examine two different cost measures for such schedules. For the first of these, we show that the problem of finding minimum cost schedules is NP-complete; however, we give an efficient algorithm that finds minimum cost schedules whenever the tasks either all have the same length or are required to be executed in a given fixed sequence. For the second cost measure, we give an efficient algorithm that finds minimum cost schedules in general, with no constraints on the ordering or lengths of the task.

Original languageEnglish (US)
Pages (from-to)330-348
Number of pages19
JournalMathematics of Operations Research
Volume13
Issue number2
DOIs
StatePublished - Jan 1 1988
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES.'. Together they form a unique fingerprint.

  • Cite this