網格系統中時間限制的工作排程

Abstract

這篇論文介紹了將具有順序限制的工作排程到可使用時間被分割成一段段的處理器上的方法。我們討論了兩種順序限制的狀況─樹狀及鏈狀。我們證明在樹狀限制下的工作排程是一個NPC的問題，接著我們對於線性順序的工作排程提出動態規劃演算法取得最佳解。該動態規劃演算法可以被推廣到異質環境中，亦可推廣以解決似樹狀結構的工作排程問題。而為了減少排程的時間，我們提出了三種不同的演算法。實驗結果顯示，我們的三種演算法即使與以動態規劃取得的最 佳解比較，仍然可以得到近似最佳的排程。

This paper introduces techniques in scheduling jobs with dependency constraint to processors whose available time are fragmented into time slots. We discuss two job dependency patterns – tree and chains. We show that it is NP-complete to schedule jobs with a tree dependency pattern. Then we propose a dynamic programming algorithm to get the optimal schedule for assigning jobs with linear dependency. The dynamic programming can be generalized to heterogeneous environment and tree-like dependency structure. In order to reduce the time of scheduling we also propose three different heuristics. Experimental results indicate that these heuristics do provide near optimal schedules even when compared against the optimal solution found by the dynamic programming.