Computer Science ›› 2020, Vol. 47 ›› Issue (11A): 119-125.doi: 10.11896/jsjkx.200200016

• Artificial Intelligence • Previous Articles     Next Articles

Hybrid Search Algorithm for Two Dimensional Guillotine Rectangular Strip Packing Problem

GUO Chao1,2, WANG Lei1,2, YIN Ai-hua3   

  1. 1 College of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430065,China
    2 Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System,Wuhan University of Science and Technology,Wuhan 430065,China
    3 School of Software and Communication Engineering,Jiangxi University of Finance and Economics,Nanchang 330013,China
  • Online:2020-11-15 Published:2020-11-17
  • About author:GUO Chao,born in 1994,postgraduate.His main research interests include heuristic algorithm for packing problems.
    WANG Lei,born in 1977,Ph.D,lectu-rer.His main research interests include heuristic algorithm for rectangular packing problems and job shop scheduling problem.
  • Supported by:
    This work was supported by the National Natural Science Foudation of China(61862027,71701156).

Abstract: The guillotine rectangular strip packing problem is NP-hard.This problem has industrial applications such as glass cutting and integrated circuit layout design.These real world applications can be formulated as packing problems with the objective of maximize the usage ratio of the materials.The whole sketch is as follows.Firstly,a hybrid search algorithm is presented for solving the two dimensional guillotine rectangular packing problem (2D-GRPP),then the hybrid search algorithm is adopted for solving the two dimensional guillotine rectangular strip packing problem (2D-GRSPP) in the manner of jump search and binary search.According to the quasi-human approach,the basic definitions such as corner-occupying,action space,maximal height and rectangle combination are presented so as to induce the basic algorithm.Based on the basic algorithm,the hybrid search algorithm involves three phases.In the first phase,the initial solution is generated.In the second phase,the local search procedure runs to adjust the priority numbers of the rectangles.When the local search procedure encounters local optimal solutions,the off-trap strategy procedure is used to jump out of the trap and guide the search into the new areas.In the third phase,the beauty degree enumeration procedure is adopted to improve the selection of the corner-occupying actions.The hybrid search algorithm (called HS) is tested on two sets of 91 benchmark instances.The computational results show that the proposed algorithm generally outperforms the best heuristics (called SPTRS) in the literature up to now.The mean relative errors of HS and SPTRS are 3.83% and 4.26%,respectively.The HS algorithm is efficient for solving the problem.

Key words: Global optimization, Guillotine, Heuristic, Quasi-human, Rectangular strip packing

CLC Number: 

  • TP301
