A Synthesized Heuristic Task Scheduling Algorithm
Authors:
Open Access
- 1 January 2014
- journal article
- research article
- Published by Wiley in The Scientific World Journal
- Vol. 2014, 1-9
Abstract
Aiming at the static task scheduling problems in heterogeneous environment, a heuristic task scheduling algorithm named HCPPEFT is proposed. In task prioritizing phase, there are three levels of priority in the algorithm to choose task. First, the critical tasks have the highest priority, secondly the tasks with longer path to exit task will be selected, and then algorithm will choose tasks with less predecessors to schedule. In resource selection phase, the algorithm is selected task duplication to reduce the interresource communication cost, besides forecasting the impact of an assignment for all children of the current task permits better decisions to be made in selecting resources. The algorithm proposed is compared with STDH, PEFT, and HEFT algorithms through randomly generated graphs and sets of task graphs. The experimental results show that the new algorithm can achieve better scheduling performance.Keywords
Funding Information
- National Natural Science Foundation of China (61363031, GKG1211-80172C, 20120104-13)
- Tech. Development Foundation (61363031, GKG1211-80172C, 20120104-13)
- Tech. Development Foundation (61363031, GKG1211-80172C, 20120104-13)
This publication has 17 references indexed in Scilit:
- An effective duplication-based task-scheduling algorithm for heterogeneous systemsSIMULATION, 2011
- List scheduling with duplication for heterogeneous computing systemsJournal of Parallel and Distributed Computing, 2010
- Task scheduling algorithm using minimized duplications in homogeneous systemsJournal of Parallel and Distributed Computing, 2008
- A high performance algorithm for static task scheduling in heterogeneous distributed computing systemsJournal of Parallel and Distributed Computing, 2008
- Scheduling algorithm based on critical tasks in heterogeneous environmentsJournal of Systems Engineering and Electronics, 2008
- A high performance, low complexity algorithm for compile-time task scheduling in heterogeneous systemsParallel Computing, 2005
- An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systemsIEEE Transactions on Parallel and Distributed Systems, 2003
- Performance-effective and low-complexity task scheduling for heterogeneous computingIEEE Transactions on Parallel and Distributed Systems, 2002
- Scheduling multiprocessor tasks with genetic algorithmsIEEE Transactions on Parallel and Distributed Systems, 1999
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1996