Article ID: | iaor20052535 |
Country: | Netherlands |
Volume: | 159 |
Issue: | 2 |
Start Page Number: | 420 |
End Page Number: | 429 |
Publication Date: | Dec 2004 |
Journal: | European Journal of Operational Research |
Authors: | Akkan Can, Karabati Seluk |
Keywords: | programming: branch and bound |
This paper presents a branch-and-bound algorithm for the two-machine flowshop scheduling problem with the objective of minimizing the sum of completion times. The main feature of the branch-and-bound algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the branch-and-bound algorithm can solve problems with up to 60 (45) jobs, where processing times are uniformly distributed in the [1, 10] ([1, 100]) range.