期刊
INFORMATION SCIENCES
卷 270, 期 -, 页码 255-287出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2014.02.122
关键词
Directed acyclic graph; Genetic algorithm; Heuristic algorithm; Makespan; Multiple priority queue; Task scheduling
资金
- 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]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据