A dual criteria sequencing problem with earliness and tardiness penalties

Joseph Y.‐T. Leung

Naval Research Logistics (NRL), 2002, vol. 49, issue 4, 422-431

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\over 2}$. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020

Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.10020

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:49:y:2002:i:4:p:422-431

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().