Complexity of the job insertion problem in multi-stage scheduling

Complexity of the job insertion problem in multi-stage scheduling

0.00 Avg rating0 Votes
Article ID: iaor20083765
Country: Netherlands
Volume: 35
Issue: 6
Start Page Number: 754
End Page Number: 758
Publication Date: Nov 2007
Journal: Operations Research Letters
Authors: , ,
Abstract:

The job insertion problem in multi-stage scheduling is: given a schedule for n jobs and an additional job, find a feasible insertion of the additional job into the schedule that minimizes the resulting makespan. We prove that finding the optimal job insertion is NP-hard for flow shops and open shops.

Reviews

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