A Dynamic-Fit Heuristic Algorithm for the Rectangular Strip Packing Problem

Jiang Xingbo; Lü Xiaoqing; Liu Chengcheng; Li Monan

Journal of Computer Research and Development > 2009 > 46(3): 505-512.

Jiang Xingbo, Lü Xiaoqing, Liu Chengcheng, Li Monan. A Dynamic-Fit Heuristic Algorithm for the Rectangular Strip Packing Problem[J]. Journal of Computer Research and Development, 2009, 46(3): 505-512.

Citation:

PDF (679 KB)

A Dynamic-Fit Heuristic Algorithm for the Rectangular Strip Packing Problem

1(Institute of Computer Science and Technology, Peking University, Beijing 100871) 2(Department of Health Service, Second Military Medical University, Shanghai 200433) 3(National Engineering Research Center of New Tech in Electronic Publishing, Peking University, Beijing 100871)

More Information

Published Date: March 14, 2009

Graphical Abstract

Abstract

Abstract

Given a set of small rectangular pieces of different sizes and a rectangular container of fixed width and infinite length, the rectangular strip packing problem (RSPP) consists of orthogonally placing all the pieces within the container, without overlapping, such that the overall length of the packing is minimized. RSPP belongs to NP-hard problem in theory and has many industrial applications such as the composition of news, the cutting of clothing and the cutting of metal, etc. To solve the rectangular strip packing problem, a hybrid algorithm, which combines a novel heuristic algorithm—dynamic-fit heuristic algorithm (DFHA), with the genetic algorithm, is adopted. The DFHA algorithm can dynamically select the better-fit rectangle for packing, according to the width-fit first (WFF) rule, the height-fit first (HFF) rule, the placeable first (PF) rule, and the biggest-rectangle first (BRF) rule, and the evolutionary capability of genetic algorithm is used to optimize the height of the packing which is calculated by DFHA. The hybrid algorithm is tested on two sets of benchmark problems taken from the previous literature. The first set includes 21 instances and the other one includes 13 instances. The computational results show that the hybrid algorithm is more effective than the existing algorithms from the previous literature.

FullText(HTML)

References (0)

[1]	Ma Aman, Jiang Xianliang, Jin Guang. HDT: A Heuristic Dynamic Threshold Algorithm to Avoid Reprioritization of LEDBAT[J]. Journal of Computer Research and Development, 2020, 57(6): 1292-1301. DOI: 10.7544/issn1000-1239.2020.20190692
[2]	Dong Xueshi, Dong Wenyong, Cai Yongle. Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2018, 55(11): 2372-2385. DOI: 10.7544/issn1000-1239.2018.20180009
[3]	Dong Xueshi, Dong Wenyong, Wang Yufeng. Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2017, 54(8): 1751-1762. DOI: 10.7544/issn1000-1239.2017.20170347
[4]	Ma Chao, Deng Chao, Xiong Yao, and Wu Jun. An Intelligent Optimization Algorithm Based on Hybrid of GA and PSO[J]. Journal of Computer Research and Development, 2013, 50(11): 2278-2286.
[5]	Li Ziqiang, Tian Zhuojun, Wang Yishou, Yue Benxian. A Fast Heuristic Parallel Ant Colony Algorithm for Circles Packing Problem with the Equilibrium Constraints[J]. Journal of Computer Research and Development, 2012, 49(9): 1899-1909.
[6]	Liu Quan, Chen Hao, Zhang Yonggang, Li Jiao, Zhang Shenbin. An Ant Colony Optimization Algorithm Based on Dynamic Evaporation Rate and Amended Heuristic[J]. Journal of Computer Research and Development, 2012, 49(3): 620-627.
[7]	Zhu Xia, Li Xiaoping, and Wang Qian. Total-Idle-Time Increment Based Hybrid GA for No-Wait Flowshops with Makespan Minimization[J]. Journal of Computer Research and Development, 2011, 48(3): 455-463.
[8]	Chen Mao, Huang Wenqi. A Heuristic Algorithm for the Unequal Circle Packing Problem[J]. Journal of Computer Research and Development, 2007, 44(12): 2092-2097.
[9]	Li Qinghua, Yang Shida, and Ruan Youlin. Improving Optimization for Genetic Algorithms Based on Level Set[J]. Journal of Computer Research and Development, 2006, 43(9): 1624-1629.
[10]	Shang Ji. Study of Key Techniques of the Inference Machine Model for Function-Structure Project of the New Instrument Product Development Based on Genetic Algorithm(GA)[J]. Journal of Computer Research and Development, 2005, 42(9): 1544-1549.