簡易檢索 / 詳目顯示

研究生: 吳培弘
Wu, Pei-Hong
論文名稱: 以基因演算法求解在雲端環境下具時間限制之工作流排程成本最佳化問題
A Genetic Algorithm for Deadline-Constrained Workflow Scheduling in Clouds
指導教授: 蔣宗哲
Chiang, Tsung-Che
口試委員: 丁川康 陳穎平 蔣宗哲
口試日期: 2021/07/27
學位類別: 碩士
Master
系所名稱: 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年: 2021
畢業學年度: 109
語文別: 中文
論文頁數: 54
中文關鍵詞: 基因演算法機器配置經驗法則工作流排程成本最佳化問題自適應控制
DOI URL: http://doi.org/10.6345/NTNU202101311
論文種類: 學術論文
相關次數: 點閱:88下載:8
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 雲端運算是一種新興的分散式運算系統,特色是可以透過付費租借的方式 取得大量的運算資源,並且可以隨時調整運算資源規模,隨著需求增減以控制 成本,擁有很高的使用彈性與可擴充性。雲端環境的工作流排程問題中,使用 者除了考慮如何讓工作流在期限內完成之外,在預算有限的情況下也須考量如 何最小化總租借成本。本研究求解考慮期限的工作流排程問題,並以最小化總 租借成本為目標。
    工作流排程問題包含同一台機器上的任務要如何安排執行順序和要將任務 指派到哪一台機器,同時具有任務排列和機器配置兩個子問題。本論文提出的 解決方法為基因演算法配合經驗法則。基因演算法解決任務排列子問題,使用 向上等級初始化族群,讓產生初始排列時更有方向性;並對虛擬機新增規則之 省略機率進行自適應控制。經驗法則解決機器配置子問題,依照給定規則決定 使用的運算資源數量與類型,減少演算法的搜尋空間;新增虛擬機時考慮各種 類型的性價比,並且在新增虛擬機的規則中加入隨機性,緩解經驗法則可能誤 判所帶來的負面效果。實驗結果顯示與文獻中演算法相比能帶來較好的效果。

    第一章 緒論 1 1.1 研究背景 1 1.2 工作流排程問題 2 1.3 問題定義 3 1.4 數學模型 5 1.5 相似問題類型 7 1.6 論文架構 8 第二章 文獻探討 9 2.1 任務排序經驗法則 9 2.1.1 等級排序法 10 2.1.2 插入法 11 2.1.3 最短時間法 11 2.2 機器配置經驗法則 12 2.2.1 有限運算資源 12 2.2.2 無限運算資源 13 2.3 啟發式演算法 15 2.3.1 有限運算資源 15 2.3.2 無限運算資源 16 2.4 混合方法 17 第三章 工作流排程基因演算法 19 3.1 基因演算法 19 3.2 編碼方式 21 3.3 族群初始化 21 3.4 親代選擇與環境選擇 22 3.5 交配方式 22 3.6 突變方式 24 3.7 機器配置經驗法則 25 第四章 實驗結果與分析 28 4.1 測試資料集 28 4.2 實驗設定 29 4.3 演算法參數設定 30 4.4 任務排序方法比較 31 4.5 性價比新增虛擬機規則 32 4.6 加入省略機率 SR 之影響 35 4.7 省略機率 SR 自適應參數控制 40 4.8 與文獻中演算法比較 43 第五章 結論與未來研究方向 51 參考文獻 52

    [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.

    下載圖示
    QR CODE