工作可複製之排程問題的啟發式演算法

Abstract

如何把一組有部份順序關系且可重覆進入的工作排程至有限個關行處理單元上, 並使 此組工作能在最短的時間內完成的這類問題為本文所探討之主題。由於此問題是NP-h ard , 故對於工作複制排程問題我們提出了三個啟發式演算法, 其中KAB 及KET 是針 對同質機器架構, 而KEF 則是針對祑質機器架構。這三個演算法的主要概念是充分利 用處理單元工作間之先後順序及通訊延遲所造成的空置時間。來執行一些被複制的工 作以縮短整組工作的完成時間。在一千組的模擬實驗中, 比較每組工作的完成時間。 在一千組的模擬實驗中, 比較每組工作分別經過KET 和ERT 排程後之完成時間及比較 每組工作分別經過KAB 和ERT 排程後之完成時間, KET 的改進率超過70% 而KAB 的改 進率亦超過65% 。除此之外, 在本文中我們亦對每一個演算法分析其時間複雜度及最 差狀況下的最高時間界限。