TY  - EJOU
AU  - Zaman, Sardar Khaliq uz 
AU  - Maqsood, Tahir 
AU  - Ali, Mazhar 
AU  - Bilal, Kashif 
AU  - Madani, Sajjad A. 
AU  - Khan, Atta ur Rehman 

TI  - A Load Balanced Task Scheduling Heuristic for Large-Scale Computing Systems
T2  - Computer Systems Science and Engineering

PY  - 2019
VL  - 34
IS  - 2
SN  - 

AB  - Optimal task allocation in Large-Scale Computing Systems (LSCSs) that endeavors to balance the load across limited computing resources is considered an
NP-hard problem. MinMin algorithm is one of the most widely used heuristic for scheduling tasks on limited computing resources. The MinMin minimizes
makespan compared to other algorithms, such as Heterogeneous Earliest Finish Time (HEFT), duplication based algorithms, and clustering algorithms.
However, MinMin results in unbalanced utilization of resources especially when majority of tasks have lower computational requirements. In this work
we consider a computational model where each machine has certain bounded capacity to execute a predefined number of tasks simultaneously. Based
on aforementioned model, a task scheduling heuristic Extended High to Low Load (ExH2LL) is proposed that attempts to balance the workload across
the available computing resources while improving the resource utilization and reducing the makespan. ExH2LL dynamically identifies task-to-machine
assignment considering the existing load on all machines. We compare ExH2LL with MinMin, H2LL, Improved MinMin Task Scheduling (IMMTS), Load
Balanced MaxMin (LBM), and M-Level Suffrage-Based Scheduling Algorithm (MSSA). Simulation results show that ExH2LL outperforms the compared
heuristics with respect to makespan and resource utilization. Moreover, we formally model and verify the working of ExH2LL using High Level Petri Nets,
Satisfiability Modulo Theories Library, and Z3 Solver.
KW  - Large-Scale Computing Systems
KW  -  Load Balancing
KW  -  List-based Task Scheduling
KW  -  Makespan
KW  -  Resource Utilization

DO  - 10.32604/csse.2019.34.079