A Branch and Bound Heuristic for the Flow Shop Problem

Our focus in this contribution is on the flow shop problems. These problems are classified as NP-complete ones; it is why, our interest is on the branch and bound procedure to solve them. In this paper, we present a new heuristic for the flow shop scheduling problem of N jobs over M machines, with the goal of minimizing the flow time or the sum of completion times of all the jobs on the last machine. This heuristic is based on a branch & bound algorithm, while introducing some modifications for obtaining, within reasonable computing times, improved solutions. We use heuristic approaches because the problem cannot be solve exactly within accepted computing times. Experimental results are proposed in order to compare our heuristic to those available in the literature. The result obtained seems to be better than some other heuristics in the literature.