在先行關係下求最下加總延遲時間之工作排程

Abstract

本篇論文旨在介紹一排程問題，並有效運用人工智慧之Ａ□演算法，提出解決此問 題之道。茲將問題描述如下： 在一電腦系統中，若給予一等待處理之工作集合，與各工作之執行所需時間，在具 有工作執行次序先行關係之前提下，如何求得具有最小加總延遲時間(total delay time) 之最佳排程？ 該問題有如大多數的排程問題般，已證明為一NP-完備 (NP-complete) 問題，即所 需之求解時間，截至目前為止，並無法突破多項式時間(polynomial time) 之囿限 。吾等則運用人工智慧所發展出的Ａ□演算法，針對單一處理器系統與多元處理器 系統，分別提出兩個演算法以解決該問題。同時我們亦提出此演算法所需之評估函 數，它可以加速搜尋處理的過程，配合〝反向範圍限制表〞 (backward range- limited table)以輔助評估函數之計算，並期能儘量縮短求解所需之時間。 經實驗結果證明，吾等所提出之演算法的確能有效地縮減平均搜尋的次數，而獲致 最佳解；尤其當結合研究所提出之限制條件時，其縮減效果更為顯著。另外，我們 也針對多元處理器系統上某些特殊的情形予以個別討論。