兩階段限制規劃模式求解護理人員輪值問題

Nurse Rostering Using Two-Phased Constraint Programming Models

韓復華(Anthony F. Han) ； 李俊德(Chun-Te Li)

《管理與系統》 14卷1期 (2007/01) Pp. 121-146

摘要

護理人員每月輪值排班的決策是目前醫院均面臨的重要問題之一，輪值班表結果之良窳攸關護理服務的品質與人員工作的士氣。護理人員的輪值(Rostering)決策是屬於NP-hard的高複雜度問題，傳統有關護理人員輪值問題的研究，大都把問題定式為一個最佳化的模式(Optimization Model)來求解。但實際上護理人員的輪值問題，除了要滿足有關各種法律與醫院等「哽限制」條件外，亦需儘量滿足員工個人偏好等「軟限制」條件。因此，本研究將護理人員輪值視為限制滿足問題(Constraint Satisfaction Problem)，並建立「排休」與「派班」兩階段限制規劃(Constraint Programming)模式依序求解；並以署立新竹醫院某內科病房為個案，於個人電腦上執行求解20位護理人員與6種班別之月班表。與實際班表比較發現，本研究結果在求解效率與限制滿足程度兩方面均有優越之處，顯示本文建立之限制規劃模式具實際應用價值。

關鍵字

護理人員輪值 ； 限制滿足問題 ； 限制規劃法

並列摘要

Nurse rostering is a NP-hard problem because of the very complicated hospital constraints and nurse preferences involved in the problem. In this paper, we formulated the problem as a CSP (Constraint Satisfaction Problem) and developed CP (Constraint Programming) models to solve it. A two-phase heuristic approach is proposed to first solve the offday scheduling and then the shift scheduling sequentially. We applied our models to a real-world medical ward in Hisnchu General Hospital, and successfully generated a full-month timetable in less than 10 minutes. It is found our results are better than the timetables previously used by the hospital in many ways. CP-generated timetables not only can fully satisfy all the hard constraints, but also provide excellent fairness among nurses.

並列關鍵字

Nurse Rostering ； Constraint Satisfaction Problem ； Constraint Programming

參考文獻

Soft Constraints in The Nurse Rostering Problem, Full description of all the constraint types in use in Plane System

Aickelin, U.,Dowsland, K.(2001).Exploiting Problem Structure in A Genetic Algorithm Approach to A Nurse Rostering Problem.Journal of Scheduling.3(3),139-153.

Berrada, I.,Ferland, J. A.,Michelon, P.(1996).A Multi-Objective Approach to Nurse Scheduling with Both Hard and Soft Constraints.Socio-Economic Planning Science.30,183-193.

Cheang, B.,Li, H.,Lim, A.(2003).Nurse Rostering Problems-a Bibliographic Survey.European Journal of Operational Research.151,447-460.

Cheng, B. M. W.,Lee, J. H. M.,Wu , J. C. K.(1997).A nurse Rostering System Using Constraint Programming and Redundant Modeling.IEEE Transactions in Information Technology in Biomedicine.1,44-54.