A cooperative algorithm for constrained two-staged 2D cutting problems

被引：0
作者：
Hifi, Mhand [1 ,2 ]
Saadi, Toufik [2 ]
机构：
[1] Univ Picardie, LaRIA, FRE 2733, F-80025 Amiens, France
[2] Univ Paris 01, CERMSEM, CNRS, UMR 8095,MSE, F-75231 Paris 05, France
来源：
2006 INTERNATIONAL CONFERENCE ON SERVICE SYSTEMS AND SERVICE MANAGEMENT, VOLS 1 AND 2, PROCEEDINGS | 2006年
关键词：
combinatorial optimization; cutting problem; dynamic programming; knapsack;
D O I：
10.1109/ICSSSM.2006.320756
中图分类号：
F [经济];
学科分类号：
02 ;
摘要：
In this paper, we propose a cooperative solution procedure for the two-staged two-dimensional cutting stock problem (2TDC). We solve 2TDC by considering two key features: a search strategy and a fast filling procedure. The search strategy uses a beam-search method and the second strategy uses a local filling procedure for improving the quality of the obtained solutions.
引用
收藏
页码：928 / 933
页数：6
相关论文
共 21 条
[1]   A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems [J].
Alvarez-Valdés, R ;
Parajón, A ;
Tamarit, JM .
COMPUTERS & OPERATIONS RESEARCH, 2002, 29 (07) :925-947
[2]  
ALVAREZVALDES R, 2006, IN PRESS SIAM J COMP
[3]  
Arenales M., 1997, DECISION MAKING COND, P207
[4]  
BEASLEY JE, 1985, J OPER RES SOC, V36, P297
[5]  
BELOV G, 2003, MATHNM03 DRESD U
[6]   ALGORITHM FOR 2-DIMENSIONAL CUTTING PROBLEMS [J].
CHRISTOFIDES, N ;
WHITLOCK, C .
OPERATIONS RESEARCH, 1977, 25 (01) :30-44
[7]   A TYPOLOGY OF CUTTING AND PACKING PROBLEMS [J].
DYCKHOFF, H .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 44 (02) :145-159
[8]   A LINEAR-PROGRAMMING APPROACH TO THE CUTTING-STOCK PROBLEM [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1961, 9 (06) :849-859
[9]   MULTISTAGE CUTTING STOCK PROBLEMS OF 2 AND MORE DIMENSIONS [J].
GILMORE, PC ;
GOMORY, RE .
OPERATIONS RESEARCH, 1965, 13 (01) :94-&
[10]   An exact algorithm for constrained two-dimensional two-staged cutting problems [J].
Hifi, M ;
M'Hallah, R .
OPERATIONS RESEARCH, 2005, 53 (01) :140-150
123