More on three-machine no-idle flow shops

摘要

Recently in this journal Saadani, Guinet, and Moalla [Comput Ind Engng 44 (2003) 425] considered the NP-hard problem of minimizing the makespan in a three-machine no-idle flow shop. We identify a simple network representation of the makespan that provides a better insight into the problem, reveals a certain anomaly resulting from the no-idle condition, and leads to some dominance relations among the machines under which the problem becomes efficiently solvable. Extensions to m-machine no-idle flow shops are also included.