PARALLEL MACHINE SCHEDULING WITH MONTE CARLO TREE SEARCH
Keywords:Parallel-machine scheduling, Monte Carlo Tree Search.
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
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.
Copyright (c) 2021 Anita Agárdi, Károly Nehéz
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).