1、管理系統建模與優化期末作業護士排班問題專業：管理科學與工程時間：2015年1月目錄1案例背景32研究現狀33案例模型43.1 護士排班問題43.2 護士排班模型44護士排班算法74.1 整數規劃74.2 模擬退火算法74.3 數規劃與模擬退火混合算法85案例計算與分析105.1 案例數據105.2 分支界定法計算結果125.3 模擬退火算法仿真結果135.4 分支界定與模擬退火算法混合仿真結果146結論15參考文獻16研究背景及現狀護士排班問題1案例背景護理工作是整個醫療衛生工作的重要組成部分，在醫療實踐中擔負著特殊的工作和任務，是整個醫院開展醫療服務的運營基礎。目前各國護士短缺嚴重，已引起了

2、國外護理管理的高度重視1。我國護士長期處于特殊的環境氛圍和接待各種病情的患者，并承受超負荷的工作和長期緊張腦力勞動、不規則的排班等護理狀況，它將直接影響護士的身心健康，影響工作質量，造成護患關系的緊張2。科學管理護理資源，有效控制醫院護理成本預算和提升患者滿意度是目前研究的熱點課題3。在目前護理工作量大、應急性險強、不規則輪班，傳統的單一的簡單排班模式的情況下，由于醫院存在控制成本的壓力，造成了醫院和護士的利益沖突和目標差異，為更好的調高護理質量、降低醫院護理成本，需要建立一個完整的帶有勞動法規約束和滿足護士自身需求的護士排班模型以及護士排班算法。護士排班問題主要是指在現有醫療資源的約束條件下

3、，從醫院的護理成本、護士的滿意度、班次的偏好、降低護士工作壓力和改善護士身心健康等方面，編制出科學的排班表，從而有效改善排班表的質量和提升護理工作的滿意度和社會形象42研究現狀國外對護士排班問題的研究起步較早，護士排班問題已經被臨床研究機構和計算機方面研究多達40余年了，護士排班問題是建立在一系列的勞動法規和班次需求約束下的復雜組合優化問題，屬于NP問題5,6,7,目前可行的主要技術是數學規劃8,9,10,11,12和啟發式算法13,14,15以及傳統數學規劃和啟發式算法的融合技術，但是國外的勞動法規與護士：作狀況與國內完全不同，模型和約束條件與國內存在明顯的差異。而國內護士排班問題研究起步較

4、晚，主要是按功能模式和整體護理模式排班，按固定、彈性、“三班制”、“APN”排班，護士自我排班等簡單手工排班模式16,而定量排班的ILP模型的約束條件并未考慮“APN”等機制和排班公平性等，難以綜合考慮以病人的需要為中心、互補增值、均衡平等、穩定機制、人性化原則，故缺乏一套有效的模型優化機制。由于一系列約束條件和護士的偏好，整個護士排班模型是復雜的組合優化問題，比TSP問題更難的NP問題，解決此問題能有效推動調度算法的改進。隨著現代醫院的發展,醫院資源的資源緊缺和護士短缺以及護士自身的潛在需求,迫切需要實現信息化的護士排班系統，從而有效的改善護士的管理和工作狀況，整合醫院的資源優勢，更好的為患

5、者服務，有效改善醫患關系，促進社會的和諧發展。案例模型3案例模型3.1護士排班問題護士排班問題是一種滿足系列勞動法規和班次約束的護理資源最優分配問題。在實際的護士排班中，約束條件主要包括匚作強度要求、夜班班次要求、護土對匚作環境的滿意度、工作時段的偏好和排班公平性等。護士排班問題的目標就是在一個排班周期內（一周或一月），滿足一系列勞動約束和醫院資源需求的約束，使得整個醫院的護理成本最小化和護士工作的滿意度最高。護士排班問題要服從以下的三個關犍假設：（1）護士排班模型的約束條件必須符合我國現行的勞動法規和大型醫院護理工作實際狀況。（2）護士的自身的要求要盡量去滿足，這對于護士排班問題的研究是很重

