中华大学生物资讯学系专题报告

中華大學生物資訊學系專題報告護理人員排班程式設計與實作Nurserosteringprogramsdesignandimplementation專題組員:洪翊豪、張鈺生、周育生、張治倫專題編號：PROJ2008-BIOINFO-9403指導老師:侯玉松老師一、摘要護理人員排班是每位護理長每月需面臨的問題，輪值班表的好壞，影響護理服務的品質與人員工作的士氣。因此，設計護理人員排班軟體是相當實用與重要的課題，實作電腦軟體，產生有效率與限制滿足程度高之護理人員排班表，此即本專題之目的。文獻顯示，護理人員排班問題是NP-hard的難題，至今尚未發展出快速的演算法，可以得到最佳的排班結果。在本專題中，我們希望運用回溯法與分而治之法等演算法設計技巧，結合國內外相關文獻優點，實作護理人員排班程式，再以彰化基督教醫院的實際資料做測試，快速得到排班良好可行解，減輕護理長的工作負擔，提升護理人員工作士氣。關鍵字：護理人員排班、演算法、回溯法、分而治之法二、簡介(一)專題研究背景護理人員排班是每位護理長每月需面臨的問題，據彰化基督教醫院(簡稱「彰基」)曾麗卿護理長的觀察，護理長需耗時半日至二日，才能完成一份輪值班表，而且輪值班表結果的好壞，攸關護理服務的品質與人員工作的士氣。因此，設計與實作護理人員排班軟體是相當實用與重要的課題，如何設計完成電腦軟體，構建有效率與限制滿足程度高之護理人員排班表，此即本專題之目的。從1976年開始，Miller[16]即已經研究護理人員排班問題。經資訊學者研究證明[9、17]，護理人員排班問題是NP-hard的難題，所以護理人員排班困擾許多護理長，至今也尚未發展出快速的演算法，可以得到最佳的排班結果。早期在求解護理人員排班問題，多為設計最佳化演算法[4-5、7、13、15-16]，但是程式的執行效率不佳，非常耗時。爲加快求解效率，近來求解此問題則為設計適合的啟發式演算法(HeuristicAlgorithm)，求其次佳解，來增加求解效率[1、6、9、10]。最新的國內相關文獻為交通大學運輸科技與管理學系韓復華教授所著[8]，該論文採用二階段整數規劃的方法，解決護理人員排班問題。但是從論文的測試結果來看，20名護士的排班，在二階段分別需先產生3520、4660個變數與5592、4939個限制式，才能使用ILOGOPLStudio軟體，解出其整數規劃式的答案。對護理長而言，要學習如何產生8000多個變數、10000多個限制式，還要學習數學規劃軟體，而且醫院還要購買ILOGOPLStudio軟體，就實務層面來看，是行不通的。為研究護理人員排班問題，我們曾與彰基曾麗卿與相青琪護理長，進行多次溝通，瞭解人工排班的方法，希望能設計護理人員排班軟體，以更有效率的方式產生排班表，降低護理長的工作負擔，並達到彰基護理人員的需求。(二)專題目的護理人員排班問題是在人力與法規限制下，決定每月護理人員排班表，並儘量滿足護理人員的期望。以97年十月彰基第二呼吸照護中心為例，該月中心有23名護士，每位護士在九月先填寫約班期望，綜合為約班表，部分約班表如表一。表一約班表顯示王素娥在7月1日要做JCI/PMR，7月5日期望上白天班(約D)，7月6日期望休假(約R)，餘類推。在約班表左邊會顯示「包班」資訊，例如：王素娥期望本月不要排小夜班(不上E)、洪湘縈期望不要排大夜班(不上N)等等。表一：97年7月第二呼吸照護中心部分護理人員約班表。護理長根據約班表，製作排班表。表二為97年7月第二呼吸照護中心部分排班表，為滿足護理人員的期望，王素娥在7月1日排休假(R)，以方便做JCI/PMR，7月5、6日則依其約班，分別排給白天班(D)、休假(R)。因為洪湘縈期望不要排大夜班，所以表二顯示其1-6日排班為RREEEE，未排大夜班(N)。表二：97年7月第二呼吸照護中心部分護理人員排班表。在排班時，除了要盡量滿足護理人員需求之外，還須遵守相關規定限制，經彰基多位護理長所給的資訊後，歸納出下列排班規定必須遵守：（1）上班天數不可連續超過7天（＜7天），後面一定要休假。（2）大夜隔天不可以接白班，（3）大夜隔天不可以接小夜（4）小夜隔天不可以接白班。（5）每天每個人只能上一種班。（6）強制要求每個班level3一定要有一個人上班。（7）須滿足每日白班（D）護理人員需求數。（8）須滿足每日小夜班（E）護理人員需求數。（9）須滿足每日大夜班（N）護理人員需求數。除了上述護理人員個人需求與排班規定之外，彰基多位護理長還歸納下列護理人員的一般需求，排班時也需盡量滿足：（1）休假天數平均分配給每個護理人員。（2）星期六日及國定假日需平均分配給每個人。（3）日夜班天數須符合該人員班別需求所需要的日夜班天數。（4）連續三天不要出現休假，上班，休假的組合。由上述多項護理人員需求與排班規定來看，以人工方式產生排班表，確實是複雜而耗時。所以本研究希望能發展護理人員排班程式，以資訊技術快速產生符合規定的排班表，且能滿足護理人員需求。三、專題進行方式(一)排班程式排班程式的主要目的，是根據護理人員約班需求與排班規定，而產生排班結果。就演算法設計的觀點來看，假設有n位護士，每月有d天，因為每位護士每天只能值一種班，班別有白班(D)、小夜班(E)、大夜班(N)三種，再加上休假(R)，共有四種可能性，所以每月排班表，將有4nd種可能解，排班問題就是在4nd種可能解當中，找尋最佳解或次佳可行解，以院方提供97年7月第二呼吸照護中心為例，護士人數n=23且七月天數d=31，所以共有42331=4713種可能解，解集合太大，難以一一檢視是否為最佳解或次佳可行解。在演算法設計技巧中，回溯法(backtracking)[11]可以使用在眾多可能解當中，找尋最佳解或良好可行解的方法，是本專題計畫設計排班核心程式的主要演算法。回溯法的原理是利用深先搜尋法(depth-firstsearch,DFS)與界限函式(boundingfunction)，利用DFS，程式可以逐日產生護士的值班內容，再由界限函式檢查是否違反排班規定與約班需求，快速搜尋解答。圖一與圖二為回溯法的應用案例。圖一、實作回溯法原理圖。圖二、當遇到問題往回推演找到解救方法繼續往下執行程式圖。在排班時，常會發現約班需求與排班規定互相矛盾，無法兼顧的情形。例如97年7月第二呼吸照護中心，每天白班需求6人、小夜5人、大夜5人，因為護士人數23人，所以每天只有7人可以休假，如果某日有超過7人約休假，一定無法滿足約班需求。利用回溯法排班，當約班需求與排班規定互相矛盾時，會造成程式產生護士的值班內容發生停頓，可以偵測約班需求與排班規定互相矛盾的情形，據此可放寬約班需求，使排班流程得以繼續進行。為了驗證回溯法排班的可行性，我們使用專題時撰寫的程式測試。輸入97年7月第二呼吸照護中心的約班資料，可以找到護理長可接受之可行解，但是仍有程式需執行一小時以上，平均約有14處護士個人約班需求無法滿足，假日排休不平均，休假天數不平均，日夜班天數與班別需求的誤差大等缺點。為了解決上述缺點，我們導入另一個演算法設計技巧－分而治之(divide-and-conquer)法[11]，將一個月分為五個時段，每個時段有5-7天，分別排班，再將個別排班結果整合成一個月的排班結果。此種方法將原本4nd種可能解，降為只考慮其中54nd/5種可能解，以上例來看，是從4713種可能解，降到54143種可能解，增進程式執行效率。我們在9月完成分而治之法的初步程式，使用97年7月與10月第二呼吸照護中心與8月52病房的約班資料做測試，發現程式執行時間可以降低到10分鐘，護士個人約班需求不滿足處減少，休假天數也較平均，日夜班天數與班別需求的誤差變小，大幅改進前版程式。(二)視窗介面視窗介面呈現約班需求輸入畫面、參數資料輸入畫面與排班結果輸出畫面。在約班需求輸入畫面中，可以儲存或修改約班需求。最後在所有護理人員完成輸入約班需求後，可以產生綜合約班表，提供後續排班程式使用，或護理長參考運用。執行排班程式時，需要參考許多參數，例如：護理人員人數、每日各班別需求人數等參數，都需藉由參數資料輸入畫面，輸入到排班程式。在排班程式完成排班表之後，排班結果輸出畫面將會輸出排班報表檔案，以便公告排班結果。除了排班表，排班結果輸出畫面也會統計排班結果，主要有每位護士的休假與各班別工作天數功能。此部分程式設計技術，也是利用一般視窗程式設計與檔案處理技巧可以達成。(三)進行步驟與執行進度專題進行步驟流程圖如表三，說明如下：1.瞭解護理人員排班問題此步驟已於專題進行期間，與彰基護理長進行多次討論，並由護理長提供約班表，以及訂定明確的排班規則與一般需求，已充分瞭解護理人員排班問題。2.整合護理人員排班方法與參數此步驟需要閱讀整理國內外相關文獻，從中吸取優良的排班演算法設計技巧，並且與彰基護理長訪談，瞭解排班的困難與實務經驗，希望能整合設計出一套高效率、高品質的排班演算法，並能符合排班實務需求。表三、計畫進行流程。3.設計與修改排班核心程式如前所述，我們已經根據回溯法與分而治之法的演算法設計理念，撰寫排班程式初版，在參考國內外文獻與護理長實務經驗之後，陸續加強修改排班程式。4.設計與修改排班視窗介面程式步驟3的排班程式，旨在探討排班演算法的效能。除此之外，相關視窗介面也會在本專題研究內完成。這部分都需運用視窗程式設計技巧，難度不高，但是很繁瑣，為了完成某一項視窗介面功能，需先找出合適的物件(object)，研究其屬性(property)設定事件程序的撰寫技巧，然後才能完成這一項視窗介面功能。除此之外，設計視窗介面程式時，還需要常與使用者溝通，將完成的某一項視窗介面功能，提供使用者測試，如果使用不習慣或有其他意見，還要再修改介面程式，直到使用者滿意為止，所以此步驟是繁瑣而耗時的工作，在專題進行期間，常要做視窗介面程式修改的工作。5.測試護理人員排班程式目前在測試排班程式方面，我們得到彰基護理長提供的約排班歷史資料，已經完成多次測試。在專題進行末期，我們希望能得到更多護理長的約排班歷史資料做測試。在排班視窗介面程式方面，我們則希望有更多護理長操作視窗介面，收集其使用意見，加強視窗介面程式，反覆修改，期能得到使用者滿意。6.撰寫軟體使用手冊與結案報告在程式完成後，我們會製作使用手冊，期望提供使用者完整的軟體操作指引與說明。四、主要成果1.作業平台(1)使用WindowsXP(2)硬體規格：a.Pentium(R)IV2.80GHzb.RAM:DDR512MB2.計算時間從與彰基護理長討論的結果中得知，在人工的排班上要花4小時以上的時間，而經過我們撰寫的程式上，電腦隨機跑出來的數據中，所得的平均時間在10分鐘上下，比較起來我們所寫的程式縮短了很多時間。3.必須遵守規則及護理人員約班需求之比較：(1)必須遵守規定：在排班結束後，我們可以從附錄的表中的知，每天人員的所需，上班和休假人員的統計數目都有符合規定。(2)護理人員的約班需求：因為在約班的需求上，是比較沒有硬性規定說護理人員約班就一定要給，能的話當然最好，所以做了一份統計變異數的統計成果，如表四，我們在把程式所跑出的五項電腦隨機排班去做平均如表五，所得知在：a.放假變異數(R)：人工比電腦排班好。b.例假變異數(R在周末)：人工比電腦排班差。c.上班變異數(上班天數)人工比電腦排班好。d.未達成約班需求個數比(整個排班表約班次數)：人工比電腦排班差。e.連續三天出現休假，上班，休假的個數比(整月所有人員排班出現的頻率次數)：人工比電腦排班好。表四、人工與程式跑出的五項電腦隨機排班的變異數比較表表五、人工與程式跑出的五項電腦隨機排班的變異數平均做比較表總和以上的比較，在護理人員的約班需求上，此撰寫的程式經電腦隨機排班的解果比人工排班出來的成果好。五、評估與展望以目前所學和了解的電腦演算法有限所以在電腦排班的變異數和人工排班的變異數比較下來，仍需有改進的空間；好比在護理人員排班需求的約班上，還沒達到每個人都能在自己想要的約班下排班。在未來希望繼續研究發展此護理人