This paper proposes scheduling algorithms using metaheuristics for production processes in which cranes can interfere with each other. There are many production processes that involve cranes in manufacturing industry, such as in the steel industry, so a general purpose algorithm for this problem can be of practical use. The scheduling problem for this process is very complicated and difficult to solve because the cranes must avoid interfering with each other plus each machine has its own operational constraints. Although several algorithms have been proposed for a specific problem or small-scale problem, general purpose algorithms that can be solved in real time (about 30 minutes or less) in the company’s production planning work have not been developed for large-scale problems. This paper develops some metaheuristic algorithms to obtain suboptimal solutions in a short time, and it confirms their effectiveness through 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, No.1, pp. 1-20, 2001.
2. [2] K. Ota, A. Matsubara, and H. Mizuyama, “A Study on Analytical Modeling for Machine Tool Production,” Int. J. of Automation Technol., Vol.7, No.1, pp. 83-85, 2013.
3. [3] T. Ogata, T. Okubo, H. Nagai, M. Yamamoto, M. Sugi, and J. Ota, “A Novel Algorithm for Continuous Steel Casting Scheduling with Focus on Quality Property Constraint and Slab Width Maximization,” Int. J. of Automation Technol., Vol.9, No.3, pp. 235-247, 2015.
4. [4] T. Sanaka, “Case Study on Production Schedule System in Chemical Plant,” Communications of the Operations Research Society of Japan, Vol.54, No.11, pp. 12-16, 2009 (in Japanese).
5. [5] O. Yamaguchi, A. Watanabe, H. Sasai, M. Tano, Y. Amanuma, and T. Koge, “Application of Optimization and Simulation Technology for Thin Plate Production Management System,” Communications of the Operations Research Society of Japan, Vol.56, No.11, pp. 10-15, 2011 (in Japanese).
6. [6] Y. Yoshinari, “Application of Optimization Technology to Steel Product Delivery Problem,” Systems Control and Information, Vol.60, No.8, pp. 338-343, 2016 (in Japanese).
7. [7] T. Imai, Y. Nakagawa, K. Kumamoto, M. Nohira, and T. Yamaguchi, “Multistage Job Shop Scheduling with Complex Material Handling System,” Proc. of Production Scheduling Symp. ’96, pp. 151-156, 1996 (in Japanese).
8. [8] T. Imai, K. Asada, Y. Nakagawa, K. Kumamoto, and M. Nohira, “A Scheduling System for the Steel-Making Process Using a General Approach,” Trans. of the Institute of Systems, Control and Information Engineers, Vol.10, No.4, pp. 204-210, 1997 (in Japanese).
9. [9] N. Honda, S. Mouri, and H. Ishi, “Steel making process scheduling with care interference,” Proc. of Scheduling Symposium 2002, pp. 108-113, 2002 (in Japanese).
10. [10] P. Liu and L.Tang, “The Refining Scheduling Problem with Crane Non-collision Constraint in Steel-making Process,” Proc. of the IEEE Int. Conf. on Automation and Logistics, Vol.36, pp. 536-541, 2008.
11. [11] X. Xie and L.Tang, “Heuristics of Scheduling a Single Crane in Batch Annealing Process,” Int. Joint Conf. on Computational Sciences and Optimization, Vol.27, pp. 891-894, 2009.
12. [12] K. H. Kim and Y. M. Park, “A crane scheduling method for port container terminals,” European J. of Operational Research, Vol.156, No.3, pp. 752-768, 2004.
13. [13] L. Moccia, J. F. Cordeau, M. Gaudioso, and G. Laporte, “A Branch-and-Cut Algorithm for the Quay Crane Scheduling Problem in a Container Terminal,” Wiley InterScinece, pp. 45-59, 2005.
14. [14] M. Sammarra, J. F. Cordeau, G. Laporte, and M. F. Monace, “A tabu search heuristic for the quay crane scheduling problem,” J. of Scheduling, Vol.10, pp. 327-336. 2007.
15. [15] S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, “Hybrid evolutionary computation methods for quay crane scheduling problems,” Computers & Operations Research, Vol.40, pp. 2083-2093, 2013.
16. [16] W. C. Ng and K. L. Mak, “Yard crane scheduling in port container terminals,” Applied Mathematical Modelling, Vol.29, pp. 263-276, 2005.
17. [17] C. Bierwirth and F. Meisel, “A fast heuristic for quay crane scheduling with interference constraints,” J. of Scheduling, Vol.12, pp. 345-360, 2009.
18. [18] T. Tanizaki and T. Kataoka, “A Scheduling Algorithm for Job-Shop Process with Crane Interference,” J. of Japan Association for Management Systems, Vol.31, No.3, pp. 319-324, 2015 (in Japanese).
19. [19] F. Glover, “A template for scatter search and path relinking,” Artificial Evolution, Vol.1363 of the series Lecture Notes in Computer Science, pp. 1-51, 2005.
20. [20] M. Yagiura and T. Ibaraki, “Combinational Optimization,” Asakura Publishing Co., Ltd., 2001 (in Japanese).