The parallel machine min‐max weighted absolute lateness scheduling problem

Chung‐Lun Li and T. C. E. Cheng

Naval Research Logistics (NRL), 1994, vol. 41, issue 1, 33-46

Abstract: Given a set of jobs, a processing time and a weight for each job, several parallel and identical machines, and a common due date that is not too early to constrain the scheduling decision, we want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. We show that this problem is NP‐complete even for the single‐machine case, and is strongly NP‐complete for the general case. We present a polynomial time heuristic for this problem and analyze its worst‐case performance. Empirical testing of the heuristic is reported, and the results suggest that the performance is asymptotically optimal as the number of jobs tends to infinity. © 1994 John Wiley & Sons, Inc.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199402)41:13.0.CO;2-S

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:41:y:1994:i:1:p:33-46

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 ().