摘要
This paper presents a quasi-human algorithm for the rectangular strip packing problem without guillotine constraint. The basic version of the algorithm works according to seven heuristic selection rules, which are designed to select a corner-occupying action. The strengthened version of the algorithm adopts a branching scheme in which the basic version of the algorithm is applied in a heuristic series of parallel branches. Computational tests carried on eight sets of well-known benchmark instances show that the algorithm is efficient for approximately solving the problem. In comparison with the best algorithms in the literature, the algorithm performs better for zero-waste instances and large scale non-zero-waste instances.
学科与关键词
关键词
Combinatorial optimizationRectangular strip packingHeuristicQuasi-human
- A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problemCui, Yaodong*; Yang, Yuh; Cheng, Xian; Song, PeihuaCOMPUTERS & OPERATIONS RESEARCH, 2008, 35(4): 1281-1291.被引 43
- A simple randomized algorithm for two-dimensional strip packingYang, Shuangyuan*; Han, Shuihua; Ye, WeiguoCOMPUTERS & OPERATIONS RESEARCH, 2013, 40(1): 1-8.被引 23
- A two-stage intelligent search algorithm for the two-dimensional strip packing problemLeung, Stephen C. H.; Zhang, Defu*; Sim, Kwang MongEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 215(1): 57-69.被引 68
