PARALLEL MACHINE SCHEDULING WITH MONTE CARLO TREE SEARCH
DOI:
https://doi.org/10.14311/AP.2021.61.0307Keywords:
Parallel-machine scheduling, Monte Carlo Tree Search.Abstract
In this article, a specific production scheduling problem (PSP), the Parallel Machine Scheduling Problem (PMSP) with Job and Machine Sequence Setup Times, Due Dates and Maintenance Times is presented. In this article after the introduction and literature review the mathematical model of the Parallel Machines Scheduling Problem with Job and Machine Sequence Setup Times, Due Dates and Maintenance Times is presented. After that the Monte Carlo Tree Search and Simulated Annealing are detailed. Our representation technique and its evaluation are also introduced. After that, the efficiency of the algorithms is tested with benchmark data, which result, that algorithms are suitable for solving production scheduling problems. In this article, after the literature review, a suitable mathematical model is presented. The problem is solved with a specific Monte Carlo Tree Search (MCTS) algorithm, which uses a neighbourhood search method (2-opt). In the article, we present the efficiency of our Iterative Monte Carlo Tree Search (IMCTS) algorithm on randomly generated data
sets.
Downloads
References
J. Y. Leung. Handbook of scheduling: algorithms, models, and performance analysis. CRC press, 2004.
M. Pinedo. Scheduling: theory, algorithms, and systems. 5-th ed. cham, 2016.
E. Vallada, R. Ruiz. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research 211(3):612–622, 2011. doi:10.1016/j.ejor.2011.01.011.
O. A. Arık, M. D. Toksarı. Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects. International Journal of Production Research 56(7):2488–2505, 2018. doi:10.1080/00207543.2017.1388932.
G. Bektur, T. Saraç. A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. Computers & Operations Research 103:46–63, 2019.
D. Biskup, J. Herrmann, J. N. Gupta. Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics 115(1):134–142, 2008. doi:10.1016/j.ijpe.2008.04.011.
H. Safarzadeh, S. T. A. Niaki. Bi-objective green scheduling in uniform parallel machine environments. Journal of cleaner production 217:559–572, 2019. doi:10.1016/j.jclepro.2019.01.166.
M. Ji, W. Zhang, L. Liao, et al. Multitasking parallel-machine scheduling with machine-dependent slack due-window assignment. International Journal of Production Research 57(6):1667–1684, 2019.
G. Centeno, R. L. Armacost. Minimizing makespan on parallel machines with release time and machine eligibility restrictions. International Journal of Production Research 42(6):1243–1256, 2004. doi:10.1080/00207540310001631584.
L. Nie. Parallel machine scheduling problem of flexible maintenance activities with fuzzy random time windows. In Proceedings of the tenth international conference on management science and engineering management, pp. 1027–1040. Springer, 2017.
S. Ghanbari, M. Othman. A priority based job scheduling algorithm in cloud computing. Procedia Engineering 50(0):778–785, 2012.
A. Agnetis, J.-C. Billaut, S. Gawiejnowicz, et al. Scheduling problems with variable job processing times. In Multiagent Scheduling, pp. 217–260. Springer, 2014.
K.-C. Ying, Z.-J. Lee, S.-W. Lin. Makespan minimization for scheduling unrelated parallel machines with setup times. Journal of Intelligent Manufacturing 23(5):1795–1803, 2012. doi:10.1007/s10845-010-0483-3.
Z. Wu, M. X. Weng. Multiagent scheduling method with earliness and tardiness objectives in flexible job shops. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 35(2):293–301, 2005. doi:10.1109/tsmcb.2004.842412.
M. Ciavotta, C. Meloni, M. Pranzo. Speeding up a rollout algorithm for complex parallel machine scheduling. International Journal of Production Research 54(16):4993–5009, 2016.
T.-Y. Wu, I.-C. Wu, C.-C. Liang. Multi-objective flexible job shop scheduling problem based on monte-carlo tree search. In 2013 Conference on Technologies and Applications of Artificial Intelligence, pp. 73–78. IEEE, 2013. doi:10.1109/taai.2013.27.
C. B. Browne, E. Powley, D. Whitehouse, et al. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4(1):1–43, 2012. doi:10.1109/tciaig.2012.2186810.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Anita Agárdi, Károly Nehéz
This work is licensed under a Creative Commons Attribution 4.0 International License.
