一個用以解決工作匹配與排程問題之快速螞蟻系統優化法

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.