Full Text:
<12005>
CLC number: TP391.72
On-line Access:
Received: 2005-10-20
Revision Accepted: 2005-11-21
Crosschecked: 0000-00-00
Cited: 0
Clicked: 16925
Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle
| |||||||||||||
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.
[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>