In manufacturing industries, customers demand a wide variety of products, with high quality and fast delivery. Production scheduling systems have become critical for efficient operation. However, scheduling problems in manufacturing are generally large and complex with many constraints. It is difficult to create an optimal production schedule that satisfies all constraints within a reasonable timeframe. This study targets a factory with multiple working machines and two overhead cranes. Our research aims to obtain a solution algorithm to avoid interference of overhead cranes and machine competition and a production plan that minimizes the total makespan for each job. As the problem must be solved within a reasonable timeframe, we have developed the solution algorithm using metaheuristics and scheduling simulation. In general, metaheuristic algorithms must strike a balance between an intensive search for good solutions and a search for diverse solutions. Accordingly, we propose a new algorithm using path relinking in a scatter search. This method was demonstrated to be effective in obtaining good solutions with little variation in numerical experiments. In this paper, we describe previous research, our target process, and new solution algorithm and discuss algorithm design methods based on computer experiments.

1. [1] L. Tang, J. Liu, A. Rong, and Z. Yang, “A review of planning and scheduling systems and methods for integrated steel production,” European J. of Operational Research, Vol.133, Issue 1, pp. 1-20, 2001.
2. [2] T. Tanizaki, T. Tamura, H. Sakai, Y. Takahashi, and T. Imai, “A heuristic scheduling algorithm for steel making process with crane handling,” J. of the Operations Research Society of Japan, Vol.49, No.3, pp. 188-201, 2006.
3. [3] Y. Tanizaki and H. Katagiri, “Genetic Algorithms with Simulation for a Job Shop Scheduling Problem with Crane Conveyance,” IFIP Advances in Information and Communication Technology, Vol.513, Part 1, pp. 483-491, 2017.
4. [4] T. Tanizaki, H. Katagiri, and A. O. N. René, “Scheduling Algorithms Using Metaheuristics for Production Processes with Crane Interference,” Int. J. Automation Technol., Vol.12, No.3, pp. 297-307, 2018.
5. [5] K. H. Kim and Y.-M. Park, “A crane scheduling method for port container terminals,” European J. of Operational Research, Vol.156, Issue 3, pp. 752-768, 2004.
6. [6] W. C. Ng, “Crane scheduling in container yards with inter-crane interference,” European J. of Operational Research, Vol.164, Issue 1, pp. 64-78, 2005.
7. [7] D.-H. Lee, H. Q, Wang, and L. Miao, “Quay crane scheduling with non-interference constraints in port container terminals,” Transportation Research Part E: Logistics and Transportation Review, Vol.44, Issue 1, pp. 124-135, 2008.
8. [8] C. Bierwirth and F. Meisel, “A fast heuristic for quay crane scheduling with interference constraints,” J. of Scheduling, Vol.12, Issue 4, pp. 345-360, 2009.
9. [9] A. Lajjam, M. El Mohamed, T. Yassine, and M. Abdellatif, “An Efficient Algorithm for Solving Quay Crane Assignment Problem,” Int. J. of Research in Manufacturing Technology & Management, Vol.2, Issue 1, pp. 13-18, 2009.
10. [10] S. H. Chung and K. L. Choy, “A modified genetic algorithm for quay crane scheduling operations,” Expert Systems with Applications, Vol.39, Issue 4, pp. 4123-4221, 2012.
11. [11] Y.-M. Fu, A. Diabat, and I.-T. Tsai, “A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach,” Expert Systems with Applications, Vol.41, Issue 15, pp. 6959-6961, 2014.
12. [12] Y. Guan, K.-H. Yang, and Z. Zhou, “The crane scheduling problem: Models and solution approaches,” Annals of Operations Research, Vol.203, Issue 1, pp. 119-139, 2013.
13. [13] R. Tavakkoli-Moghaddam, A. Makui, S. Salahi, M. Bazzazi, and F. Taheri, “An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports,” Computers & Industrial Engineering, Vol.56, Issue 1, pp. 241-248, 2009.
14. [14] L. Song, T. Cherrett, and W. Guan, “Study on berth planning problem in a container seaport: Using an integrated programming approach,” Computers & Industrial Engineering, Vol.62, Issue 1, pp. 119-128, 2012.
15. [15] G. Zäpfel and M. Wasner, “Warehouse sequencing in the steel supply chain as a generalized job shop model,” Int. J. of Production Economics, Vol.104, Issue 2, pp. 482-501, 2006.
16. [16] L. Tang, X. Xie, and J. Liu, “Crane scheduling in a warehouse storing steel coils,” IIE Trans., Vol.46, Issue 3, pp. 267-282, 2014.
17. [17] X. Xie, Y. Zheng, and Y. Li, “Multi-crane scheduling in steel coil warehouse,” Expert Systems with Applications, Vol.41, Issue 6, pp. 2874-2885, 2014.
18. [18] X. Xie, Y. Zheng, and Y. Li, “Genetic Algorithm and its Performance Analysis for Scheduling a Single Crane,” Discrete Dynamics in Nature and Society, Vol.2015, 2015.
19. [19] A. Dohn and J. Clausen, “Optimising the Slab Yard Planning and Crane Scheduling Problem using a two-stage heuristic,” Int. J. of Production Research, Vol.48, Issue 15, pp. 4585-4608, 2010.
20. [20] Y. Kung, Y. Kobayashi, T. Higashi, M. Sugi, and J. Ota, “Order scheduling of multiple stacker cranes on common rails in an automated storage/retrieval system,” Int. J. of Production Research, Vol.52, Issue 4, pp. 1171-1187, 2014.
21. [21] X. Cheng, L. Tang, and P. M. Pardalos, “A Branch-and-Cut algorithm for factory crane scheduling problem,” J. of Production Research, Vol.63, Issue 4, pp. 729-755, 2015.
22. [22] B. Peterson, I. Harjunkoski, S. Hoda, and J. N. Hooker, “Scheduling multiple factory cranes on a common track,” Computers & Operations Research, Vol.48, pp. 102-112, 2014.
23. [23] J. Li, A. Xu, and X. Zang, “Simulation-based solution for a dynamic multi-crane-scheduling problem in a steelmaking shop,” Int. J. of Production Research, Vol.58, Issue 22, pp. 6970-6984, 2020.
24. [24] F. Yuan, K. Feng, S. Lin, and A. Xu, “A study on DAA-based crane scheduling models for steel plant,” Int. J. of Production Research, Vol.59, Issue 20, pp. 6241-6251, 2021.
25. [25] F. Glover, M. Laguna, and R. Martí, “Fundamentals of Scatter Search and Path Relinking,” Control and Cybernetics, Vol.29, No.3, pp. 653-684, 2000.
26. [26] M. Laguna and R. Marti, “Scatter Search: Methodology and Implementations in C,” Springer, 2003.