An algorithm for solving the job-shop problem. (English) Zbl 0677.90036

Summary: We propose a branch and bound method for solving the job-shop problem. It is based on one-machine scheduling problems and is made more efficient by several propositions which limit the search tree by using immediate selections. It solved for the first time the famous 10\(\times 10\) job- shop problem proposed by J. F. Muth and G. L. Thompson [Industrial scheduling (Englewood Cliffs/NJ 1963)].


90B35 Deterministic scheduling theory in operations research
65K05 Numerical mathematical programming methods
68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
90C35 Programming involving graphs or networks
Full Text: DOI