護士排班問題-管理系統(tǒng)建模與優(yōu)化作業(yè)

1、管理系統(tǒng)建模與優(yōu)化期末作業(yè)護士排班問題專業(yè)：管理科學與工程時間：2015年1月目錄 TOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 1案例背景3 HYPERLINK l bookmark10 o Current Document 2研究現(xiàn)狀3 HYPERLINK l bookmark12 o Current Document 3案例模型4護士排班問題4護士排班模型4 HYPERLINK l bookmark22 o Current Document 4護士排班算法7整數(shù)規(guī)劃7模擬退火算法7數(shù)規(guī)劃與模擬退火混合算法8 HYPERLIN

2、K l bookmark24 o Current Document 5案例計算與分析10案例數(shù)據10分支界定法計算結果12模擬退火算法仿真結果13分支界定與模擬退火算法混合仿真結果14 HYPERLINK l bookmark33 o Current Document 6結論15 HYPERLINK l bookmark35 o Current Document 參考文獻16研究背景及現(xiàn)狀護士排班問題1案例背景護理工作是整個醫(yī)療衛(wèi)生工作的重要組成部分，在醫(yī)療實踐中擔負著特殊的工作和 任務，是整個醫(yī)院開展醫(yī)療服務的運營基礎。目前各國護士短缺嚴重，已引起了國外護 理管理的高度重視1。我國護士長期處

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

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

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

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

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

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

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

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

11、第k班次對護士的需求量；Pxk表示第i位護士對第k個班次的工作滿意度，記為p11Kl（非常不滿意）,2（不滿 意），3（一般）,4（滿意），5（非常滿意）;xljk=l表示第i位護士在第J天安排第k個班次，反之xljk=0;1,中級及以上職稱0,其他A i表示工資成本權重系數(shù)，其中凡人代0,1; 入2表示班次滿意度權重系數(shù)，其中人2印01；基于上述定義的參數(shù)，我們建立如下護士排班模型：min F(x) = fi(x),f2(x)其中n J 4fl(x)= WWWcMiiki=l j=l k=ln I 4f2(x) = ww” ikxijki=l j=l k=lS.t. HC1： i)n2,1

