A Branch-and-bound algorithm for n-job two-machine flow shop scheduling problems

In this paper, we study the n-job two machine flow shop scheduling problem, minimizing the total job flow times. The problem is mathematically formulated, and two heuristic approaches are invented to find near optimum schedules. Then a branch-and-bound algorithm is developed to obtain the optimum schedule by improving the near optimum schedule. In the algorithm, very tight lower bounds are designed to reduce the searching space. Numerical computations demonstrate that the algorithm developed in this paper is very efficient