Abstract
排程問題在電腦科學及工業上一直扮演著重要的角色，在本論文□，我們一共考慮了五個多機器的排程問題，也就是，最大延遲（Maximum lateness）、最大延後（Maximun tardiness ）、最大流程時間（Maximun folw time ）、最後完成時間（Maximun completion time ）、最後送達時間（Maximun delivery time ）等問題，而且，我們分別就相等機器（Ident-ical machine）及統一機器（Unifprm machine ）來討論這些問題的。對於相等機器，高斯菲爾德君[Gusfield 84] 曾探討過最大延遲及最大送達時間這兩個問題。他提出了兩個近似演算法，並求得演算法的上限（Upper bound ）。我們另外提出兩個新的近似演算法，也求得它們的上限。由實驗數據，可以看出我們的演算法所算出的結果，較接近最佳解。對於其它的問題，我們提出了近似演算法來求近似解，同樣地，也求得它們的上限。對於統一機器，我們所面臨的問題和在相等機器上類似，因此，我們並沒有提出新的演算法，就用相等機器上的演算法來解它們。每個演算法的上限我們也一併提出。