分散式資源分配

Abstract

由於分散式演算法是分散式系統最主要的理論基礎，目前已有不少的研究成果，但在 應用方面的研究卻不多見，因此我們提出三套不同類型的分散式演算法：(1) 鄰近優 先搜尋法，(2) 預定路徑搜尋法，以及(3) 最小擴張樹搜尋法，來解決管理科學上資 源分配的問題，以擴展資訊科技的應用範圍，並對資源分配的傳統問題提供新的研究 方向。 此外，在本論文中，我們選擇以單一電腦來模擬多部電腦的分散處理之環境，設計了 兩套不同性質的績效評估軟體作為研究之工具，以探討這三種演算法的特性及差異情 形，並互相驗證彼此的正確性。它對各演算法的績效評估，著重於三方面：(1) 請求 的平均反應時間, (2) 反應時間的標準變異差, 及(3) 最差的反應時間。根據模擬結 果顯示，我們發現最小擴張樹搜尋演算法在這三種目標函數中表現最好，而鄰近優先 搜尋法則表現最差。 其中最小擴張樹搜尋演算法雖然在各方面的表現，皆優於其它兩類演算法，但此類演 算法並不適用於變動的綱路環境之中。反之，鄰近優先搜尋演算法雖雖然在各方面的 表現最差，但此種演算法很有彈性，且易實作於現實的綱路環境上，故，當綱路節點 常有增減時，此種演算法不失為一解決之道。至於預定路徑搜尋演算法其表現界在其 它兩類演算法之間，當資源高度集中時，會有較佳的績效。