建構啟發式演算法求解有軟硬限制之最佳化問題：以醫護人員排班問題為例

Developing a heuristic algorithm to solve optimization problems with soft-and-hard constraints: An application on medical staff scheduling problems

曾智揚(Zhi-Yang Zeng)

指導教授 ： 陳平舜

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2017年)

https://doi.org/10.6840/cycu201700410

摘要

本研究針對有軟硬限制之最佳化問題發展一啟發式演算法，以改善其收斂解的品質及縮短演算法搜尋時間。本研究針對隨機初始解加以改善，利用決策樹分析題目軟硬限制式資訊，以縮短產生可行初始解之時間。再者，本研究新增鄰域搜尋概念，根據題目軟硬限制式資訊，設計一區域(貪婪)搜尋法，以獲較佳之近似最佳解和縮短其啟發式演算法之收斂時間。
為驗證本研究所發展的啟發式演算法觀念之可行性，本研究以醫護人員排班問題為例，透過兩組醫護人員的人力分配下，測試所發展的啟發式演算法結合粒子群演算法或結合蝙蝠演算法其近似最佳解之品質和求解時間之長短。其數值結果顯示本研究提出之啟發式演算法在結合蝙蝠演算法和結合粒子群演算法均快速產生不錯的初始解，且區域(貪婪)搜尋法在結合蝙蝠演算法和結合粒子群演算法均有效產生更佳的近似最佳解。

關鍵字

有軟硬限制之最佳化問題 ； 醫護人員排班、啟發式演算法、粒子群演算法 ； 蝙蝠演算法 ； 初始解 ； 區域搜尋法

並列摘要

This research developed a heuristic algorithm to solve the optimization problems with soft-and-hard constraints in order to improve the solution quality and reduce the solution time. This study combined the information of soft and hard constraints with the decision tree method to generate an initial feasible solution, thereby reducing the generated initial feasible solution’s time. Furthermore, this study applied the local search concept and the information of soft and hard constraints to develop a new local search (greedy) method in order to obtain the better near-optimal solution and reduce the solution time.
In order to verify the feasibility of the proposed heuristic algorithm, this research used a radiologist scheduling problem as a case study. Through two numerical sets of different numbers of radiologists, this research tested the solution quality and solution time of two scenarios: the proposed heuristic algorithm with the particle swarm optimization (PSO) and the proposed heuristic algorithm with the bat algorithm (BA). The results showed that, for generating an initial solution, both PSO and BA methods with the designed initial solution mechanism could have better performance on solution time than both PSO and BA methods without the designed initial solution mechanism, and that for generating a local search, both PSO and BA methods with the greedy search could have better performance on solution quality than both PSO and BA methods without the greedy search.

並列關鍵字

Optimization problems with soft-and-hard constraints ； Medical staff scheduling ； heuristic algorithm ； particle swarm optimization ； bat algorithm ； initial solution ； local search

參考文獻

江宗恒，運用啟發式演算法解跨醫院人力配置排班問題，中原大學工業與系統工程學系碩士論文，2013。

彭迺淳，模組化建構多班別之學校排課問題，中原大學工業與系統工程學系碩士論文，2016。

蔡嘉哲，運用萬用啟發式演算法解醫護人員排班問題，中原大學工業與系統工程學系碩士論文，2015。

Alvarez-Valdes, R., Tamarit, J. M., & Villa, F. (2015). Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics. Computers & Operations Research, 54, 1-11.

Chen, P. S., Lin, Y. J., & Peng, N. C. (2016). A two-stage method to determine the allocation and scheduling of medical staff in uncertain environments. Computers & Industrial Engineering, 99, 174-188.