Nesting and Berth Allocation by an Expert System Using Heuristic Search
- 1 School of Naval Architecture and Ocean Engineering, University of Ulsan, Ulsan, Korea
- 2 School of Industrial Management Engineering, Korea University, Seoul, Korea
Abstract
Nesting is a common problem in industries such as shipbuilding, auto-maker, clothing, shoe-making, and furniture, in which various parts are cut off from a stock or stocks while minimizing the wastes or maximizing the utilization of the stock. Berth allocation at seaside is also considered one form of two dimensional nesting problems, in which a ship is assigned a location for service during a certain time slot. This paper presents an expert system using a heuristic search method for nesting problems. The parts and stocks are represented by pixels with which utility function is used to evaluate current state in search tree. The system is developed in CLIPS, an expert system shell and applied to various example problems with different constraints and to a berth allocation example to illustrate its applicability under different conditions.
- Bennell, J.A. and Oliveira, J.F. (2008) The Geometry of Nesting Problems: A Tutorial. European Journal of Operational Research, 184, 397-415.
- Burke, E.K., Hellier, R.S.R., Kendall, G. and Whitwell, G. (2007) Complete and Robust No-Fit Polygon Generation for the Irregular Stock Cutting Problem. European Journal of Operational Research, 179, 27-49.
- Babu, A.R. and Babu, N.R. (2001) Ageneric Approach for Nesting of 2-D Parts in 2-D Sheets Using Genetic and Heuristic Algorithms. Computer-Aided Design, 33, 879-891.
- Weng, W.-C. and Kuo, H.-C. (2011) Irregular stock Cutting System Based on Auto CAD. Advances in Engineering Software, 42, 634-643.
- Sherif, S.U., Jawahar, N. and Balamurali, M. (2014) Sequential Optimization Approach for Nesting and Cutting Sequence in Laser Cutting. Journal of Manufacturing Systems, 33, 624-638.
- Zheng, J., Jiang, Z., Chen, Q. and Liu, Q. (2011) Spatial Scheduling Algorithm Minimizing Makespan at Block Assembly Shop in Shipbuilding. International Journal of Production Research, 49, 2351-2371. https://doi.org/10.1080/00207541003709536
- Koh, S., Logendran, R., Choi, D. and Woo, S. (2011) Spatial Scheduling for Shape-Changing Mega-Blocks in Shipbuilding Company. International Journal of Production Research, 49, 7135-7149. https://doi.org/10.1080/00207543.2010.535863
- Bierwirth, C. and Meisel, F. (2010) A Survey of Berth Allocation and Quay Crane Scheduling Problems in Container Terminals. European Journal of Operations Research, 202, 615-627.
- Lee, W.-C., Ma, H. and Cheng, B.-W. (2008) A Heuristic for Nesting Problems of Irregular Shapes. Computer-Aided Design, 40, 625-633.
- Tay, F.E.H., Chong, T.Y. and Lee, F.C. (2002) Pattern Nesting on Irregular-Shaped Stock Using Genetic Algorithms. Engineering Applications of Artificial Intelligence, 15, 551-558.
- Lee, C.S. and Park, G.R. (1996) Automatic Nesting and NC Cutting of Flat-Bar. IE Interfaces, 9, 283-297.
- Lee, C.S., Heo, E.-Y., Shim, J.-H., Chen, F.F. and Kim, D.-W. (2013) Ship and Nesting by Pattern Recognition and Group Arrangement. Robotics and Computer-Integrated Manufacturing, 29, 56-63.
- Frojan, P., Correcher, J.F., Alvarez-Valdes, R., Koulouris, G. and Tamarit, J.M. (2015) The Continuous Berth Allocation Problem in a Container Terminal with Multiple Quays. Expert Systems with Applications, 42, 7356-7366.