A note on one-processor scheduling with asymmetric earliness and tardiness penalties

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)

Abstract

We consider the problem of scheduling n independent and simultaneously available jobs on one processor. Each job has a specified processing time and a preferred starting time. The jobs are to be schedules nonpreemptively on the processor to begin as close to their preferred starting times as possible. We examine one cost measure - the amximum weighted discrepancy from the preferred starting time. Under an assumption on penalty weights, we show that the problem is reducible to the problem with equal penalty weights and the algorithms given by Garey, Tarjan and Wilfong can be modified to solve our problem.
Original languageEnglish
Pages (from-to)45-48
Number of pages4
JournalOperations Research Letters
Volume13
Issue number1
DOIs
Publication statusPublished - 1 Jan 1993

Keywords

  • earlines
  • scheduling
  • tardiness

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Statistics, Probability and Uncertainty
  • Discrete Mathematics and Combinatorics
  • Modelling and Simulation

Cite this