Two-machine flow-shop scheduling to minimize total late work: revisited. Issue 7 (3rd July 2019) - Chen, Xin; Wang, Zhongyu; Pesch, Erwin; Sterna, Malgorzata; Błażewicz, Jacek
ABSTRACT: This article revisits the scheduling problem in a two-machine flow-shop system with the total late work criterion, which penalizes parts of jobs executed after their due dates. Firstly, it is shown that a lower bound presented previously in the literature, in the context of a branch-and-bound algorithm proposed for the same problem, is invalid. Then a novel proposal of the branch-and-bound method is given equipped with a new lower-bound technique, as well as an upper-bound and dominance rules. Numerical experiments show that the newly proposed lower-bound technique works well in cutting unpromising branches.