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

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

10.6840/cycu201700410

曾智揚

有軟硬限制之最佳化問題 ； 醫護人員排班、啟發式演算法、粒子群演算法 ； 蝙蝠演算法 ； 初始解 ； 區域搜尋法 ； Optimization problems with soft-and-hard constraints ； Medical staff scheduling ； heuristic algorithm ； particle swarm optimization ； bat algorithm ； initial solution ； local search

中原大學工業與系統工程學系學位論文

2017年

碩士

陳平舜

繁體中文

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

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.

1. 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.
   連結：
2. 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.
   連結：
3. Eusuff, M., Lansey, K., & Pasha, F. (2006). Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization. Engineering Optimization, 38(2), 129.
   連結：
4. Fraser, A. S. (1957). Simulation of genetic systems by automatic digital computers. Australian Journal of Biological Sciences, 10, 484-491.
   連結：
5. Glover, F. (1986). Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research, 13(5), 533-549.
   連結：
6. Jans, R., & Degraeve, Z. (2007). Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches. European Journal of Operational Research, 177(3), 1855-1875.
   連結：
7. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220, 671-680.
   連結：
8. Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261-293.
   連結：
9. Shirazi, B., Fazlollahtabar, H., & Sahebjamnia, N. (2010). Minimizing arbitrary earliness/tardiness penalties with common due date in single-machine scheduling problem using a tabu-geno-simulated annealing. Materials and Manufacturing Processes, 25(6), 515-525.
   連結：
10. Tassopoulos, I. X., & Beligiannis, G. N. (2012). A hybrid particle swarm optimization based algorithm for high school timetabling problems. Applied Soft Computing, 12(11), 3472-3489.
    連結：
11. Tassopoulos, I. X., Solos, I. P., & Beligiannis, G. N. (2015). A two-phase adaptive variable neighborhood approach for nurse rostering. Computers & Operations Research, 60, 150-169.
    連結：
12. Todorovic, N., & Petrovic, S. (2013). Bee colony optimization algorithm for nurse rostering. IEEE Transactions on Systems Man Cybernetics-Systems, 43(2), 467-473.
    連結：
13. Valente, J. M. S., Moreira, M. R. A., Singh, A., & Alves, R. A. F. S. (2011). Genetic algorithms for single machine scheduling with quadratic earliness and tardiness costs. International Journal of Advanced Manufacturing Technology, 54(1-4), 251-265.
    連結：
14. Wang, I. L., Wang, Y. C., & Chen, C. W. (2013). Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics. Flexible Services and Manufacturing Journal, 25(3), 343-366.
    連結：
15. Wong, T. C., Xu, M., & Chin, K. S. (2014). A two-stage heuristic approach for nurse scheduling problem: A case study in an emergency department. Computers & Operations Research, 51, 99-110.
    連結：
16. Wright, P. D., & Mahar, S. (2013). Centralized nurse scheduling to simultaneously improve schedule cost and nurse satisfaction. Omega-International Journal of Management Science, 41(6), 1042-1052.
    連結：
17. Wu, T. H., Yeh, J. Y., & Lee, Y. M. (2015). A particle swarm optimization approach with refinement procedure for nurse rostering problem. Computers & Operations Research, 54, 52-63.
    連結：
18. Yang, X. S. (2009). Cuckoo search via Lévy flights. World Congress on Nature & Biologically Inspired Computing, 210-214.
    連結：
19. 江宗恒，運用啟發式演算法解跨醫院人力配置排班問題，中原大學工業與系統工程學系碩士論文，2013。
    連結：
20. 彭迺淳，模組化建構多班別之學校排課問題，中原大學工業與系統工程學系碩士論文，2016。
    連結：
21. 蔡嘉哲，運用萬用啟發式演算法解醫護人員排班問題，中原大學工業與系統工程學系碩士論文，2015。
    連結：
22. Beheshti, Z., & Shamsuddin, S. M. H. (2013). A review of population-based meta-heuristic algorithm. International Journal of Advances in Soft Computing and its Applications, 5(1), ISSN 2074-8523.
23. Colorni, A., Dorigo, M., & Maniezzo, V. (1991). Distributed optimization by ant colonies. Proceedings of the 1st European Conference on Artificial Life, 134-142.
24. Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department
25. Yang, X. S. (2010). A new metaheuristic bat-inspired algorithm. Nature Inspired Cooperative Strategies for Optimization, 284, 65-74.
26. 林達偉，人力指派最佳化模式之研究-以軍事院校排課系統為例，崑山科技大學資訊管理研究所碩士論文，2015。
27. 陳思銘，啟發式演算法於大學排課之研究，國防大學管理學院運籌管理學系碩士論文，2012。