人工蜂群演算法於工作流量排程問題之探討

Artificial Bee Colony Algorithm for Workflow Scheduling Optimization Problem

粘詠翔(Yung-Hsiang Nien)

指導教授 ： 梁韵嘉

元智大學/工程學院/工業工程與管理學系/碩士(2013年)

https://doi.org/10.6838/YZU.2013.00012

摘要

雲端運算是一種透過網際網路的方式來提供運算資源給予使用者，並且處理使用者所傳遞的需求之服務。近年來，隨著資訊科技產品的快速發展，愈來愈多的使用者應用雲端服務，導致需求量大幅提升；此外，不少的複雜工作係以工作流量（workflow）的概念，在雲端環境下執行。因此，當雲端服務提供者面對龐大的需求時，如何編排工作流量之最佳執行順序，以縮短回應時間已成為目前相當重要的議題。本研究首先針對工作流量之排程問題，結合專案排程之概念，以總完工時間最小化為目標提出一數學模型，並且利用線性混合整數優化軟體Gurobi來驗證合理性以及求出最佳解；之後則應用人工蜂群（Artificial Bee Colony；ABC）演算法求出工作流量之最佳排程，並且為了提高演算法的求解速度與品質，本研究針對人工蜂群演算法及求解問題之特性提出十種不同的演算架構，以及利用收斂性分析以觀察不同演算架構之間的收斂與求解表現。最後，將各演算架構求解十題大小不一測試例題之實驗結果與Gurobi所求得之最佳解相比，實驗分析結果說明使用本研究中所提出的改良式資訊交換機制之ABC_Ⅵ演算法可獲得良好的求解品質，而混合改良式資訊交換機制與區域搜尋法的ABC_Ⅸ演算法和混合改良式資訊交換機制與門檻接受法的ABC_Ⅹ演算法則具有良好的求解效果，且足以大幅降低Gurobi最佳化軟體之求解時間，為複雜的工作流量排程問題提供了一個實用之求解方法。

關鍵字

雲端運算 ； 工作流量排程 ； 人工蜂群演算法

並列摘要

Cloud computing is the provision of computing resource services from which users can obtain resources via network to tackle their demands. In recent years, with fast growing information technology, more users apply this service; as a result, the demand has increased dramatically. In addition, most of the complex tasks are represented by workflow and executed in the cloud. Therefore, as service providers face this increasing demand, how to schedule the workflow and reduce the response time becomes more and more important. First, this research integrates the concept of project scheduling with the workflow scheduling problem and presents a mathematical model, which expects to minimize the total completion time. Moreover, the feasibility and optimal solution of this model is obtained by Gurobi optimizer. This study adopts Artificial Bee Colony algorithm to solve workflow scheduling optimization problem, and to increase the speed and quality of the proposed algorithm, ten variations of the ABC algorithm are proposed. Furthermore, this research analyzes the convergence behavior for each variation of ABC to observe their solving performance. Finally, these ten variations of ABC are used to solve ten test instances with different sizes and use these results to compare with the optimal solutions which are obtained from Gurobi optimizer. The experimental results show that the ABC_VI, which including a revised information exchange mechanism proposed in this study, has good solution quality; on the other hand, ABC_IX and ABC_X, which mix the revised information exchange mechanism with local search and threshold accepting respectively, perform better in terms of effectiveness and reduce the CPU time of Gurobi optimizer significantly. As a result, ABC_VI, ABC_IX and ABC_X can provide a practical method for complicated workflow scheduling problems.

並列關鍵字

Cloud computing ； Workflow scheduling ； Artificial Bee Colony

參考文獻

劉佳倩，人工蜂群演算法於投資組合最佳化問題之應用，元智大學工業工程與管理研究所，碩士論文，2011。

王苡宸，資源限制下比例式非等效平行機臺排程問題之研究，元智大學工業工程與管理研究所，碩士論文，2008。

徐烈昭，應用塔布搜尋法於非等效平行機臺之研究-以PCB鑽孔作業為例，元智大學工業工程與管理研究所，碩士論文，2001。

高文慶，螞蟻演算法於有限資源專案排程最佳化之研究，元智大學工業工程與管理研究所，碩士論文，2004。

Pandey S., A. Barker, K. K. Gupta and R. Buyya, Minimizing Execution Costs when using Global Distributed Cloud Services, Proceedings of IEEE International Conference on Advanced Information Networking and Applications, pp. 222-229, 2010.