臺灣博碩士論文加值系統

平行處理是個解決需要龐大運算量之應用的有效方法之一，而要實現有效率的平行處理，用來解決工作匹配與排程問題的技術便顯得相當重要。在本論文中，我們提出了一個螞蟻族群最佳化演算法，用以解決在異質性環境下的工作匹配與排程問題。我們以競爭式選擇法取代傳統螞蟻族群最佳化中的輪盤式選擇法以縮短求解的時間，也設計了適當的區域搜尋法來改善求解的品質。此外，我們並利用了品質工程技術中的「田口實驗法」概念，採用其直交表(Orthogonal Array，OA)以減少實驗次數並求得最佳的參數組合，使得螞蟻族群最佳化演算法的求解效率更佳。我們並將本文中所提出的方法與基因演算法(Genetic Algorithm, GA)和以list scheduling 為基礎且在同類型方法中表現出色的Dynamic Priority Scheduling (DPS)演算法進行比較。實驗結果顯示，在解決工作匹配與排程問題上，我們所提出的方法表現優於基因演算法以及DPS演算法。

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.

1. INTRODUCTION 1
2. PROBLEM DEFINITIONS 3
3. LITERATURE REVIEWS 8
3.1 DYNAMIC PRIORITY SCHEDULING 8
4. THE PROPOSED METHOD 10
4.1 COMPONENTS OF THE ANT COLONY ALGORITHM 14
4.1.1 State transition rules 15
4.1.2 Pheromone updating rules 17
4.1.3 Local optimization strategy 19
4.2 ORTHOGONAL ARRAY AND FACTOR ANALYSIS 24
5. EXPERIMENTAL RESULTS 27
5.1 PARAMETER SETTINGS 28
5.2 LOCAL SEARCH STRATEGIES COMPARISON 31
5.3 SCHEDULING ALGORITHMS COMPARISON 33
6. CONCLUSIONS AND FUTURE WORK 40
REFERENCES 41

[1] Ahmad, I. and Dhodhi, M.K., “Multiprocessor Scheduling in a Genetic Paradigm,” Parallel Computing, Vol. 22, No. 3, pp. 395-406, March, 1996.
[2] Ahmad, I., Dhodhi, M.K., and UI-Mustafa, R., “DPS: Dynamic Priority Scheduling Heuristic for Heterogeneous Computing Systems,” IEE Proceedings- Computers and Digital Techniques, Vol. 145, pp. 411-418, November, 1998.
[3] AI-Mouhamed, M. and Najjari, H., “Adaptive Scheduling of Computations and Communications on Distributed-Memory Systems,” Parallel and Distributed Computing, Vol. 60, pp. 716-740, 2000.
[4] Chien, Y.H., "A Hybrid Evolutionary Algorithm for Task Matching and Scheduling," Master dissertation of Department of Computer Science and Information Engineering, Da-Yeh University, 2003.
[5] Colorni, A., Dorigo, M., and Maniezzo, V., “Distributed Optimization by Ant Colonies,” Proceedings of the First European Conference on Artificial Life, Paris, France, F.Varela and P.Bourgine (Eds.), Elsevier Publishing, pp. 134-142, 1992.
[6] Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M., “Ant System for Job-shop Scheduling,” Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), Vol. 34, pp. 39-53, 1994.
[7] den Besten, M.L., Stützle, T., and Dorigo, M., “Ant Colony Optimization for the Total Weighted Tardiness Problem,” Lecture Notes in Computer Science, Springer-Verlag, Vol. 1917, pp. 611-620, Berlin, Germany, 2000.
[8] Dorigo, M., and Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53-66, 1997.
[9] Dorigo, M., Maniezzo, V., and Colorni, A., “The Ant System: An Autocatalytic Optimizing Process,” Technical Report, No. 91-016, Politecnico di Milano, Italy, 1991.
[10] Dorigo, M., Maniezzo, V., and Colorni, A., “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, pp. 29-41, 1996.
[11] Hou, E.S., Ansari, N., and Ren, H., “A Genetic Algorithm for Multiprocessor Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 2, pp. 113-120, February, 1994.
[12] Iverson, M.A., Ozguner, F., and Follen, G.J., “Parallelizing Existing Applications in a Distributed Heterogeneous Environment,” Proceedings of Heterogeneous computing workshop, pp. 93-100, April, 1995.
[13] Kohler, W.H. and Steiglitz, K., “Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems,” J. ACM, Vol. 21, No. 1, pp. 140-156, January, 1974.
[14] Kwok, Y.K. and Ahmad, I., “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Transactions on Parallel and Distributed Systems, Vol. 7, pp. 506-521, May, 1996.
[15] Maniezzo, V. and Carbonaro, A., “An Ants Heuristic for the Frequency Assignment Problem,” Future Generation Computer Systems, Vol. 16, pp. 927-935, 2000.
[16] Maniezzo, V., Colorni, A., and Dorigo, M., “The Ant System applied to the Quadratic Assignment Problem,” Technical Report IRIDIA/94-28, IRIDIA, Universite Libre de Bruxelles, Belgium, 1994.
[17] Merkle, D., Middendorf, M., and Schmeck, H., “Ant Colony Optimization for Resource-Constrained Project Scheduling,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 4, pp. 333-346, August, 2002.
[18] Sih, G.C. and Lee, E.A., “A Compile-time Scheduling Heuristic for Interconnection-constrained Heterogeneous Processor Architectures,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, pp. 175-187, February, 1993.
[19] Sloane, N.J.A, “A Library of Orthogonal Arrays,” Website, http://www.research.att.com/~njas/oadir/.
[20] Stutzle, T. and Dorigo, M., “ACO Algorithms for the Quadratic Assignment Problem,” In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 1999.
[21] Wang, L., Siegel, H.J., Roychowdhury, V.P., and Maciejewski, A.A., “Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach,” Parallel and Distributed Computing, Vol. 47, pp. 8-22, 1997.
[22] Wu, M.Y., Shu, W., and Gu, J., “Efficient Local Search for DAG Scheduling,” IEEE Transactions on Parallel and Distributed Systems, Vol. 12, No. 6, pp. 617-627, June, 2001.