# zbMATH — the first resource for mathematics

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)].

##### MSC:
 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: