DocumentCode :
766535
Title :
Fast Nesting of 2-D Sheet Parts With Arbitrary Shapes Using a Greedy Method and Semi-Discrete Representations
Author :
Ma, Heng ; Liu, Chia-Cheng
Author_Institution :
Dept. of Ind. Manage., Chung-Hua Univ., Hsinchu
Volume :
4
Issue :
2
fYear :
2007
fDate :
4/1/2007 12:00:00 AM
Firstpage :
273
Lastpage :
282
Abstract :
An efficient approach for 2-D sheet part nesting, incorporating a novel space encoding scheme and a greedy method for placing parts, is presented. The space encoding scheme denotes the occupancy of the part and the vacancy of the material sheet by discrete strip segments with an equal width and utilizes real-number coordinates on each segment for representing the occupancy and the vacancy. The greedy method operates in an iterative fashion by generating a part sequence and searching for the best position and orientation of each part in the part sequence. The part sequences are generated by a genetic algorithm with appropriate operators. The searching, based on bound settings, results in a stable searching process that is independent of the number of the parts involved. Experimental results show that the approach proposed is able to operate in an efficient manner and the final placements for the parts are more economical in comparison with a benchmark. The greedy method is particularly efficient in cases containing parts with multiple pieces because the range of the bounds for searching is gradually reduced as the method progresses. Note to Practitioners-This paper was motivated by observing sheetmetal parts in various shapes that are arranged on a rectangular sheet manually to minimize the usage of the sheet. The manual arrangements are highly dependent on one\´s expertise and experience but the results may vary from case to case. Existing approaches to arrange the parts automatically are usually time-consuming for dealing with parts in complicated shapes. This paper suggests a simple approach using a new decomposition method to describe the parts and the sheet, and a part placing method to efficiently decide the position of each part in a sequence. The part sequences are automatically generated by a known searching algorithm. The proposed approach has been tested in many industrial cases and the results suggest its feasibility and efficiency. In future research, we- - will address the cases requiring "offsets" among parts
Keywords :
genetic algorithms; geometry; greedy algorithms; search problems; sheet metal processing; 2D sheet metal part nesting; arbitrary shapes; discrete strip segment; genetic algorithm; geometric representations; greedy method; part placing method; real-number coordinates; searching algorithm; semidiscrete representations; sheet part sequences; space encoding scheme; Computer aided manufacturing; Encoding; Genetic algorithms; Geometry; Iterative methods; Shape; Sheet materials; Strips; Technology management; Testing; Genetic algorithms (GAs); geometric representations; nesting; search methods;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2006.874973
Filename :
4147556
Link To Document :
بازگشت