The parallel machine min-max weighted absolute lateness scheduling problem

The parallel machine min-max weighted absolute lateness scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor19941471
Country: United States
Volume: 41
Issue: 1
Start Page Number: 33
End Page Number: 46
Publication Date: Feb 1994
Journal: Naval Research Logistics
Authors: ,
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, the authors want to find an optimal job schedule so as to minimize the maximum weighted absolute lateness. They show that this problem is NP-complete even for the single-machine case, and is strongly NP-complete for the general case. The authors 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.

Reviews

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