Job-Shop Scheduling by Implicit Enumeration

The classical combinatorial optimization problem of minimizing maximum completion time in a general job-shop has been the subject of extensive research. In this paper we review and extend this work. A general bounding approach is developed which includes all previously presented lower bounds as special cases. The strongest bound obtainable in this way is combined with two enumeration schemes, the relative merits of which are discussed. The results of some computational experiments and a large bibliography are included as well.