【正文】 護(hù)士需求數(shù)沒有得到滿足。 直到該班次相應(yīng)級(jí)別的需求得到滿足。 4 基于模擬退火的護(hù)士排班算法 實(shí)現(xiàn)與 案例分析 上一章 講述了基于模擬退火的護(hù)士排班算法的設(shè)計(jì)，本章詳細(xì)講述算法的程序?qū)崿F(xiàn)。再設(shè)計(jì)模擬退火的算法程序。 pref[i][j]表示第 i 個(gè)護(hù)士 對(duì) 第 j 個(gè)班次 的偏好程度， 取值 1,2,3,4,5 分別對(duì)應(yīng)非常喜歡，喜歡，一般，不喜歡，非常不喜歡五個(gè)等級(jí)。 二維數(shù)組 demand[3][21]表示每個(gè)班次對(duì)于每種護(hù)士的需求 ， 設(shè)計(jì)為整型變量 。 可分為兩部分 調(diào)整。 函數(shù) Solution generate_solution(Solution cur) 用于產(chǎn)生新解。 結(jié)果 分析 利用背景 中的數(shù)據(jù)，代入程序中運(yùn)行可以看到結(jié)果。如果能找到更好的鄰域結(jié)構(gòu)將會(huì)取到更好的效果。和沈老師的接觸已經(jīng)將近兩年了，沈老師 對(duì)教學(xué)的熱情和嚴(yán)謹(jǐn)?shù)难芯烤駥?duì)我的影響很大，讓我明白了做研究的人要有什么樣的態(tài)度。 Third International Conference,Konstanz, Springer, 2021, 159–175. [34] . Beddoe, S. Petrovic, G. Vanden Berghe: Casebased reasoning in employee rostering: learning repair strategies from domain ex。 然后要感謝我的家人，是他們的默默付出和無私支持讓我完成了學(xué)業(yè)。如果允許接受不可行解，并且能保證最后的收斂到可行的最優(yōu)解，將會(huì)更好。 初始可行解的總費(fèi)用為 ，如 圖 4 1 圖 4 1 初始可行解 有了初始解后，接下來就是不斷的進(jìn)行迭代，窗體中顯示了優(yōu)化過程中best_solution 的總費(fèi)用的變化過程。 函數(shù) bool accept(Solution cur, Solution new_solution, double T)用于判斷是否接受產(chǎn)生的新解，形參為當(dāng)前解 cur 和新解 new_solution，以及退火溫度 T,返回值為布爾型， 1 表示接受， 0 表示不接受。 函數(shù) void Calculate_cost() 計(jì)算費(fèi)用和懲罰值 。 取值見 表 4 1 。 grade[i]表示對(duì) i個(gè)護(hù)士的級(jí)別，取值 1,2,3 分別對(duì)應(yīng)低級(jí)，中級(jí)和高級(jí)護(hù)士。首先要用計(jì)算機(jī)里面的數(shù)據(jù)來表示實(shí)際問題的 變量。 案例背景 湖南省 某市級(jí)醫(yī)院某科室 [46]有 28 位護(hù)士，其中高、中、低級(jí)別護(hù)士分別為 1 10 位。 第一種 可表示為 讓 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)則中被淘汰。 對(duì)于第一種情況，搜索出該護(hù)士沒有當(dāng)班次天數(shù)，然后隨機(jī)將早中晚其中的 一個(gè)班次賦值為 1，如果是早班的話就要先考慮之前的晚班是否當(dāng)班。由此就可以形成一個(gè)初始方案，即得到一個(gè)初始解。 初始解的生成 護(hù)士排班問題的解 用一個(gè) n*m 的矩陣表示，其中每個(gè)元素取值為 0 或者 1。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S(是算法迭代的起點(diǎn) )無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 第二步是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。根據(jù)Metropolis 準(zhǔn)則，粒子在溫度 T 時(shí)趨于平衡的概率為 eΔE/(kT)，其中 E 為溫度T 時(shí)的內(nèi)能， ΔE 為其改變量， k 為 Boltzmann 常數(shù)。 第一，每一個(gè)排班周期內(nèi)，每位護(hù)士的最長(zhǎng)工作時(shí)間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。 表 2 1 排班表 星期 護(hù)士序號(hào) 周日 周一 周二 周三 周四 周五 周六 1 2 … N 護(hù)士排班問題整數(shù)規(guī)劃模型 針對(duì)上述護(hù)士排班問題，本節(jié)將 建立一個(gè)帶有一系列勞動(dòng)法規(guī)約束的且考慮護(hù)士級(jí)別差異的護(hù)士排班整數(shù)規(guī)劃模型。在該問題中，每位護(hù)士都應(yīng)有一個(gè)特定的護(hù)士級(jí)別，并且規(guī)定級(jí)別高的護(hù) 士允許替代級(jí)別低的護(hù)士進(jìn)行工作，反之不行。 第 2章首先對(duì)護(hù)士排班問題進(jìn)行了詳細(xì)描述，然后建立了護(hù)士排班問題的數(shù)學(xué)模型，建立了考慮護(hù)士級(jí)別和偏好的整數(shù)規(guī)劃模型。定義 多 個(gè)目標(biāo)也是常見的 ，如[23,24,25,26,27,28]。 班次分 類、 排班原則 和排班方法 都是 一些定性方面的研究，隨著研究的不斷深入，也產(chǎn)生了很多定量化的研究，用到了不少科學(xué)方法。 對(duì)于 排班方式 ， 戴琴、周力 等 [910]提出 按功能制護(hù)理模式排班實(shí)行全院統(tǒng)一排班的方式，按功能制護(hù)理方式分配崗位，按崗位配備護(hù)士，由白班、中班、前夜班、后夜班組成，每名護(hù)士 1個(gè)班次值 l d，循環(huán)進(jìn)行。 國(guó)內(nèi)研究現(xiàn)狀 由于 國(guó)內(nèi)的研究 大部分 都停留在定性方面， 從 排班類型，排班原則，排班方式三個(gè)方面進(jìn)行總結(jié)。 護(hù)士排班問題已經(jīng)成為醫(yī)院管理的核心內(nèi)容之一。 護(hù)理人力資源與病人期望非常不平衡，臨床護(hù)士編制嚴(yán)重不足，護(hù)士班次更換頻繁，病人沒有相對(duì)固定的護(hù)理人員，整體護(hù)理難以真正落實(shí)到位，如何通 過 管理合理使用人力資源，從而解決人力短缺問題，值得我們不斷探討與研究 [2]。 然后 探討用模擬退火算法求解護(hù)士排班問題?；谀M退火的護(hù)士排班算法研究 摘要 隨著經(jīng)濟(jì)的發(fā)展， 國(guó)內(nèi)外醫(yī)療問題越來越受注。 本文首先 對(duì)護(hù)士排班問題建立整數(shù)規(guī)劃模型， 考慮護(hù)士級(jí)別和偏好 ，在 減少醫(yī)院成本的同時(shí)，盡量滿足護(hù)士對(duì)于班次的偏好。但是在我國(guó)管理機(jī)構(gòu)對(duì)護(hù)士資源的重視度尚不夠，致使很多地方出 現(xiàn)護(hù)士嚴(yán)重不足的問題。 護(hù)士排班是基層護(hù)理者的一項(xiàng)經(jīng)常性工作，是在現(xiàn)有的人力資源基礎(chǔ)上，對(duì)護(hù)理工作任務(wù)、內(nèi)容、程序、人力、和時(shí)間因素通盤考慮，做出系統(tǒng)、科學(xué)地安排，使護(hù)理人員明確職責(zé)，工作效率得到提高，保證醫(yī)院護(hù)理質(zhì)量，同時(shí)降低人力資源成本 [1]。 對(duì)于護(hù)士排班問題 ，國(guó)外的研究 較早 ，很多人用了很多科學(xué)方法來優(yōu)化，而國(guó)內(nèi)的研究 較少 ， 很多都停留在手工排班方法 ，用算法優(yōu)化的比較少。 茍艷梅 等 [8]提出 人性化原則 :護(hù)士并非單一角色，除工作中的職業(yè)角色外，還有社會(huì)角色，應(yīng)以入為本，盡量滿足護(hù)士的合理要求。做到年齡、學(xué)歷、資歷、氣質(zhì)、技能及能力互補(bǔ)，形成團(tuán)隊(duì)合力，揚(yáng)長(zhǎng)避短，全員參與管理。后來 很多學(xué)者采用啟發(fā)式算法（如 [18,19,20,21,22]）。通過查閱相關(guān)文獻(xiàn)，基本把握了當(dāng)前國(guó)內(nèi)外護(hù)士排班問題的研究現(xiàn)狀，從而確定了自己的研究方向。 護(hù)士排班問題 本文研究的護(hù)士排班問題是指：給定一個(gè)排班周期（如：一周）內(nèi)的全部護(hù)理工作，并且給定一組具有不同級(jí)別的護(hù)士，要求滿足一系列勞動(dòng)法規(guī)等約束，編制出一個(gè)最有效（即成本最低）的護(hù)士排班方案。如果表中的方案能夠滿足上述全部約束，則為可行方案，否則為不可行方案。 公式如（ 3 1） ： ? ?11m in 1 0 1nmi j i j i j i jij c x p x? ? ? ? ? ??? ? ? ? ??? ， ， ， （ 3 2） ? 表示工資成本占的比重， ? 表示偏好成本占的比重，兩者之和為 1 約束條件可以分為三類。 模擬退火算法概述 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡(jiǎn)單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。而當(dāng)新解被判定為舍棄時(shí)，則 在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。 圖 3 1 算法框架 本章接下來的小節(jié)將對(duì)圖里面的各個(gè)環(huán)節(jié)進(jìn)行詳細(xì)闡 述。 每位護(hù)士的工作級(jí)別直接賦值為其自身的級(jí)別，這樣可以保證_ ij iw ork grad e s?的約束。 對(duì)于這兩種情況， 可以分別用增加班次和增加護(hù)士?jī)煞N 方法進(jìn)行調(diào)整，具體描述如下。 新解的產(chǎn)生 任意選一個(gè)護(hù)士和一個(gè)班次， 可以通過讓護(hù)士 從 當(dāng) 該 班 變成不當(dāng)該班 或者 從不當(dāng)該班變成當(dāng)該班 ， 也 讓護(hù)士從當(dāng)一個(gè)班換到另一個(gè)班，讓一個(gè)護(hù)士代替另一個(gè)護(hù)士當(dāng) 這 個(gè)班，三種方法實(shí)現(xiàn) 。 算法已經(jīng)在 C++ builder 環(huán)境中實(shí)現(xiàn)， 并 結(jié)合 案例分析 驗(yàn)證算法的有效性。 類 的設(shè)計(jì) 將實(shí)際問題 抽象到計(jì)算機(jī)里面。 一維數(shù)組 grade[28]表示護(hù)士的工作級(jí)別 ，設(shè)計(jì)為整型變量。 demand[i][j]表示對(duì) j 個(gè)班次對(duì)于第 i 個(gè)級(jí)別護(hù)士的需求。 第一部分使得護(hù)士需求數(shù)得到滿足 ，第二部分使得護(hù)士的最低工作天數(shù)得到滿足。 Cur 為輸入的當(dāng)前解，在當(dāng)前解的基礎(chǔ)上產(chǎn)生新解，并把新解作為返回值。 由于算法是隨機(jī)去更新 解 ，算法效率不高，要將近十分鐘才能運(yùn)行完畢。 第二，本研究迭代只接受可行解，原因是當(dāng)我的算法接受不可行解時(shí)，最后的解都會(huì)是不可行的。在指導(dǎo)畢業(yè)設(shè)計(jì) 的過程中， 從文獻(xiàn)翻譯、算法設(shè)計(jì)、 程序設(shè)計(jì)、 論文撰寫，沈老師都給了我細(xì)致的指導(dǎo)，讓我受