Journal
INFORMATION SCIENCES
Volume 270, Issue -, Pages 255-287Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2014.02.122
Keywords
Directed acyclic graph; Genetic algorithm; Heuristic algorithm; Makespan; Multiple priority queue; Task scheduling
Categories
Funding
- Key Program of National Natural Science Foundation of China [61133005]
- National Natural Science Foundation of China [61370095, 90715029, 61070057, 60603053]
- National Science Foundation for Distinguished Young Scholars of Hunan [12JJ1011]
- Hunan Provincial Science and Technology Program of China [2013GK3082]
Ask authors/readers for more resources
On parallel and distributed heterogeneous computing systems, a heuristic-based task scheduling algorithm typically consists of two phases: task prioritization and processor selection. In a heuristic based task scheduling algorithm, different prioritization will produce different makespan on a heterogeneous computing system. Therefore, a good scheduling algorithm should be able to efficiently assign a priority to each subtask depending on the resources needed to minimize makespan. In this paper, a task scheduling scheme on heterogeneous computing systems using a multiple priority queues genetic algorithm (MPQGA) is proposed. The basic idea of our approach is to exploit the advantages of both evolutionary-based and heuristic-based algorithms while avoiding their drawbacks. The proposedalgorithm incorporates a genetic algorithm (GA) approach to assign a priority to each subtask while using a heuristic-based earliest finish time (EFT) approach to search for a solution for the task-to-processor mapping. The MPQGA method also designs crossover, mutation, and fitness function suitable for the scenario of directed acyclic graph (DAG) scheduling. The experimental results for large-sized problems from a large set of randomly generated graphs as well as graphs of real-world problems with various characteristics show that the proposed MPQGA algorithm outperforms two non-evolutionary heuristics and a random search method in terms of schedule quality. (C) 2014 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available