【正文】 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。 最后要感謝我的朋友和同學，他們給我很多鼓勵和支持，陪我度過了美好的大學時光。沈老師從大三上學期開始授我的課，大 三下依然是我的授課老師，大三暑假在她那里實習，學習護士排班問題， 到大四指導我做畢業(yè)設(shè)計。 第三，如果再用遺傳算法和緊 急搜索等其他算法進行求解，然后再進行比較分析，將會是問題更加透徹。 展 望 本文在護士排班方面取得了 一定的成果，但是仍然存在不足之處，還可以繼續(xù)深入研究： 第一，本研究的優(yōu)化效果不是特別明顯，鄰域結(jié)構(gòu)設(shè)置的不是特別好。最優(yōu)解的總費用變化的過程如 圖 4 2 圖 4 2 最優(yōu)解總費用變化過程 最后 輸出最優(yōu)解的排班表，如 圖 4 3 圖 4 3 最優(yōu)解 5 總結(jié)與展望 本論文有好的地方也有值得改進的地方。使得最優(yōu)解在主體函數(shù)循環(huán)的時候不斷更新。 函數(shù) void nurse_scheduling_SA(double Tmax,double Tmin,int k,double r,Solutionamp。具體程序見附錄 2。 程序中取 ? 為 ， ? 為 ， 由于類之間的賦值不能直接用等號，故利用面向?qū)ο笾剌d的思想，對“ =”進行重載。給 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) 整為零。 Penalty 為違反約束產(chǎn)生的懲罰值，設(shè)計為 double 型。 work_cost[i]j]表示 i 個護士上第 j 個班次的工資費用， 取值 1,2,3 對應(yīng) 低，中，高級護士 。 二維數(shù)組 work_grade[28][21]表示 排班表上每個 當班 護士的實際工作等級 。 二維數(shù)組 pref[28][21]表示護士對班次的偏好程度 ，設(shè)計為整型變量 。 將解決方案設(shè)計為主要類 solution，包含成員變量和成員函數(shù)兩部分。 算法實現(xiàn) 算法實現(xiàn) 采用面向?qū)ο蟮某绦蛟O(shè)計思想，以解決方案為問題的主要類，記為solution 類，然后設(shè)計好主要的成員變量和成員函數(shù)。設(shè)定的排班周期為一周（ T=7）；每日工作分為早、中、晚三個班型。首先是退火溫度的設(shè)置，設(shè)定初始溫度為 Tmax,然后就是溫度遞減的速率 r, 最小溫度 Tmin,還有就是每個溫度下的迭代 次數(shù) N的設(shè)置。 變換流程如 圖 3 1 圖 3 2 變換流程 否 是 是 否 是 否 第一種變換 方案是否可行 第二 種變換 方案是否可行 第三種變換 接受準則 方案是否可行 接 受準則 當新解可行且總費用值小于當前解時，接受新解。當然同樣要考慮，如果是早班的話就要先考慮該護士之前的晚班是否當班，是晚班則要考慮它之后的早班是否當班。是晚班則要考慮它之后的早班是否當班。 根據(jù)初始化方法的特點，總結(jié)出會出現(xiàn)以下 幾種使得方案不可行的可能。 由于考慮到對各個級別的護士的需求數(shù)等約束，還有可能某些護士沒有達到最低班次數(shù)，初始解可能 是不可行的。 若選中的是中班或者晚班，相應(yīng)的班次該護士請假，或者其工作班次數(shù)也已經(jīng)達到最大值，則該天的三個班型都賦值為 0。每天有 m/T 個班次，前面 T 個班為第一類班次（如早班），最后面 T 個班次為最后一類班次（如晚班）。 算法的流程可以分為生成初始方案，可行化初始方案，生成新方案，判斷是否接受新方案，判斷是否滿足終止準則。 基于模擬退火的護士排班算法設(shè)計 為便于闡述的方便這里先說明一個符號， _ ijwork grade 表示第 i 個護士做第 j 個班次的工作級別 ，它不允許高于護士的實際級別。此時，當前解實現(xiàn)了一次迭代。因為目標函數(shù)差僅由變 換部分產(chǎn)生，所以目標函數(shù)差的 計算最好按增量計算。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對當前解重復 “產(chǎn)生新解 → 計算目標函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t 值，算法終止時的當前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。 元 啟發(fā)式算法這種時候就能取到很好的作用。 對應(yīng)公式如 (3 3)： WTlow?1mijj x??? WTup i=1,2,…,n (3 4) 第二，每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且 任何護士不允許進行要求比自己級別高的護士的護理工作，反之可以； 對應(yīng)公式如 (3 5)： 11 , 2 , . . . 。 ijP 表示第 i 個護士對第 j 個班次的偏好程度。 整數(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 位護士的級別。 現(xiàn)在給定 N 個護士，可以用一個二維表格 [46]（如 （ 3 2） 所示） 來表示一個 護士排班方案。這樣不同級別的護士不可能單獨排班，必須對全部護士一起排班，因此使得該問題變得復雜。 2 護士排班問題建模 本章 主要講述護士排班問題的建模。 第 3章首先概述模擬退火算法，然后將模擬退火算法和護士排班算法結(jié)合起來，設(shè)計基于模擬退火的護士排班算法。首先闡述了護士排班問題，然后建立考慮護士偏好和級別的護士排班問題整數(shù)規(guī)劃模型，然后概述模擬退火算法，再將兩者結(jié)合起來，用模擬退火算法求解護士排班問題，優(yōu)化排班方 案。 20 世紀 80 年代以來，人工智能被應(yīng)用于 護士調(diào)度問題（陳述方法 [29],約束編程 [30,31,32,33], 專家系統(tǒng) [24,27,33],基于案例的歸因 [34,35]等）。 數(shù)據(jù)的簡化是不可避免 的。 沈吟東等 [12]利用矩陣向量化變換來求解護士排班問題。每組由各層次護士組成，責任護士值白班， 3個月輪轉(zhuǎn) 1次，有利于病人的全程護理，并通過與醫(yī)生共同查房，充實了?？浦R及避免醫(yī)護間的不一致。白班人員有 4— 5名，中午、夜班只有 1名護士值班，其缺點是白班人員多、夜班人員少，遇到病重、手術(shù)病人多或搶救時難以應(yīng)付，無暇顧及其他病人。 楊玉霞 [6]提出 均衡平等原則 ： 保持各班工作量的均衡，按工作量安排人力，一視同仁，各崗位輪轉(zhuǎn)機會均等，使人人充分發(fā)揮效能。 另外，也有少數(shù)算法的研究。現(xiàn)代醫(yī)學不斷發(fā)展，對護理工作也提出了更高的要求。但是由于排班中存在一系列勞動法約束，外加需要考慮不同護士的能力級別差異，因此，護士排班問題是極為復雜的組合優(yōu)化問題，屬 NP難問題，在國外深受研究關(guān)注。 從護士數(shù)量、結(jié)構(gòu)、配置、分工（排班）等，實施人性化排班。此外，傳統(tǒng)的護士排班方法采用手工排班方法，這樣顯得混亂無序 ，而且效率低下 。 護士排班問題也屬于醫(yī)療問題的一個方面。 詳細 設(shè)計了模擬退火算法， 首先在不破壞一些約束的情況下（如晚班后不能接著上早班）， 隨機產(chǎn)生初始解，然后 用增加護士和減少班次的方法 對初 始解進行可行化，再在不破壞解的可行性的情況下，對排班表進行變換來產(chǎn)生 新解，構(gòu)成模擬退火的關(guān)鍵部分 ，再設(shè)計接受準則和算法參數(shù)，完成了算法的設(shè)計 。 由于 護士排班問題受 各種勞動法規(guī)約束，不同護士的能力 有 差異以及護士 有班次 偏好需求，護 士排班問題是極為復雜的組合優(yōu)化問題，屬 NP 難問題。護士是醫(yī)療機構(gòu)中的重要成員。護士排班是 醫(yī)院日常工作 的重要方面。本文旨在利用模擬退火算法求解該問題。 最后， 在 C++ builder 環(huán)境中進行編程實現(xiàn)， 對 湖南省 某市級醫(yī)院某科室的護士排班問題就行求解， 取得了良好的效果。 目前世界各地（特別是在發(fā)達國家）的護士資源不足的問題越來越嚴重，