Task Assignment Problems in Distributed Computing Systems by Simulated Annealing

CCUR > College of Natural Science and Engineering > College of Science > Department of Applied Mathematics > journal articles > Item 987654321/32505

Please use this identifier to cite or link to this item: https://irlib.pccu.edu.tw/handle/987654321/32505

Title:	Task Assignment Problems in Distributed Computing Systems by Simulated Annealing 使用模擬退火求解分散式系統之工作分派問題
Authors:	林豐澤許清琦
Contributors:	應數系
Keywords:	分派分散式求解系統退火模擬
Date:	1991-09
Issue Date:	2016-04-07 10:35:50 (UTC+8)
Abstract:	本文使用一種隨機的啟發式找尋方法稱為模擬退火來求解分散式系統之靜態工作分派問題。工作分派問題的目的在於將程式的模組群分派給一些相互聯結的處理機，希望求得處理機之最大使用率同時也減少處理機之間傳遞資料的通訊成本，這個問題已被證明是 NP-HARD。雖然模擬退火已被用於求解廣泛的組合性最佳化問題，但是為了要收斂於最佳解往往需要花費冗長的計算時間。在本文中，我們設計一套非常有效率的退火程序加上一種很好的移動策略以及使用比熱觀念作為系統的凍結條件，因而可求得工作分派問題的最佳近似解，並且明顯地大量減少了原來所需之遞迴執行次數。 The stochastic , hcuristic search algorithm calld simulated annealing is considered for the problems of static task assignment in distributed computing systmes. The purposes of task assignment problems are to assign modules of programs over a set of interconnected processors in order to both maximize the utilization of processors and minimize interprocessor communication costs. This problem has been proven to be NP-hard. Although simulated annealing has been applied to a broad class of combinatorial optimization problems, but it requires a long computation time in order to converge to the globally optimal solution. In this paper, we design a very efficient annealing schedule with good move generation strategies and use the concept of specific heat and the frozen condition to obtain near-optimal solutions for task assignment problems with a significantly large reduction in the number of iterations.
Relation:	中國工程學刊 14:5 民80.09 頁537-550
Appears in Collections:	[Department of Applied Mathematics] journal articles

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	188	View/Open

View Licence

Loading...