Dynamic Adaptation for Independent Task Scheduling Using Dynamic Programming in Multiprocessor Systems

Authors

  • Lotfi BENDIAF LME Laboratory, Faculty of Exact Sciences and Informatics, Hassiba Ben Bouali University of Chlef
  • Ahmed HARBOUCHE LIA Laboratory, Hassiba Benbouali University, Chlef, Algeria
  • Mohammed Amin TAHRAOUI LIA Laboratory, Hassiba Benbouali University, Chlef, Algeria

Abstract

Performance in IT systems is critical to ensuring that systems meet user needs and expectations. In heterogeneous computing systems (HCS), which consist of processors with varying capabilities, dynamic adaptation plays a vital role in maintaining high performance. Dynamic adaptation enables systems to adjust task allocation and resource usage in real-time to respond to changes in workloads, resource availability, and system conditions. Task scheduling is a key aspect of achieving dynamic adaptation and remains a challenging NP-hard problem in HCS. Efficient scheduling requires optimizing competing objectives, such as minimizing makespan and maximizing processor utilization, to ensure that resources are used effectively. In this work, we propose DYnamic Task Allocation using dynamic programminG (DyTAg), a task scheduling algorithm based on dynamic programming, designed to support dynamic adaptation in HCS. Dynamic programming is particularly suited to this context as it breaks the scheduling problem into smaller, manageable subproblems and solves them incrementally, enabling efficient real-time adjustments. DyTAg leverages dynamic programming to minimize makespan while maximizing resource utilization, ensuring that tasks are allocated optimally even in complex, heterogeneous environments. To evaluate its performance, DyTAg is compared against established algorithms, including Min-Min, Max-Min, and Quality of Service Guided Min-Min, using various task sets and processor configurations. The results demonstrate that DyTAg achieves superior performance, particularly in scenarios involving independent tasks and small task sets, showcasing its potential to enhance dynamic adaptation and optimize performance in heterogeneous computing systems.

Downloads

Published

03/30/2025

How to Cite

BENDIAF, L., HARBOUCHE, A., & TAHRAOUI, M. A. (2025). Dynamic Adaptation for Independent Task Scheduling Using Dynamic Programming in Multiprocessor Systems. Revue Nature Et Technologie, 17(1), 09–16. Retrieved from https://journals.univ-chlef.dz/index.php/natec/article/view/501

Issue

Vol. 17 No. 1 (2025)

Section

Fundamental & Engineering Sciences

License

Copyright (c) 2025 Revue Nature et Technologie

Creative Commons License

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

  • All publications of "Nature & Technology Journal" are available under CC-BY Creative Commons Attribution 4.0 International which allows sharing, copying, reproduction, distribution, communication, reuse, adaptation by all means, in all formats and under all licenses.
  • Any exploitation of the work or derivative works, including for commercial purposes, is possible. The only obligation is to credit the creators of the authorship of the original works, to indicate the sources and to indicate if modifications were made to the works (obligation of attribution).

This License gives:

  • Nature & Technology Journal the right to develop, promote, distribute and archive the article set cited above (including, without limitation, the right to publish the work in whole or in part in any form whatsoever) and ensure the widest dissemination.
  • The author (s) reserves the right to use all or part of this article, including tables and figures of his own works, providing that the appropriate recognition is given to the publisher as the holder of the copyrights, and the right to make copies of this article for its own use, but not for sale.