Erratum to 'Johnson's algorithm: A key to solve optimally or approximately flowshop scheduling problems with unavailability periods'[International Journal of Production Economics 121 (2009) 81-87]

摘要

In Allaoui, H., Artiba, A., 2009. Johnson's algorithm: a key to solve optimally or approximately flowshop scheduling problems with unavailability periods. International Journal of Production Economics 121, 81-87, the authors propose optimality conditions for the Johnson sequence in the presence of one unavailability period on the first machine and pretend for a performance guarantee of 2 when several unavailability periods may occur. We establish in this note that these conditions are false, and that minimizing the makespan in the presence of more than one unavailability period is not in APX, unless P = NP. We also point out that the results given for the stochastic part of the problem are incorrect. Finally, we propose a simplified proof and a generalization for the two-stage hybrid flowshop.