A dual criteria sequencing problem with earliness and tardiness penalties

Joseph Leung

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)-time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we Show that the problems are NP-hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than 3/2.

Original languageEnglish (US)
Pages (from-to)422-431
Number of pages10
JournalNaval Research Logistics
Volume49
Issue number4
DOIs
StatePublished - Jun 1 2002

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'A dual criteria sequencing problem with earliness and tardiness penalties'. Together they form a unique fingerprint.

Cite this