This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Menon, S. Articles by Schrage, L. Search for Related Content

Order Allocation for Stock Cutting in the Paper Industry

College of Business Administration, Oklahoma State University, Stillwater, Oklahoma 74078
Graduate School of Business, University of Chicago, Chicago, Illinois 60637
smenon{at}mstm.okstate.edu
linus.schrage{at}gsb.uchicago.edu

A common problem encountered in paper-production facilities is that of allocating customer orders to machines so as to minimize the total cost of production. It can be formulated as a dual-angular integer program, with identical machines inducing symmetry. While the potential advantages of decomposing large mathematical programs into smaller subproblems have long been recognized, the solution of decomposable integer programs remains extremely difficult. Symmetry intensifies the difficulty. This paper develops an approach, based on the construction of tight subproblem bounds, to solve decomposable dual-angular integer programs and successfully applies it to solve the problem from the paper industry. This method is of particular interest as it significantly reduces the impact of symmetry.

Subject classifications: Production/scheduling; cutting stock: multimachine order allocation; Programming, integer, applications: decomposition.
History: Received September 1999; revision received May 2000; accepted October 2000.