Journal of Smart Computing ISSN 2979-8752 · Biannual
Register Log in
Research Article · Vol. 2, No. 1 (2026)

A Hybrid Metaheuristic Algorithm for Energy-Aware Task Scheduling

Ana Paula Maia Tanajura Ellefsen* , Giorgio Mossa

Telenor, Snarøyveien 30, Oslo, Norway · Department of Mechanics, Mathematics and Management, Politecnico di Bari, Via Orabona, 4, 70125, Bari, Italy

* Corresponding author: ana.ellefsen@dsv.com

Abstract Energy use is now a primary constraint in heterogeneous computing systems: schedules that minimize the makespan of dependent tasks must also limit the power drawn by the processors that execute them. Energy-aware scheduling on heterogeneous processors is NP-hard, so exact methods do not scale. Single metaheuristics typically explore broadly without refining local structure, or refine a single solution without leaving poor regions of the search space. This paper proposes a hybrid metaheuristic that embeds simulated annealing as a local-refinement operator within a genetic algorithm and couples the search to a dynamic voltage-and-frequency-scaling energy model, so that voltage assignment is optimized together with task mapping. The scheduler minimizes a weighted objective that combines energy, makespan, and processor utilization; the method is specified formally and as reproducible pseudocode. On an illustrative synthetic benchmark of dependency graphs scheduled on heterogeneous processors, the proposed method is compared with a genetic algorithm, simulated annealing, particle swarm optimization, ant colony optimization, and a list-scheduling heuristic. The results indicate faster convergence and lower energy and makespan than these baselines, which supports combining memetic search with an explicit energy model for this class of scheduling problems.

Keywords: Task scheduling, Energy-aware computing, Hybrid metaheuristic, Genetic algorithm, Simulated annealing

DOI
10.5281/zenodo.23266056
Pages
43-52
Published
25 Apr 2026
Download PDF

To cite this article: Ellefsen, A.P.M.T., & Mossa, G. (2026). A Hybrid Metaheuristic Algorithm for Energy-Aware Task Scheduling. Journal of Smart Computing , 2(1) , 43-52. https://doi.org/10.5281/zenodo.23266056

References

  1. Abdel-Basset, M., El-Shahat, D., Deb, K., & Abouhawwash, M. (2020). Energy-aware whale optimization algorithm for real-time task scheduling in multiprocessor systems. Applied Soft Computing, 93, 106349. https://doi.org/10.1016/j.asoc.2020.106349
  2. Ahmad, S. G., Liew, C. S., Munir, E. U., Ang, T. F., & Khan, S. U. (2016). A hybrid genetic algorithm for optimization of scheduling workflow applications in heterogeneous computing systems. Journal of Parallel and Distributed Computing, 87, 80–90. https://doi.org/10.1016/j.jpdc.2015.10.001
  3. Akbari, M., Rashidi, H., & Alizadeh, S. H. (2017). An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Engineering Applications of Artificial Intelligence, 61, 35–46. https://doi.org/10.1016/j.engappai.2017.02.013
  4. Baskiyar, S., & Abdel-Kader, R. (2010). Energy aware DAG scheduling on heterogeneous systems. Cluster Computing, 13(4), 373–383. https://doi.org/10.1007/s10586-009-0119-6
  5. Dorigo, M., & Stützle, T. (2004). Ant colony optimization. MIT Press. https://doi.org/10.7551/mitpress/1290.001.0001
  6. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
  7. Holland, J. H. (1992). Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. MIT Press. https://doi.org/10.7551/mitpress/1090.001.0001
  8. Ismayilov, G., & Topcuoglu, H. R. (2020). Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing. Future Generation Computer Systems, 102, 307–322. https://doi.org/10.1016/j.future.2019.08.012
  9. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN'95 – International Conference on Neural Networks (Vol. 4, pp. 1942–1948). IEEE. https://doi.org/10.1109/icnn.1995.488968
  10. Keshanchi, B., & Navimipour, N. J. (2016). Priority-based task scheduling in the cloud systems using a memetic algorithm. Journal of Circuits, Systems and Computers, 25(10), 1650119. https://doi.org/10.1142/s021812661650119x
  11. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
  12. Lee, Y. C., & Zomaya, A. Y. (2011). Energy conscious scheduling for distributed computing systems under different operating conditions. IEEE Transactions on Parallel and Distributed Systems, 22(8), 1374–1381. https://doi.org/10.1109/tpds.2010.208
  13. Li, K., Tang, X., & Li, K. (2014). Energy-efficient stochastic task scheduling on heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 25(11), 2867–2876. https://doi.org/10.1109/tpds.2013.270
  14. Masanet, E., Shehabi, A., Lei, N., Smith, S., & Koomey, J. (2020). Recalibrating global data center energy-use estimates. Science, 367(6481), 984–986. https://doi.org/10.1126/science.aba3758
  15. Mezmaz, M., Melab, N., Kessaci, Y., Lee, Y. C., Talbi, E.-G., Zomaya, A. Y., & Tuyttens, D. (2011). A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems. Journal of Parallel and Distributed Computing, 71(11), 1497–1508. https://doi.org/10.1016/j.jpdc.2011.04.007
  16. Mirjalili, S., Mirjalili, S. M., & Lewis, A. (2014). Grey wolf optimizer. Advances in Engineering Software, 69, 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007
  17. Tanha, M., Hosseini Shirvani, M., & Rahmani, A. M. (2021). A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments. Neural Computing and Applications, 33(24), 16951–16984. https://doi.org/10.1007/s00521-021-06289-9
  18. Topcuoglu, H., Hariri, S., & Wu, M.-Y. (2002). Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3), 260–274. https://doi.org/10.1109/71.993206
  19. Ullman, J. D. (1975). NP-complete scheduling problems. Journal of Computer and System Sciences, 10(3), 384–393. https://doi.org/10.1016/s0022-0000(75)80008-0
  20. Verma, A., & Kaushal, S. (2017). A hybrid multi-objective particle swarm optimization for scientific workflow scheduling. Parallel Computing, 62, 1–19. https://doi.org/10.1016/j.parco.2017.01.002
  21. Xu, Y., Li, K., Hu, J., & Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270, 255–287. https://doi.org/10.1016/j.ins.2014.02.122
CC BY Creative Commons Attribution 4.0
Creative Commons Attribution 4.0 International CC BY 4.0

This work is licensed under a Creative Commons Attribution 4.0 International License.

Read the full CC BY 4.0 license →