Hot rolling batch scheduling problems are NP-hard and have a large number of multi-criteria constraints that do not allow to develop a feasible solution. The goal of this research is to generate plans with minor technological violations quickly and efficiently and to avoid any serious violations. A standardized method of transforming the problem with technological constraints into a constrained optimization problem and a heuristic threshold algorithm are proposed. The algorithm threshold system is determined by penalty constants. An equivalence relation is introduced for threshold systems. The threshold algorithm generates the same plan for any two equivalent threshold systems. An effective algorithm for automatic selection of penalty constants based on real data is also proposed. The model was tested at plate rolling shops of the Magnitogorsk Iron and Steel Works with the purpose of scheduling manufacture, storage and shipment of flat rolled products.
hot rolling batch scheduling, dynamic scheduling, threshold algorithm, heuristics.
Стр. 106-114.
References
1. Balas, E. 1989. The prize collecting traveling salesman problem. Networks. 19:621–636. doi: 10.1002/net.3230190602.
2. Kosiba E. D., Right J.R., & Cobbs A. E. 1992. Discrete event sequencing as a traveling salesman problem. Computers in Industry. 19:317–327. doi: 10.1016/0166- 3615(92)90069-Y.
3. Cowling, P. I. 1995. Optimization in Industry (ch. Optimization in steel hot rolling). Wiley, Chichester, England.
4. Lopez L, Carter M. W., & Gendreau M. 1998. The hot strip mill production scheduling problem: A tabu search approach. European Journal of Operation Research. 106(2- 3):317–335. doi: 10.1016/S0377-2217(97)00277-4.
5. Tang L., Liu J., Rong A., & Yang Z. 2000. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operation Research. 124(2):267–282. doi: 10.1007/s10878-017-0130-4.
6. Jia S.J., Yi J., Yang G.K., Du B., & Zhu J. 2013. Multiobjective optimization algorithm for the hot rolling batch scheduling problem. International Journal of Production Research. 51(3):667-681. doi: 10.1080/00207543.2011.654138.
7. Zixuan W., Tieke L., & Bailin W. 2016. Hybrid variable neighborhood search for batch scheduling of hot rolled steel tube. 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC): 335–338. doi:10.1109/IMCEC.2016.7867228.
8. Pan Z., Wang T., Zhou X., & Chen P. 2017. Application of extremal optimization approach to the integrated scheduling problem of continuous casting and hot rolling process. 29th Chinese Control and Decision Conference (CCDC). 2017: 2429–2434. doi:10.1109/CCDC.2017.7978922.
9. Zhang B., Pan Q., Gao L., Zhang X., & Chen Q. 2018. A hybrid variable neighborhood search algorithm for the hot rolling batch scheduling problem in compact strip production. Computers & Industrial Engineering. 116 (2018): 22 – 36. doi:10.1016/j.cie.2017.12.013.
10. Pan Q.-K., Gao, L., & Wang, L. 2019. A multi-objective hot-rolling scheduling problem in the compact strip production. Applied Mathematical Modelling. 73:327 – 348. doi:10.1016/j.apm.2019.04.006.
11. Hu W., Zheng Z., Gao X., & Pardalos P.M. 2019. An improved method for the hot strip mill production scheduling problem. International Journal of Production Research. 57 (10):3238–3254. doi:10.1080/00207543.2019.1579932.
12. Hu Z., He D., Song W., & Feng K. 2020. Model and Algorithm for Planning Hot-Rolled Batch Processing under Time-of-Use Electricity Pricing. Processes 8 (1): 42. doi:10.3390/pr8010042.
13. Özgür A., Uygun Y. & Hütt M.-T. 2021. A review of planning and scheduling methods for hot rolling mills in steel production. Computers & Industrial Engineering. 151:106606. doi: 10.1016/j.cie.2020.106606.
14. Devyatov, D. Kh., Fainshtein, S.I., Belyavsky, A.B., & Torchinsky, V.E. 2009. Evristicheskaya optimizatsionnaya model' dlya zadach s ogranicheniyami, voznikayushchikh pri operativnom planirovanii prokatnogo proizvodstva [A heuristic optimization model for constrained problems arising during dynamic scheduling of plate rolling]. Informacionnye tehnologii [Information technologies]. 9:16-20.
15. Fainshtein S.I. 2010. Adaptivnaya optimizatsionnaya model' dlya operativnogo planirovaniya zadach listoprokatnogo proizvodstva [Adaptive optimization model for dynamic scheduling of plate rolling problems existing in flat rolled product manufacturing]. Informatsionnye tekhnologii i vychislitel'nyye sistemy [Information technologies and computing systems]. 1:92-98.
16. Fainshtein S.I., Tutarova V.D., Kalitayev A.N., Bukreyev A.Y., & Kolesnikov Y.F. 2007. Operativnoye planirovaniye dvizheniya gotovoy produktsii na skladakh metallurgicheskikh predpriyatiy [Dynamic Scheduling of Finished Product Movement at Warehouses of Metallurgical Enterprises]. Vestnik Magnitogorskogo gosudarstvennogo tekhnicheskogo universiteta im. G.I. Nosova [Herald of the Magnitogorsk State Technical University n.a. Nosov]. 4(20):108-112.
17. Kaplan D.S., Devyatov D.Kh., Fainshtein S.I., Tutarova V.D., & Kalitayev A.N. 2009. Evristicheskiy polinomial'nyy algoritm operativnogo planirovaniya razmeshcheniya gotovoy produktsii na skladakh metallurgicheskikh predpriyatiy [Heuristic polynomial algorithm for dynamic scheduling of finished product allocation at warehouses of metallurgical enterprises]. Avtomatizatsiya. Sovremennyye tekhnologii [Automation. Modern technologies]. 6:35-39.
18. Devyatov D.Kh., Fainshtein S.I., Tutarova V.D., & Kalitaev A.N. 2008. Operativnoe planirovanie otgruzki gotovoj produktsii so skladov metallurgicheskikh predprijatij [Dynamic scheduling of finished product shipment from warehouses of metallurgical enterprises]. Mekhatronika, avtomatizatsija, upravlenie [Mechatronics, automation, control]. 4:36-40.
19. Fainshtein S.I. 2013. Adaptivnaya model' dlya zadach uporyadochennogo razbiyeniya s ogranicheniyami [Adaptive model for constrained problems involved with ordered partition]. Matematicheskoye i programmnoye obespecheniye sistem v promyshlennoy i sotsial'noy sferakh [Mathematical and software systems in industrial and social areas]. 1(3):53-56.
20. Wentzel E.S. 1983. Operations Research: a Methodological Approach. Moscow: Mir Publishers. 264 p.
21. Tang L., Liu J., Rong A., & Yang Z. 2001. A review of planning and scheduling systems and methods for integrated steel production. European Journal of Operation Research. 133(1):1-20.
