【正文】 在指導(dǎo)畢業(yè)設(shè)計 的過程中， 從文獻(xiàn)翻譯、算法設(shè)計、 程序設(shè)計、 論文撰寫，沈老師都給了我細(xì)致的指導(dǎo)，讓我受益匪淺 。 由于算法是隨機(jī)去更新 解 ，算法效率不高，要將近十分鐘才能運行完畢。 第一部分使得護(hù)士需求數(shù)得到滿足 ，第二部分使得護(hù)士的最低工作天數(shù)得到滿足。 一維數(shù)組 grade[28]表示護(hù)士的工作級別 ，設(shè)計為整型變量。 算法已經(jīng)在 C++ builder 環(huán)境中實現(xiàn)， 并 結(jié)合 案例分析 驗證算法的有效性。 對于這兩種情況， 可以分別用增加班次和增加護(hù)士兩種 方法進(jìn)行調(diào)整，具體描述如下。 圖 3 1 算法框架 本章接下來的小節(jié)將對圖里面的各個環(huán)節(jié)進(jìn)行詳細(xì)闡 述。 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： 第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。 公式如（ 3 1） ： ? ?11m in 1 0 1nmi j i j i j i jij c x p x? ? ? ? ? ??? ? ? ? ??? ， ， ， （ 3 2） ? 表示工資成本占的比重， ? 表示偏好成本占的比重，兩者之和為 1 約束條件可以分為三類。 護(hù)士排班問題 本文研究的護(hù)士排班問題是指：給定一個排班周期（如：一周）內(nèi)的全部護(hù)理工作，并且給定一組具有不同級別的護(hù)士，要求滿足一系列勞動法規(guī)等約束，編制出一個最有效（即成本最低）的護(hù)士排班方案。后來 很多學(xué)者采用啟發(fā)式算法（如 [18,19,20,21,22]）。 茍艷梅 等 [8]提出 人性化原則 :護(hù)士并非單一角色，除工作中的職業(yè)角色外，還有社會角色，應(yīng)以入為本，盡量滿足護(hù)士的合理要求。 護(hù)士排班是基層護(hù)理者的一項經(jīng)常性工作，是在現(xiàn)有的人力資源基礎(chǔ)上，對護(hù)理工作任務(wù)、內(nèi)容、程序、人力、和時間因素通盤考慮，做出系統(tǒng)、科學(xué)地安排，使護(hù)理人員明確職責(zé)，工作效率得到提高，保證醫(yī)院護(hù)理質(zhì)量，同時降低人力資源成本 [1]。 本文首先 對護(hù)士排班問題建立整數(shù)規(guī)劃模型， 考慮護(hù)士級別和偏好 ，在 減少醫(yī)院成本的同時，盡量滿足護(hù)士對于班次的偏好。 然后 探討用模擬退火算法求解護(hù)士排班問題。 護(hù)士排班問題已經(jīng)成為醫(yī)院管理的核心內(nèi)容之一。 對于 排班方式 ， 戴琴、周力 等 [910]提出 按功能制護(hù)理模式排班實行全院統(tǒng)一排班的方式，按功能制護(hù)理方式分配崗位，按崗位配備護(hù)士，由白班、中班、前夜班、后夜班組成，每名護(hù)士 1個班次值 l d，循環(huán)進(jìn)行。定義 多 個目標(biāo)也是常見的 ，如[23,24,25,26,27,28]。在該問題中，每位護(hù)士都應(yīng)有一個特定的護(hù)士級別，并且規(guī)定級別高的護(hù) 士允許替代級別低的護(hù)士進(jìn)行工作，反之不行。 第一，每一個排班周期內(nèi)，每位護(hù)士的最長工作時間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。 第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。 初始解的生成 護(hù)士排班問題的解 用一個 n*m 的矩陣表示，其中每個元素取值為 0 或者 1。 對于第一種情況，搜索出該護(hù)士沒有當(dāng)班次天數(shù)，然后隨機(jī)將早中晚其中的 一個班次賦值為 1，如果是早班的話就要先考慮之前的晚班是否當(dāng)班。 案例背景 湖南省 某市級醫(yī)院某科室 [46]有 28 位護(hù)士，其中高、中、低級別護(hù)士分別為 1 10 位。 grade[i]表示對 i個護(hù)士的級別，取值 1,2,3 分別對應(yīng)低級，中級和高級護(hù)士。 函數(shù) void Calculate_cost() 計算費用和懲罰值 。 初始可行解的總費用為 ，如 圖 4 1 圖 4 1 初始可行解 有了初始解后，接下來就是不斷的進(jìn)行迭代，窗體中顯示了優(yōu)化過程中best_solution 的總費用的變化過程。 然后要感謝我的家人，是他們的默默付出和無私支持讓我完成了學(xué)業(yè)。和沈老師的接觸已經(jīng)將近兩年了，沈老師 對教學(xué)的熱情和嚴(yán)謹(jǐn)?shù)难芯烤駥ξ业挠绊懞艽?，讓我明白了做研究的人要有什么樣的態(tài)度。 結(jié)果 分析 利用背景 中的數(shù)據(jù)，代入程序中運行可以看到結(jié)果。 可分為兩部分 調(diào)整。 pref[i][j]表示第 i 個護(hù)士 對 第 j 個班次 的偏好程度， 取值 1,2,3,4,5 分別對應(yīng)非常喜歡，喜歡，一般，不喜歡，非常不喜歡五個等級。 4 基于模擬退火的護(hù)士排班算法 實現(xiàn)與 案例分析 上一章 講述了基于模擬退火的護(hù)士排班算法的設(shè)計，本章詳細(xì)講述算法的程序?qū)崿F(xiàn)。第一，護(hù)士的班次沒有達(dá)到最低工作班次；第二，某班次的某級別護(hù)士需求數(shù)沒有得到滿足。 算法 流程 描述如 圖 3 1 。 (7) T 逐漸減少，且 T0，然后轉(zhuǎn)第 2 步。對于偏好程度設(shè)置五個等級：非常喜歡，喜歡，一般，不喜歡，非常不喜歡，依次用 1 到 5 五個數(shù)字表示，并定義ijP ?{1,2,3,4,5}； 模型的目標(biāo)函數(shù)為使總費用最小，總費用為工資成本加上偏好成本。首先詳細(xì)闡述了護(hù)士排班問題，然后建立了考慮護(hù)士級別和偏好的整數(shù)規(guī)劃模型?，F(xiàn)實世界的問題很 復(fù)雜以致難以 用線性規(guī)劃的方法優(yōu)化， 當(dāng)護(hù)士的人數(shù)、排班時間和約束個數(shù)增加時，該方法就陷入了“維數(shù)災(zāi)”。 張萍 [7]提出 穩(wěn)定機(jī)動原則 ： 護(hù)理排班方式應(yīng)相對穩(wěn)定，護(hù)士長提前安排好下一周班次后向護(hù)士公示并上報護(hù)理部，使護(hù)士對自己的班次有預(yù)見性；常備機(jī)動人員，以便隨時調(diào)配歸 。提高護(hù) 士工作積極性和主動性，使排班具有規(guī)律性、提高了管理效率。本文旨在利用模擬退火算法求解該問題。 詳細(xì) 設(shè)計了模擬退火算法， 首先在不破壞一些約束的情況下（如晚班后不能接著上早班）， 隨機(jī)產(chǎn)生初始解，然后 用增加護(hù)士和減少班次的方法 對初 始解進(jìn)行可行化，再在不破壞解的可行性的情況下，對排班表進(jìn)行變換來產(chǎn)生 新解，構(gòu)成模擬退火的關(guān)鍵部分 ，再設(shè)計接受準(zhǔn)則和算法參數(shù)，完成了算法的設(shè)計 。但是由于排班中存在一系列勞動法約束，外加需要考慮不同護(hù)士的能力級別差異，因此，護(hù)士排班問題是極為復(fù)雜的組合優(yōu)化問題，屬 NP難問題，在國外深受研究關(guān)注。白班人員有 4— 5名，中午、夜班只有 1名護(hù)士值班，其缺點是白班人員多、夜班人員少，遇到病重、手術(shù)病人多或搶救時難以應(yīng)付，無暇顧及其他病人。 20 世紀(jì) 80 年代以來，人工智能被應(yīng)用于 護(hù)士調(diào)度問題（陳述方法 [29],約束編程 [30,31,32,33], 專家系統(tǒng) [24,27,33],基于案例的歸因 [34,35]等）。這樣不同級別的護(hù)士不可能單獨排班，必須對全部護(hù)士一起排班，因此使得該問題變得復(fù)雜。 對應(yīng)公式如 (3 3)： WTlow?1mijj x??? WTup i=1,2,…,n (3 4) 第二，每日工作的各種級別的護(hù)士數(shù)都不允許少于規(guī)定的需求數(shù)，并且 任何護(hù)士不允許進(jìn)行要求比自己級別高的護(hù)士的護(hù)理工作，反之可以； 對應(yīng)公式如 (3 5)： 11 , 2 , . . . 。因為目標(biāo)函數(shù)差僅由變 換部分產(chǎn)生，所以目標(biāo)函數(shù)差的 計算最好按增量計算。每天有 m/T 個班次，前面 T 個班為第一類班次（如早班），最后面 T 個班次為最后一類班次（如晚班）。是晚班則要考慮它之后的早班是否當(dāng)班。設(shè)定的排班周期為一周（ T=7）；每日工作分為早、中、晚三個班型。 二維數(shù)組 work_grade[28][21]表示 排班表上每個 當(dāng)班 護(hù)士的實際工作等級 。 程序中取 ? 為 ， ? 為 ， 由于類之間的賦值不能直接用等號，故利用面向?qū)ο笾剌d的思想，對“ =”進(jìn)行重載。最優(yōu)解的總費用變化的過程如 圖 4 2 圖 4 2 最優(yōu)解總費用變化過程 最后 輸出最優(yōu)解的排班表，如 圖 4 3 圖 4 3 最優(yōu)解 5 總結(jié)與展望 本論文有好的地方也有值得改進(jìn)的地方。 最后要感謝我的朋友和同學(xué)，他們給我很多鼓勵和支持，陪我度過了美好的大學(xué)時光。沈老師從大三上學(xué)期開始授我的課，大 三下依然是我的授課老師，大三暑假在她那里實習(xí)，學(xué)習(xí)護(hù)士排班問題， 到大四指導(dǎo)我做畢業(yè)設(shè)計。使得最優(yōu)解在主體函數(shù)循環(huán)的時候不斷更新。給 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) 整為零。 二維數(shù)組 pref[28][21]表示護(hù)士對班次的偏好程度 ，設(shè)計為整型變量 。首先是退火溫度的設(shè)置，設(shè)定初始溫度為 Tmax,然后就是溫度遞減的速率 r, 最小溫度 Tmin,還有就是每個溫度下的迭代 次數(shù) N的設(shè)置。 根據(jù)初始化方法的特點，總結(jié)出會出現(xiàn)以下 幾種使得方案不可行的可能。 算法的流程可以分為生成初始方案，可行化初始方案，生成新方案，判斷是否接受新方案，判斷是否滿足終止準(zhǔn)則。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。 ijP 表示第 i 個護(hù)士對第 j 個班次的偏好程度。 2 護(hù)士排班問題建模 本章 主要講述護(hù)士排班問題的建模。 數(shù)據(jù)的簡化是不可避免 的。 楊玉霞 [6]提出 均衡平等原則 ： 保持各班工作量的均衡，按工作量安排人力，一視同仁，各崗位輪轉(zhuǎn)機(jī)會均等，使人人充分發(fā)揮效能。 從護(hù)士數(shù)量、結(jié)構(gòu)、配置、分工（排班）等，實施人性化排班。 由于 護(hù)士排班問題受 各種勞動法規(guī)約束，不同護(hù)士的能力 有 差異以及護(hù)士 有班次 偏好需求，護(hù) 士排班問題是極為復(fù)雜的組合優(yōu)化問題，屬 NP 難問題。 最后， 在 C++ builder 環(huán)境中進(jìn)行編程實現(xiàn)， 對 湖南省 某市級醫(yī)院某科室的護(hù)士排班問題就行求解， 取得了良好的效果。 在解決組合優(yōu)化問題時，元啟發(fā)式算法能起到很好的作用。該排班方