期刊
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
卷 92, 期 -, 页码 35-49出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jpdc.2016.03.003
关键词
Optimal task scheduling; A*; Iterative Deepening A*; Depth-First Branch and Bound A*; Parallel systems; Memory limited; Iterative deepening; State space pruning; Optimisation algorithm
资金
- Marsden Fund Council from Government funding [9073-3624767]
- University of Auckland
To hilly benefit from a multi-processor system, tasks need to be scheduled optimally. Given that the task scheduling problem with communication delays, P vertical bar prec, c(ij)vertical bar C-max, is a well known strong NP-hard problem, exhaustive approaches are necessary. The previously proposed A* based algorithm retains its entire state space in memory and often runs out of memory before it finds an optimal solution. This paper investigates and proposes two memory limited optimal scheduling algorithms: Iterative Deepening A* (IDA*) and Depth-First Branch and Bound A* (BBA*). When finding a guaranteed near optimal schedule length is sufficient, the proposed algorithms can be combined, reporting the gap while they run. Problem specific pruning techniques, which are crucial for good performance, are studied for the two proposed algorithms. Extensive experiments are conducted to evaluate and compare the proposed algorithms with previous optimal algorithms. (C) 2016 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据