On no-wait and no-idle flowshops with makespan criterion

On no-wait and no-idle flowshops with makespan criterion

0.00 Avg rating0 Votes
Article ID: iaor2009242
Country: Netherlands
Volume: 178
Issue: 3
Start Page Number: 677
End Page Number: 685
Publication Date: May 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: flowshop
Abstract:

The paper deals with the NP-hard problems of minimizing the makespan in m-machine no-wait and no-idle permutation flowshops. We identify networks whose longest path lengths represent the makespans. These networks reveal the duality between the two problems, and show graphical explanations of the fact that under no-wait and no-idle conditions the makespan can be a decreasing function of some job processing times. Moreover, they also lead to a natural reduction of the no-wait flowshop problem to the traveling salesman problem, some lower bounds on the shortest makespan, and new efficiently solvable special cases.

Reviews

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