To realize efficient parallel processing, which is one of effective methods that deal with computing intensive applications, the technology of solving the problems of task matching and scheduling becomes extremely important. In this thesis, an Ant Colony Optimization (ACO) approach is employed for allocating task graphs onto a heterogeneous computing system. The approach uses a new state transition rule to reduce the time needed for finding a satisfactory solution. And a local search procedure is designed to improve the obtained solution. Furthermore, by applying the Taguchi Method in the technology of Quality Engineering, and further utilizing the Orthogonal Array (OA) to reduce the number of experiments and find the optimal combination of parameters, which allows the Ant Colony Algorithm to find solutions more efficient. The proposed algorithm is compared with the genetic-algorithm-based approach and the dynamic priority scheduling (DPS) heuristic. Experimental results show that the ACO approach outperforms two computing approaches in solving the task matching and scheduling problem.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0218105-221434 |
| Date | 18 February 2005 |
| Creators | Lee, Yi-chan |
| Contributors | Tung-kuan Liu, Chang-Biau Yang, Chuan-wen Chiang, John Y. Chiang, Chungnan Lee |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0218105-221434 |
| Rights | withheld, Copyright information available at source archive |
Page generated in 0.0022 seconds