Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

0.00 Avg rating0 Votes
Article ID: iaor20001517
Country: Netherlands
Volume: 114
Issue: 2
Start Page Number: 403
End Page Number: 410
Publication Date: Apr 1999
Journal: European Journal of Operational Research
Authors: ,
Keywords: parallel machines
Abstract:

We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(n log n) time.

Reviews

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