Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2006, Vol. 7 Issue (4): 570-576    DOI: 10.1631/jzus.2006.A0570
Computer & Information Science     
Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle
Liu Hu-yao, He Yuan-jun
Department of Computer Science and Technology, Shanghai Jiao Tong University, Shanghai 200030, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

Abstract  The nesting problem involves arranging pieces on a plate to maximize use of material. A new scheme for 2D irregular-shaped nesting problem is proposed. The new scheme is based on the NFP (No Fit Polygon) algorithm and a new placement principle for pieces. The novel placement principle is to place a piece to the position with lowest gravity center based on NFP. In addition, genetic algorithm (GA) is adopted to find an efficient nesting sequence. The proposed scheme can deal with pieces with arbitrary rotation and containing region with holes, and achieves competitive results in experiment on benchmark datasets.

Key words： Nesting      Cutting stock      No Fit Polygon (NFP)      Genetic algorithm (GA)      Lowest gravity center     
Received: 20 October 2005     
CLC:  TP391.72  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Liu Hu-yao
He Yuan-jun
Cite this article:

Liu Hu-yao, He Yuan-jun. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(4): 570-576.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.2006.A0570     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2006/V7/I4/570

[1] Hao Zheng, Yi-xiong Feng, Jian-rong Tan, Zhi-feng Zhang, Zi-xian Zhang. An integrated cognitive computing approach for systematic conceptual design[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2016, 17(4): 286-294.
[2] Jin Cheng, Ming-yang Tang, Zhen-yu Liu, Jian-rong Tan. Direct reliability-based design optimization of uncertain structures with interval parameters[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2016, 17(11): 841-854.
[3] Zhi-feng Zhang, Yi-xiong Feng, Jian-rong Tan, Wei-qiang Jia, Guo-dong Yi. A novel approach for parallel disassembly design based on a hybrid fuzzy-time model[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2015, 16(9): 724-736.
[4] Xiao Liu, Jia-wei Ye. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(11): 860-872.
[5] Hong-li QI, Hui ZHAO, Wei-wen LIU, Hai-bo ZHANG. Parameters optimization and nonlinearity analysis of grating eddy current displacement sensor using neural network and genetic algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(8): 1205-1212.
[6] Shervin VAKILI, Sied Mehdi FAKHRAIE, Siamak MOHAMMADI, Ali AHMADI. Low-cost fault tolerance in evolvable multiprocessor systems: a graceful degradation approach[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(6): 922-926.
[7] Mohsen GITIZADEH, Mohsen KALANTAR. Optimum allocation of FACTS devices in Fars Regional Electric Network using genetic algorithm based goal attainment[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2009, 10(4): 478-487.
[8] Peng-fei LIU, Ping XU, Shu-xin HAN, Jin-yang ZHENG. Optimal design of pressure vessel using an improved genetic algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(9): 1264-1269.
[9] Li ZHU, Zhi-shu LI, Liang-yin CHEN, Yan-hong CHENG. Two-stage evolutionary algorithm for dynamic multicast routing in mesh network[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(6): 791-798.
[10] Arash SAYYAH, Mitra AFLAKI, Alireza REZAZADEH. Optimization of total harmonic current distortion and torque pulsation reduction in high-power induction motors using genetic algorithms[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(12): 1741-1752.
[11] Qing GAO, Qin-he ZHANG, Shu-peng SU, Jian-hua ZHANG. Parameter optimization model in electrical discharge machining process[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(1): 104-108.
[12] WU Xiao-juan, ZHU Xin-jian, CAO Guang-yi, TU Heng-yong. Nonlinear modelling of a SOFC stack by improved neural networks identification[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(9): 1505-1509.
[13] SUDHAKARAN M., AJAY-D-VIMALRAJ P., PALANIVELU T.G.. GA and PSO culled hybrid technique for economic dispatch problem with prohibited operating zones[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(6): 896-903.
[14] CHEN Yue-hua, CAO Guang-yi, ZHU Xin-jian. LS-SVM model based nonlinear predictive control for MCFC system[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(5): 748-754.
[15] Ma Qi-ming, Wang Xuan-yin, Du Shuan-ping. Method and application of wavelet shrinkage denoising based on genetic algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(3 ): 14-.