6、要的。（3）沒有必要把在崗的所有護士都考慮在護士排班模型之中。那些實習和兼職的護土可以實行排班后，根據實際情況動態調整到護士排班表中。自從2008年5月12口新護士條例頒布實施后，我國大部分醫院實行“APN”時間排班制。“APN”時間制，即每天平均分為3個班次:其中A班（8:0016:00）,P班（16:000:00）,N班（0:008:00,若將“休班”定義為R（rest）班，那么護士的排班主要指A班、P班、N班和R班。其中“APN”充分保證了高峰時段的護理安全。強約束條件（HardCoiistraintJIC）是在我國任何醫院的護士排班環境中都必須滿足的約束條件，否則整個排班表就不可行。強

7、約束條件主要考慮勞動法規、醫院的護理資源和班次約束等：HC1:A班和P班均有1-2名中級資質以上的護士；HC2:任何一個班次（A班、P班和N班）的護士數不低于實際需求量；HC3:每位護士一天最多只能進行一個班次的工作；HC4:任何護士在相鄰2天的班次不能連續（若第1天排N班，則第2天不能排A班）;HCS:在一個排班周期內，每位護士的最長工作班次不能超過規定的上限；HC6:在一個排班周期內，每位護士的最短工作班次不能少于規定的下限；HC7:在一個排班周期內，每位護士的最長連續N班不能超過規定的上限；HC8:在一個排班周期內，每位護士的最長連續班次不能超過規定的上限；弱約束條件（SoftConst

8、raint,SC）是指在醫院實際護士排班中盡可能多的去滿足的條件，各所醫院在實際排班巾將弱約束條件進行調整和增加，本文中主要考慮護士的周末休息和排班的公平性：SC1:盡可能多的護士在周末至少休息一天；SC2：不對某個護士特殊照顧A班；如果護士的排班表滿足了所有的強、弱約束條件，則為可行的護士排班表，如表31所示：表3-1可行護士排班表周一周二周三周四周五周六周口1AAPRNNR2RANNRPNNPNNRAAR32護士排班模型護士排班模型的目標就是在一個排班周期內（一周或一月），滿足一系列勞動法規、案例模型醫院護理資源需求和班次約束條件下，使得整個醫院的護理成本最小化和護士工作的滿意度最高。旨在

9、降低醫院的護理運營成本，同時有效降低護士工作壓力，讓護士更好的處理好工作、生活和家庭的關系、從而提高醫院的護理工作效率。參數假設：I=1,2,.n表示n名護士集合；T=1,2,。表示一個排班周期內的天數集合；K=1,234表示每天班次的類型（ARNE）;m表示在一個排班周期內，每位護士的最長工作時間；w表示在一個排班周期內，每位護士的最短工作時間；m表示在一個排班周期內，每位護士連續夜班的最長時間；叱表示在一個排班周期內，每位護士連續班次的最長時間；G#表示第i位護士在第j天選擇第k個班次工作的工資等級，記為=12,3,4,5;爾表示在第j天第k班次對護士的需求量；Pxk表示第i位護士對第k個

10、班次的工作滿意度，記為p11Kl（非常不滿意）,2（不滿意），3（一般）,4（滿意），5（非常滿意）;xljk=l表示第i位護士在第J天安排第k個班次，反之xljk=0;1,中級及以上職稱0,其他Ai表示工資成本權重系數，其中凡人代0,1;入2表示班次滿意度權重系數，其中人2印01；基于上述定義的參數，我們建立如下護士排班模型：minF(x)=fi(x),f2(x)其中nJ4fl(x)=WWWcMiiki=lj=lk=lnI4f2(x)=ww”ikxijki=lj=lk=lS.t.HC1：i)n1 2,1<qiXij22VieI,VjeTi=li=lHC2:nWXijkN"Vj

