タスクスケジューリング問題の厳密解求解における探索ノード数削減アルゴリズム

• 中村, あすか

• 前川, 仁孝

書誌事項

タイトル別名

• A Reduction Algorithm of Branching Nodes for Solving Task Scheduling Problems

抄録

本論文は，分枝限定法を用いたタスクスケジューリング問題の厳密解法の1つであるDF/IHS法（Depth First/Implicit Heuristic Search method）の探索ノード数を削減するアルゴリズムを提案する．本手法を用いて大規模なタスクスケジューリング問題を高速に解くために，並列探索アルゴリズムが提案されているが，さらなる高速化を行うためには探索ノード数の削減が必要となる．DF/IHS法の分枝操作は，スケジュールが未確定となる時刻に実行可能なタスクの処理またはレディ状態を割り当てる全組合せを部分問題として生成する．このため，不必要なレディ状態が割り当てられた部分問題が生成されることがある．そこで，本論文では，DF/IHS法の探索ノード数を削減するために，レディ状態を割り当てる部分問題のうち，他の部分問題よりも短いスケジューリング長が得られない問題を探索することなしに判定し，探索木中に生成することを抑制する．提案するアルゴリズムは，同一のPEに割り当てられたタスクを融合することで，部分問題のタスクグラフを再定義する．次に，再定義したタスクグラフを比較することで，探索する必要のない部分問題の生成を中止する．本アルゴリズムは，暫定解や下界値を用いないため，探索の進行状況の影響を受けずに探索ノードを削減することができる．

This paper proposes a reduction algorithm of branching nodes for DF/IHS (Depth First/Implicit Heuristic Search method) which is one of the efficient algorithms for solving task scheduling problems using branch and bound method. For solving large-scale task scheduling problems fast using the DF/IHS, it is necessary to not only using parallel search algorithms but reducing branching nodes. The branching operation of the DF/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 DF/IHS may make subproblems assigned some unnecessary idle tasks. Therefore, for reduction of branching nodes of the DF/IHS, the proposed method picks out some subproblems, whose schedule length is longer than others, from among subproblems assigned idle tasks without search. The proposed algorithm redefines task graph of subproblem assigned idle tasks in terms of task-fusion. Then it does not make unnecessary subproblems using the comparison of the redefined task graphs. Since the algorithm does not use upper and lower bounds, it is able to reduce branching nodes without effects of the search order.

収録刊行物

• 情報処理学会論文誌プログラミング（PRO）

  情報処理学会論文誌プログラミング（PRO） 7 (1), 1-9, 2014-01-22

キーワード

• [通常論文] タスクスケジューリング，並列処理，組合せ最適化，DF/IHS法，分枝限定法

詳細情報

• CRID: 1050845762834513024
• NII論文ID: 110009658968
• NII書誌ID: AA11464814
• ISSN: 18827802
• Web Site: http://id.nii.ac.jp/1001/00098076/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles