タスクスケジューリング問題におけるレディ状態の割当て削減によるPDF/IHSの高速化

• Item type: Journal(1)
• 公開日: 2017-03-15
• タイトル: タスクスケジューリング問題におけるレディ状態の割当て削減によるPDF/IHSの高速化
• タイトル / 言語: en
• タイトル: A Speedup Method for PDF/IHS by Reducing Allocations of Idle Tasks in Task Scheduling Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：2020年に向けた情報処理技術] タスクスケジューリング，並列処理，組合せ最適化，PDF/IHS，分枝限定法
• 資源タイプ / 資源タイプ識別子: 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
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者名: 中村, あすか; 富永, 浩文; 前川, 仁孝
• 著者名(英): Asuka, Nakamura; Hirobumi, Tominaga; Yoshitaka, Maekawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文は，タスクスケジューリング問題の厳密解法であるPDF/IHS（Parallel Depth First/Implicit Heuristic Search）の探索ノード数を削減するアルゴリズムを提案する．PDF/IHSは，階層的挟み撃ち探索を用いた分枝限定法の並列探索アルゴリズムであり，大規模なタスクスケジューリング問題を高速に解くためには探索ノード数の削減が必要となる．PDF/IHSの分枝操作は，スケジュールが未確定となる時刻に実行可能なタスクの処理またはレディ状態を割り当てる全組合せを部分問題として生成する．このため，不必要なレディ状態が割り当てられた部分問題が生成されることがある．そこで，本論文では，PDF/IHSの探索ノード数を削減するために，レディ状態を割り当てる部分問題のうち，最適解が得られないことが保障できる部分問題を枝刈りする．提案するアルゴリズムは，分枝操作で割り当てられたタスクの処理時間の情報から探索する必要のない部分問題を判定する．評価の結果，提案手法は，PDF/IHSに対して最大約96倍高速に求解できることを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 58, 号 3, p. 654-662, 発行日 2017-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764