タスクスケジューリング問題におけるDF/IHS法の探索ノード数削減

• Item type: Trans(1)
• 公開日: 2017-02-27
• タイトル: タスクスケジューリング問題におけるDF/IHS法の探索ノード数削減
• タイトル / 言語: en
• タイトル: A Reduction Method of Branching Node of DF/IHS for Task Scheduling Problems
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 千葉工業大学大学院情報科学研究科情報科学専攻
• 著者所属: 千葉工業大学大学院情報科学研究科情報科学専攻
• 著者所属: 千葉工業大学大学院情報科学研究科情報科学専攻
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information and Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information and Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Information and Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Faculty of Information and Computer Science, Chiba Institute of Technology
• 著者名: 松瀬, 弘明; 中村, あすか; 富永, 浩文; 前川, 仁孝
• 著者名(英): Hiroaki, Matsuse; Asuka, Nakamura; Hirobumi, Tominaga; Yoshitaka, Maekawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本発表では，分枝限定法を用いたタスクスケジューリング問題の最適解法の1つであるDF/IHS法（Depth First/Implicit Heuristic Search method）の探索ノード数を削減するアルゴリズムを提案する．本手法は，割当て可能なタスクを列挙することで最適解を求解する．このため，問題規模が大きくなるほど探索ノード数が膨大になり，探索ノード数の削減が必要となる．DF/IHS法は，分枝操作で実行可能なタスクをプロセッサ（PE）に割り当てるすべての組合せを列挙するため，PEに不必要な待ち状態を割り当てる部分問題を生成する．不必要な待ち状態を割り当てる部分問題は，探索済みの部分問題の割当てタスク情報を用いて判定をすることができる．DF/IHS法は不必要な部分問題を枝刈りするために，下界値を用いた限定操作を行うが，すべての不必要な部分問題を枝刈りできないため，さらなる高速化を行うためにはすべての不要な部分問題を枝刈りする必要がある．そこで本発表では，すべての不必要な部分問題を削減するために，探索済みノード情報を記憶し，記憶した情報と比較することにより探索する必要のない部分問題をすべて枝刈りする．本アルゴリズムは暫定解や下界値の影響を受けないため，探索の進行状況によらずに探索ノードを削減することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This presentation proposes a reduction algorithm of branching nodes for the DF/IHS (Depth First/Implicit Heuristic Search) method which is one of the efficient algorithms for solving task scheduling problems using the branch and bound method. The DF/IHS method solves the optimal solution by enumerating all combinations of the allocatable tasks. Therefore, when problem's scale is large, the number of search nodes is a lot, and it is necessary to reduce the number of search nodes. The DF/IHS method makes some subproblems by enumerating all combinations of the allocatable tasks. For this reason, the DF/IHS method makes subproblems of allocating unnecessary idle tasks. The DF/IHS cuts unnecessary nodes using the lower bounds for reducing search nodes, but it reduces a few search nodes. Therefore, it is necessary to reduce all nodes to perform further speedup. The proposed method reduces unnecessary subproblems by using subproblems in the table to the number of search nodes. Therefore, the proposed method to cutting all of the required portions, without problem to search by comparing it with stored information. 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）; 巻 10, 号 2, p. 4-4, 発行日 2017-02-27
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会