A branch and bound algorithm for job-shop scheduling

Abstract EN

The problem of scheduling jobs in a general job-shop to minimize the maximum completion time is considered.

A branch and bound algorithm is proposed.

The lower bound is obtained from the preemptive schedules which fqrm solutions of single machine subproblems.

In the branching rule, a set of operations which each require the same machine is selected and branches of the search tree corresponding to the possibilities that an operation of this set is sequenced before (or after) the optohretersd..

Computational experience with a v.ariety of test problems is re-poted.