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

• Item type: Trans(1)
• 公開日: 2014-01-22
• タイトル: タスクスケジューリング問題の厳密解求解における探索ノード数削減アルゴリズム
• タイトル / 言語: en
• タイトル: A Reduction Algorithm of Branching Nodes for Solving Task Scheduling Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [通常論文] タスクスケジューリング，並列処理，組合せ最適化，DF/IHS法，分枝限定法
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 千葉工業大学情報工学科
• 著者所属: 千葉工業大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者名: 中村, あすか; 前川, 仁孝
• 著者名(英): Asuka, Nakamura; Yoshitaka, Maekawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文は，分枝限定法を用いたタスクスケジューリング問題の厳密解法の1つであるDF/IHS法（Depth First/Implicit Heuristic Search method）の探索ノード数を削減するアルゴリズムを提案する．本手法を用いて大規模なタスクスケジューリング問題を高速に解くために，並列探索アルゴリズムが提案されているが，さらなる高速化を行うためには探索ノード数の削減が必要となる．DF/IHS法の分枝操作は，スケジュールが未確定となる時刻に実行可能なタスクの処理またはレディ状態を割り当てる全組合せを部分問題として生成する．このため，不必要なレディ状態が割り当てられた部分問題が生成されることがある．そこで，本論文では，DF/IHS法の探索ノード数を削減するために，レディ状態を割り当てる部分問題のうち，他の部分問題よりも短いスケジューリング長が得られない問題を探索することなしに判定し，探索木中に生成することを抑制する．提案するアルゴリズムは，同一のPEに割り当てられたタスクを融合することで，部分問題のタスクグラフを再定義する．次に，再定義したタスクグラフを比較することで，探索する必要のない部分問題の生成を中止する．本アルゴリズムは，暫定解や下界値を用いないため，探索の進行状況の影響を受けずに探索ノードを削減することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 7, 号 1, p. 1-9, 発行日 2014-01-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会