휴리스틱 탐색 기법을 이용한 네스팅 전문가 시스템
Nesting Expert System using Heuristic Search
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
Two dimensional nesting is a common problem in industries such as the shipbuilding, automotive, clothing, shoe-making, and furniture industries, in which various parts are cut off from stock or packed in a flat space while minimizing waste or unoccupied space. Nesting is known as an NP-complete problem, which has a solution time proportional to the superpolynomial of the input size. It becomes practically impossible to find an optimal solution using algorithmic methods as the number of shapes to nest increases. Therefore, heuristic methods are commonly used to solve nesting problems. This paper presents an expert system that uses a heuristic search method based on an evaluation function for nesting problems, in which parts and stock are represented by pixels. The system is developed in CLIPS, an expert system shell, and is applied to four different kinds of example problems to verify its applicability in practical problems.
Abstract
Two dimensional nesting is a common problem in industries such as the shipbuilding, automotive, clothing, shoe-making, and furniture industries, in which various parts are cut off from stock or packed in a flat space while minimizing waste or unoccupied space. Nesting is known as an NP-complete problem, which has a solution time proportional to the superpolynomial of the input size. It becomes practically impossible to find an optimal solution using algorithmic methods as the number of shapes to nest increases. Therefore, heuristic methods are commonly used to solve nesting problems. This paper presents an expert system that uses a heuristic search method based on an evaluation function for nesting problems, in which parts and stock are represented by pixels. The system is developed in CLIPS, an expert system shell, and is applied to four different kinds of example problems to verify its applicability in practical problems.
참고문헌 (9)
- 이철수, "선박용 플랫바의 자동네스팅 및 가스", 플라즈마에 의한 NC 절단, 1996, pp.3, 283~297
- 한국찬, "레이저 절단공정에서 절단부재의 최적배치를 위한 네스팅 알고리즘", 대한용접학회지, 12(2), pp.11~19 (1994)
- 한창봉, "파라메트릭 매크로를 이용한 부재생성 및네스팅에 관한 연구", 한국해양공학회지, 13(2), pp.176~185 (1999)
- Babu, A.R., "A Generic Approach for Nesting of 2-D Parts in 2-D Sheets using Genetic and Heuristic Algorithms", Computer-Aided Design, 33, pp.879~891 (2001)
- Bennell, J.A., "The Geometry of Nesting Problems: A Tutorial", European Journal of Operational Research, 184, pp.397~415 (2008)
- Burke, E. K., "Complete and Robust No-fit Polygon Generation forthe Irregular Stock Cutting Problem", European Journalof Operational Research, 179, pp.27~49 (2007)
- Lee, W. -C., "A Heuristic for Nesting Problems of Irregular Shapes", Computer-Aided Design, 40, pp.625~633 (2008)
- Tay, F.E.H., "Pattern Nesting on Irregular-shaped Stock using Genetic Algorithms", Engineering Applications of Artificial Intelligence, 15, pp.551~558 (2002)
- Weng, W.C., "Irregular Stock Cutting System Based on AutoCAD", Advances in Engineering Software, 42, pp.634~643 (2011)