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