Quantum genetic algorithm based scheduler for batch of precedence constrained jobs on heterogeneous computing systems

• Published in: The Journal of systems and software 2018-01, Vol.135, p.126-142
• Main Authors: Alam, Taj, Raza, Zahid
• Format: Article
• Language: English
• Subjects: Batch scheduling; Heterogeneous distributed systems; Load Balancing; Load balancing cost ratio; Load Imbalance; Workflow application
• ISSN: 0164-1212; 1873-1228
• DOI: 10.1016/j.jss.2017.10.001

•Scheduling the DAG based tasks on heterogeneous distributed systems.•Exploits the features of Quantum Computing and NSGA II to establish the Pareto fronts.•QGLBS ensures that the communication cost and the critical path are considered.•Hypervolume Indicator to assess the quality of Pareto fronts. Distributed systems are efficient means of realizing High-Performance Computing (HPC). They are used in meeting the demand of executing large-scale high-performance computational jobs. Scheduling the tasks on such computational resources is one of the prime concerns in the heterogeneous distributed systems. Scheduling requires optimizing either single objective or multiple objectives. Load Imbalance (LIB) and Load balancing Cost Ratio (LCR) are two such objectives. LIB and LCR are used in deciding the distribution of load over available resources for utilization and the computational cost respectively. Scheduling jobs with precedence constraints are NP-complete in nature. Scheduling requires either heuristic or metaheuristic approach for sub-optimal but acceptable solutions. Quantum computing is one such metaheuristic approach. It has proven to be promising in addressing the multi-objective scheduling problems with an effective exploration of the search space. This work proposes a dual-objective Quantum-inspired Genetic Algorithm based Load Balancing Strategy (QGLBS) for workflow application with the objective of optimizing both LIB and LCR. The DAG representation of the batch of jobs helps in effective exploitation of the parallelism available at the job level as well as the sub-job level with the modules at the same level of the batch executing at the same time. The strategy ensures that the communication cost and the critical path are considered in making scheduling decisions. QGLBS exploits the features of Quantum Computing and Genetic Algorithm to establish the Pareto fronts using non-dominated sorting based on NSGA-II. Hypervolume measures are used to compare the results of the quality assessment of Pareto fronts. Simulation study on Gridsim ensures that the QGLBS approach works effectively for real life scenario with various workflow applications.