Abstract
Task scheduling is crucial for achieving high performance in parallel computing. Since task scheduling is NP-hard, the efficient assignment of tasks to compute resources remains an issue. Across the literature, several algorithms have been proposed to solve different scheduling problems. One such approach is Ant Colony Optimization (ACO) which has a potential to benefit from a parallel execution. In this article, we propose two new scheduling methods based on parallel ACO to solve the problem of scheduling independent tasks onto heterogeneous multicore platforms. The results of performance measuements demonstrate the improvements on the makespan by both parallel ACO variants.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alba, E., Luque, G., Nesmachnow, S.: Parallel metaheuristics: recent advances and new trends. Int. Trans. Oper. Res. 20(1), 1–48 (2013). https://doi.org/10.1111/j.1475-3995.2012.00862.x
Boveiri, H.R.: ACO-MTS: a new approach for multiprocessor task scheduling based on ant colony optimization. In: 2010 International Conference on Intelligent and Advanced Systems, pp. 1–5 (2010). https://doi.org/10.1109/ICIAS.2010.5716203
Cheng, X., Dai, F.: A heterogeneous multiprocessor independent task scheduling algorithm based on improved PSO. In: Yang, C.-N., Peng, S.-L., Jain, L.C. (eds.) SICBS 2018. AISC, vol. 895, pp. 267–279. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-16946-6_21
Crainic, T.G., Toulouse, M.: Parallel meta-heuristics. In: Gendreau, M., Potvin, J.Y. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 497–541. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_17
Elcock, N.E.J.: Task scheduling in heterogeneous multiprocessor environments - an efficient ACO-based approach. Institute of Advanced Engineering and Science 10 (2018)
Jin, S., Schiavone, G., Turgut, D.: A performance study of multiprocessor task scheduling algorithms. J. Supercomput. 43(1), 77–97 (2008)
Krishnamoorthy, N., Asokan, R.: Optimized resource selection to promote grid scheduling using hill climbing algorithm. Int. J. of Comput. Science and Telecommun. (IJCST) 5(2), 14–19 (2014)
de Melo Menezes, B.A., Herrmann, N., Kuchen, H., Buarque de Lima Neto, F.: High-level parallel ant colony optimization with algorithmic skeletons. Int. J. Parallel Prog. 49(6), 776–801 (2021). https://doi.org/10.1007/s10766-021-00714-1
Pedemonte, M., Nesmachnow, S., Cancela, H.: A survey on parallel ant colony optimization. Appl. Soft Comput. 11(8), 5181–5197 (2011). https://doi.org/10.1016/j.asoc.2011.05.042
Srikanth, G.U., Geetha, R.: Task scheduling using Ant Colony Optimization in multicore architectures: a survey. Soft. Comput. 22(15), 5179–5196 (2018). https://doi.org/10.1007/s00500-018-3260-4
Srikanth, U., Maheswari, U., Palaniswami, S., Siromoney, A.: Task scheduling using probabilistic ant colony heuristics. Int. Arab. J. Inf. Technol. (IAJIT) 13(4), 375–379 (2016)
Thiruvady, D., Ernst, A.T., Singh, G.: Parallel ant colony optimization for resource constrained job scheduling. Ann. Oper. Res. 242(2), 355–372 (2014). https://doi.org/10.1007/s10479-014-1577-7
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Dietze, R., Kränert, M. (2023). Parallel Ant Colony Optimization for Scheduling Independent Tasks. In: Abraham, A., Bajaj, A., Gandhi, N., Madureira, A.M., Kahraman, C. (eds) Innovations in Bio-Inspired Computing and Applications. IBICA 2022. Lecture Notes in Networks and Systems, vol 649. Springer, Cham. https://doi.org/10.1007/978-3-031-27499-2_34
Download citation
DOI: https://doi.org/10.1007/978-3-031-27499-2_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-27498-5
Online ISBN: 978-3-031-27499-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)