SOLVING TWO-DIMENSIONAL BIN PACKING PROBLEMS WITH TWO-STAGE GUILLOTINE CUTTING BY COMBINED LOCAL SEARCH HEURISTICS

被引:0
作者
Chan, T. M. [1 ]
Alvelos, Filipe [1 ,2 ]
Silva, Elsa [1 ]
Valerio de Carvalho, J. M. [1 ,2 ]
机构
[1] Univ Minho, Ctr Invest Algoritmi, P-4710057 Braga, Portugal
[2] Univ Minho, Dept Prod & Sistemas, P-4710057 Braga, Portugal
来源
PACIFIC JOURNAL OF OPTIMIZATION | 2013年 / 9卷 / 03期
关键词
two-dimensional guillotine bin packing problems; local search heuristics; variable neighborhood descent (VND); random neighbor selection (RNS); optimization; NEIGHBORHOOD DESCENT ALGORITHM; OPTIMIZATION;
D O I
暂无
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, a new efficient algorithm named combined local search heuristics which comprise two local search heuristics, Variable Neighborhood Descent (VND) and Random Neighbor Selection (RNS), is designed and proposed to solve two-dimensional guillotine bin packing problems. The objective of these problems is to pack smaller pieces of rectangular items into large rectangular bins without overlapping such that the total number of used bins is minimized. A constructive heuristic (CH) is conceived to construct a solution by packing items into bins with the use of a defined item packing sequence. VND and RNS, which consist of three deterministic neighborhood structures and three random neighbor selection operators, respectively, are used for improving a solution given by the CH. Benchmark instances were adopted to verify the effectiveness of the designed algorithm via computational experiments. Computational results show that, in terms of the quality of solutions, the proposed approach is better than other heuristics and metaheuristics. In terms of computational times, the proposed algorithm cannot be compared to other algorithms and the computational experiments cannot offer enough evidence of showing any good running-time behavior of the proposed algorithm because of different models of computers used. However, from a practical point of view, easy implementation and reasonable and affordable computational times confirm the usefulness of the proposed algorithm.
引用
收藏
页码:391 / 412
页数:22
相关论文
共 23 条
[1]   TWO-DIMENSIONAL FINITE BIN-PACKING ALGORITHMS [J].
BERKEY, JO ;
WANG, PY .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1987, 38 (05) :423-429
[2]   An evolutionary framework for 3-SAT problems [J].
Borgulya, I .
ITI 2003: PROCEEDINGS OF THE 25TH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2003, :471-476
[3]   The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds [J].
Boschetti, Marco A. ;
Mingozzi, Aristide .
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (02) :135-147
[4]  
Carter M.W., 2001, Operations research: a practical introduction
[5]   A jumping gene paradigm for evolutionary multiobjective optimization [J].
Chan, T. M. ;
Man, K. F. ;
Kwong, S. ;
Tang, K. S. .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2008, 12 (02) :143-159
[6]   ON PACKING TWO-DIMENSIONAL BINS [J].
CHUNG, FRK ;
GAREY, MR ;
JOHNSON, DS .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (01) :66-76
[7]   Topological design optimization of a Yottabit-per-second lattice network [J].
Dégila, JR ;
Sansò, B .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2004, 22 (09) :1613-1625
[8]   New resolution algorithm and pretreatments for the two-dimensional bin-packing problem [J].
El Hayek, Joseph ;
Moukrim, Aziz ;
Negre, Stephane .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (10) :3184-3201
[9]   A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems [J].
Gao, Jie ;
Sun, Linyan ;
Gen, Mitsuo .
COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (09) :2892-2907
[10]   A parallel hybrid heuristic for the multicommodity capacitated location problem with balancing requirements [J].
Gendron, B ;
Potvin, JY ;
Soriano, P .
PARALLEL COMPUTING, 2003, 29 (05) :591-606