|
早稲田大学
笠原 博徳
教授
機関別共同研究
Discovery Saga
論文分野別Discovery Saga
研究テーマDiscovery Saga
協賛企業
共同研究先:Yokogawa Hokushin Electric Corp
Corporate
共同研究数 1
Article
1988 6
Wiley Online Library
Application of df/ihs to minimum total weighted flow time multiprocessor scheduling problems
(First author)
重み付け総フロー時間最小化マルチプロセッサ・スケジューリング問題へのdf/ihsの適用
Hironori Kasahara, Munenori Kai, Seinosuke Narita, Hidehiko Wada
Systems and Computers in Japan
【抄録】
In most cases, the scheduling problem for the multiprocessor system is NP‐ or strong NP‐hard. For this problem, we have already proposed a practical optimization algorithm DF/IHS (Depth First/Implicit Heuristic Search), which combines the list‐scheduling algorithm and the depth‐first search, for the minimum parallel processing time multiprocessors scheduling problem. This paper presents a result of application of DF/IHS to the minimum total weighted flow time problem, which is used in the optimization of memory utilization. The problem of allocating tasks to m processors is considered with or without precedence constraints among the tasks. It was verified that the DF/IHS can be applied to this kind of problem very effectively, where the optimal or highly accurate approximate solution is obtained for the large‐scale problem with several hundreds of tasks. Copyright © 1988 Wiley Periodicals, Inc., A Wiley Company
【抄録日本語訳】
多くの場合、マルチプロセッサシステムのスケジューリング問題はNP-または強NP-困難である。この問題に対して、我々は既にリストスケジューリングと深さ優先探索を組み合わせた実用的な最適化アルゴリズムDF/IHS(Depth First/Implicit Heuristic Search)を提案し、マルチプロセッサの最小並列処理時間スケジューリング問題に適用してきた.本論文では、メモリ使用量の最適化に用いられる最小総加重フロー時間問題に対して、DF/IHSを適用した結果を示す。m個のプロセッサにタスクを割り当てる問題を、タスク間の優先度制約の有無に関わらず検討した。その結果,DF/IHSはこの種の問題に非常に有効に適用でき,数百のタスクからなる大規模な問題に対して,最適解または高精度な近似解が得られることが確認された.著作権 © 1988 Wiley Periodicals, Inc.