頁籤選單縮合
題名 | An Efficient Scheduling Algorithm for Multiprocessor Systems=在多處理機系統環境下一個具效能的排程演算法 |
---|---|
作 者 | 林建福; | 書刊名 | 德明學報 |
卷期 | 26 民94.12 |
頁次 | 頁123-135 |
分類號 | 494.542 |
關鍵詞 | 愈快愈佳工作排程; 愈慢愈佳工作排程; 最長工作優先排程; 愈急迫且愈有利益工作排程; 最佳排程; ASAP; ALAP; LPT; MUMB; Optimal schedule; |
語文 | 英文(English) |
中文摘要 | 眾所皆知,在多處理機系統環境下對具有任意先後條件限制且不可分割的工作做排程是個NP-完整問題,只有在某些特殊的情況下,才有可能存在具效能的排程演算法。本文將藉由“愈快愈佳”與“愈慢愈佳”的工作排程技巧,提出一個稱為“愈急迫且愈有利益”的工作排程演算法。本文主要目的在證明MUMB演算法與Hu及Coffman的運作模式相同,所以在某些特殊的情況下,它將會產生最佳的排程。此外,本文也將證明MUMB演算法對於處理無先後條件限制的工作排程問題,它的工作排程方式將等同於“最長工作優先排程”的工作排程演算法。 |
英文摘要 | The problem of scheduling nonpreemptive tasks with arbitrary precedence constraints on a multiprocessor system is known to be NP-complete. Only for some special cases of this problem, they do exist efficient algorithm. In this paper, an efficient heuristic scheduling algorithm, the most-urgent with most-benefit (MUMB) algorithm, is developed which is based on the concept of as soon as possible (ASAP) and as late as possible (ALAP) scheduling techniques. The goal of this paper is to prove the behavior of MUMB algorithm is equivalent to the Hu's and Coffman's heuristic algorithm do, therefore, it could generate an optimal schedule in some special case. Besides, we will prove it is equivalent to the largest processing time first (LPT) scheduling algorithm for the case where the precedence relation does not exist will be given. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。