Efficient Resource Constrained Scheduling Using Parallel Structure-Aware Pruning Techniques

doi:10.1109/TC.2015.2468230

Efficient Resource Constrained Scheduling Using Parallel Structure-Aware Pruning Techniques

2016-07-01

5

PRE

AI

DOI：10.1109/TC.2015.2468230

Original

Original request for help

Save

Abstract

En 中文

Branch-and-bound approaches are promising in pruning fruitless search space during the resource constrained scheduling. However, such approaches only compare the estimated upper and lower bounds of an incomplete schedule to the length of the best feasible schedule at that iteration, which does not fully exploit the potential of the pruning during the search. Aiming to improve the performance of resource constrained scheduling, this paper proposes a parallel structure-aware pruning approach that can traverse the search space significantly faster than state-of-the-art branch-and-bound techniques. This paper makes three major contributions: i) it proposes an efficient pruning technique using the structural scheduling information of the obtained best feasible schedules; ii) it investigates how to perform parallel search to enable efficient multi-directional search and generation of effective fences by tuning the operation enumeration order; and iii) it presents a framework that supports the sharing of minimum upper-bound and fence information among different search tasks to enable efficient parallel structure-aware pruning. The experimental results demonstrate that our parallel pruning approach can drastically reduce the overall resource constrained scheduling time under a wide variety of resource constraints.

Keywords:

Resource constrained scheduling

branch-and-bound

parallel pruning

structure-aware pruning

Efficient Resource Constrained Scheduling Using Parallel Structure-Aware Pruning Techniques

Abstract

AI Summary

Journal

Organization