A heuristic for the one-dimensional cutting stock problem with pattern reduction

被引:19
作者
Cui, Y. [1 ]
Zhao, X. [1 ]
Yang, Y. [1 ]
Yu, P. [1 ]
机构
[1] Guangxi Normal Univ, Dept Comp Sci, Guilin 541004, Guangxi, Peoples R China
关键词
cutting stock; one-dimensional cutting; pattern reduction;
D O I
10.1243/09544054JEM966
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
A sequential heuristic algorithm is presented for the one-dimensional cutting stock problem in which a set of items with specified length and demand are cut from the stock rods such that the waste is minimized. The algorithm generates a cutting pattern using items of a selected subset of the unassigned items, determines the frequency (number of times) at which the pattern can be used, deletes from the set of the unassigned items those that are assigned to the current pattern, and repeats until all items have been assigned. The selected subset is determined such that the frequency of the generated pattern can be as large as possible, provided that some constraints are observed to keep reasonable trim loss, and the cutting pattern is obtained from solving a bounded knapsack problem. The computational test on 18 classes of 1800 benchmark instances indicates that the algorithm performs better than two recently published algorithms for pattern reduction.
引用
收藏
页码:677 / 685
页数:9
相关论文
共 16 条
[1]   Generating optimal T-shape cutting patterns for rectangular blanks [J].
Cui, Y .
PROCEEDINGS OF THE INSTITUTION OF MECHANICAL ENGINEERS PART B-JOURNAL OF ENGINEERING MANUFACTURE, 2004, 218 (08) :857-866
[2]   A successive elimination method for one-dimensional stock cutting problems in ship production [J].
Dikili, A. Cemil ;
Sarioez, Ebru ;
Pek, Nazan Akman .
OCEAN ENGINEERING, 2007, 34 (13) :1841-1849
[3]   A TYPOLOGY OF CUTTING AND PACKING PROBLEMS [J].
DYCKHOFF, H .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 44 (02) :145-159
[4]   FIXED CHARGE PROBLEMS WITH IDENTICAL FIXED CHARGES [J].
FARLEY, AA ;
RICHARDSON, KV .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 18 (02) :245-249
[5]   Pattern reduction in one-dimensional cutting stock problems [J].
Foerster, H ;
Wäscher, G .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2000, 38 (07) :1657-1676
[6]   A LINEAR-PROGRAMMING APPROACH TO THE CUTTING-STOCK PROBLEM [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1961, 9 (06) :849-859
[7]   CUTTING STOCK PROBLEMS AND SOLUTION PROCEDURES [J].
HAESSLER, RW ;
SWEENEY, PE .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1991, 54 (02) :141-150
[8]   CONTROLLING CUTTING PATTERN CHANGES IN ONE-DIMENSIONAL TRIM PROBLEMS [J].
HAESSLER, RW .
OPERATIONS RESEARCH, 1975, 23 (03) :483-493
[9]  
Kellerer H, 2004, KNAPSACK PROBLEMS, P190
[10]   Pattern minimisation in cutting stock problems [J].
McDiarmid, C .
DISCRETE APPLIED MATHEMATICS, 1999, 98 (1-2) :121-130