12、qiXij2 2 Vi e I, Vj e Ti=li = lHC2:nW Xijk N VjGT,kG 1,2,3i=lHC3:4耿=1 VielVjGT k=lHC4:Xij3 + 1 Vi C I, Vj C T(3-1)(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)HC5:J 3(3-8)g Xijk w m Vi e IHC6:HC7:HC8:SCI:SC2:J 3WWxijkNw Vi G I fcl(3-9)r+iiiV Xij3 ni Vi G I, r G 1,2,J - nx)(3 - 10)r+n2 3xijk ；, 則令i=jk第4步:若達到熱平衡(內循環(huán)

13、次數(shù)大于n (Tk)轉第5步：否則轉第2步。第5步:降低Tk，k=k+l,若TkTf，則算法停止，否則轉第2步。上述模擬退火算法流程如圖4.1所示。圖4.1 SA算法流程圖整數(shù)規(guī)劃與模擬退火混合算法在護士排班領域研究中，一些算法的混合優(yōu)化技術已經存在很多年了。國外將整數(shù) 規(guī)劃和領域搜索算法的混合優(yōu)化策略應用于護士排班領域，有效的改善了解的質量和算 法的效率。基于上述的研究，本文提出整數(shù)規(guī)劃和模擬退火算法混合優(yōu)化策略處理護士 排班問題的約束條件和護士的潛在要求，從算法的優(yōu)化機制融合、算法結構互補、優(yōu)化 操作的結合、優(yōu)化行為的互補和削弱參數(shù)的苛刻條件等方面61闡述了混合優(yōu)化機制的 優(yōu)越性，其中整數(shù)

14、規(guī)劃的分支定界算法保證了解的可行解，而模擬退火算法以一定的概 率接受劣解，從而有效擴大可行解區(qū)域，能高效求解組合優(yōu)化問題。分支定界算法(BBA)與模擬退火算法(SA)的混合策略，以下簡稱BBASA,BBASA算 法其算法流程如下：步驟1：狀態(tài)初始化，確定初溫；步驟2:確定最大點，次大點，最小點；步驟3:算法收斂準則是否滿足，滿足就輸出結果;否則轉到步驟4;步驟4:使用分支定界算法求出局部極小點：步驟5:由SA利用“護士互換規(guī)則”和“班次調整規(guī)則”規(guī)則產生函數(shù)產生新個體;步驟6:以一定概率接受新個體；步驟7: SA抽樣穩(wěn)定，則進行退溫操作，跳到步驟3;否則返回步驟5;步驟8:退出上述模擬退火算法

15、流程如圖4.2所示。圖4. 2BBASA算法流程圖案例計算與分析5案例計算與分析案例數(shù)據本文的護士數(shù)據來源于XX醫(yī)院護士工作狀況調研問卷的調研結果。目前某三 甲醫(yī)院重癥科室共有30名護士，其中高、中、初級護士分別3, 5和22位。假設排班周 期為一周0=7),并將每天的工作時間平均分為a班(8:0016:00,p班(6:00-0:00)和N班 (0:00-8:00)三種班次。影響排班質量的主要因素如表51所示。表5-1排班質量影響因素表序號排班影響因素參考建議1連續(xù)上班天數(shù)3-4天2連續(xù)工作時長340小時3連續(xù)晚班時長1-2天4排班周期內的總班次4-6天5排班周期內的總工時周工時在40小時左右

16、6連續(xù)休息天數(shù)1-2天7換班的合理性如護士上了晚班之后應該安排休息，不能又安排護士繼續(xù)去 上早班8排班周期內上班工時的平衡要保證在排班周期內每個護士的工時相等9排班周期內上晚班的平衡要保證在排班周期內每個護士上晚班的次數(shù)相對公平10排班周期內休息時間的平衡要保證在排班周期內每個護士休息的時間相對公平11排班周期內班次的平衡要保證在排班周期內每個護士上的各種班次的次數(shù)相對公 平12排班的高規(guī)律性護士上班的時間變化相而穩(wěn)定，不要每天的變動 都很大，提供一種人性化的排班由上述排班質量影響因素統(tǒng)計表可知，每位護士可連續(xù)匚作的最長時間是4個班次, 可連續(xù)夜班的最長時間是2個班次。在一個排班周期內內每位護

17、士最長工作班次至多為 6個班次，最短工作班次至少為4個班次，在排班周期內的總工時大概在40小時左右, 而每天“APN”各班次的實際需求護士數(shù)目由科室護士長給定，如表52所示：表5-2各班次護士需求人數(shù)(A/P/N)周一周二周三周四周五周六周日需求9/6/48/5/39/6/38/5/39/7/410/7/710/7/7XX醫(yī)院重癥科室采取的是“彈性排班”制，每周的排班表由護士長根據科室的護士需求量和護士的家庭、生活狀態(tài)等約束手工排班而成，詳細的手工排班表如下表5-3 所示。表5-3護士原始排班表序號周一周二周三周四周五周六周口1APRNNAP2APPRAPN3PANRAPA4APNRAAP5P

18、RPRAAP6RRPAPNN7APPRPNN8APPRPAP9PRNNRPA10PRNNRPP11PAARPNR12PAPNPPN13PRAPARN14PRANNRP15NNRAPAP16RNRRPNP17NNRAPAN18NNRPNRA19RPAPRPA20RPAPNRA21RAAPPRP22RAPNRAP23NRPARPA24RPAARNP25RPRPNNN26RNNRRPP27NNRpAPN28RNNRAPP29RAAPRPP30RPPANRA由于每位護士在不同班次內的工資成本是不一樣的，定義工資成本為5個等級，5代表最高級別的工資，1代表最低級別的工資，30位護士的工資級別如下表54所

19、示：表5-4護士工資表陰 1234567891011121314U16171819202122則中初中初初中初初初初初初初初初中初初初初初初232432222222223222222案例計算與分析23中344224初233125高455326高455327中344228初233129中344230初1331每位護士對各個班次的工作滿意度是不一樣的，定義班次滿意度為5個級別，1=非 常不滿意，2=不滿意，3二一般，4=滿意，5=非常滿意，為了計算的統(tǒng)一性，將對R班 定義為非常滿意，詳細的班次滿意度表見下表55所示表5-5護士班次滿意度序號APNR1532525325325154251555215

20、61515725158521592515102515115215125215131255142515152515162515172515181255192515201515211255221255235215242515251255261255275325285325292515302515分支界定法計算結果在MATLAB上用分支界定算法對護士排班模型進行仿真實驗，并令人1=0.乃，入案例計算與分析2=0.25,其計算結果如表56所示。表5-6護士排班模型計算結果手工排班表仿真排班表偏差目標值252.5155.75-38.17%工資成本575522-9.22%班次滿意度71594331.19%

21、運行時間/11.29s/其中，目標值偏差=仿式目標值一手工目標值* 0%手工目標值0o工資成本和班次滿意度的偏差類似計算。從表56可見，護士排班模型的目標值比 實際手工排班的目標值低38.17%,其中護士工資成本降低9.22%,但是護士對班次的滿 意度提升了 31.19%。這表明:基丁強、弱約束的護士排班模型明顯優(yōu)丁手工排班模式, 并且醫(yī)院管理成本和護士對工作的滿意度得到了有效的改善。模擬退火算法仿真結果在MATLAB上用模擬退火算法對護士排班模型(2214)進行仿真，采用近鄰編碼， 取初始狀態(tài)to=lOOOl,退溫策略選用指數(shù)倒退函數(shù)，B|J tk=A tk4,退溫速率入=0.99,迭 代終

22、止策略為連續(xù)20代不變。如此的算法收斂情況如圖5.1所示，所得結果如表57所 示。圖5. ISA算法收斂圖表5-7護士排班模型計算結果手工排班表仿真排班表偏差目標值 工資成本 班次滿意度 運行時間252.5143-43.4%575513-10.8%71596735.24%/5.08s/從表57可知，護士排班模型的目標值比實際手工排班的目標值降低了 43.43%,其 中工資成本降低10. 8%,但是護士對班次的滿意度卻提升了 3 5.24%。這表明:基于強、 弱約束的護士排班模型明顯優(yōu)于手工排班模式，在醫(yī)院1：資成本控制和護士的滿意度提 開方面達到了有效的平衡，而基于模擬退火算法的成功應用護士排

23、班模型，對求解大規(guī) 模的護士排班問題帶來新的啟發(fā)和思路。分支界定與模擬退火算法混合仿真結果參數(shù)選擇與SA仿真相同?；旌纤惴ńY果如表58所示，收斂情況如圖5.2所示。圖5.2SA算法收斂圖表5-8護士排班模型計算結果手工排班表仿真排班表偏差目標值252.513347.32%工資成本575504-10.96%班次滿意度71598037.6%運行時間/8.76s/基于分支定界和模擬退火算法的混合優(yōu)化策略求得目標值比手工排班低47.32%,其 中工資成本下降10.96%,而護士工作班次滿意度上升37.6%。這表明:基于分支定界和 模擬退火算法的混合優(yōu)化策略明顯強于原始的排班表，在護士排班模型的求解中能

24、取得 好的效果。結論6結論（1）基于分支定界和模擬退火算法的混合優(yōu)化策略融合了分支定界和模擬退火算 法優(yōu)化機制融合、算法結構互補、優(yōu)化操作的結合、優(yōu)化行為的互補和削弱參數(shù)的苛刻 條件等優(yōu)點，綜合評價最好，其護士排班模型的優(yōu)化性能和算法的效率遠遠好于傳統(tǒng)的 數(shù)學規(guī)劃和單一的啟發(fā)式算法。（2）基于強、弱約束的護士排班模型明顯優(yōu)于手工排班模式，并且醫(yī)院管理成本和 護士對工作的滿意度得到了有效的改善。其中增加的“APN排班”機制能有效的應付高 峰時段護理壓力和錯開上下班的交通高峰期;更多的護士在周末可以休息將有效改善護 士的家庭關系，而排班的公平性護士，提高護士的身心健康，使得整個醫(yī)院的護理工作 更加

25、高效的開展和管理。參芍文獻1345789101112131415參考文獻劉玉寬，張莉，李梅.醫(yī)療衛(wèi)生機構陷入困境的原因和出路燈.中國衛(wèi)生經濟, 1999, 18(6):15 16豐雪榮，華正麗.護士的壓力源分析及應對措施J.中國醫(yī)藥指南，2011,9(33):153-154范淑玉等.我國護士排班狀況研窕進展J.護士管理雜志，2008, 8(12) :27-29 姜小鷹.護理管理學國.上海:上?？茖W技術出版社，2001:139-143Be lien J, Demeulemeester E. A Branch and Price Approach for Integrating Nurse and

26、Surgery Scheduling J. European Journal of Operational Research, 2008, 189(3): 652-668Aick elfin U, Li J. An Estimation of Distribution Algorithm for Nurse Scheduling J. Annals of Operations Research, 2007, 155 (1): 289 309 Bard J E Purnomo H W Cyclic Preference Scheduling of Nurses Using a Lag rangi

27、anBased Heuristic J. Journal of Scheduling, 2007, 10(1)： 5-23 HolmesE. Miller, William P. Pierskalla, et al. Nurse Scheduling Using MathematicalProgramming J. Operations Research, 1976, 24 (5)：857 - 870 D. M Warner. Scheduling nursing personnel according to nursing preference： Amathematical programm

28、ing approach J. Operations Research, 1976, 24(5):842-856B. Jaumard, F Semet, and T. Vovor . A generalized linear programming model for nursescheduling J. European Journal of Operational Research, 1998, 107(1):1 一 18Ozkarahan, J. E. Bailey. Goal programming model subsystem of a flexible nursescheduli

29、ng support system J. HE Transactions on Industrial Electronics, 2003, 50(3) :833 838M aenhout B, Uanhoucke M Comparison and Hybridization of Crossover Operators for the Nurse Scheduling Problem J. Annals of Operations Research, 2008, 159 (1)：333 353Burk EK, Curtois T, Post q et al. A Hybrid Heuristic Ordering and Variab1eNeighborhood Search f or the Nurse Rostering Problem J. European Journal of Operat TonalResearch, 2008, 188(2)： 330-3