異質處理器基數的分散式系統中的排程技巧

Abstract

本篇論文提出了將進入系統時間，執行時間及所需處理器皆相異的工作指派到不同處理器基數上的排程演算法。我們證明了這是一個NP完備的問題，並提出了動態規劃的方法求得最佳解。由於動態規劃需要大量的時間計算，我們還提出了有效的加速法來改善我們的動態規劃。我們還提出了快速的啟發示算法來解個個問題。實驗結果說明了部份啟發示算法不僅是執行時間快速，也能提供相當良好的解答。

This paper proposes scheduling algorithms for assigning jobs with different release time and execution time, to machines with heterogeneous processor cardinality. We show that this scheduling problem is NP-complete, and propose dynamic programming to find the optimal schedules. Since the dynamic programming is time-consuming we propose techniques that improve the efficiency of the dynamic programming. We also propose heuristic algorithms for this scheduling problem. Experimental results suggest that some of the heuristics not only compute the answer efficiently but also provide good solution.