【正文】 直到該班次相應級別的需求得到滿足。則讓該護士當該班。直到該護士的班次大于等于最低班次為止。 對于第一種情況，搜索出該護士沒有當班次天數(shù)，然后隨機將早中晚其中的 一個班次賦值為 1，如果是早班的話就要先考慮之前的晚班是否當班。第一，護士的班次沒有達到最低工作班次；第二，某班次的某級別護士需求數(shù)沒有得到滿足。 方案可行化 由于護士排班問題 很復雜，有很多約束條件，如果不能滿足則為不可行解，因此方案的可行化是算法的重要內(nèi)容之一。需要先將之可行化，然后再不影響可行性的情況下，進行模擬退火的迭代過程。由此就可以形成一個初始方案，即得到一個初始解。否則，該班次賦值為 1，當天的其他班賦值為零； 若選中的是休班，那么該天的三個班次都賦值為零。否則，如果該早班之前的晚班該護士不當班，則該班次賦值為 1，當天的中班和晚班賦值為零；如果該早班 之前的晚班該護士當班，則去查看該護士能否當中班或者晚班。 每天依次從早班、中班、夜班、和休班中隨機選擇一個班型。 初始解的生成 護士排班問題的解 用一個 n*m 的矩陣表示，其中每個元素取值為 0 或者 1。 算法 流程 描述如 圖 3 1 。對于很多問題要得到初始可行解很簡單，但是對于護士排班問題，得到初始可行解往往是很復雜的，所以算法框架中，方案的可行化是重要的一個步驟。 _ ij iw ork grad e s?。 模擬退火算法與初始值無關，算法求得的解與初始解狀態(tài) S(是算法迭代的起點 )無關；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。可在此基礎上開始下一輪試驗。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。 第二步是計算與新解所對應的目標函數(shù)差。 (7) T 逐漸減少，且 T0，然后轉(zhuǎn)第 2 步。 模擬退火的基本思想 : (1) 初始化：初始溫度 T(充分大 )，初始解狀態(tài) S(是算法迭代的起點 )， 每個 T 值的迭代次數(shù) L (2) 對 k=1， …… ， L 做第 (3)至第 6 步： (3) 產(chǎn)生新解 S′ (4) 計算增量 Δt′=C(S′)C(S)，其中 C(S)為評價函數(shù) (5) 若 Δt′0則接受 S′作為新的當前解，否則以概率 exp(Δt′/T)接受 S′作為新的當前解 . (6) 如果滿足終止條件則輸出當前解作為最優(yōu)解， 結(jié)束程序。退火過程由冷卻進度表 (Cooling Schedule)控制，包括控制參數(shù)的初值 t 及其衰減因子 Δt、每個 t 值時的迭代次數(shù) L 和 停止條件 S。根據(jù)Metropolis 準則，粒子在溫度 T 時趨于平衡的概率為 eΔE/(kT)，其中 E 為溫度T 時的內(nèi)能， ΔE 為其改變量， k 為 Boltzmann 常數(shù)。本章主要講述基于模擬退火的護士排班算法，首先介紹模擬退火算法，然后將模擬退火算法用到護士排班問題。對應公式如（ 35） ( 1 ) 1 1 , 2 , .. . , 1 , .. . 1ij i j m Tx x i n j m T m T m? ? ? ? ? ? ? ? ? ? （ 35） 3 基于模擬退火的護士排班算法 上一章 對護士排班 問題進行了數(shù)學建 模，由于隨著護士數(shù)的增加，用傳統(tǒng)的線性規(guī)劃方法會陷入“維數(shù)災” 。 1 , 2 , . . .n i j g i j g jq x D j m g u? ? ?? (3 6) 10{ igijgq ? 如 果 第 位 護 士 上 第 j 個 班 次 的 實 際 工 作 級 別 是否 則 第三， |每位護士一日最多只能進行一個班次的工作；對應公式如（ 3 7） ： /1,*0 1 1 , 2 , . . . , 。 第一，每一個排班周期內(nèi)，每位護士的最長工作時間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。對于偏好程度設置五個等級：非常喜歡，喜歡，一般，不喜歡，非常不喜歡，依次用 1 到 5 五個數(shù)字表示，并定義ijP ?{1,2,3,4,5}； 模型的目標函數(shù)為使總費用最小，總費用為工資成本加上偏好成本。 ijc 表示第 i 位護士進行第 j 個班次的工資成本（簡稱成本，用護士的等級表示）； gjD 表示第 j 班次對第 g 級別護士的需求數(shù)量。記排班周期為 T；記 J={1,2， …,m}表示一個周期 T 內(nèi)的班次集合；記 Wtup 和 WTlow 分別表示一個排班周期內(nèi)的護士的總工時的上限和下限。 表 2 1 排班表 星期 護士序號 周日 周一 周二 周三 周四 周五 周六 1 2 … N 護士排班問題整數(shù)規(guī)劃模型 針對上述護士排班問題，本節(jié)將 建立一個帶有一系列勞動法規(guī)約束的且考慮護士級別差異的護士排班整數(shù)規(guī)劃模型。其中， 每個空格處填上為每位護士安排 早班、中班、晚班、休班的一種。 對于違反這些約束的行為在程序設計的時候都將記入懲罰值，視為影響方 案 的因素。 根據(jù)我國護理工作的普遍特性，本文對擬研究的護士排班問題做如下假設： 1） 排班周期為七天，從周日到周六 ； 2） 每日平均分三個班次，即分為如下三個班型：早班、中班、晚 班，并且 每個班次的工作時間為連續(xù)八個小時。在該問題中，每位護士都應有一個特定的護士級別，并且規(guī)定級別高的護 士允許替代級別低的護士進行工作，反之不行。首先詳細闡述了護士排班問題，然后建立了考慮護士級別和偏好的整數(shù)規(guī)劃模型。 第 5章 對論文進行了 總結(jié)，并且做出展望。 第 4章講述算法實現(xiàn)。 第 2章首先對護士排班問題進行了詳細描述，然后建立了護士排班問題的數(shù)學模型，建立了考慮護士級別和偏好的整數(shù)規(guī)劃模型。 本文結(jié)構(gòu)安排如 圖 1 1 所示： 圖 1 1 論文框架 本文主要內(nèi)容如下： 第 1章講述護士排班問題的背景和意義，對國內(nèi)外研究現(xiàn)狀進行了綜述。 研究內(nèi)容與組織結(jié)構(gòu) 本文主要研究用模擬退火算法求解護士排班問題。這些方法中的一部分和今天 的研究問題依然相關 [31,36,33]。定義 多 個目標也是常見的 ，如[23,24,25,26,27,28]?，F(xiàn)實世界的問題很 復雜以致難以 用線性規(guī)劃的方法優(yōu)化， 當護士的人數(shù)、排班時間和約束個數(shù)增加時，該方法就陷入了“維數(shù)災”。 很多 早期 論文 [14,15,16,17]都為他們的線性模型提到數(shù)學優(yōu)化方法。 劉曉榮等 [13]設計了一種能同時 滿足醫(yī)院和護士需求的更具彈性的決策支持系統(tǒng)，它采用了選擇性模型 ， 而這些模型又融合了彈性工作方式，因為它結(jié)合了每天 24h 每周 7d 的排班問題，并給出了彈性護上排班圖和決策支持系統(tǒng)的結(jié)構(gòu)。 班次分 類、 排班原則 和排班方法 都是 一些定性方面的研究，隨著研究的不斷深入，也產(chǎn)生了很多定量化的研究，用到了不少科學方法。該排班方式適用于整體護理模式病房及護理人員充足的科室，值得注意的是排班時應遵循“互補增值”原則。辦公室組值白班，有利于 高年資護士及特殊時期護士 (妊娠及哺乳期 )的合理利用，體現(xiàn)了“以人為本”的管理理念；臨床組實施以責任護士負責制的小組或整體護理，相對固定，分組負責病區(qū)全都病人的健康教育、 基礎護理及中、晚班工作。該排班方式是我國醫(yī)院護士排班最常用的，也是近年來要求改革的一種方式，適用于急診、危重病人較少的五官科、腫瘤化療科及康復科等。 對于 排班方式 ， 戴琴、周力 等 [910]提出 按功能制護理模式排班實行全院統(tǒng)一排班的方式，按功能制護理方式分配崗位，按崗位配備護士，由白班、中班、前夜班、后夜班組成，每名護士 1個班次值 l d，循環(huán)進行。 張萍 [7]提出 穩(wěn)定機動原則 ： 護理排班方式應相對穩(wěn)定，護士長提前安排好下一周班次后向護士公示并上報護理部，使護士對自己的班次有預見性；常備機動人員，以便隨時調(diào)配歸 。 秦玉霞 等 [5]提出 互補增值原則 ： 掌握護理工作規(guī)律，分清主次緩急，合理搭配各層次人員，做到年齡、學歷、資 歷、氣質(zhì)及技能互補，使工作互不重疊、互不干擾，既能保證重點，又能照顧一般 。 李秋潔 [3]提出 排班類型依照排班權(quán)利的歸屬分為集權(quán)式排班 (由護理部負責 )、分權(quán)式排班 (由護士長負責 )及自我排班 (由護士自行排班 )3種。 國內(nèi)研究現(xiàn)狀 由于 國內(nèi)的研究 大部分 都停留在定性方面， 從 排班類型，排班原則，排班方式三個方面進行總結(jié)。研究護士排班問題對于提高護理水平有重要作用，對于促進護理學與先進的醫(yī)學同時前進具有重大意義。 護士排班研究屬于護理研究的 一部分。 在解決組合優(yōu)化問題時，元啟發(fā)式算法能起到很好的作用。 護士排班問題已經(jīng)成為醫(yī)院管理的核心內(nèi)容之一。提高護 士工作積極性和主動性，使排班具有規(guī)律性、提高了管理效率。運用計算機算法生成排班表，既能提高準確度又提高了效率。 隨著生活水平的提高，大眾對于護理工作的要求也必然隨之提高。 護理人力資源與病人期望非常不平衡，臨床護士編制嚴重不足，護士班次更換頻繁，病人沒有相對固定的護理人員，整體護理難以真正落實到位，如何通 過 管理合理使用人力資源，從而解決人力短缺問題，值得我們不斷探討與研究 [2]。 目前世界各地（特別是在發(fā)達國家）的護士資源不足的問題越來越嚴重， 受到了廣泛重視。 護士是一種需要經(jīng)過專業(yè)訓練的人力資源、是醫(yī)院日常運營的基礎。 最后， 在 C++ builder 環(huán)境中進行編程實現(xiàn)， 對 湖南省 某市級醫(yī)院某科室的護士排班問題就行求解， 取得了良好的效果。 然后 探討用模擬退火算法求解護士排班問題。本文旨在利用模擬退火算法求解該問題。 護士排班是基層護理者的一項經(jīng)常性工作，是在現(xiàn)有的人力資源基礎上，對護理工作任務、內(nèi)容、程序、人力、和