Average-case analysis of cutting and packing in two dimensions

Average-case analysis of cutting and packing in two dimensions

0.00 Avg rating0 Votes
Article ID: iaor1991212
Country: Netherlands
Volume: 44
Issue: 2
Start Page Number: 134
End Page Number: 144
Publication Date: Jan 1990
Journal: European Journal of Operational Research
Authors: ,
Keywords: cutting plane algorithms
Abstract:

Stock-cutting and packing in two dimensions is a source of problems of great practical significance. Much has been written on the subject, including several surveys, but the focus of the mathematically oriented research has been largely on combinatorical optimization and worst-case analysis. Recently, substantial progress has been made in the average-case analysis of algorithms for two-dimensional packing. This paper reviews selected, illustrative results in this area of research, and discusses desirable extensions and open problems. Several cutting and packing algorithms are defined and the results of their probabilistic analysis reported. From the presentation of this material it is clear that the field is still in early stages of development; the algorithms and probability models tend to be simplistic, and estimates of performance are far more common than exact measures. In spite of these limitations, valuable and in some cases unexpected insights have emerged.

Reviews

Required fields are marked *. Your email address will not be published.