An Innovative Task Scheduling Method Using the Knapsack Algorithm in Heterogeneous Computing Systems

Abstract

Performance is widely acknowledged as a crucial aspect of IT systems, particularly to meet user requirements and expectations. Task scheduling plays a vital role in achieving high performance in these systems. However, task scheduling, especially in Heterogeneous Computing Systems (HCS), is known to be a challenging NP-hard problem. It involves finding an optimal balance between minimizing the makespan (time to complete all tasks) and maximizing processor utilization. In this research paper, we propose a novel tasks scheduling algorithm, a knapsack-based optimal algorithm for HCS called KnApsack based Co-Scheduling algorithm for Tasks Allocation (KaCoSTA). Our primary objective is to minimize the makespan while ensuring maximum system resources utilization. We conducted experiments to evaluate our heuristic approach, KaCoSTA, with existing methods like Directed Acyclic Graph (DAG) application model, including Priority path-based Heuristic Task Scheduling (PHTS), Performance Effective Task Scheduling (PETS). The results indicate that KaCoSTA outperforms these algorithms, especially in terms of makespan metric. The comparison study included different task sets and processor measurements, combining both small task sets and real applications criteria. By presenting an innovative approach to task scheduling in HCS, this research contributes to the optimization of system performance and resource utilization. The findings highlight the efficiency of KaCoSTA.