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