【文章內(nèi)容簡介】 不能超過規(guī)定的上限，亦不能少于規(guī)定的下限 ； 3） 每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且任何護 士不允許進行要求比自己級別高的護士的護理工作，反之可以； 4） 上了晚班后，另一天不能上早班 。 對于違反這些約束的行為在程序設(shè)計的時候都將記入懲罰值，視為影響方 案 的因素。 現(xiàn)在給定 N 個護士，可以用一個二維表格 [46]（如 （ 3 2） 所示） 來表示一個 護士排班方案。其中， 每個空格處填上為每位護士安排 早班、中班、晚班、休班的一種。如果表中的方案能夠滿足上述全部約束，則為可行方案，否則為不可行方案。 表 2 1 排班表 星期 護士序號 周日 周一 周二 周三 周四 周五 周六 1 2 … N 護士排班問題整數(shù)規(guī)劃模型 針對上述護士排班問題，本節(jié)將 建立一個帶有一系列勞動法規(guī)約束的且考慮護士級別差異的護士排班整數(shù)規(guī)劃模型。 整數(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 位護士的級別。記排班周期為 T；記 J={1,2， …,m}表示一個周期 T 內(nèi)的班次集合；記 Wtup 和 WTlow 分別表示一個排班周期內(nèi)的護士的總工時的上限和下限。上限不小于下限。 ijc 表示第 i 位護士進行第 j 個班次的工資成本（簡稱成本，用護士的等級表示）； gjD 表示第 j 班次對第 g 級別護士的需求數(shù)量。 ijP 表示第 i 個護士對第 j 個班次的偏好程度。對于偏好程度設(shè)置五個等級：非常喜歡，喜歡，一般，不喜歡，非常不喜歡，依次用 1 到 5 五個數(shù)字表示，并定義ijP ?{1,2,3,4,5}； 模型的目標(biāo)函數(shù)為使總費用最小，總費用為工資成本加上偏好成本。 公式如（ 3 1） ： ? ?11m in 1 0 1nmi j i j i j i jij c x p x? ? ? ? ? ??? ? ? ? ??? ， ， ， （ 3 2） ? 表示工資成本占的比重， ? 表示偏好成本占的比重，兩者之和為 1 約束條件可以分為三類。 第一，每一個排班周期內(nèi)，每位護士的最長工作時間不能超過規(guī)定的上限，亦不能少于規(guī)定的下限。 對應(yīng)公式如 (3 3)： WTlow?1mijj x??? WTup i=1,2,…,n (3 4) 第二，每日工作的各種級別的護士數(shù)都不允許少于規(guī)定的需求數(shù)，并且 任何護士不允許進行要求比自己級別高的護士的護理工作，反之可以； 對應(yīng)公式如 (3 5)： 11 , 2 , . . . 。 1 , 2 , . . .n i j g i j g jq x D j m g u? ? ?? (3 6) 10{ igijgq ? 如 果 第 位 護 士 上 第 j 個 班 次 的 實 際 工 作 級 別 是否 則 第三， |每位護士一日最多只能進行一個班次的工作；對應(yīng)公式如（ 3 7） ： /1,*0 1 1 , 2 , . . . , 。 1 , 2 , . . . ,mTi j k Tk x i n j T??? ? ? ?? （ 3 8） 其中， 10{ ijijx ? 第 個 護 士 做 第 個 班 次否 則 第四，上了晚班后不能接著上另一天的早班。對應(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ù)學(xué)建 模，由于隨著護士數(shù)的增加，用傳統(tǒng)的線性規(guī)劃方法會陷入“維數(shù)災(zāi)” 。 元 啟發(fā)式算法這種時候就能取到很好的作用。本章主要講述基于模擬退火的護士排班算法，首先介紹模擬退火算法，然后將模擬退火算法用到護士排班問題。 模擬退火算法概述 模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis 準(zhǔn)則，粒子在溫度 T 時趨于平衡的概率為 eΔE/(kT)，其中 E 為溫度T 時的內(nèi)能， ΔE 為其改變量， k 為 Boltzmann 常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能 E 模擬為目標(biāo)函數(shù)值 f，溫度 T 演化成控制參數(shù) t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解 i 和控制參數(shù)初值 t 開始，對當(dāng)前解重復(fù) “產(chǎn)生新解 → 計算目標(biāo)函數(shù)差 → 接受或舍棄 ”的迭代，并逐步衰減 t 值，算法終止時的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機搜索過程。退火過程由冷卻進度表 (Cooling Schedule)控制，包括控制參數(shù)的初值 t 及其衰減因子 Δt、每個 t 值時的迭代次數(shù) L 和 停止條件 S。 模擬退火算法可以分解為解空間、目標(biāo)函數(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′作為新的當(dāng)前解，否則以概率 exp(Δt′/T)接受 S′作為新的當(dāng)前解 . (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解， 結(jié)束程序。 終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。 (7) T 逐漸減少，且 T0，然后轉(zhuǎn)第 2 步。 模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： 第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。 第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變 換部分產(chǎn)生，所以目標(biāo)函數(shù)差的 計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。 第三步是判斷新解是否被接受 ,判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是 Metropo1is 準(zhǔn)則 : 若 Δt′0則接受 S′作為新的當(dāng)前解 S，否則以概率exp(Δt′/T)接受 S′作為新的當(dāng)前解 S。 第四步是當(dāng)新解被確定接受時，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標(biāo)函數(shù)值即可。此時，當(dāng)前解實現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當(dāng)新解被判定為舍棄時，則 在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài) S(是算法迭代的起點 )無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率 l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。 基于模擬退火的護士排班算法設(shè)計 為便于闡述的方便這里先說明一個符號， _ ijwork grade 表示第 i 個護士做第 j 個班次的工作級別 ，它不允許高于護士的實際級別。 _ ij iw ork grad e s?。 基于護士排 班的算法框架跟模擬退火的算法框架大致相同，但是由于護士排班問題的具體特征，也會有些特殊的地方，比如方案的可行化過程。對于很多問題要得到初始可行解很簡單，但是對于護士排班問題，得到初始可行解往往是很復(fù)雜的，所以算法框架中，方案的可行化是重要的一個步驟。 算法的流程可以分為生成初始方案，可行化初始方案，生成新方案，判斷是否接受新方案，判斷是否滿足終止準(zhǔn)則。 算法 流程 描述如 圖 3 1 。 圖 3 1 算法框架 本章接下來的小節(jié)將對圖里面的各個環(huán)節(jié)進行詳細闡 述。 初始解的生成 護士排班問題的解 用一個 n*m 的矩陣表示，其中每個元素取值為 0 或者 1。每天有 m/T 個班次，前面 T 個班為第一類班次（如早班），最后面 T 個班次為最后一類班次（如晚班）。 每天依次從早班、中班、夜班、和休班中隨機選擇一個班型。 若選中的是早班，相應(yīng)的班次該護士請假，或者其工作班次數(shù)也 已經(jīng) 達到最大值 ，則該天的三個班型都賦值為 0。否則，如果該早班之前的晚班該護士不當(dāng)班，則該班次賦值為 1，當(dāng)天的中班和晚班賦值為零；如果該早班 之前的晚班該護士當(dāng)班，則去查看該護士能否當(dāng)中班或者晚班。 若選中的是中班或者晚班，相應(yīng)的班次該護士請假，或者其工作班次數(shù)也已經(jīng)達到最大值，則該天的三個班型都賦值為 0。否則，該班次賦值為 1，當(dāng)天的其他班賦值為零； 若選中的是休班，那么該天的三個班次都賦值為零。 每位護士的工作級別直接賦值為其自身的級別，這樣可以保證_ ij iw ork grad e s?的約束。由此就可以形成一個初始方案，即得到一個初始解。 由于考慮到對各個級別的護士的需求數(shù)等約束，還有可能某些護士沒有達到最低班次數(shù)，初始解可能 是不可行的。需要先將之可行化，然后再不影響可行性的情況下，進行模擬退火的迭代過程。 并且該早班之前的晚班該護士不當(dāng)班，其工作班次數(shù)也