標題: 在先行關係下求最下加總延遲時間之工作排程
Task scheduling with precedence constraints to minimize the total delay time
作者: 張肇明
ZHAGN, ZHAO-MING
陳安斌
徐俊傑
CHEN, AN-BIN
XU, JUN-JIE
資訊管理研究所
關鍵字: 先行關係;最下加總延遲時間;工作排程
公開日期: 1991
摘要: 本篇論文旨在介紹一排程問題,並有效運用人工智慧之A□演算法,提出解決此問 題之道。茲將問題描述如下: 在一電腦系統中,若給予一等待處理之工作集合,與各工作之執行所需時間,在具 有工作執行次序先行關係之前提下,如何求得具有最小加總延遲時間(total delay time) 之最佳排程? 該問題有如大多數的排程問題般,已證明為一NP-完備 (NP-complete) 問題,即所 需之求解時間,截至目前為止,並無法突破多項式時間(polynomial time) 之囿限 。吾等則運用人工智慧所發展出的A□演算法,針對單一處理器系統與多元處理器 系統,分別提出兩個演算法以解決該問題。同時我們亦提出此演算法所需之評估函 數,它可以加速搜尋處理的過程,配合〝反向範圍限制表〞 (backward range- limited table)以輔助評估函數之計算,並期能儘量縮短求解所需之時間。 經實驗結果證明,吾等所提出之演算法的確能有效地縮減平均搜尋的次數,而獲致 最佳解;尤其當結合研究所提出之限制條件時,其縮減效果更為顯著。另外,我們 也針對多元處理器系統上某些特殊的情形予以個別討論。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT802396006
http://hdl.handle.net/11536/55969
顯示於類別:畢業論文