雲端運算是一種新興的分散式系統服務供應模式，隨著網際網路和周邊硬體設備不斷地演進，有愈來愈多的使用者將工作流程配置到雲端虛擬機器上執行，因此如何在滿足使用者最小化工作總執行時間和金錢成本的需求下將工作有效地排程已經成為一個很重要的議題。由於多核心架構的問題較符合實際情況，本論文探討了兩種實際的問題模型，分別為單核心模組和多核心模組。本論文以粒子群最佳化演算法為基礎，並透過新的粒子編碼形式和速度更新方式，來解決雲端運算工作排程問題所遇到的困難和預防原始演算法容易提早收斂的特性，以及加入有智慧的初始化機制和區域鄰居搜尋法來增強整個粒子群集的多樣性。最後本論文以Amazon EC2的服務規格定義系統環境和使用五種不同領域的工作流程圖來驗證本演算法的執行效能，並於實驗結果証實本研究方法在單核心模組中優於其他演算法且在多核心模組的問題上也能產生不錯的執行結果。

With the progress of Internet and improvement of hardware, there are more and more users rent virtual machines that are provided by a cloud provider to executing tasks, which usually are represented as a workflow. Cloud providers, such as Amazon and Google, offer several virtual machines of various types, allowing users to quickly scale compute capacity as computing requirements change. Therefore, in Cloud computing, efficient task allocation for optimizing the tradeoff of time and cost constraints has become an important and challenging issue. In this thesis, we propose a new algorithm, based on particle swarm optimization, to solve the workflow problem in Cloud. Our new local search mechanism can increase the diversity, and the updating strategy of inertia velocity can prevent premature convergence. Finally, our proposed algorithm is implemented and evaluated using a set of well-known applications on the realistic computing modules based on the service provided by Amazon EC2, included single-core and multi-core modules. The experimental results show that the proposed algorithm outperforms other popular algorithms in the single-core module, and deals with workflow scheduling for the multi-core module efficiently.

