A dual criteria sequencing problem with earliness and tardiness penalties

A dual criteria sequencing problem with earliness and tardiness penalties

0.00 Avg rating0 Votes
Article ID: iaor2003215
Country: United States
Volume: 49
Issue: 4
Start Page Number: 422
End Page Number: 431
Publication Date: Jun 2002
Journal: Naval Research Logistics
Authors:
Keywords: combinatorial analysis
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 1.5.

Reviews

Required fields are marked *. Your email address will not be published.