[1] LODI A,MARTELLO S,VIGO D.Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems [J].INFORMS Journal on Computing,1999,11(4):345-357.
[2] MARTELLO S,MONACI M,VIGO D.An exact approach tothe strip packing problem [J].INFORMS Journal on Computing,2003,15(3):310-319.
[3] JIANG X B,L X Q,LIU C C.Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem [J].Journal of Software,2009,20(6):1528-1538.
[4] CUI Y D,YANG Y L,CHENG X,et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem [J].Computers & Operations Research,2008,35(4):1281-1291.
[5] HUANG W Q,CHEN D B,XU R C.A new heuristic algorithm for rectangle packing [J].Computers & Operations Research,2007,34(11):3270-3280.
[6] HUANG W Q,CHEN D B.An efficient heuristic algorithm for rectangle-packing problem [J].Simulation Modelling and Practice Theory,2007,15(10):1356-1365.
[7] HE K,HUANG W Q,JIN Y.Efficient algorithm based on action space for solving the 2D rectangular packing problem [J].Journal of Software,2012,23(5):1037-1044.
[8] WANG L,YIN A H.A beauty degree enumeration algorithm for the 2D rectangular packing problem [J].Scientia Sinica Informationis,2015,45(9):1127-1140.
[9] HUANG W Q,HE K.A pure quasi-human algorithm for solving the cuboid packing problem [J].Science China Series F:Information Sciences,2009,52(1):52-58.
[10] HE K,HUANG W Q.An efficient place heuristic for three-dimensional rectangular packing [J].Computers & Operations Research,2011,38(1):227-233.
[11] ZHANG D F,SHI L Y,LEUNG S C H,et al.A priority heuristic for the guillotine rectangular packing problem [J].Information Processing Letters,2016,116(1):15-21.
[12] BORTFELDT A,JUNGMANN S.A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint [J].Annals of Operations Research,2012,196(1):53-71.
[13] ALVAREZ-VALDES R,PARRENO F,TAMMRIT J M.Reactive GRASP for the strip-packing problem [J].Computers & Operations Research,2008,35(4):1065-1083.
[14] LEUNG S C H,ZHANG D F.A two-stage intelligent search algorithm for the two-dimensional strip packing problem [J].European Journal of Operational Research,2011,215(1):57-69.
[15] WEI L J,OON W C,ZHU W B,et al.A skyline heuristic for the 2D rectangular packing and strip packing problems [J].Euro-pean Journal of Operational Research,2011,215(2):337-346.
[16] YANG S Y,HAN S H,YE W G.A simple randomized algorithm for two-dimensional strip packing [J].Computers & Operations Research,2013,40(1):1-8.
[17] WEI L J,QIN H,CHEANG B,et al.An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem [J].International Transactions in Operational Research,2016,232(1/2):65-92.
[18] ZHANG D F,CHE Y X,YE F R,et al.A hybrid algorithm based on variable neighborhood for the strip packing problem [J].Journal of Combinatorial Optimization,2016,32(2):513-530.
[19] BORTFELDT A.A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces [J].European Journal of Operational Research,2006,172(3):814-837.
[20] HE K,HUANG W Q,JIN Y.An efficient deterministic heuristic for two-dimensional rectangular packing [J].Computers & Operations Research,2012,39(7):1355-1363.
[21] DENG J K,WANG L,YIN A H.A quasi-human global optimization algorithm for solving the two dimensional rectangular packing problem [J].Computer Engineering & Science,2018,40(2):331-340.
[22] WANG L,YIN A H.A quasi-human algorithm for the two dimensional rectangular strip packing problem:in memory of Prof.Wenqi Huang [J].Journal of Combinatorial Optimization,2016,32(2):416-444.
[23] HOPPER E,TURTON B C H.An empirical investigation ofmeta-heuristic and heuristic algorithm for a 2D packing problem [J].European Journal of Operational Research,2001,128(1):34-57.
[1] GENG Hai-jun, WANG Wei, YIN Xia. Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks [J]. Computer Science, 2022, 49(2): 329-335.
[2] GUO Biao, TANG Qi, WEN Zhi-min, FU Juan, WANG Ling, WEI Ji-bo. List-based Software and Hardware Partitioning Algorithm for Dynamic Partial Reconfigurable System-on-Chip [J]. Computer Science, 2021, 48(6): 19-25.
[3] LIU Zhong-hui, ZHAO Qi, ZOU Lu, MIN Fan. Heuristic Construction of Triadic Concept and Its Application in Social Recommendation [J]. Computer Science, 2021, 48(6): 234-240.
[4] GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm [J]. Computer Science, 2021, 48(12): 304-311.
[5] TANG Wen-jun, LIU Yue, CHEN Rong. User Allocation Approach in Dynamic Mobile Edge Computing [J]. Computer Science, 2021, 48(1): 58-64.
[6] GUO Fei-yan, TANG Bing. Mobile Edge Server Placement Method Based on User Latency-aware [J]. Computer Science, 2021, 48(1): 103-110.
[7] ZHANG Yu-qin, ZHANG Jian-liang and FENG Xiang-dong. Parametric-free Filled Function Algorithm for Unconstrained Optimization [J]. Computer Science, 2020, 47(6A): 54-57.
[8] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[9] ZHANG Xu, WANG Li-li, YANG Bo-tao. Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints [J]. Computer Science, 2020, 47(5): 212-216.
[10] PAN Heng, LI Jing feng, MA Jun hu. Role Dynamic Adjustment Algorithm for Resisting Insider Threat [J]. Computer Science, 2020, 47(5): 313-318.
[11] YANG Ting, LUO Fei, DING Wei-chao, LU Hai-feng. Bin Packing Algorithm Based on Adaptive Optimization of Slack [J]. Computer Science, 2020, 47(4): 211-216.
[12] LI Zhang-wei,WANG Liu-jing. Population Distribution-based Self-adaptive Differential Evolution Algorithm [J]. Computer Science, 2020, 47(2): 180-185.
[13] LUO Fei, REN Qiang, DING Wei-chao, LU Hai-feng. Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack [J]. Computer Science, 2019, 46(9): 315-320.
[14] SONG Xin,ZHU Zong-liang,GAO Yin-ping,CHANG Dao-fang. Vessel AIS Trajectory Online Compression Algorithm Combining Dynamic Thresholding and Global Optimization [J]. Computer Science, 2019, 46(7): 333-338.
[15] NI Hong-jie, PENG Chun-xiang, ZHOU Xiao-gen, YU Li. Differential Evolution Algorithm with Stage-based Strategy Adaption [J]. Computer Science, 2019, 46(6A): 106-110.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!