Full Text:   <11228>

CLC number: TP391.72

On-line Access: 

Received: 2005-10-20

Revision Accepted: 2005-11-21

Crosschecked: 0000-00-00

Cited: 0

Clicked: 16016

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.4 P.570-576

http://doi.org/10.1631/jzus.2006.A0570


Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle


Author(s):  Liu Hu-yao, He Yuan-jun

Affiliation(s):  Department of Computer Science and Technology, Shanghai Jiao Tong University, Shanghai 200030, China

Corresponding email(s):   liuhuyao@sjtu.edu.cn

Key Words:  Nesting, Cutting stock, No Fit Polygon (NFP), Genetic algorithm (GA), Lowest gravity center


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

@article{title="Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle",
author="Liu Hu-yao, He Yuan-jun",
journal="Journal of Zhejiang University Science A",
volume="7",
number="4",
pages="570-576",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A0570"
}

%0 Journal Article
%T Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle
%A Liu Hu-yao
%A He Yuan-jun
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 4
%P 570-576
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A0570

TY - JOUR
T1 - Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle
A1 - Liu Hu-yao
A1 - He Yuan-jun
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 4
SP - 570
EP - 576
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A0570


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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Adamowicz, M., Albano, A., 1976. Nesting two dimensional shapes in rectangular modules. Computer-Aided Design, 8(1):27-33.

[2] Art, R.C., 1966. An Approach to the Two Dimensional Irregular Cutting Stock Problem. IBM Cambridge Scientific Centre, Report 36-Y08.

[3] Bennell, J.A., Dowsland, K.A., Dowsland, W.B., 2001. The irregular cutting-stock problem—A new procedure for deriving the no-fit polygon. Computers & Operations Research, 28(3):271-287.

[4] Davis, L., 1985. Job Shop Scheduling with Genetic Algorithm. Proceedings of the First International Conference on Genetic Algorithm, Lawrence Erlbaum Associates Publishers, p.136-140.

[5] Dowsland, K.A., Dowsland, W.B., 1995. Solution approaches to irregular nesting problems. European Journal of Operational Research, 84(3):506-521.

[6] Fischer, A.D., Dagli, H., 2004. Employing subgroup evolution for irregular-shape nesting. Journal of Intelligent Manufacturing, 15(2):187-199.

[7] Gomes, A.M., Oliveira, J.F., 2002. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 141(2):359-370.

[8] Grinde, R.B., Cavalier, T.M., 1995. A new algorithm for the minimal-area convex enclosure problem. European Journal of Operational Research, 84(3):522-538.

[9] Hopper, E., Turton, B.C.H., 2001. A review of the application of meta-heuristic algorithms to 2D strip nesting problems. Artificial Intelligence Review, 16(4):257-300.

[10] Jakobs, S., 1996. On genetic algorithms for the nesting of polygons. European Journal of Operational Research, 88(1):165-181.

[11] Tay, F.E.H., Chong, T.Y., Lee, F.C., 2002. Pattern nesting on irregular-shaped stock using genetic algorithms. Engineering Applications of Artificial Intelligence, 15(6):551-558.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE