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