A new branching scheme for job shop scheduling

The job-shop scheduling problem consists in scheduling a set of jobs on a set of machines, in order to minimize the makespan. In this paper, we develop and implement a variation of a branch-and-bound method for solving the job-shop scheduling problem, presented by Brucker, Jurisch and Sievers. The modifications refer to the lower bound method and to the branching scheme. The lower bound is obtained by solving a one-machine scheduling problem with lags. A relaxation of this problem can be solved in polynomial time by the early–late algorithm, developed by Lourenÿo. We studied some branching rules that can be adapted to this new lower bound method, in a way that the successive partition of feasible solutions set gives good lags. We present some computational results in order to compare the different versions of the branch-and-bound method.