【正文】 望 ....................................................................................... 18 總結(jié) ......................................................................................... 19 展望 ......................................................................................... 19 致謝 ....................................................................................................... 19 參考文獻 ............................................................................................... 20 1 緒論 選題背景和意義 近年來， 國內(nèi)外醫(yī)療問題越來越受重視。 護士排班問題也屬于醫(yī)療問題的一個方面。但是在我國管理機構(gòu)對護士資源的重視度尚不夠，致使很多地方出 現(xiàn)護士嚴重不足的問題。此外，傳統(tǒng)的護士排班方法采用手工排班方法，這樣顯得混亂無序 ，而且效率低下 。因此提高護士利用效率非常有必要。 從護士數(shù)量、結(jié)構(gòu)、配置、分工（排班）等，實施人性化排班。 護士排班是基層護理者的一項經(jīng)常性工作，是在現(xiàn)有的人力資源基礎(chǔ)上，對護理工作任務(wù)、內(nèi)容、程序、人力、和時間因素通盤考慮，做出系統(tǒng)、科學(xué)地安排，使護理人員明確職責(zé)，工作效率得到提高，保證醫(yī)院護理質(zhì)量，同時降低人力資源成本 [1]。但是由于排班中存在一系列勞動法約束，外加需要考慮不同護士的能力級別差異，因此，護士排班問題是極為復(fù)雜的組合優(yōu)化問題，屬 NP難問題，在國外深受研究關(guān)注。 本論文 用模擬退火方法研究護士排班算法。現(xiàn)代醫(yī)學(xué)不斷發(fā)展，對護理工作也提出了更高的要求。 對于護士排班問題 ，國外的研究 較早 ，很多人用了很多科學(xué)方法來優(yōu)化，而國內(nèi)的研究 較少 ， 很多都停留在手工排班方法 ，用算法優(yōu)化的比較少。 另外，也有少數(shù)算法的研究。 對于 排班原則 ， 呂芳 [4]提出 以病人的需要為基本原則 ： 以病人的護理需要為中心，適應(yīng)護理工作的連續(xù)性， 24 h不間斷，合理有效地安排人力，護理、教學(xué)、科研須統(tǒng)籌兼顧 。 楊玉霞 [6]提出 均衡平等原則 ： 保持各班工作量的均衡，按工作量安排人力，一視同仁，各崗位輪轉(zhuǎn)機會均等，使人人充分發(fā)揮效能。 茍艷梅 等 [8]提出 人性化原則 :護士并非單一角色，除工作中的職業(yè)角色外，還有社會角色，應(yīng)以入為本，盡量滿足護士的合理要求。白班人員有 4— 5名，中午、夜班只有 1名護士值班，其缺點是白班人員多、夜班人員少，遇到病重、手術(shù)病人多或搶救時難以應(yīng)付，無暇顧及其他病人。 何麗 等 [11]提出 按整體護理模式排班將病區(qū)工作分為臨床組與辦公室組。每組由各層次護士組成，責(zé)任護士值白班， 3個月輪轉(zhuǎn) 1次，有利于病人的全程護理，并通過與醫(yī)生共同查房，充實了?？浦R及避免醫(yī)護間的不一致。做到年齡、學(xué)歷、資歷、氣質(zhì)、技能及能力互補，形成團隊合力，揚長避短，全員參與管理。 沈吟東等 [12]利用矩陣向量化變換來求解護士排班問題。 國外研究現(xiàn)狀 國外的 護士排班 研究 可以分為三個階段，早期的數(shù)學(xué)方法，隨后的人工智能法，近期的元啟發(fā)式算法 。 數(shù)據(jù)的簡化是不可避免 的。后來 很多學(xué)者采用啟發(fā)式算法（如 [18,19,20,21,22]）。 20 世紀 80 年代以來，人工智能被應(yīng)用于 護士調(diào)度問題（陳述方法 [29],約束編程 [30,31,32,33], 專家系統(tǒng) [24,27,33],基于案例的歸因 [34,35]等）。 20 世紀 90 年代以來 ，很多 論文用 元 啟發(fā)式算法如模擬退火 [37,38]，禁忌搜索[39,40]和進化算法 [41,42,43,44,45]來解決這個問題。首先闡述了護士排班問題，然后建立考慮護士偏好和級別的護士排班問題整數(shù)規(guī)劃模型，然后概述模擬退火算法，再將兩者結(jié)合起來，用模擬退火算法求解護士排班問題，優(yōu)化排班方 案。通過查閱相關(guān)文獻，基本把握了當(dāng)前國內(nèi)外護士排班問題的研究現(xiàn)狀，從而確定了自己的研究方向。 第 3章首先概述模擬退火算法，然后將模擬退火算法和護士排班算法結(jié)合起來，設(shè)計基于模擬退火的護士排班算法。最后利用實際案例中的數(shù)據(jù)進行計算。 2 護士排班問題建模 本章 主要講述護士排班問題的建模。 護士排班問題 本文研究的護士排班問題是指：給定一個排班周期（如：一周）內(nèi)的全部護理工作，并且給定一組具有不同級別的護士，要求滿足一系列勞動法規(guī)等約束，編制出一個最有效（即成本最低）的護士排班方案。這樣不同級別的護士不可能單獨排班，必須對全部護士一起排班，因此使得該問題變得復(fù)雜。 主要勞動法規(guī)約束有： 1）每位護士一日最多只能進行一個班次的工作； 2）每一個排班周期內(nèi)， 每位護士的最長工作時間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限 ； 3） 每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且任何護 士不允許進行要求比自己級別高的護士的護理工作，反之可以； 4） 上了晚班后，另一天不能上早班 。 現(xiàn)在給定 N 個護士，可以用一個二維表格 [46]（如 （ 3 2） 所示） 來表示一個 護士排班方案。如果表中的方案能夠滿足上述全部約束，則為可行方案，否則為不可行方案。 整數(shù)規(guī)劃的 矩陣表達式一般可以做如下表達： Max(min)cX AX? B X={ ix |i=0,1,2,… n}, ix ?Z 為了表述方便，首先做如下假設(shè)和定義：共有 n 為護士，分屬 u 個級別，記I={1,2,…， n}， 表示護士集合；記 S={1,2， …， u}表示護士級別集合； is ? S 表示第 i 位護士的級別。上限不小于下限。 ijP 表示第 i 個護士對第 j 個班次的偏好程度。 公式如（ 3 1） ： ? ?11m in 1 0 1nmi j i j i j i jij c x p x? ? ? ? ? ??? ? ? ? ??? ， ， ， （ 3 2） ? 表示工資成本占的比重， ? 表示偏好成本占的比重，兩者之和為 1 約束條件可以分為三類。 對應(yīng)公式如 (3 3)： WTlow?1mijj x??? WTup i=1,2,…,n (3 4) 第二，每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且 任何護士不允許進行要求比自己級別高的護士的護理工作，反之可以； 對應(yīng)公式如 (3 5)： 11 , 2 , . . . 。 1 , 2 , . . . ,mTi j k Tk x i n j T??? ? ? ?? （ 3 8） 其中， 10{ ijijx ? 第 個 護 士 做 第 個 班 次否 則 第四，上了晚班后不能接著上另一天的早班。 元 啟發(fā)式算法這種時候就能取到很好的作用。 模擬退火算法概述 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對當(dāng)前解重復(fù) “產(chǎn)生新解 → 計算目標函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t 值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。 模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： 第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。因為目標函數(shù)差僅由變 換部分產(chǎn)生，所以目標函數(shù)差的 計算最好按增量計算。 第三步是判斷新解是否被接受 ,判斷的依據(jù)是一個接受準則，最常用的接受準則是 Metropo1is 準則 : 若 Δt′0則接受 S′作為新的當(dāng)前解 S，否則以概率exp(Δt′/T)接受 S′作為新的當(dāng)前解 S。此時，當(dāng)前解實現(xiàn)了一次迭代。而當(dāng)新解被判定為舍棄時，則 在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。 基于模擬退火的護士排班算法設(shè)計 為便于闡述的方便這里先說明一個符號， _ ijwork grade 表示第 i 個護士做第 j 個班次的工作級別 ，它不允許高于護士的實際級別。 基于護士排 班的算法框架跟模擬退火的算法框架大致相同，但是由于護士排班問題的具體特征，也會有些特殊的地方，比如方案的可行化過程。 算法的流程可以分為生成初始方案，可行化初始方案，生成新方案，判斷是否接受新方案，判斷是否滿足終止準則。 圖 3 1 算法框架 本章接下來的小節(jié)將對圖里面的各個環(huán)節(jié)進行詳細闡 述。每天有 m/T 個班次，前面 T 個班為第一類班次（如早班），最后面 T 個班次為最后一類班次（如晚班）。 若選中的是