【正文】 士請假，或者其工作班次數(shù)也已經(jīng)達到最大值，則該天的三個班型都賦值為 0。 根據(jù)初始化方法的特點，總結(jié)出會出現(xiàn)以下 幾種使得方案不可行的可能。當然同樣要考慮，如果是早班的話就要先考慮該護士之前的晚班是否當班，是晚班則要考慮它之后的早班是否當班。首先是退火溫度的設(shè)置，設(shè)定初始溫度為 Tmax,然后就是溫度遞減的速率 r, 最小溫度 Tmin,還有就是每個溫度下的迭代 次數(shù) N的設(shè)置。 算法實現(xiàn) 算法實現(xiàn) 采用面向?qū)ο蟮某绦蛟O(shè)計思想，以解決方案為問題的主要類，記為solution 類，然后設(shè)計好主要的成員變量和成員函數(shù)。 二維數(shù)組 pref[28][21]表示護士對班次的偏好程度 ，設(shè)計為整型變量 。 work_cost[i]j]表示 i 個護士上第 j 個班次的工資費用， 取值 1,2,3 對應(yīng) 低，中，高級護士 。給 tab[28][21]，work[28][21]， pref[28][21]， grade[28]， work_grade[28][21]， work_cost[28][21]，demand[3][21]賦初值，并通過調(diào)整規(guī)則將 penalty 的值調(diào) 整為零。具體程序見附錄 2。使得最優(yōu)解在主體函數(shù)循環(huán)的時候不斷更新。 展 望 本文在護士排班方面取得了 一定的成果，但是仍然存在不足之處，還可以繼續(xù)深入研究： 第一，本研究的優(yōu)化效果不是特別明顯，鄰域結(jié)構(gòu)設(shè)置的不是特別好。沈老師從大三上學(xué)期開始授我的課，大 三下依然是我的授課老師，大三暑假在她那里實習(xí)，學(xué)習(xí)護士排班問題， 到大四指導(dǎo)我做畢業(yè)設(shè)計。 First International Conference Edinburgh, Springer, 1995, 93– 105. [31] H. Meyer auf ’ m Hofe: ConPlan/SIEDAplan: Personnel assignment as aproblem of hierarchical constraint satisfaction, Proceedings of theThirdInternational Conference on the Practical Applicationof Constraint Technology, London, 1997, 257– 271. [32] M. Okada: An approach to the generalised nurse scheduling problemgeneration of a declarative program to represent institutionspecific knowledge, Computers and Biomedical Research, Vol. 25,1992, 417– 434. [33] P. Chan, G. Weil: Cyclical staff scheduling using constraint logic programming, In . Burke,W. Erben (Editors), Practice and Theory of Automated Timetabling。 最后要感謝我的朋友和同學(xué)，他們給我很多鼓勵和支持，陪我度過了美好的大學(xué)時光。 第三，如果再用遺傳算法和緊 急搜索等其他算法進行求解，然后再進行比較分析，將會是問題更加透徹。最優(yōu)解的總費用變化的過程如 圖 4 2 圖 4 2 最優(yōu)解總費用變化過程 最后 輸出最優(yōu)解的排班表，如 圖 4 3 圖 4 3 最優(yōu)解 5 總結(jié)與展望 本論文有好的地方也有值得改進的地方。 函數(shù) void nurse_scheduling_SA(double Tmax,double Tmin,int k,double r,Solutionamp。 程序中取 ? 為 ， ? 為 ， 由于類之間的賦值不能直接用等號，故利用面向?qū)ο笾剌d的思想，對“ =”進行重載。 Penalty 為違反約束產(chǎn)生的懲罰值，設(shè)計為 double 型。 二維數(shù)組 work_grade[28][21]表示 排班表上每個 當班 護士的實際工作等級 。 將解決方案設(shè)計為主要類 solution，包含成員變量和成員函數(shù)兩部分。設(shè)定的排班周期為一周（ T=7）；每日工作分為早、中、晚三個班型。 變換流程如 圖 3 1 圖 3 2 變換流程 否 是 是 否 是 否 第一種變換 方案是否可行 第二 種變換 方案是否可行 第三種變換 接受準則 方案是否可行 接 受準則 當新解可行且總費用值小于當前解時，接受新解。是晚班則要考慮它之后的早班是否當班。 由于考慮到對各個級別的護士的需求數(shù)等約束，還有可能某些護士沒有達到最低班次數(shù)，初始解可能 是不可行的。每天有 m/T 個班次，前面 T 個班為第一類班次（如早班），最后面 T 個班次為最后一類班次（如晚班）。 基于模擬退火的護士排班算法設(shè)計 為便于闡述的方便這里先說明一個符號， _ ijwork grade 表示第 i 個護士做第 j 個班次的工作級別 ，它不允許高于護士的實際級別。因為目標函數(shù)差僅由變 換部分產(chǎn)生，所以目標函數(shù)差的 計算最好按增量計算。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對當前解重復(fù) “產(chǎn)生新解 → 計算目標函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t 值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。 對應(yīng)公式如 (3 3)： WTlow?1mijj x??? WTup i=1,2,…,n (3 4) 第二，每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且 任何護士不允許進行要求比自己級別高的護士的護理工作，反之可以； 對應(yīng)公式如 (3 5)： 11 , 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 位護士的級別。這樣不同級別的護士不可能單獨排班，必須對全部護士一起排班，因此使得該問題變得復(fù)雜。 第 3章首先概述模擬退火算法，然后將模擬退火算法和護士排班算法結(jié)合起來，設(shè)計基于模擬退火的護士排班算法。 20 世紀 80 年代以來，人工智能被應(yīng)用于 護士調(diào)度問題（陳述方法 [29],約束編程 [30,31,32,33], 專家系統(tǒng) [24,27,33],基于案例的歸因 [34,35]等）。 沈吟東等 [12]利用矩陣向量化變換來求解護士排班問題。白班人員有 4— 5名，中午、夜班只有 1名護士值班，其缺點是白班人員多、夜班人員少，遇到病重、手術(shù)病人多或搶救時難以應(yīng)付，無暇顧及其他病人。 另外，也有少數(shù)算法的研究。但是由于排班中存在一系列勞動法約束，外加需要考慮不同護士的能力級別差異，因此，護士排班問題是極為復(fù)雜的組合優(yōu)化問題，屬 NP難問題，在國外深受研究關(guān)注。此外，傳統(tǒng)的護士排班方法采用手工排班方法，這樣顯得混亂無序 ，而且效率低下 。 詳細 設(shè)計了模擬退火算法， 首先在不破壞一些約束的情況下（如晚班后不能接著上早班）， 隨機產(chǎn)生初始解，然后 用增加護士和減少班次的方法 對初 始解進行可行化，再在不破壞解的可行性的情況下，對排班表進行變換來產(chǎn)生 新解，構(gòu)成模擬退火的關(guān)鍵部分 ，再設(shè)計接受準則和算法參數(shù)，完成了算法的設(shè)計 。護士是醫(yī)療機構(gòu)中的重要成員。本文旨在利用模擬退火算法求解該問題。 目前世界各地（特別是在發(fā)達國家）的護士資源不足的問題越來越嚴重， 受到了廣泛重視。提高護 士工作積極性和主動性，使排班具有規(guī)律性、提高了管理效率。研究護士排班問題對于提高護理水平有重要作用，對于促進護理學(xué)與先進的醫(yī)學(xué)同時前進具有重大意義。 張萍 [7]提出 穩(wěn)定機動原則 ： 護理排班方式應(yīng)相對穩(wěn)定，護士長提前安排好下一周班次后向護士公示并上報護理部，使護士對自己的班次有預(yù)見性；常備機動人員，以便隨時調(diào)配歸 。該排班方式適用于整體護理模式病房及護理人員充足的科室，值得注意的是排班時應(yīng)遵循“互補增值”原則?，F(xiàn)實世界的問題很 復(fù)雜以致難以 用線性規(guī)劃的方法優(yōu)化， 當護士的人數(shù)、排班時間和約束個數(shù)增加時，該方法就陷入了“維數(shù)災(zāi)”。 本文結(jié)構(gòu)安排如 圖 1 1 所示： 圖 1 1 論文框架 本文主要內(nèi)容如下： 第 1章講述護士排班問題的背景和意義，對國內(nèi)外研究現(xiàn)狀進行了綜述。首先詳細闡述了護士排班問題，然后建立了考慮護士級別和偏好的整數(shù)規(guī)劃模型。其中， 每個空格處填上為每位護士安排 早班、中班、晚班、休班的一種。對于偏好程度設(shè)置五個等級：非常喜歡，喜歡，一般，不喜歡，非常不喜歡，依次用 1 到 5 五個數(shù)字表示，并定義ijP ?{1,2,3,4,5}； 模型的目標函數(shù)為使總費用最小，總費用為工資成本加上偏好成本。本章主要講述基于模擬退火的護士排班算法，首先介紹模擬退火算法，然后將模擬退火算法用到護士排班問題。 (7) T 逐漸減少，且 T0，然后轉(zhuǎn)第 2 步?？稍诖嘶A(chǔ)上開始下一輪試驗。 算法 流程 描述如 圖 3 1 。否則，該班次賦值為 1，當天的其他班賦值為零； 若選中的是休班，那么該天的三個班次都賦值為零。第一，護士的班次沒有達到最低工作班次；第二，某班次的某級別