E-HEFT: Enhancement Heterogeneous Earliest Finish Time algorithm for Task Scheduling based on Load Balancing in Cloud Computing
Authors:
- Yassir SamadiYSYassir Samadi
- Mostapha ZbakhMZMostapha Zbakh
- Claude TadonkiCTClaude Tadonki
- 1 July 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 601-609
Abstract
Cloud computing is one of the most widely spreaded platforms for executing tasks through virtual machines as processing elements. However, there are various issues that need to be addressed in order to be efficiently utilized for workflow applications. One of the fundamental issues in cloud computing is related to task scheduling. Optimal scheduling of tasks in cloud computing is an NP-complete optimization problem, and many algorithms have been proposed to solve it. Furthermore, the existing algorithms fail to either meet the user's Quality of Service (QoS) requirements such as minimizing the makespan and satisfying budget constraints, or to incorporate some basic principles of cloud computing such as elasticity and heterogeneity of computing resources. Among these algorithms, the Heterogeneous Earliest Finish Time (HEFT) heuristic is known to give good results in short time for tasks scheduling in heterogeneous systems. Generally, the HEFT algorithm yields good tasks execution time, but its drawback is that there is no load balancing. In this paper, an enhancement of Heterogeneous Earliest Finish Time (E-HEFT) algorithm under a user-specified financial constraint is proposed to achieve a well balanced load across the virtual machines while trying to minimize the makespan of a given workflow application. To evaluate the performance of the enhancement algorithm, we compare our algorithm with some existing scheduling algorithms. Experimental results show that our algorithm outperforms other algorithms by reducing the makespan and improving load balance among virtual machines.Keywords
This publication has 19 references indexed in Scilit:
- End-to-End Delay Minimization for Scientific Workflows in Clouds under Budget ConstraintIEEE Transactions on Cloud Computing, 2014
- Dynamic task scheduling algorithm with load balancing for heterogeneous computing systemEgyptian Informatics Journal, 2012
- BUDGET ESTIMATION AND CONTROL FOR BAG-OF-TASKS SCHEDULING IN CLOUDSParallel Processing Letters, 2011
- CyberShake: A Physics-Based Seismic Hazard Model for Southern CaliforniaPure and Applied Geophysics, 2010
- Deferred acceptance algorithms: history, theory, practice, and open questionsInternational Journal of Game Theory, 2008
- A Taxonomy of Workflow Management Systems for Grid ComputingJournal of Grid Computing, 2005
- Improving scheduling of tasks in a heterogeneous environmentIEEE Transactions on Parallel and Distributed Systems, 2004
- Taverna: a tool for the composition and enactment of bioinformatics workflowsBioinformatics, 2004
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- Static scheduling algorithms for allocating directed task graphs to multiprocessorsACM Computing Surveys, 1999