A branch and bound algorithm for the two-machine flowshop problem with unit-time operations and time delays. Issue 2 (7th March 2014) - Moukrim, Aziz; Rebaine, Djamal; Serairi, Mehdi
Abstract : In this paper we consider the problem of scheduling, on a two-machine flowshop, a set of unit-time operations subject to time delays with respect to the makespan. This problem is known to be\hbox{${\cal NP}$} 𝒩𝒫 -hard in the strong sense. We propose an algorithm based on a branch and bound enumeration scheme. This algorithm includes the implementation of new lower and upper bound procedures, and dominance rules. A computer simulation to measure the performance of the algorithm is provided for a wide range of test problems.