An Efficient Algorithm for Multi-Item Scheduling

A number of resource-allocation problems, including that of multi-item scheduling, may be solved approximately as large linear programs, as in Manne [ Management Sci. 4, 115–135 (1958)]. Dzielinski and Gomory [ Management Sci. 11, 874–890 (1965)] applied the Dantzig-Wolfe decomposition principle to this problem. Here, the problem is attacked directly, using a column generation technique and Dantzig and Van Slyke's generalized upper-bounding method [ J. Comp. and Syst. Sci. 1, 213–226 (1967)]. For problems involving I items and T time periods, one need deal with a basis matrix of dimension only T by T . A lower bound on the optimal cost may be developed, and intermediate solutions all have Manne's integer property (loc. cit.). Computational experiments, including an option for pricing out subproblem solutions until none is useful, show a number of iterations to optimality of from one-half to one-ninth the number required by the decomposition principle with work per iteration remaining approximately the same. Extensions of the basic model are also described. These form the core of an automated production-scheduling and inventory-control system, currently being used by a major U. S. manufacturer. Computational experience with this extended model is presented.