AN ALGORITHM FOR THE 2-DIMENSIONAL ASSORTMENT PROBLEM

被引：31

作者：

BEASLEY, JE

机构：

[1] Imperial Coll of Science &, Technology, Dep of Management, Science, London, Engl, Imperial Coll of Science & Technology, Dep of Management Science, London, Engl

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1985年 / 19卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms - MANAGEMENT SCIENCE - MATHEMATICAL PROGRAMMING; LINEAR;

D O I：

10.1016/0377-2217(85)90179-1

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Consideration is given to the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting. A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut. Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.

引用

页码：253 / 261

页数：9