An Improved Tabu Search Algorithm for Parallel Task Scheduling on Identical Machines
By: Wenhao Jia, Xin Chen, Di Wu, Shumin Shi, Liang Zhao, Jedrzej Musial and Jacek Blazewicz
References
- Błądek, I., Drozdowski, M., Guinand, F. and Schepler, X. (2015). On contiguous and non-contiguous parallel task scheduling, Journal of Scheduling 18(5): 487–495.
- Blazewicz, J., Drabowski, M. and Weglarz, J. (1986). Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers C-35(5): 389–393.
- Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G. and Weglarz, J. (2019). Handbook on Scheduling, Springer, Cham.
- Blazewicz, J., Pesch, E., Sterna, M. and Werner, F. (2008). Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date, Computers & Operations Research 35(2): 574–599.
- Blazewicz, J. and Weglarz, J. (1984). Scheduling independent 2-processor tasks to minimize schedule length, Information Processing Letters 18(5): 267–273.
- Chu, C.-H., Weng, C.-Y. and Chen, Y.-T. (2024). Enhancing manual inspection in semiconductor manufacturing with integrated augmented reality solutions, Journal of Manufacturing Systems 77: 933–945.
- Du, J. and Leung, J.Y.-T. (1989). Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics 2(4): 473–487.
- Gad, A.G. (2022). Particle swarm optimization algorithm and its applications: A systematic review, Archives of Computational Methods in Engineering 29(5): 2531–2561.
- Graham, R.L., Lawler, E.L., Lenstra, J.K. and Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5: 287–326.
- Katoch, S., Chauhan, S.S. and Kumar, V. (2021). A review on genetic algorithm: Past, present, and future, Multimedia Tools and Applications 80(5): 8091–8126.
- Kowalczyk, D. and Leus, R. (2018). A branch-and-price algorithm for parallel machine scheduling using ZDDS and generic branching, INFORMS Journal on Computing 30(4): 768–782.
- Kumar, B.A., Jyothi, B., Singh, A.R., Bajaj, M., Rathore, R.S. and Tuka, M.B. (2024). Hybrid genetic algorithm-simulated annealing based electric vehicle charging station placement for optimizing distribution network resilience, Scientific Reports 14(1): 7637.
- Lee, D., Kang, H., Lee, D., Lee, J. and Kim, K. (2023). Deep reinforcement learning-based scheduler on parallel dedicated machine scheduling problem towards minimizing total tardiness, Sustainability 15(4): 2920.
- Li, Y., Liu, J., Wang, L., Liu, J., Tang, H., Guo, J. and Xu, W. (2024). A k-means-teaching learning based optimization algorithm for parallel machine scheduling problem, Applied Soft Computing 161: 111746.
- Liu, X., Chen, X., Chau, V., Musial, J. and Blazewicz, J. (2025). Flexible job shop scheduling problem using graph neural networks and reinforcement learning, Computers & Operations Research 182: 107139.
- Liu, X., Wang, W., Chen, X., Sterna, M. and Blazewicz, J. (2023). Exact approaches to late work scheduling on unrelated machines, International Journal of Applied Mathematics and Computer Science 33(2): 285–295, DOI: 10.34768/amcs-2023-0021.
- Priyadarshi, R. and Kumar, R.R. (2025). Evolution of swarm intelligence: A systematic review of particle swarm and ant colony optimization approaches in modern research, Archives of Computational Methods in Engineering 32(6): 3609–3650.
- Rahdar, S., Ghanbari, R. and Ghorbani-Moghadam, K. (2022). Tabu search and variable neighborhood search algorithms for solving interval bus terminal location problem, Applied Soft Computing 116: 108367.
- Rodrigues, F. and Agra, A. (2022). Berth allocation and quay crane assignment/scheduling problem under uncertainty: A survey, European Journal of Operational Research 303(2): 501–524.
- Sarker, I.H. (2021). Machine learning: Algorithms, real-world applications and research directions, SN Computer Science 2(3): 160.
- Song, Y., Ji, B. and Yu, S.S. (2025). Multi-port berth allocation and time-invariant quay crane assignment problem with speed optimization, IEEE Transactions on Intelligent Transportation Systems 26(1): 128–142.
- Squires, M., Tao, X., Elangovan, S., Gururajan, R., Zhou, X. and Acharya, U. R. (2022). A novel genetic algorithm based system for the scheduling of medical treatments, Expert Systems with Applications 195: 116464.
- Swat, S., Antczak, M., Zok, T., Blazewicz, J. and Musial, J. (2025). Exact algorithms for the satellite image selection problem, International Journal of Applied Mathematics and Computer Science 35(2): 293–309, DOI: 10.61822/amcs-2025-0021.
- Switalski, P. and Seredynski, F. (2015). Scheduling parallel batch jobs in grids with evolutionary metaheuristics, Journal of Scheduling 18(4): 345–357.
- Umam, M.S., Mustafid, M. and Suryono, S. (2022). A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem, Journal of King Saud University Computer and Information Sciences 34(9): 7459–7467.
- Wang, W., Chen, X., Musial, J. and Blazewicz, J. (2020). Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion, International Journal of Applied Mathematics and Computer Science 30(3): 573–584, DOI: 10.34768/amcs-2020-0030.
- Wei, X., Wei, H., Lu, M., Zhang, Z., Chang, S., Zeng, S., Wang, F. and Chen, M. (2024). Large-scale parallel embedded computing with improved-MPI in off-chip distributed clusters, IEEE Transactions on Industrial Informatics 20(11): 12575–12585.
- Wu, L. and Wang, S. (2018). Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks, International Journal of Production Economics 201: 26–40.
- Xie, J., Li, X., Gao, L. and Gui, L. (2023). A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems, Journal of Manufacturing Systems 71: 82–94.
Language: English
Page range: 459 - 474
Submitted on: Oct 26, 2025
Accepted on: Jun 11, 2026
Published on: Sep 19, 2026
Published by: University of Zielona Góra
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year
Keywords:
Related subjects:
© 2026 Wenhao Jia, Xin Chen, Di Wu, Shumin Shi, Liang Zhao, Jedrzej Musial, Jacek Blazewicz, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.