11、GT,kG1,2,3i=lHC3:4耿=1VielVjGTk=lHC4:Xij3+<1ViCI,VjCT(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)HC5:案例模型J3(3-8)gXijkwmVieIHC6:HC7:HC8:SCI:SC2:J3WWxijkNwViGIfcl(3-9)r+iiiVXij3<niViGI,rG1,2,J-nx)(3-10)r+n23xijk<n2ViGI,re1,2,.,J-nJj=rk=l(311)+xi(j+i)421ViW1,2,.,10),VjGT(3-12)(3-13)x23(j)i=°VjET護士排

12、班模型要求在任何排班中強約束條件都必須滿足，并盡可能多的滿足弱約束條件。可根據實際環境中的重要性程度將弱約束做出如下的順序:SCISC2,其中表示優先級，優先級的順序由醫院決定。由此可將目標函數(31)化為：2其中w入i=ii=l(3-14)2min戶Q)=2入/Q)，i=ls.t.HC1:HC8,SCI,SC2模型(314)是一個典型的01整數規劃模型，包含4*n*J個01決策變量，以及(17+2n)升(24iiE】2)n個約束方程。由于是在固定周期T內進行n位護士排班，并假設每口分4個班次，故模型的求解難度與護士數量呈線性關系。模型算法4護士排班算法4.1整數規劃整數線性規劃（Intege

13、rLinearProgramming,IIP）是最優化理論中比較重要的體系，在工業和工程設計和科學研究方面、計算機設計、系統可靠性、編碼和經濟分析等諸多領域有廣泛應用。但是整數線性規劃間遮屬于NP難問題，一般不存在多項式算法，目前求解ILP的方法主要有分支定界法、割平面法、多面體法、列生成法、禁忌搜索和遺傳算法等53,54,55。在求解整數線性規劃問題中，分支定界算法是一種最常用的方法，分支定界（branchandbound）算法在問題的解空間上采取樹形搜索整數規劃問題的方法。分支定界（branchandbound）算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法

14、采用廣度優先或最小耗費優先的方法在解空間搜索樹,并且在分支定界算法中，每一個活結點只有一次機會成為擴展結點。對于大規模整數規劃問題（IP，直接采取舉例法相當的困難，采用“分而治之"（divideandconquer）的策略，先將可行解區域劃分為一些小的解集合，然后在較小的解集合上求解相應目標函數的最優值，并將所求結果集成在一起生成原問題的最優解。在求解較小的解集合對應的子問題時，既可以采用分而治之的策略進行分析，也可以采取其方法對子問題進行求解。分支定界算法的基本思想是從原問題（IP）的線性規劃松弛解X出發，若最優解不符合原問題的整數條件，那么該解X必是原問題的上界W而原問題的任何可

15、行解都看作是目標解的一個下界乎它將可行解區域劃分為若干子區域，并逐步縮小上界Z和增大下界©從而得到最優目標解以求得最優解。對于0-1整數規劃問題的分支定界算法步驟如下所示：0-1整數規劃問題分支界定算法流程58步驟1（初始）:求解原問題（IP）的線性規劃松弛解，若得到整數解，則視為原問題的最優解，否則得到原問題的一個上界；步驟2（分支）:選擇適當的變量Xi,分別固定Xi=0和1=1得到2個子問題；步驟3（定界）:選擇一個子問題，求解該子問題的線性規劃松弛解；步驟4（剪枝）:若發生下列情況之一，則停止對該問題進行分支（剪枝）：（1）子問題的線性規劃松弛解的最優解是整數；（2）子問題不可

16、行；（3）子問題的上界等于或小于己知的可行解的目標函數值。步驟5（最優性）:重復上述過程，直到分支定界樹中沒有需要考慮的節點（子問題），則當前最好的可行解就是原問題（IP）的最優解.4.2 模擬退火算法組合優化（CombinatorialOptimization）問題的目標就是從組合問題的可行解空間求出最優解，一般包含變量、約束和目標函數這三個基本要素。在求解過程中選定的基本參數稱為變量，對變量取值的種種限制稱為約束，表示可行方案衡量標準的函數稱為目標函數。求解組合優化問題就是在目的函數的解集合里找到最適合的解，這必然要求運用一定的算法去降低求解過程的時間復雜性和空間復雜性。Kirkpatri

