【正文】 184. [29],eck:Horoplan:puterassisted nurse scheduling using constraint based programming, Journal of the Society forHealth Systems, Vol. 5, 1995, 41– 54. [30] A. Meisels, E. Gudes, G. Solotorevski: Employee timetabling,constraintworks and knowledgebasedrules: A mixed approach, In . Burke, P. Ross (Editors), Practice and Theory of AutomatedTimetabling。 然后要感謝我的家人，是他們的默默付出和無私支持讓我完成了學業(yè)。 首先要感謝論文指導(dǎo)老師沈吟東教授。如果允許接受不可行解，并且能保證最后的收斂到可行的最優(yōu)解，將會更好。 可以自動生成排班方案，這樣 相對于手工排班就可以 省去很多麻煩，并且能取到一定的優(yōu)化作用，能降低成本，總體的框架還是處理的很好的，但是美中不足是優(yōu)化的效果 不是太明顯，究其原因可能是鄰域結(jié)構(gòu)設(shè)置的不是很好，如果以后的研究再深入點，可以尋找更好的鄰域結(jié)構(gòu)。 初始可行解的總費用為 ，如 圖 4 1 圖 4 1 初始可行解 有了初始解后，接下來就是不斷的進行迭代，窗體中顯示了優(yōu)化過程中best_solution 的總費用的變化過程。 best_solution 送入函數(shù)的是引用，故而它的值會變化。 函數(shù) bool accept(Solution cur, Solution new_solution, double T)用于判斷是否接受產(chǎn)生的新解，形參為當前解 cur 和新解 new_solution，以及退火溫度 T,返回值為布爾型， 1 表示接受， 0 表示不接受。 模擬退火算法實現(xiàn) 模擬退火的算法程序設(shè)計 有幾個函數(shù)構(gòu)成，主體是 迭代變換函數(shù) 。 函數(shù) void Calculate_cost() 計算費用和懲罰值 。 成員函數(shù)也設(shè)為公共型，下面依次進行說明： 函數(shù) void initialize()為初始化函數(shù)，產(chǎn)生可行的初始化方案。 取值見 表 4 1 。 二維數(shù)組 work_cost[28][21]表示 工作費用， 設(shè)計為整型變量。 grade[i]表示對 i個護士的級別，取值 1,2,3 分別對應(yīng)低級，中級和高級護士。 二維數(shù)組 tab 表示排班表， 設(shè)計為整型變量， 由于有 28 個護士，并且一周七天，每天三個班，總共有 21 個班次，前面七個代表早班，中間七個代表中班，最后七個代表晚班，所以設(shè)計為 tab[28][21]， tab[i][j]=1 表示第 i 個護士上第 j 個班 ； 二維數(shù)組 work[28][21]表示是否請假， 設(shè)計為整型變量， work [i][j]表示第 i個護士能否上第 j 個班次， 為 0 表示請假 ， 為 1 表示能工作 。首先要用計算機里面的數(shù)據(jù)來表示實際問題的 變量。 表 4 1 一周各級別護士需求表 接下來的程序設(shè)計都是 基于這些數(shù)據(jù)的，試圖用計算機來為該科室排班，并用算法進行排班優(yōu)化。 案例背景 湖南省 某市級醫(yī)院某科室 [46]有 28 位護士，其中高、中、低級別護士分別為 1 10 位。 參數(shù)設(shè)計 模擬退火中參數(shù)設(shè)置也很重要 。 第一種 可表示為 讓 1ij ijxx?變 成 ；第二種可表示為讓 ijx 和 ikx 的數(shù)值進行交換，要求是 1ik ijxx??；第三種相當于讓 1 1ij k j k j ijx x x x? ? ?變 成 要 求 是 這三種變換的方法，依次進行，如果滿足了不違反約束，增加懲罰值則得到新解，如果不行，則進行下一種交換方法，如果第三種還是產(chǎn)生增加懲罰值的新解，則接受，該新解也將在接受準則中被淘汰。則讓該護士當該班。 對于第一種情況，搜索出該護士沒有當班次天數(shù)，然后隨機將早中晚其中的 一個班次賦值為 1，如果是早班的話就要先考慮之前的晚班是否當班。 方案可行化 由于護士排班問題 很復(fù)雜，有很多約束條件，如果不能滿足則為不可行解，因此方案的可行化是算法的重要內(nèi)容之一。由此就可以形成一個初始方案，即得到一個初始解。否則，如果該早班之前的晚班該護士不當班，則該班次賦值為 1，當天的中班和晚班賦值為零；如果該早班 之前的晚班該護士當班，則去查看該護士能否當中班或者晚班。 初始解的生成 護士排班問題的解 用一個 n*m 的矩陣表示，其中每個元素取值為 0 或者 1。對于很多問題要得到初始可行解很簡單，但是對于護士排班問題，得到初始可行解往往是很復(fù)雜的，所以算法框架中，方案的可行化是重要的一個步驟。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S(是算法迭代的起點 )無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。 第二步是計算與新解所對應(yīng)的目標函數(shù)差。 模擬退火的基本思想 : (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é)束程序。根據(jù)Metropolis 準則，粒子在溫度 T 時趨于平衡的概率為 eΔE/(kT)，其中 E 為溫度T 時的內(nèi)能， ΔE 為其改變量， k 為 Boltzmann 常數(shù)。對應(yīng)公式如（ 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ù)災(zāi)” 。 第一，每一個排班周期內(nèi)，每位護士的最長工作時間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。 ijc 表示第 i 位護士進行第 j 個班次的工資成本（簡稱成本，用護士的等級表示）； gjD 表示第 j 班次對第 g 級別護士的需求數(shù)量。 表 2 1 排班表 星期 護士序號 周日 周一 周二 周三 周四 周五 周六 1 2 … N 護士排班問題整數(shù)規(guī)劃模型 針對上述護士排班問題，本節(jié)將 建立一個帶有一系列勞動法規(guī)約束的且考慮護士級別差異的護士排班整數(shù)規(guī)劃模型。 對于違反這些約束的行為在程序設(shè)計的時候都將記入懲罰值，視為影響方 案 的因素。在該問題中，每位護士都應(yīng)有一個特定的護士級別，并且規(guī)定級別高的護 士允許替代級別低的護士進行工作，反之不行。 第 5章 對論文進行了 總結(jié)，并且做出展望。 第 2章首先對護士排班問題進行了詳細描述，然后建立了護士排班問題的數(shù)學模型，建立了考慮護士級別和偏好的整數(shù)規(guī)劃模型。 研究內(nèi)容與組織結(jié)構(gòu) 本文主要研究用模擬退火算法求解護士排班問題。定義 多 個目標也是常見的 ，如[23,24,25,26,27,28]。 很多 早期 論文 [14,15,16,17]都為他們的線性模型提到數(shù)學優(yōu)化方法。 班次分 類、 排班原則 和排班方法 都是 一些定性方面的研究，隨著研究的不斷深入，也產(chǎn)生了很多定量化的研究，用到了不少科學方法。辦公室組值白班，有利于 高年資護士及特殊時期護士 (妊娠及哺乳期 )的合理利用，體現(xiàn)了“以人為本”的管理理念；臨床組實施以責任護士負責制的小組或整體護理，相對固定，分組負責病區(qū)全都病人的健康教育、 基礎(chǔ)護理及中、晚班工作。 對于 排班方式 ， 戴琴、周力 等 [910]提出 按功能制護理模式排班實行全院統(tǒng)一排班的方式，按功能制護理方式分配崗位，按崗位配備護士，由白班、中班、前夜班、后夜班組成，每名護士 1個班次值 l d，循環(huán)進行。 秦玉霞 等 [5]提出 互補增值原則 ： 掌握護理工作規(guī)律，分清主次緩急，合理搭配各層次人員，做到年齡、學歷、資 歷、氣質(zhì)及技能互補，使工作互不重疊、互不干擾，既能保證重點，又能照顧一般 。 國內(nèi)研究現(xiàn)狀 由于 國內(nèi)的研究 大部分 都停留在定性方面， 從 排班類型，排班原則，排班方式三個方面進行總結(jié)。 護士排班研究屬于護理研究的 一部分。 護士排班問題已經(jīng)成為醫(yī)院管理的核心內(nèi)容之一。運用計算機算法生成排班表，既能提高準確度又提高了效率。 護理人力資源與病人期望非常不平衡，臨床護士編制嚴重不足，護士班次更換頻繁，病人沒有相對固定的護理人員，整體護理難以真正落實到位，如何通 過 管理合理使用人力資源，從而解決人力短缺問題，值得我們不斷探討與研究 [2]。 護士是一種需要經(jīng)過專業(yè)訓練的人力資源、是醫(yī)院日常運營的基礎(chǔ)。 然后 探討用模擬退火算法求解護士排班問題。 護士排班是基層護理者的一項經(jīng)常性工作，是在現(xiàn)有的人力資源基礎(chǔ)上，對護理工作任務(wù)、內(nèi)容、程序、人力、和時間因素通盤考慮，做出系統(tǒng)、科學地安排，使護理人員明確職責，工作效率得到提高，保證醫(yī)院護理質(zhì)量，同時降低人力資源成本 [1]。基于模擬退火的護士排班算法研究 摘要 隨著經(jīng)濟的發(fā)展， 國內(nèi)外醫(yī)療問題越來越受注。 科學合理的