Journal Article タスクスケジューリング問題におけるレディ状態の割当て削減によるPDF/IHSの高速化
A Speedup Method for PDF/IHS by Reducing Allocations of Idle Tasks in Task Scheduling Problem

中村, あすか  ,  富永, 浩文  ,  前川, 仁孝

58 ( 3 )  , pp.654 - 662 , 2017-03-15
本論文は,タスクスケジューリング問題の厳密解法であるPDF/IHS(Parallel Depth First/Implicit Heuristic Search)の探索ノード数を削減するアルゴリズムを提案する.PDF/IHSは,階層的挟み撃ち探索を用いた分枝限定法の並列探索アルゴリズムであり,大規模なタスクスケジューリング問題を高速に解くためには探索ノード数の削減が必要となる.PDF/IHSの分枝操作は,スケジュールが未確定となる時刻に実行可能なタスクの処理またはレディ状態を割り当てる全組合せを部分問題として生成する.このため,不必要なレディ状態が割り当てられた部分問題が生成されることがある.そこで,本論文では,PDF/IHSの探索ノード数を削減するために,レディ状態を割り当てる部分問題のうち,最適解が得られないことが保障できる部分問題を枝刈りする.提案するアルゴリズムは,分枝操作で割り当てられたタスクの処理時間の情報から探索する必要のない部分問題を判定する.評価の結果,提案手法は,PDF/IHSに対して最大約96倍高速に求解できることを確認した.
This paper proposes a reduction algorithm of branching nodes for the task scheduling algorithm PDF/IHS (Parallel Depth First/Implicit Heuristic Search). The PDF/IHS is a parallel branch and bound method using HPAS (Hierarchical Pincers Attack Search). For solving large-scale task scheduling problems fast using the PDF/IHS, it is necessary to not only using parallel search algorithms but reducing branching nodes. The branching operation of the PDF/IHS makes some subproblems by enumerating all combinations of the allocatable tasks and idle tasks at the time when the schedule is undecided. For this reason, the PDF/IHS may make subproblems assigned some unnecessary idle tasks. Therefore, for reduction of branching nodes of the PDF/IHS, the proposed method cuts some subproblems assigned idle tasks, whose schedule length is longer than others. The proposed algorithm determines unnecessity of searching subproblems using time of allocated task in the branching operation. As a result of evaluation, the speedup ratio of the proposal method compared with the PDF/IHS is about 96 times on the maximum.

Number of accesses :  

Other information