Two-machine flow-shop scheduling to minimize total late work: revisited |
| |
| Authors: | Xin Chen Zhongyu Wang Erwin Pesch Jacek B?a?ewicz |
| |
| Affiliation: | 1. School of Electronics and Information Engineering, Liaoning University of Technology, Jinzhou, PR China;2. School of Software, Dalian University of Technology, Dalian, PR China;3. Faculty III, University of Siegen, Siegen, Germany;4. Center for Advanced Studies in Management, Handelshochschule Leipzig (HHL Leipzig Graduate School of Management), Leipzig, Germany;5. Institute of Computing Science, Poznań University of Technology, Poznań, Poland;6. Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznań, Poland;7. European Centre for Bioinformatics and Genomics, Poznań, Poland |
| |
| 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. |
| |
| Keywords: | Late work flow shop branch-and-bound algorithm |
|
|
