An Efficient Algorithm for Multi-Item Scheduling

L. S. Lasdon and R. C. Terjung
Additional contact information
L. S. Lasdon: Case Western Reserve University, Cleveland, Ohio
R. C. Terjung: Goodyear Tire and Rubber Co., Akron, Ohio

Operations Research, 1971, vol. 19, issue 4, 946-969

Abstract: 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.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (36)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.4.946 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:19:y:1971:i:4:p:946-969

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().