[1]Amazon Web Services: http://aws.amazon.com/ec2/.
[2]S. Abrishami, M. Naghibzadeh and D. H. J. Epema, “Deadline- constrained workflow scheduling algorithms for Infrastructure as a Service Clouds,” Future Generation Computer Systems, vol. 29, issue 1, pp. 158-169, Jan. 2013.
[3]S. Andey and L. Wu, “A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments,” IEEE International Conference on Advanced Information Networking and Applications, pp. 400-407, Apr. 2010.
[4]K. Bessai, S. Youcef, A. Oulamara, C. Godart and S. Nurcan, “Bi-criteria workflow tasks allocation and scheduling in Cloud computing environments,” IEEE International Conference on Cloud Computing (CLOUD), pp. 638-645, Jun. 2012.
[5]S. Bharathi, A. Chervenak, E. Deelman, G. Mehta, M. H. Su and K. Vahi, “Characterization of Scientific Workflows,” Third Workshop on IEEE workflows in Support of Large-Scale Science, pp. 1-10, Nov. 2008.
[6]L. F. Bittencourt and E. R. M. Madeira, “A performance-oriented adaptive scheduler for dependent tasks on grids,” Concurrency Computatation: Practice Experience, vol. 20, issue 9, pp. 1029-1049, Jun. 2008.
[7]L. F. Bittencourt, E. R. M. Madeira, “HCOC: a cost optimization algorithm for workflow scheduling in hybrid clouds,” Journal of Internet Services and Applications, vol. 2, issue 3, pp. 207-227, Dec. 2011.
[8]E. K. Byun, Y. S. Kee, J. S. Kim and S. Maeng, “Cost optimized provisioning of elastic resources for application workflows,” Future Generation Computer Systems, vol. 27, issue 8, pp. 1011-1026, Oct. 2011.
[9]S. Y. Chiu, T. Y. Sun, S. T. Hsieh and C. W. Lin, “Cross- Searching Strategy for Multi-objective Particle Swarm Optimization,” IEEE Congress on Evolutionary Computation, pp. 3135-3141, Sep. 2007.
[10]M. Daneshyari and G. G. Yen, “Cultural-Based Multi-objective Particle Swarm optimization,” IEEE Transaction on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 41, issue 2, pp. 553-567, Apr. 2011.
[11]K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ,” IEEE transactions on evolutionary computation, vol. 6, issue 2, pp. 182-197, Apr. 2002.
[12]J. J. Durillo, H. M. Fard and R. Prodan, “MOHEFT: A Multi-Objective List-based Method for Workflow Scheduling,” IEEE 4th International Conference on Cloud Computing Technology and Science, pp. 185- 192, Dec. 2012.
[13]R. C. Eberhart and Y. Shi, “Empirical study of particle swarm optimization,” Proceedings of the 1999 Congress on Proceedings of the 1999 Congress on, vol. 3, Jul. 1999.
[14]H. M. Fard, R. Prodan and T. Fahringer, “A Truthful Dynamic Workflow Scheduling Mechanism for Commercial Multi-Cloud Environments,” IEEE Trans. on Parallel and Distributed Systems, vol. 24, issue 6, pp. 1203- 1212, Jun. 2013.
[15]Google Compute Engine: https://cloud.google.com/pricing/compute-engine
[16]H. Gao and W. Xu, “Particle swarm algorithm with hybrid mutation strategy,” Applied Soft Computing, vol. 11, issue 8, pp. 5129-5142, Dec. 2011.
[17]M. R. Gary and D. S. Johnson, “Computrs and Intractability: A Guide to the Theory of NP-Completeness,” W.H. Freeman and Co., 1979.
[18]Y. S. Jiang, “Task Scheduling in Grid Computing Environments,” Department of Electronic and Computer Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan, Jun. 2013.
[19]J. Kennedy and R. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, Dec. 1995.
[20]A. Konaka, D. W. Coit, A. E. Smith, “Multi-objective optimization using genetic algorithms: A tutorial,” Reliability Engineering & System Safety, vol. 91, issue 9, pp. 992-1007, Sep. 2006.
[21]X. Li, “A Non-dominated Sorting Particle Swarm Optimizer for Multiobjective Optimization,” Genetic and Evolutionary Computation, vol. 2723, pp. 37-48, 2003.
[22]J. J. Liang and B. Y. Qu, “Dynamic Multi-Swarm Particle Swarm Optimization for Multi-Objective Optimization Problems,” IEEE World Congress on Computational Intelligence, pp. 1-8, Jun. 2012.
[23]H. Liu, L. Gao, Q. Pan, “A hybrid particle swarm optimization with estimation of distribution algorithm solving permutation flow-shop scheduling problem,” Expert Systems with Applications, vol. 38, issue 4, pp. 4348-4360, Apr. 2011.
[24]H. Liu, A. Abraham, V. Snasel and S. McLoone, “Swarm scheduling approaches for work-flow applications with security constraints in distributed data-intensive computing environments,” Information Science, vol. 192, pp. 228- 243, Jun. 2012.
[25]M. Malawski, G. Juve, E. Deelman and J. Nabrzyski, “Cost-and deadline-constrained provisioning for scientific workflow ensembles in IaaS clouds,” SC '12 Proceedings of the International Conference on High Performance Computing, Nov. 2012.
[26]M. Mao, M. Humphrey, “Auto-Scaling to Minimize Cost and Meet Application Deadlines in Cloud Workflows,” International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 1-12, Nov. 2011.
[27]G. Moslehi and M. Mahnam, “A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search,” International Journal of Production Economics, vol. 129, issue 1, pp. 14-22, Jan. 2011.
[28]S. Mostaghim and J. Teich, “Strategies for Finding Good Local Guides in Multi-objective Particle Swarm Optimization (MOPSO),” IEEE Swarm Intelligence Symposium, pp. 24-26, Apr. 2003.
[29]T. Murata and H. Ishibuchi, “MOGA: Multi-Objective Genetic Algorithms,” IEEE International Conference on Evolutionary Computation, vol. 1, pp. 289-194, Dec. 1995.
[30]N. Netjinda, B. Sirinaovakul and T. Achalakul, “Cost Optimization in Cloud Provisioning using Particle Swarm Optimization,” International Conference on Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), pp. 1-4, May. 2012.
[31]NIST, NIST Definitoon of cloud computing v15, NIST, Editor. 2009, National Institute of Standards and Technology: Gaithersburg, MD (2009).
[32]F. A. Omara, M. M. Arafa, “Genetic algorithms for task scheduling problem,” Journal of Parallel and Distributed Computing, vol. 70, issue 1, pp. 13-22, Jan. 2010.
[33]M. R. Palankar, A. Iamnitchi, M. Ripeanu and S. Garfinkel, “Amazon S3 for science grids: a viable solution?,” ACM Proceedings of the 2008 international workshop on Data-aware distributed computing, pp. 55-64, 2008.
[34]Q. K. Pan and L. Wang, “No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm,” The International Journal of Advanced Manufacturing Technology, vol. 39, issue 7-8, pp. 796-807, Nov. 2008.
[35]Y. Penga and B. L. Lu, “A Hierarchical Particle Swarm Optimizer with Latin Sampling Based Memetic Algorithm for Numerical Optimization,” Applied Soft Computing, vol. 13, issue 5, pp. 2823-2836, May. 2013.
[36]A. Ratnaweera, S. K. Halgamuge and H. C. Watson, “Self-Organizing Hierarchical Particle Swarm Optimizer With Time-Varying Acceleration Coefficients,” IEEE Trans. on Evolutionary Computation, vol. 8, issue 3, pp. 240-255, Jun. 2004.
[37]A. Salman and I. Ahmad, “Particle swarm optimization for task assignment problem,” Microprocessors and Microsystems, vol. 26, issue 8, pp. 363-371, Nov. 2002.
[38]Y. Shi and R. Eberhart, “A Modified Particle Swarm Optimizer,” IEEE International Conference on Computational Evolutionary Computation Proceedings, pp. 69-73, May. 1998.
[39]M. R. Sierra and C. A. Coello, “Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art,” International Journal of Computational Intelligence Research, vol. 2, pp. 287-308, 2006.
[40]S. Sua, J. Li, Q. Huang, X. Huang, K. Shuang and J. Wang, “Cost- Efficient Task Scheduling for Executing Large Programs in the Cloud,” Parallel Computing, vol. 39, issue 4-5, pp. 177-188, Apr. 2013.
[41]C. Szabo and T. Kroeger, “Evolving Multi-objective Strategies for Task Allocation of Scientific Workflows on Public Clouds,” IEEE World Congress on Evolutionary Computation, pp. 1-8, Jun. 2012.
[42]H. Topcuoglu, S. Hariri and M. Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, issue 3, pp. 260-274, Mar. 2002.
[43]P. K. Tripathi, S. Bandyopadhyay and S. K. Pal, “Multi- Objective Particle Swarm Optimization with time variant inertia and acceleration coefficients,” Information Sciences, vol. 177, issue 22, pp. 5033-5049, Nov. 2007.
[44]S. J. Tsai, T. Y. Sun, C. C. Liu, S. T. Hsieh, W. C. Wu and S. Y. Chiu, “An improved multi-objective particle swarm optimizer for multi-objective problems,” Expert Systems with Applications, vol. 37, issue 8, pp. 5872-5886, Aug. 2010.
[45]Y. Wang, B. Li, T. Weise, J. Wang, B. Yuan and Q. Tian, “Self-adaptive learning based particle swarm optimization,” Information Sciences, vol. 181, issue 20, pp. 4515-4538, Oct. 2011.
[46]H. Wang, H. Sun, C. Li, S. Rahnamayan and J. S. Pan, “Diversity enhanced particle swarm optimization with neighborhood search,” Information Sciences, vol. 223, pp. 119-135, Feb. 2013.
[47]X. Wang and L. Tang, “A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flow-shop problem with blocking,” Applied Soft Computing, vol. 12, issue 2, pp. 652-662, Feb. 2012.
[48]L. Wang, G. Zhou, T. Xu and M. Liu, “An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 60, issue 9-12, pp. 1111-1123, Jun. 2012.
[49]Y. Wen, H. Xu and J. Yang, “A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system,” Information Sciences, vol. 181, issue 3, pp. 567-581, Feb. 2011.
[50]Workflows: https://confluence.pegasus.isi.edu/display/pegasus/WorkflowGenerator.
[51]J. Yu, M. Kirley and R. Buyya, “Multi-objective Planning for workflow Execution on Grids,” ACM International Conference on Grid Computing, pp. 10-17, 2007.
[52]Y. Zhang and D. W. Gong, “Handling multi-objective optimization problems with a multi-swarm cooperative particle swarm optimizer,” Expert Systems with Applications, vol. 38, issue 11, pp. 13933-13941, Oct. 2011.
[53]H. Zhang and Heng Li, “Multi-objective particle swarm optimization for construction time-cost tradeoff problems,” Construction Management and Economics, vol. 28, issue 1, pp. 75-88, Feb. 2010.
[54]W. Zhang and Y. Liu, “Multi-objective reactive power and voltage control based on fuzzy optimization strategy and fuzzy adaptive particle swarm,” International Journal of Electrical Power & Energy Systems, vol. 30, issue 9, pp. 525-532, Nov. 2008.