基於雲端具有回饋機制之模組化混合型基因演算法解決NSP最佳化排程問題

本文在護士調度問題（NSP）NP-完整格局基於雲端混合遺傳進化演算法的計算軟件即服務（SCaaS）。由於低出生率，人力資源成為限制工作分配的資源。要查找調度人員的最佳解決方案成為一個重要問題。本文所提出的系統遵循NSP的定義和識別NP完全格局。將格局識別為NSP優化問題，所提出的系統可以找到最優解。然後，在進化步驟不同類型進化算法的集合。基於提出的反饋援助法，進化算法的進化適宜步驟可以動態地決定和執行。相似於TaskTracker和JobTracker的雲端運算，所有的計算負載可以被劃分和分佈。仿真結果表明，所提出的混合進化算法可以找到最佳解決方案並減少約50％演化世代。

關鍵字

基因演算法；護理人員調度問題；雲端運算；回饋幫助；混合；模組化

並列摘要

In this thesis, the Cloud based Hybrid evolution algorithm for NP-Complete Pattern in Nurse Scheduling Problem (NSP) is proposed as the Software Computing as a Service (SCaaS). Due to the low birth rate, the human resource becomes the limited resource for job assignment. To find the optimal solution for staff scheduling becomes an important issue. The proposed system follows the definition of NSP and recognizes the possible problem of NP-Complete Pattern. Only the pattern is recognized as the NSP optimal problem, the proposed system can find the optimal solution. Then, the different types of evolutionary algorithm in evolution steps are integrated. Based on the proposed Feedback Assistance method, the suitable evolution steps of the evolutionary algorithm can be dynamically decided and executed. Similar to the Tasktracker and Jobtracker in cloud, all the computing load can be divided and distributed. The simulation results show that the proposed hybrid evolution algorithm can find the optimal solution with about 50% less evolution generations.

並列關鍵字

Evolution (Genetic) Algorithm ； Nurse Scheduling Problems ； Cloud ； Feedback ； Hybrid ； Modular ； NP-Complete

參考文獻

[1] M. Ohki and S. Kishida,“A parameter free algorithm of cooperative genetic algorithm for nurse scheduling problem,”2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI), pp.1201-1206, Aug 2013.

[2] M. Ohki and H. Kinjo, “PenaltyWeight Adjustment in Cooperative GA for Nurse Scheduling,”2011 Third World Congress on Nature and Biologically Inspired Computing (NaBIC), pp.75-80, Oct 2011.

[3] R.A. Abobaker, M. Ayob and M. Hadwan, “Greedy constructive heuristic and local search algorithm for solving Nurse Rostering Problems,”2011 3rd Conference on Data Mining and Optimization (DMO), pp.194-198, Jun 2011.

[4] C. Mueller,“Multi-objective optimization of Software Architectures using Ant Colony Optimization,” Lecture Notes on Software Engineering, Vol.2, No.4,pp.371-374, November 2014

[5] S. Kim, Y. Ko, S. Uhmn and J. Kim, “A Strategy to Improve Performance of Genetic Algorithm for Nurse Scheduling Problem,” International Journal of Software Engineering and Its Applications, Vol.8, No.1, pp.1-7, Jan 2014

國際替代計量

基於雲端具有回饋機制之模組化混合型基因演算法解決NSP最佳化排程問題

未授權

主題瀏覽