護士排班問題
護士排班問題（英語：nurse rostering problem，NRP）也被稱為護士排程問題（英語：nurse scheduling problem，NSP），是為運籌學領域的問題，旨在為醫院護理人員找到最佳排班方式。此類問題通常具有一組必須要遵守的硬性約束條件，以及一組彈性約束條件，旨在確保排班的質素。[1]此類排程問題也可以用於研究其他類別的排程問題。[2][3]
儘管早在20世紀50年代人們就開始藉助電腦來給護士排班[4]，但現今的護士排班問題是在1976年兩份同期出版的期刊中所提出的。[5][6]顯而易見的是，此類問題為NP困難問題。[1]
問題描述
護士排班問題涉及護士輪班以及假期的分配，每個護士都有自己的需求和條件，醫院亦是如此。因此需要排出一個輪班表，既能保障護士的權益，又能符合醫院的需要。在傳統的護士排班問題上，分為早班、夜班以及深夜班。[1]
約束條件
此類問題的約束條件分為兩類，其中一類為硬性約束條件，一旦排定的輪班表違反了這些條件，其結果便完全不能採用。另一種條件是彈性條件，最好滿足，但即使不滿足也不是問題。硬性約束通常包括輪班規範（例如時間段要求）、每個護士每天的工作時間不得超過一個輪班，以及所有患者都應享受到醫療服務。[1]而不同護士之間的資歷差異也有可能構成硬性約束條件。[7]彈性約束條件可能包括一周內分配給特定護士的最少和最大輪班數、每周工作時間、連續工作天數、連續休息天數等。[1]個別護士的輪班偏好可以成為彈性約束條件[8]，但也有可能成為硬性約束條件。[9]
求解方式
此類問題的求解運用了多種求解方式，包括數學上精確的求解方案[10]和使用分解方法的各種啟發式演算法、平行計算[10][11]、隨機最佳化[1]、遺傳演算法[8]、蟻群演算法[8]、模擬退火[8]、量子退火[12]、禁忌搜尋[8]以及坐標下降法。[11][13]
伯克等人於2004年總結了護士排班問題的學術研究現狀，其中包括對當時已發表的各種解決方案進行了簡要介紹。[14]
參考文獻
- ^ 1.0 1.1 1.2 1.3 1.4 1.5
Solos, Ioannis; Tassopoulos, Ioannis; Beligiannis, Grigorios. A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem. Algorithms. 2013-05-21, 6 (2): 278–308. doi:10.3390/a6020278
.
- ^
Aickelin, Uwe; Dowsland, Kathryn A. An Indirect Genetic Algorithm for a Nurse Scheduling Problem. Computers & Operations Research. 2004, 31 (5): 761–778. S2CID 8772185. arXiv:0803.2969 . doi:10.1016/s0305-0548(03)00034-0.
- ^ Beddoe, Gareth; Petrovic, Sanja. A novel approach to finding feasible solutions to personnel rostering problems (PDF). Savannah, Georgia: Proceedings of the 14th Annual Conference of the Production and Operation Management Society: 1–13. 2003 [2014-03-20]. （原始內容存檔 (PDF)於2017-08-29）.
- ^ Bailey, Norman T. J. Statistics in Hospital Planning and Design. Journal of the Royal Statistical Society Series C: Applied Statistics (Oxford University Press). 1956, 5 (3): 146–157 [2023-12-14]. doi:10.2307/2985416. （原始內容存檔於2023-12-14）.
- ^ Miller, Holmes E.; Pierskalla, William P.; Rath, Gustave J. Nurse Scheduling Using Mathematical Programming. Operations Research (INFORMS). 1976, 24 (5): 857–870 [2023-12-14]. doi:10.1287/opre.24.5.857. （原始內容存檔於2023-12-14）.
- ^ Warner, D. Michael. Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach. Operations Research (INFORMS). 1976, 24 (5): 842–856 [2023-12-14]. doi:10.1287/opre.24.5.842. （原始內容存檔於2023-12-14）.
- ^
Aickelin, Uwe; White, Paul. Building Better Nurse Scheduling Algorithms. Annals of Operations Research. 2004, 128 (1–4): 159–177. S2CID 14983974. arXiv:0803.2967 . doi:10.1023/b:anor.0000019103.31340.a6.
- ^ 8.0 8.1 8.2 8.3 8.4 Goodman, Melissa D.; Dowsland, Kathryn A.; Thompson, Jonathan M. A grasp-knapsack hybrid for a nurse-scheduling problem (PDF). Journal of Heuristics (Springer). 2007, 15 (4): 351–379 [2020-06-20]. S2CID 8784023. doi:10.1007/s10732-007-9066-7.
- ^ Winstanley, Graham. A hybrid approach to staff scheduling: The Staff Work Allocation Tool (SWAT) (PDF). Brighton: University of Brighton School of Computing, Engineering and Mathematics: 1–12. [2014-03-20]. （原始內容 (PDF)存檔於2014-03-20）.
- ^ 10.0 10.1 Lagatie, Ruben; Haspeslagh, Stefaan; De Causmaecker, Patrick. Negotiation Protocols for Distributed Nurse Rostering (PDF). Eindhoven University of Technology Department of Computer Science. 2009 [2014-02-14]. （原始內容 (PDF)存檔於2016-03-04）.
- ^ 11.0 11.1 Bäumelt, Zdeněk; Dvořák, Jan; Šůcha, Přemysl; Hanzálek, Zdeněk. A Novel Approach for Nurse Rerostering based on a Parallel Algorithm. European Journal of Operational Research (Elsevier). 2016, 251 (2): 624–639. doi:10.1016/j.ejor.2015.11.022.
- ^ Humble, Travis S.; Nakamura, Yuma; Ikeda, Kazuki. Application of Quantum Annealing to Nurse Scheduling Problem. Scientific Reports. 2019-04-27, 9 (1): 12837. Bibcode:2019NatSR...912837I. PMC 6731278 . PMID 31492936. arXiv:1904.12139 . doi:10.1038/s41598-019-49172-3 （英語）.
- ^ Augustine, Lizzy; Faer, Morgan; Kavountzis, Andreas; Patel, Reema. A Brief Study of the Nurse Scheduling Problem (NSP) (PDF). Pittsburgh: Carnegie Mellon School of Computer Science: 1–11. 2009-12-15 [2014-03-20]. （原始內容存檔 (PDF)於2022-03-26）.
- ^ Burke, Edmund; De Causmaecker, Patrick; Berghe, Greet Vanden; Van Landeghem, Hendrik. The state of the art of nurse rostering. Journal of Scheduling. 2004, 7 (6): 441–499 [2016-01-10]. S2CID 10537343. doi:10.1023/B:JOSH.0000046076.75950.0b. （原始內容存檔於2016-03-04）.
