任務排程在網格計算中扮演著重要的角色，它為了降低整體程式的執行時間將任務分配至平行分散的系統上執行。為了解決任務排程的問題，目前已有許多類型的演算法被提出來，其中包含基因演算法，演算法的特色是使用染色體表示法來化簡問題並經由世代交替來增強解的品質。本篇論文提出一種基於基因理念的演算法來解決此問題，透過兩個主要的想法來改進現有的基因演算法的不足。首先提出一個新的初始化策略來產生第一代的染色體，新的初始化策略為了減少探索解空間的時間而將搜索空間進行分類。其次，一些現有的基因演算法可能會在做運算時意外
地失去某些解的特性。因此我們加入了些許修正來幫助保存解決方案的特徵。最後使用五個廣為人知的應用程序和具體定義的系統環境來評估演算法的效能。實驗結果顯示再多種參數的變化下，該演算法優於其他演算法。更多的實驗結果說明該演算法與各種參數的相關性。

In the grid computing, task scheduling which maps tasks onto a parallel and distributed system is important for achieving good performance in terms of minimizing the overall execution time. Various algorithms that include genetic algorithms (GA) have been proposed for the issue of scheduling. The feature in GA-based algorithm is used the chromosome representation as a solution and transform a population of chromosomes for improving the quality of solutions. This thesis presents a GA-based algorithm to solve this problem by improving the existing genetic algorithm with two main ideas. First of all, a new initialization strategy is used to generate the first population of chromosomes, and classifies the search space into groups for the purpose of accelerating the time to explore the whole solution space. Secondly, the found solution may lose during certain operators unexpectedly in some GA-based algorithms. The modifications, based on problem-specific knowledge, are added to preserve the characteristics of the found solution. Our proposed algorithm is implemented and evaluated using five well-known applications and the specific-defined system environment. The experimental results show that the proposed algorithm outperforms other algorithms within several parameter settings. The more experimental results figure out the relationship between the parameter setting and the performance of the proposed method.

