A branch-and-bound algorithm for the two-machine flow-shop problem with time delays

摘要

We address the flow-shop scheduling problem with two machines and time delays in order to minimize the makespan, i.e, the maximum completion time. We propose an exact algorithm based on a branch-and-bound enumeration scheme, for which we introduce a heuristic method based on a local search technique and three dominance rules. Finally, we present a computer simulation of the branch-and-bound algorithm, which was carried out on a set of 360 instances. The results show that our branch- and-bound method outperforms the state of the art exact method.