A Task Scheduling Algorithm With Improved Makespan Based on Prediction of Tasks Computation Time algorithm for Cloud Computing

Belal Ali Al-Maytami, Pingzhi Fan, Abir Hussain, Thar Baker, Panos LiatsisIEEE Access 2019 · OpenReview

Abstract

Cloud computing is extensively used in a variety of applications and domains, however task and resource scheduling remains an area that requires improvement. In heterogeneous computing systems, task scheduling algorithms are essential for mapping incoming tasks to machines to satisfy high-performance requirements. Appropriate mapping reduces makespan and maximizes resource utilization. This paper presents a novel scheduling algorithm using a Directed Acyclic Graph (DAG) based on the Prediction of Tasks Computation Time (PTCT) algorithm. By employing Principal Components Analysis (PCA) to reduce the Expected Time to Compute (ETC) matrix, the proposed algorithm significantly improves makespan and reduces computational complexity. Simulation results demonstrate superior performance in terms of efficiency, speedup, and schedule length ratio compared to state-of-the-art heuristics like Min-Min and Max-Min.

Introduction: The Scheduling Challenge in Heterogeneous Clouds

In cloud computing, heterogeneity is the standard; environments consist of processors with varying speeds and communication rates. Mapping a set of incoming tasks to these diverse resources is an NP-hard problem. Inefficient mapping leads to high "makespan"—the total time elapsed from the start of the first task to the completion of the last—where some processors remain idle while others are overloaded.

Existing heuristic algorithms, such as Min-Min (prioritizing small tasks) and Max-Min (prioritizing large tasks), often struggle to balance resource utilization and Quality of Service (QoS) as task volume scales. There is a critical need for scheduling approaches that are computationally lighter yet more predictive in their mapping strategies.

Methodology: The PTCT Algorithm

The proposed PTCT algorithm operates on a Directed Acyclic Graph (DAG) model, where nodes represent individual tasks and edges represent their dependencies and communication costs.

A Directed Acyclic Graph (DAG) representing task dependencies and communication costs.

The core innovation of PTCT lies in its handling of the Expected Time to Compute (ETC) matrix through several key steps:

  1. Dimensionality Reduction via PCA: Traditional scheduling algorithms often face a computational complexity of $O(n^2m)$. PTCT utilizes Principal Component Analysis (PCA) to identify the principal components of the ETC matrix. This reduces the decision-making space and lowers complexity to $O(m)$.
  2. QoS Grouping: Tasks are categorized based on high, medium, or low Quality of Service requirements to ensure priority tasks receive appropriate resources.
  3. Algorithm Prediction: Rather than relying on a static rule, PTCT estimates the optimal scheduling strategy by matching current task requirements to the closest eigenvectors in its database.
  4. Two-Stage Calculation: The system calculates execution times on specific hosts and selects the optimal task-processor pair to minimize the overall makespan.

Experimental Setup

The study utilized simulated task graphs generated in MATLAB. The simulations involved mapping between 10 and 90 tasks across 8 processors. To simulate a sophisticated real-world environment, the researchers generated synthetic data representing various QoS levels and used randomized computation costs to ensure the robustness of the results.

Key Results and Analysis

The PTCT algorithm was benchmarked against four industry-standard algorithms: Min-Min, Max-Min, QoS-Guide, and MiM-MaM.

  • Makespan Improvement: PTCT consistently achieved the lowest makespan. At the 90-task scale, PTCT recorded a makespan of approximately 7.47, significantly outperforming QoS-Guide (12.33) and Max-Min (26.72).
  • Speedup and Efficiency: PTCT demonstrated a higher speedup ratio by effectively minimizing communication overhead. While Min-Min performed comparably at very low task counts, PTCT became the clear leader as system complexity increased, maintaining superior resource utilization.
  • The Scale Effect: The performance benefits of PTCT become increasingly pronounced as the number of tasks grows, particularly beyond the 40-task threshold.

Conclusion and Future Work

By treating scheduling as a data-reduction problem via PCA, the PTCT algorithm provides a breakthrough in reducing computational overhead while improving execution speed. However, the current research focuses on static scheduling, where task requirements are known in advance.

Future work will address the challenges of dynamic, unpredictable cloud traffic and explore energy consumption modeling. The researchers aim to further refine the algorithm to improve total energy utilization and validate its performance against real-world application graphs rather than simulated data.

Summary updated

Abstract

Cloud computing is extensively used in a variety of applications and domains, however task and resource scheduling remains an area that requires improvement. Put simply, in a heterogeneous computing system, task scheduling algorithms, which allow the transfer of incoming tasks to machines, are needed to satisfy high performance data mapping requirements. The appropriate mapping between resources and tasks reduces makespan and maximises resource utilisation. In this contribution, we present a novel scheduling algorithm using Directed Acyclic Graph (DAG) based on the Prediction of Tasks Computation Time algorithm (PTCT) to estimate the preeminent scheduling algorithm for prominent cloud data. In addition, the proposed algorithm provides a significant improvement with respect to the makespan and reduces the computation and complexity via employing Principle Components Analysis (PCA) and reducing the Expected Time to Compute (ETC) matrix. Simulation results confirm the superior performance of the algorithm for heterogeneous systems in terms of efficiency, speedup and schedule length ratio, when compared to the state-of-the-art Min-Min, Max-Min, QoS-Guide and MiM-MaM scheduling algorithms.
BibTeX
@inproceedings{almaytami2019task,
  author = {Belal Ali Al-Maytami and Pingzhi Fan and Abir Hussain and Thar Baker and Panos Liatsis},
  title = {{A Task Scheduling Algorithm With Improved Makespan Based on Prediction of Tasks Computation Time algorithm for Cloud Computing}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=0zKPmO9EWl},
}
Figure