A note on valid inequalities for minimizing the total tardiness in a two-machine flow shop
本文指出Kharbeche和Haouari（2013）提出的一个有效不等式有误，会导致解空间排除所有最优解，并给出了修正的不等式。数值实验显示，在10到20个工件的算例中，10%到22%的所谓最优解实际上不是最优，目标函数值损失最高达12%。
This note reconsiders the valid inequalities designed by Kharbeche and Haouari (2013 Kharbeche, M., & Haouari, M. (2013). MIP models for minimizing total tardiness in a two-machine flow shop. Journal of the Operational Research Society, 64(5), 690–707. https://doi.org/10.1057/jors.2012.89[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]) for mixed-integer programming formulations of minimizing the total tardiness in a two-machine flow shop scheduling problem. While the majority of their proposed valid inequalities are able to substantially improve the computational time to find an optimal solution, we show that one of them is incorrect, due to the misinterpretation of a dominance criterion proven in Pan and Fan (1997 Pan, J. C.-H., & Fan, E.-T. (1997). Two-machine flowshop scheduling to minimize total tardiness. International Journal of Systems Science, 28(4), 405–414. https://doi.org/10.1080/00207729708929401[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]). As a consequence, in some instances, all optimal solutions are excluded from the solution space, resulting in suboptimal solutions. To resolve this issue, we first demonstrate the suboptimality of the proposed valid inequality with a small illustrative example. Second, we formulate a new valid inequality, which correctly captures the dominance criteria of Pan and Fan (1997 Pan, J. C.-H., & Fan, E.-T. (1997). Two-machine flowshop scheduling to minimize total tardiness. International Journal of Systems Science, 28(4), 405–414. https://doi.org/10.1080/00207729708929401[Taylor & Francis Online], [Web of Science ®] , [Google Scholar]). Finally, we show the effect of this correction on the solution quality in a numerical study with scheduling instances that have 10 to 20 jobs. Depending on the number of jobs, between 10% and 22% of the supposedly optimal solutions with the incorrect valid inequality are in fact suboptimal. In terms of the objective function value, the error results in a loss of up to 12%.