Please use this identifier to cite or link to this item:

Title: 一個用以解決工作匹配與排程問題之快速螞蟻系統優化法
Authors: 江傳文
Keywords: 個人電腦叢集;工作匹配與排程;螞蟻系統;區域搜尋
PC Clusters;Task Matching and Scheduling;Ant System;Local Search
Date: 2005
Issue Date: 2017-10-17 13:03:53 (UTC+8)
Abstract: 本文中,我們將以快速螞蟻系統 (Fast Ant System, FANT) 的設計方法為基礎,提出一個名為FANT-TMS (Fast Ant System for Task Matching and Scheduling) 且應用在工作匹配與排程問題求解之演算方法。此一方法旨在有效地決定各個工作在執行時期的順序,並將工作分派給叢集運算環境中合適的處理單元 (processing element, PE) 執行。FANT-TMS 採用一種間接解的表示方法用以降低演算方法在執行時期的複雜度。相較於以基因演算法為基礎的工作匹配與排程技術,實驗結果顯示,本文所提出之 FANT-TMS 演算法確實優於傳統的方法。此外,為了強化演算法的執行效能,我們亦提出一種嶄新的區域搜尋方法。實驗結果亦呈現出此一設計方法的優異性。
In this paper, an efficient algorithm based on the Fast Ant System (FANT) is proposed. This algorithm, namely FANT-TMS, concentrates on properly sequencing the execution of the tasks and allocating the tasks to the processing elements of the cluster system. FANT-TMS is different from the previously proposed approaches in twofold. First, it employs an indirect representation scheme to represent a solution of the original problem. Second, it couples a local search procedure with a mechanism to improve the performance. FANT-TMS is evaluated through a comparison with the genetic algorithm (GA) based scheduling technique in terms of overall execution time of the parallel program. Simulation results show the efficiency and effectiveness of the proposed algorithm. With regarded to the performance of the proposed local search algorithm, these experimental results also demonstrate that significant improvement over existing methods (such as FASTEST and TASK) can be obtained.
Relation: TANET 2005 台灣網際網路研討會論文集
Data Type: article
Appears in Collections:[TANET 台灣網際網路研討會] 會議論文

Files in This Item:

File Description SizeFormat
306.pdf58KbAdobe PDF197View/Open

All items in 學術集成 are protected by copyright, with all rights reserved.

社群 sharing