17、ck等在1982年結合固體退火過程狀態變化的思想，提出一種類似固體退溫過程的有效近似算法一模擬退火算法（SimulateAnneal,簡稱SA）,以解決大規模組合優化問題遇到的瓶頸。模擬退火算法58,59,60J是解決組合優化問題的算法，它采用Metropolis接受準則使算法跳離局部“最優”的陷阱，并使用“冷卻進度表”來控制整個算法實施過程，最終使算法能夠在多項式時間內得出一個近似最優解。模型算法一個優化問題可以描述為:其中S是一個離散有限狀態空間，i代表狀態。針對這樣一個優化問題，SA算法的計算步驟能夠描述如下：niin/(t),ieS第1步:初始化，任選初始解ieS,給定初始溫度To和終

18、止溫度Tf,令迭代指標k=0,Tk=T0o第2步:隨機產生一個領域解jN(i),(N(i)表示i的領域)，計算目標值增量Af=fG)-f(i)o第3步:若AfV0,令i4轉第4步：否則產生隨機量g=U(O,1),若exp(-勖>；,則令i=j°k第4步:若達到熱平衡(內循環次數大于n(Tk)轉第5步：否則轉第2步。第5步:降低Tk，k=k+l,若Tk<Tf，則算法停止，否則轉第2步。上述模擬退火算法流程如圖4.1所示。圖4.1SA算法流程圖4.3 整數規劃與模擬退火混合算法在護士排班領域研究中，一些算法的混合優化技術已經存在很多年了。國外將整數規劃和領域搜索算法的混合優化

19、策略應用于護士排班領域，有效的改善了解的質量和算法的效率。基于上述的研究，本文提出整數規劃和模擬退火算法混合優化策略處理護士排班問題的約束條件和護士的潛在要求，從算法的優化機制融合、算法結構互補、優化操作的結合、優化行為的互補和削弱參數的苛刻條件等方面61闡述了混合優化機制的優越性，其中整數規劃的分支定界算法保證了解的可行解，而模擬退火算法以一定的概率接受劣解，從而有效擴大可行解區域，能高效求解組合優化問題。分支定界算法(BBA)與模擬退火算法(SA)的混合策略，以下簡稱BBASA,BBASA算法其算法流程如下：步驟1：狀態初始化，確定初溫；步驟2:確定最大點，次大點，最小點；步驟3:算法收斂

20、準則是否滿足，滿足就輸出結果;否則轉到步驟4;步驟4:使用分支定界算法求出局部極小點：模型算法步驟5:由SA利用“護士互換規則”和“班次調整規則”規則產生函數產生新個體;步驟6:以一定概率接受新個體；步驟7:SA抽樣穩定，則進行退溫操作，跳到步驟3;否則返回步驟5;步驟8:退出上述模擬退火算法流程如圖4.2所示。圖4.2BBASA算法流程圖案例計算與分析5案例計算與分析5.1 案例數據本文的護士數據來源于XX醫院護士工作狀況調研問卷的調研結果。目前某三甲醫院重癥科室共有30名護士，其中高、中、初級護士分別3,5和22位。假設排班周期為一周0=7),并將每天的工作時間平均分為a班(8:0016:

21、00,p班(6:00-0:00)和N班(0:00-8:00)三種班次。影響排班質量的主要因素如表51所示。表5-1排班質量影響因素表序號排班影響因素參考建議1連續上班天數3-4天2連續工作時長340小時3連續晚班時長1-2天4排班周期內的總班次4-6天5排班周期內的總工時周工時在40小時左右6連續休息天數1-2天7換班的合理性如護士上了晚班之后應該安排休息，不能又安排護士繼續去上早班8排班周期內上班工時的平衡要保證在排班周期內每個護士的工時相等9排班周期內上晚班的平衡要保證在排班周期內每個護士上晚班的次數相對公平10排班周期內休息時間的平衡要保證在排班周期內每個護士休息的時間相對公平11排班周

22、期內班次的平衡要保證在排班周期內每個護士上的各種班次的次數相對公平12排班的高規律性護士上班的時間變化相而穩定，不要每天的變動都很大，提供一種人性化的排班由上述排班質量影響因素統計表可知，每位護士可連續匚作的最長時間是4個班次,可連續夜班的最長時間是2個班次。在一個排班周期內內每位護士最長工作班次至多為6個班次，最短工作班次至少為4個班次，在排班周期內的總工時大概在40小時左右,而每天“APN”各班次的實際需求護士數目由科室護士長給定，如表52所示：表5-2各班次護士需求人數(A/P/N)周一周二周三周四周五周六周日需求9/6/48/5/39/6/38/5/39/7/410/7/710/7/7

23、XX醫院重癥科室采取的是“彈性排班”制，每周的排班表由護士長根據科室的護士需求量和護士的家庭、生活狀態等約束手工排班而成，詳細的手工排班表如下表5-3所示。表5-3護士原始排班表序號周一周二周三周四周五周六周口1APRNNAP2APPRAPN3PANRAPA4APNRAAP5PRPRAAP6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA案例計算與分析10PRNNRPP11PAARPNR12PAPNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRA

24、P23NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRpAPN28RNNRAPP29RAAPRPP30RPPANRA由于每位護士在不同班次內的工資成本是不一樣的，定義工資成本為5個等級，5代表最高級別的工資，1代表最低級別的工資，30位護士的工資級別如下表54所示：表5-4護士工資表陰1234567891011121314U16171819202122則中初中初初中初初初初初初初初初中初初初初初初232432222222223222222案例計算與分析23中344224初233125高455326高455327中344228初233129中344230初1331每

25、位護士對各個班次的工作滿意度是不一樣的，定義班次滿意度為5個級別，1=非常不滿意，2=不滿意，3二一般，4=滿意，5=非常滿意，為了計算的統一性，將對R班定義為非常滿意，詳細的班次滿意度表見下表55所示表5-5護士班次滿意度序號APNR1532525325325154251555215615157251585215925151025151152151252151312551425151525151625151725151812551925152015152112552212552352152425152512552612552753252853252925153025155.2 分支界定法計算

26、結果在MATLAB上用分支界定算法對護士排班模型進行仿真實驗，并令人1=0.乃，入案例計算與分析2=0.25,其計算結果如表56所示。表5-6護士排班模型計算結果手工排班表仿真排班表偏差目標值252.5155.75-38.17%工資成本575522-9.22%班次滿意度71594331.19%運行時間/11.29s/其中，目標值偏差=仿式目標值一手工目標值*0%手工目標值0o工資成本和班次滿意度的偏差類似計算。從表56可見，護士排班模型的目標值比實際手工排班的目標值低38.17%,其中護士工資成本降低9.22%,但是護士對班次的滿意度提升了31.19%。這表明:基丁強、弱約束的護士排班模型明顯

27、優丁手工排班模式,并且醫院管理成本和護士對工作的滿意度得到了有效的改善。5.3 模擬退火算法仿真結果在MATLAB上用模擬退火算法對護士排班模型(2214)進行仿真，采用近鄰編碼，取初始狀態to=lOOOl,退溫策略選用指數倒退函數，B|Jtk=Atk4,退溫速率入=0.99,迭代終止策略為連續20代不變。如此的算法收斂情況如圖5.1所示，所得結果如表57所示。圖5.ISA算法收斂圖表5-7護士排班模型計算結果手工排班表仿真排班表偏差目標值工資成本班次滿意度運行時間252.5143-43.4%575513-10.8%71596735.24%/5.08s/案例計算與分析從表57可知，護士排班模型

28、的目標值比實際手工排班的目標值降低了43.43%,其中工資成本降低10.8%,但是護士對班次的滿意度卻提升了35.24%。這表明:基于強、弱約束的護士排班模型明顯優于手工排班模式，在醫院1：資成本控制和護士的滿意度提開方面達到了有效的平衡，而基于模擬退火算法的成功應用護士排班模型，對求解大規模的護士排班問題帶來新的啟發和思路。5.4 分支界定與模擬退火算法混合仿真結果參數選擇與SA仿真相同。混合算法結果如表58所示，收斂情況如圖5.2所示。圖5.2SA算法收斂圖表5-8護士排班模型計算結果手工排班表仿真排班表偏差目標值252.513347.32%工資成本575504-10.96%班次滿意度71

29、598037.6%運行時間/8.76s/基于分支定界和模擬退火算法的混合優化策略求得目標值比手工排班低47.32%,其中工資成本下降10.96%,而護士工作班次滿意度上升37.6%。這表明:基于分支定界和模擬退火算法的混合優化策略明顯強于原始的排班表，在護士排班模型的求解中能取得好的效果。結論6結論（1）基于分支定界和模擬退火算法的混合優化策略融合了分支定界和模擬退火算法優化機制融合、算法結構互補、優化操作的結合、優化行為的互補和削弱參數的苛刻條件等優點，綜合評價最好，其護士排班模型的優化性能和算法的效率遠遠好于傳統的數學規劃和單一的啟發式算法。（2）基于強、弱約束的護士排班模型明顯優于手工排

30、班模式，并且醫院管理成本和護士對工作的滿意度得到了有效的改善。其中增加的“APN排班”機制能有效的應付高峰時段護理壓力和錯開上下班的交通高峰期;更多的護士在周末可以休息將有效改善護土的家庭關系，而排班的公平性護士，提高護士的身心健康，使得整個醫院的護理工作更加高效的開展和管理。1345789101112131415參芍文獻參考文獻劉玉寬，張莉，李梅.醫療衛生機構陷入困境的原因和出路燈.中國衛生經濟,1999,18(6):1516豐雪榮，華正麗.護土的壓力源分析及應對措施J.中國醫藥指南，2011,9(33):153-154范淑玉等.我國護士排班狀況研窕進展J.護士管理雜志，2008,8(12)

31、:27-29姜小鷹.護理管理學國.上海:上海科學技術出版社，2001:139-143BelienJ,DemeulemeesterE.ABranchandPriceApproachforIntegratingNurseandSurgerySchedulingJ.EuropeanJournalofOperationalResearch,2008,189(3):652-668AickelfinU,LiJ.AnEstimationofDistributionAlgorithmforNurseSchedulingJ.AnnalsofOperationsResearch,2007,155(1):28930

32、9BardJEPurnomoHWCyclicPreferenceSchedulingofNursesUsingaLagrangianBasedHeuristicJ.JournalofScheduling,2007,10(1)：5-23HolmesE.Miller,WilliamP.Pierskalla,etal.NurseSchedulingUsingMathematicalProgrammingJ.OperationsResearch,1976,24(5)：857-870D.MWarner.Schedulingnursingpersonnelaccordingtonursingprefere

33、nce：AmathematicalprogrammingapproachJ.OperationsResearch,1976,24(5):842-856B.Jaumard,FSemet,andT.Vovor.AgeneralizedlinearprogrammingmodelfornurseschedulingJ.EuropeanJournalofOperationalResearch,1998,107(1):1一18Ozkarahan,J.E.Bailey.GoalprogrammingmodelsubsystemofaflexiblenurseschedulingsupportsystemJ.HETransactionsonIndustrialElectronics,2003,50(3):833838MaenhoutB,UanhouckeMComparisonandHybridizationofCrossoverOperatorsfortheNurseS