Parallel Metaheuristic Algorithms for Task Scheduling Problems
DOI:
https://doi.org/10.24297/ijct.v25i.9709Keywords:
Task scheduling optimization, Parallel computing, MetaheuristicsAbstract
This study addresses the task-scheduling optimization challenges in parallel computing systems using a novel meta-
heuristic framework. We analyze the differential evolution in task scheduling and propose an advanced shift-chain
methodology to improve the cooperation between scheduling components. The proposed framework introduces a wait-
ing time-based neighborhood exploration strategy for handling complex task dependencies, along with two parallel
implementation approaches: basic matching vector (MV) parallelization and an event-driven strategy. The experi-
mental results demonstrated superior solution quality and computational efficiency compared with existing methods,
particularly in large scale problems. The modular design of this framework enables practical applications in modern
computing environments.
Downloads
References
Ahmad, M. F., Isa, N. A. M., Lim, W. H., & Ang, K. M. (2022). Differential evolution: A recent review based
on state-of-the-art works. Alexandria Engineering Journal, 61(5), 3831-3872. https://doi.org/10.1016/j.aej.
09.013
Chen, X., Yu, L., Wang, T., Liu, A., Wu, X., Zhang, B., Lv, Z., & Sun, Z. (2020). Artificial intelligence-empowered
path selection: A survey of ant colony optimization for static and mobile sensor networks. IEEE Access, 8, 71497-
https://doi.org/10.1109/ACCESS.2020.2984329
Crainic, T. G. (2019). Parallel metaheuristics and cooperative search. In International Series in Opera-
tions Research and Management Science (Vol. 272, pp. 419-451). Springer. https://doi.org/10.1007/
-3-319-91086-4_13
Du, K. L., & Swamy, M. N. S. (2016). Search and optimization by metaheuristics: Techniques and algorithms
inspired by nature. Springer. https://doi.org/10.1007/978-3-319-41192-7
Glover, F. (1996). Ejection chains, reference structures, and alternating path methods for traveling salesman
problems. Discrete Applied Mathematics, 65(1–3), 223-253. https://doi.org/10.1016/0166-218X(94)00037-E
Hijazi, N. M., Faris, H., & Aljarah, I. (2021). A parallel metaheuristic approach for ensemble feature selection
based on multi-core architectures. Expert Systems with Applications, 182, 115290. https://doi.org/10.1016/j.
eswa.2021.115290
Houssein, E. H., Gad, A. G., Wazery, Y. M., & Suganthan, P. N. (2021). Task scheduling in cloud computing based
on meta-heuristics: Review, taxonomy, open challenges, and future trends. Swarm and Evolutionary Computation,
, 100841. https://doi.org/10.1016/j.swevo.2021.100841
Katoch, S., Chauhan, S. S., & Kumar, V. (2021). A review on genetic algorithm: Past, present, and future.
Multimedia Tools and Applications, 80(5), 8091-8126. https://doi.org/10.1007/s11042-020-10139-6
Khaled Ahsan Talukder, A. K. M., Kirley, M., & Buyya, R. (2009). Multiobjective differential evolution for
scheduling workflow applications on global Grids. Concurrency and Computation: Practice and Experience, 21(13),
-1706. https://doi.org/10.1002/cpe.1417
Marini, F., & Walczak, B. (2015). Particle swarm optimization (PSO). A tutorial. Chemometrics and Intelligent
Laboratory Systems, 149, 153-165. https://doi.org/10.1016/j.chemolab.2015.08.020
Santander-Jiménez, S., & Vega-Rodríguez, M. A. (2017). Asynchronous non-generational model to parallelize
metaheuristics: A bioinformatics case study. IEEE Transactions on Parallel and Distributed Systems, 28(7), 1825-
https://doi.org/10.1109/TPDS.2016.2645764
Shehab, M., Khader, A. T., & Al-Betar, M. A. (2017). A survey on applications and variants of the cuckoo search
algorithm. Applied Soft Computing Journal, 61, 498-516. https://doi.org/10.1016/j.asoc.2017.02.034
Standard Task Graph Set. (2025, January 30). Waseda University. https://www.kasahara.cs.waseda.ac.jp/
schedule/
Yagiura, M., Ibaraki, T., & Glover, F. (2004). An ejection chain approach for the generalized assignment problem.
INFORMS Journal on Computing, 16(2), 133-151. https://doi.org/10.1287/ijoc.1030.0036
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Sirui Mao, Masato Edahiro
This work is licensed under a Creative Commons Attribution 4.0 International License.