[1] I. Ahmad and Y. Kwok, “A New Approach to Scheduling Parallel Programs Using
Task Duplication,” Proc. Int’l Conf. Parallel Processing, vol. 2, pp. 47-51, 1994.
[2] E.G. Coffman, “Computer and Job-Shop Scheduling Theory,” Wiley, New York,
1976.
[3] D. Culler, J. Singh, and A. Gupta, “Parallel Computer Architecture: A Hardware/
Software Approach,” Morgan Kaufmann Publisher., San Francisco, 1998.
[4] P. Choudhury, and P.P. Chakrabarti, R. Kumar, “Online Scheduling of Dynamic
Task Graphs with Communication and Contention for Multiprocessors,” IEEE
Trans. on Parallel and Distributed Systems, vol. 23, no. 1, pp. 126-133, 2012.
[5] G. Falzon, and Maozhen Li, “Enhancing Genetic Algorithms for Dependent Job
Scheduling in Grid Computing Environments,” Journal of Supercomputing, vol.
62, no. 1, p 290-314, 2012.
[6] M.R. Garey and D.S. Johnson, “Computers and Intractability: A Guide to the
Theory of NP-Completeness,” W.H. Freeman and Company, 1979.
[7] T.C. Hu, “Parallel Sequencing and Assembly Line Problems,” Operations Research,
vol. 19, no. 6, pp. 841-848, Nov. 1961.
[8] J.H. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan
Press, Ann Arbor, Mich., 1975.
[9] J.J. Hwang, Y.C. Chow, F.D. Anger, and C.Y. Lee, “Scheduling Precedence
Graphs in Systems with Interprocessor Communication Costs,” SIAM J. Computing.,
vol. 18, no. 2, pp. 244-257, 1989.
[10] K. Hwang, “Advanced Computer Architecture: Parallelism, Scalability, Programmability,”
McGraw-Hill, Inc., New York, 1993.
[11] E.S.H. Hou, N. Ansari, and H. Ren, “A Genetic Algorithm for Multiprocessor
Scheduling,” IEEE Trans. on Parallel and Distributed Systems, vol. 5, no. 2, pp.
113-120, 1994.
[12] K. Hyunjin, and K. Sungho, “Communication-aware Task Scheduling and Voltage
Selection for Total Energy Minimization in a Multiprocessor System Using
Ant Colony Optimization,” Information Sciences, vol. 181, issue 18, pp. 3995-
4008, Sep. 2011.
[13] S.J. Kim and J.C. Browne, “A General Approach to Mapping of Parallel Computation
upon Multiprocessor Architectures,” Proc. Int’l Conf. Parallel Processing,
vol. 2, pp. 1-8, 1988.
[14] B. Kruatrachue and T.G. Lewis, “Grain Size Determination for Parallel Processing,”
IEEE Software., pp. 23-32, Jan. 1988.
[15] Y. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique
for Allocating Task Graphs to Multi-processors,” IEEE Trans. Parallel and
Distributed Systems., vol. 7, no. 5, pp. 506-521, May 1996.
[16] Y.K. Kwok and I. Ahmad, “Efficient Scheduling of Arbitrary Task Graphs to
Multiprocessors Using a Parallel Genetic Algorithm,” Journal of Parallel and
Distributed Computing, vol. 47, no. 1, pp. 58, 1997.
[17] Y.K. Kwok, and I. Ahmad, “Static Scheduling Algorithms for Allocating Directed
Task Graphs to Multiprocessors,” ACM Computing Surveys, vol. 31, issue 4, pp.
406-471, Dec. 1999.
[18] J. Liou and M.A. Palis, “An Efficient Task Clustering Heuristic for Scheduling
DAGs on Multiprocessors,” Proc. Symp. Parallel and Distributed Processing, 1996.
[19] J. Liou and M.A. Palis, “A Comparison of General Approaches to Multiprocessor
Scheduling,” Proc. Int’l Parallel Processing Symp., pp. 152-156, 1997.
[20] H. Liu, A. Abraham, V. Snašel, and S. McLoone, “Swarm Scheduling Approaches
for Work-flow Applications with Security Constraints in Distributed
Data-intensive Computing Environments,” Information Sciences, vol. 192, pp.
228-243, Jun. 2012.
[21] M. Mirabi, “Ant Colony Optimization Technique for the Sequence-dependent
Flowshop Scheduling Problem,” International Journal of Advanced Manufacturing
Technology, vol. 55, no. 1-4, pp. 317-326, Jul. 2011.
[22] F.A. Omara and M.M. Arafa, “Genetic algorithms for task scheduling problem,”
Journal of Parallel and Distributed Computing, vol. 70, no. 1, pp. 13-22, Jan.
2010.
[23] C.H. Papadimitriou and M. Yannakakis, “Scheduling Interval-Ordered Tasks,”
SIAM Journal Computing, pp. 405-409, 1979.
[24] G. Park, B. Shirazi, and J. Marquis, “DFRN: A New Approach for Duplication
Based Scheduling for Distributed Memory Multiprocessor Systems,” Proc. Int’l
Conf. Parallel Processings, pp. 157-166, 1997.
[25] H.E. Rewini and T.G. Lewis, “Scheduling Parallel Program Tasks onto Arbitrary
Target Machines,” J. Parallel and Distributed Computing., vol. 9, pp. 138-153,
1990.
[26] H.E. Rewini, T. Lewis, and H. Ali, “Task Scheduling in Parallel and Distributed
Systems,” Prentice Hall., 1994.
[27] G.C. Sih and E.A. Lee, “A Compile-Time Scheduling Heuristic for
Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE
Trans. Parallel and Distributed Systems., vol. 4, no. 2, pp. 175-186, Feb. 1993.
[28] H. Topcuoglu, S. Hariri, and Min-You Wu, “Performance-effective and Lowcomplexity
Task Scheduling for Heterogeneous Computing,” IEEE Trans. on Parallel
and Distributed Systems, vol. 13, no. 3, pp. 260-274, Mar. 2002.
[29] J.D. Ullman, “NP-Complete Scheduling Problems,” Journal of Computer and
System Sciences, vol. 10, issue 3, pp. 384-393, Jun. 1975.
[30] M. Wu and D. Gajski, “Hypertool: A Programming Aid for Message Passing
Systems,” IEEE Trans. Parallel and Distributed Systems, vol. 1, issue 3, pp. 330-
343, Jul. 1990.
[31] A.S. Wu, H. Yu, S. Jin, K. Lin, and G. Schiavone, “An Incremental Genetic
Algorithm Approach to Multiprocessor Scheduling,” IEEE Trans. on Parallel and
Distributed Systems, vol. 15, no.9, pp. 824-834, 2004.
[32] Y. Wen, H. Xu, and Jiadong Yang, “A Heuristic-based Hybrid Genetic-variable
Neighborhood Search Algorithm for Task Scheduling in Heterogeneous Multiprocessor
System,” Information Sciences, vol. 181, no. 3, pp. 567-581, Feb. 2011.
[33] Q. Wu, and T. Wolf, “Runtime Task Allocation in Multicore Packet Processing
Systems,” IEEE Trans. on Parallel and Distributed Systems, vol. 23, no. 10, pp.
1934-1943, 2012.
[34] C. Yeh-Ching, and S. Ranka, “Applications and Performance Analysis of a
Compile-time Optimization Approach for List Scheduling Algorithms on Distributed
Memory Multiprocessors,” Proceedings of the 1992 ACM/IEEE Conference
on Supercomputing, Minneapolis, pp. 512-521, 1992.
[35] T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded
Number of Processors,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no.
9, pp. 951-967, Sept. 1994.
[36] H. Yu, “Optimizing Task Schedules using an Artificial Immune System Approach,”
Proceedings of the 10th Annual Conference on Genetic and Evolutionary
Computation., pp. 151-158, 2008.
[37] http://www.Kasahara.Elec.Waseda.ac.jp/schedule/.