以限制規劃法求解全年無休人員排班問題之研究─以護理人員排班為例

Abstract

隨著經濟發展，人力成本亦不斷提高。對於若干無法以科技自動化取代的全年無休服務業(如運輸、醫療等)而言，人員排班確是一項重要的課題。護理人員排班(Nurse Scheduling)為典型之24小時全年無休之範例，護理人員排班除須滿足勞基法(法律)、連續值班、包班、人員需求等(醫院)眾多硬性限制，並儘量滿足護理人員需求之軟性限制外，預先排班的特性更讓此問題的複雜度變得相當高，故此問題即被視為一高複雜度之組合搜尋問題。 護理人員排班問題，為求解滿足複雜限制之問題，其目標式並不明顯，特性較近似於限制滿足問題(CSP)，故本研究定義此問題為一限制滿足問題，利用限制規劃法求解，並以某署立醫院內科病房為個案病房。本研究之排班期為月，大於大部分以週或雙週為排班期之研究，並考慮多種排班情況，故其問題極為複雜。為有效求解此大規模排班問題，本研究將其分為兩階段求解，第一階段為「排休」模式，求解每位護理人員排班期之休假日期，並將休假結果匯入第二階段「派班」模式，求解整月護理人員值班班表。 本研究測試環境為Windows XP作業系統、1.8G Hz處理器速度，以ILOG OPL Studio 3.0軟體撰寫程式並求解個案三月至五月班表。測試結果每月可於15分鐘內求解完成，與實際班表比較，在兩週休假最少四天、010班別組合與包班之硬限制中，個案病房均有出現違反之情況，平均每月會出現11次違反次數，本研究則為全部符合；而在五項公平性指標分析中，個案病房平均全距最小為2天(休假天數)，但最大平均全距為9天(白班天數)，相較於本研究平均全距之結果，皆為1至2天，公平性結果亦優於實際班表。對於需反覆產生護理人員值班班表之排班者可提供一排班參考依據。

For most service industries, the crew scheduling or rostering is a major concern of the management because the increasing cost of service professionals. Nurse scheduling problem (NSP) is a typical case of year-round service crew scheduling problems. The scheduler not only has to provide a timetable or roster to satisfy all labor and the hospital regulations (hard constraints) but also needs to consider to fit individual preferences (soft constraints) as much as possible. Moreover, some nurse shift pre-assignments often reduce the choice for other unfilled slots. Thus the complicated NSP is considered as a combinatorial search problem. The character of NSP is like a constraint satisfaction problem (CSP). Thus, we formulate the NSP as a CSP, using constraint programming (CP) Model to solve the problem and conducted a case study of the medical ward in a general hospital, department of health. In order to solve the problem efficiently, we separate the NSP in two phases. The first phase is “Off-day Scheduling Problem”, which solve the off-day roster for each nurse. The second phase is “Shift Scheduling Problem”, which use the off-day roster result to solve the equitable roster. The CP models were implemented on a P4 1.8G Hz personal computer and used the ILOG OPL Studio 3.0 to solved our CP. The result of a full-month roster of case problem can be generated in 15 minutes. Compared with case rosters, and obtained very positive response. In addition to the roster schedule results, our model also provides as a reference for the scheduler.