雲端運算是一種新興的分散式運算系統，特色是可以透過付費租借的方式 取得大量的運算資源，並且可以隨時調整運算資源規模，隨著需求增減以控制 成本，擁有很高的使用彈性與可擴充性。雲端環境的工作流排程問題中，使用 者除了考慮如何讓工作流在期限內完成之外，在預算有限的情況下也須考量如 何最小化總租借成本。本研究求解考慮期限的工作流排程問題，並以最小化總 租借成本為目標。
工作流排程問題包含同一台機器上的任務要如何安排執行順序和要將任務 指派到哪一台機器，同時具有任務排列和機器配置兩個子問題。本論文提出的 解決方法為基因演算法配合經驗法則。基因演算法解決任務排列子問題，使用 向上等級初始化族群，讓產生初始排列時更有方向性;並對虛擬機新增規則之 省略機率進行自適應控制。經驗法則解決機器配置子問題，依照給定規則決定 使用的運算資源數量與類型，減少演算法的搜尋空間;新增虛擬機時考慮各種 類型的性價比，並且在新增虛擬機的規則中加入隨機性，緩解經驗法則可能誤 判所帶來的負面效果。實驗結果顯示與文獻中演算法相比能帶來較好的效果。

[1] P. Mell, and T. Grance, “The NIST Definition of Cloud Computing,” National Institute of Standards and Technology Special Publication 800-145, pp. 1–7, 2011.
[2] E. H. Housseina, A. G. Gadb, Y. M. Wazerya, and P. N. Suganthan, “Task Scheduling in Cloud Computing based on Meta-Heuristics: Review, Taxonomy, Open Challenges, and Future Trends,” Swarm and Evolutionary Computation, vol. 62, p. 100841, 2021.
[3] G. Juve, A. Chervenak, E. Deelman, S. Bharathi, G. Mehta, and K. Vahi, “Characterizing and Profiling Scientific Workflows,” Future Generation Computer Systems, vol. 29, no. 3, pp. 682–692, 2013.
[4] T. C. Chiang, and H. J. Lin, “Flexible Job Shop Scheduling using a Multiobjective Memetic Algorithm,” International Conference on Intelligent Computing, pp. 49–56, 2011.
[5] J. M. Framinan, P. Perez-Gonzalez, V. Fernandez-Viagas, “Deterministic Assembly Scheduling Problems: A Review and Classification of Concurrent-Type Scheduling Models and Solution Procedures,” European Journal of Operational Research, vol. 273, no. 2, pp. 401–417, 2019.
[6] Y. K. Kwok, and I. Ahmad, “Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors,” ACM Computing Surveys, vol. 31, no. 4, pp. 406– 471, 1999.
[7] H. Arabnejad, and J. G. Barbosa, “List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 3, 2014.
[8] G. C. Sih, and E. A. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures”, IEEE Transactions on Parallel and Distributed Systems, vol. 4, no. 2, pp. 175–186, 1993.
52
[9] 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, no. 3, pp. 260–274, 2002.
[10] H. Kanemitsu, M. Hanada, and H. Nakazato , “Clustering-Based Task Scheduling in a Large Number of Heterogeneous Processors,” IEEE Transactions on Parallel and Distributed Systems, vol. 27, no. 11, pp. 3144–3157, 2016.
[11] T. Yang, and A. Gerasoulis, “DSC : Scheduling Parallel Tasks on an Unbounded Number of Processors, ” IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 9, pp. 951–967, 1994.
[12] Y. Chung, and S. Ranka, “Applications and Performance Analysis of a Compile- Time Optimization Approach for List Scheduling Algorithms on Distributed Memory Multiprocessors,” ACM/IEEE Conference on Supercomputing, pp. 512–521, 1992.
[13] Y. K. Kwok, and I. Ahmad, “On Exploiting Task Duplication in Parallel Program Scheduling,” IEEE Transactions on Parallel and Distributed Systems, vol. 9, no. 9, pp. 872–892, 1998.
[14] 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, pp. 158–169, 2013.
[15] Q. Wu, F. Ishikawa, Q. Zhu, Y. Xia, and J. H. Wen, “Deadline-Constrained Cost Optimization Approaches for Workflow Scheduling in Clouds,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 12, pp. 3401–3412, 2017.
[16] J. Sahni, and D. P. Vidyarthi, “A Cost-Effective Deadline-Constrained Dynamic Scheduling Algorithm for Scientific Workflows in a Cloud Environment,” IEEE Transactions on Cloud Computing, vol. 6, no. 1, pp. 2–18, 2015.
[17] Z. G. Chen, K. J. Du, Z. H. Zhan, and J. Zhang, “Deadline Constrained Cloud Computing Resources Scheduling for Cost Optimization based on Dynamic Objective Genetic Algorithm,” IEEE Congress on Evolutionary Computation, pp. 708–714, 2015.
[18] Z. G. Chen, Z. H. Zhan, H. H. Li, K. J. Du, J. H. Zhong, Y. W. Foo, Y. Li, and J. Zhang, “Deadline Constrained Cloud Computing Resources Scheduling Through An Ant Colony System Approach,” International Conference on Cloud Computing Research and Innovation, pp. 112–119, 2015.
[19] H. H. Li, Y. W. Fu, Z. H. Zhan, and J. J. Li, “Renumber Strategy Enhanced Particle Swarm Optimization for Cloud Computing Resource Scheduling,” IEEE Congress on Evolutionary Computation, pp. 870–876, 2015.
[20] Z. J. Wang, Z. H. Zhan, W. J. Yu, Y. Lin, J. Zhang, T. L. Gu, and J. Zhang, “Dynamic Group Learning Distributed Particle Swarm Optimization for Large-Scale Optimization and Its Application in Cloud Workflow Scheduling,” IEEE Transactions on Cybernetics, vol. 50, no. 6, pp. 2715–2729, 2020.
[21] J. Yu, and R. Buyya, “Scheduling Scientific Workflow Applications with Deadline and Budget Constraints Using Genetic Algorithms,” Scientific Programming, vol. 14, no. 3, pp. 217–230, 2006.
[22] F. A. Omaraa, and M. M. Arafab, “Genetic Algorithms for Task Scheduling Problem,” Journal of Parallel and Distributed Computing, vol. 70, no. 1, pp. 13–22, 2010.
[23] M. A. Rodriguez, and R. Buyya, “Deadline Based Resource Provisioning and Scheduling Algorithm for Scientific Workflows on Clouds,” IEEE Transactions on Cloud Computing, vol. 2, no. 2, pp. 222–235, 2014.
[24] J. Meena, M. Kumar, and M. Vardhan, “Cost Effective Genetic Algorithm for Workflow Scheduling in Cloud Under Deadline Constraint,” IEEE Access, vol. 4, pp. 5065–5082, 2016.
[25] X. J. Ma, H. H. Gao, H. H. Xu, and M. J. Bian, “An IoT-based Task Scheduling Optimization Scheme Considering the Deadline and Cost-Aware Scientific Workflow for Cloud Computing,” EURASIP Journal on Wireless Communications and Networking, vol. 2019, no. 1, p. 249, 2019.
[26] Y. M. Xu , K. L. Li , J. T. Hu, and K. Q. Li, “A Genetic Algorithm for Task Scheduling on Heterogeneous Computing Systems Using Multiple Priority Queues,” Information Sciences, vol. 270, no. 6, pp. 255–287, 2014.
[27] Y. Wang, and X. Zuo, “A Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules,” IEEE/CAA Journal of Automatica Sinica, vol. 8, no. 5, pp. 1079–1094, 2021.