陸志強，許則鑫，任逸飛

（同濟大學(xué) 機械與能源工程學(xué)院，上海 201804）

資源投入問題（resource investment problem，RIP）是一種經(jīng)典的項目調(diào)度問題，其目標(biāo)是優(yōu)化人力資源的投入，使其成本最小化。然而人力資源作為一種重要的生產(chǎn)資源，在實際生產(chǎn)中，如飛機移動裝配線，是以排班的形式進行生產(chǎn)作業(yè)的，因此資源的投入會受排班的影響。此時，調(diào)度的關(guān)鍵在于合理地安排作業(yè)和排班，從而確定每個班次的作業(yè)調(diào)度計劃和資源投入情況，使得總體的人力資源投入最小化。在本文中，這一問題被稱之為考慮人力資源排班的人力資源投入問題（resource investment problem based on employee-timetabling，RIP-ET），其本質(zhì)上是資源投入和人力資源排班（employee timetabling problem，ETP）的整合問題。與傳統(tǒng)的RIP問題相比，RIP-ET問題有以下幾項難點：RIPET需要考慮工人排班的約束；RIP-ET不僅要決策作業(yè)的開始時間，而且還要決策作業(yè)投入的每個工人；對于RIP-ET問題，每個班次的資源投入是可變的，由于排班約束，班次之間存在資源占用情況；與RIP問題優(yōu)化目標(biāo)為資源峰值不同，該問題的目標(biāo)是降低投入整個項目的人數(shù)。由于RIP-ET問題與傳統(tǒng)RIP的決策范圍與約束范圍不同，現(xiàn)有的模型和算法無法適用，因此，對RIP-ET問題的建模與算法研究具有重要的理論與實際意義。

RIP是從經(jīng)典的項目調(diào)度問題（resource constrained project scheduling problem，RCPSP）中衍生而來，問題的目標(biāo)是在給定工期的情況下求解資源投入的最小值。M?hring［1］首先提出了資源投入問題，證明了該問題是NP-hard問題，同時證明了RIP與單模資源約束項目調(diào)度問題（single mode resource constrained project scheduling problem，SMRCPSP）的對偶關(guān)系。Demeulemeester［2］將 RIP轉(zhuǎn)化為多個SMRCPSP，提出了MBA（minimum bounding algorithm）精確算法。Rangaswamy［3］提出了一個分支定界算法，進一步提高了算法的求解效率。由于精確算法在求解大規(guī)模問題上具有局限性，很多學(xué)者在此問題上設(shè)計了不同的啟發(fā)式算法來進行求解。Yamashita等［4］將RIP轉(zhuǎn)化為RCPSP問題，通過基于Scatter Search的元啟發(fā)式算法求解該問題；Shadrokh等［5］采用遺傳算法求解帶有延遲懲罰的資源投入問題，分別對作業(yè)優(yōu)先級和資源容量進行編碼。Ranjbar等［6］首次在沒有將RIP問題轉(zhuǎn)化為RCPSP的基礎(chǔ)上，通過路徑重連和遺傳算法來求解該問題。但是其算法可能會產(chǎn)生優(yōu)先級不可行的作業(yè)列表，也會產(chǎn)生算法效率問題，而且在對作業(yè)進行調(diào)度時，并沒有考慮到當(dāng)前選擇對全局資源投入的影響。Zhu等［7］在此基礎(chǔ)上提出了一種多啟動迭代搜索算法（multi-start iterative search method），該算法有效地提高了RIP解的質(zhì)量。針對資源投入問題，許多學(xué)者還在此基礎(chǔ)上進行了擴展性的研究［8-10］。本文提出的考慮排班的人力資源投入問題就是其中的一種。

人力資源排班是將具有特殊技能的人力資源分配到特定的班次，以滿足特定時間段的服務(wù)需求。隨著人力資源排班用于各種領(lǐng)域，人力資源排班的形式也呈現(xiàn)多樣化。由于工作內(nèi)容的不同，Baker［11］首次提出了人力資源分配的分類方法，將其分為輪班調(diào)度、日程安排和行程安排三類。Kletzander等［12］針對排班問題中的各種約束提出了一種適用性框架，并在此框架上提出了一種通用的模擬退火算法。但是在現(xiàn)有的文獻中，大多只關(guān)注于人力資源的輪班順序或工作時間表，很少將人力資源調(diào)度與其他調(diào)度（例如機器調(diào)度、車輛調(diào)度、生產(chǎn)調(diào)度、手術(shù)室調(diào)度等）結(jié)合在一起研究。然而，在一個實際的生產(chǎn)活動中，人力資源的排班往往需要與生產(chǎn)項目的調(diào)度結(jié)合起來統(tǒng)籌考慮，正如Bergh等［13］提到的，這也是未來一個主要的研究方向。Daniels等［14］假定每個作業(yè)必須由作業(yè)人員操作機器才能執(zhí)行，將流水作業(yè)調(diào)度與人力資源排班整合起來。Drezet等［15］在資源受限的項目調(diào)度環(huán)境中考慮了人力資源排班，并提出一種預(yù)測算法來處理該問題。Artigues等［16］和Guyon等［17］采用了不同的精確算法對車間調(diào)度和人力資源排班的整合問題進行了求解。Smet等［18］將作業(yè)調(diào)度與排班問題結(jié)合起來，將任務(wù)與班次同時分配給員工。Eeckhout等［19］提出了一種新的迭代局部搜索方法，解決資源受限項目調(diào)度中的人員配置問題。由于車間調(diào)度、作業(yè)調(diào)度與資源投入項目調(diào)度具有一定的相似性，這對研究項目調(diào)度與人力資源排班的整合問題具有借鑒意義。不過，目前還沒有關(guān)于RIP與人力資源排班的整合問題的研究。

RIP作為RCPSP的一個衍生問題，也是一種經(jīng)典的項目調(diào)度問題，經(jīng)常應(yīng)用于實際項目決策中，它本身也對RIP-ET的研究具有很重要的意義。本文研究的RIP-ET除了考慮RIP的特性之外，還需要考慮人力資源排班約束，具有較高的復(fù)雜度，精確算法在求解這類大規(guī)模的問題時效率較低。遺傳算法由于具有較好的全局搜索能力，在RIP中得到了很好的使用［20-23］。由于排班約束會導(dǎo)致班次間的資源搶占，故采用作業(yè)優(yōu)先級和資源編碼的方式對于該問題無法取得較優(yōu)解。因此，本文采用了對作業(yè)開始時間進行搜索的遺傳算法。

在分析現(xiàn)有文獻中人力資源投入問題與人力資源排班問題和遺傳算法的基礎(chǔ)上，本文以最小化人力資源投入作為目標(biāo)，從實際生產(chǎn)活動的決策需求出發(fā)，建立了RIP-ET的數(shù)學(xué)模型。通過分析，將該整合問題拆分為了人力資源投入和人力資源排班問題，并且設(shè)計了一種新型編碼方式的遺傳算法，通過對作業(yè)延遲時間進行編碼的方式，對作業(yè)的開始時間進行全局搜索，此外還對作業(yè)延遲時間和開始時間進行局部優(yōu)化。

1 問題描述及建模

記一個項目由若干項作業(yè)構(gòu)成，j={1，2，3，…，n}為項目的作業(yè)集合。其中，1、n為虛任務(wù)不占用時間和資源，j∈J為作業(yè)編號，其標(biāo)準(zhǔn)作業(yè)時間為tj；全部作業(yè)共需要K種人力資源進行作業(yè)，資源集合R={1，2，…，K}，k∈R為人力資源種類編號，其中第k種人力資源對應(yīng)的單價為ck；定義m∈Mk為第k種人力資源中的工人編號，集合Mk={1，2，…，M}表示第k種人力資源的集合，同時假設(shè)同類資源下的所有資源不具有差異性。

項目的總工期為-T，每個班次8 h，將項目分為U個班次，定義班次集合為W={1，2，…，U}，w∈W為班次編號，對于每個工人，規(guī)定在連續(xù)的3個班次中只能工作1個班次。假設(shè)作業(yè)從開始到結(jié)束不得中斷，當(dāng)班次結(jié)束時，若當(dāng)前作業(yè)未完成，不允許工人加班，必須換上相同數(shù)目的同類工人繼續(xù)該工作。在實際的人力資源排班中，很多情況下使用的是三班制排班。在文本中，不妨也使用三班制排班，假設(shè)每個班次8 h，將1 d分為3個班次。

Pj為作業(yè)j的緊前作業(yè)的集合，i∈Pj表示作業(yè)i為作業(yè)j的緊前作業(yè)；rjk表示作業(yè)j對第k種人力資源的需求量。對時間進行離散化，d∈D為離散時間點，D={1，2，…，T}，T為項目的實際完工時間。

定義決策變量如下：

xjd——0，1變量，作業(yè)j在d時刻處于執(zhí)行狀態(tài)為1，否則為0；

hjdkm——0，1變量，第k種人力資源中的第m號工人在時間d執(zhí)行作業(yè)j則為1，否則為0。

定義中間變量如下：

λwkm——0，1變量，第k種人力資源中的第m號工人在第w班次中進行作業(yè)則為1，否則為0；

?km——0，1變量，第k種人力資源中的第m號工人投入了整個項目則為1，否則為0。

RIP-ET問題P1的數(shù)學(xué)模型如下：

目標(biāo)函數(shù)為

傳統(tǒng)RIP約束為

排班約束為

決策變量可行域為

其中，式（1）為最小化人力資源的投入；式（2）表示作業(yè)的執(zhí)行時間等于作業(yè)工期；式（3）為優(yōu)先關(guān)系約束；式（4）為項目工期約束；式（5）表示任務(wù)一旦開始就不能中斷；式（6）為資源約束；式（7）為決策變量hjdkm與中間變量λwkm的關(guān)系；式（8）為人力資源排班約束，單個個體的人力資源在連續(xù)3個班次中只能工作1個班次；式（9）表示中間變量λwkm與中間變量?km的關(guān)系；式（10）表示定義所有決策變量中間變量的可行域。

2 問題分析與簡化

上節(jié)給出問題P1的數(shù)學(xué)模型，是對作業(yè)調(diào)度與人力資源排班進行同時決策，需要在滿足排班約束下求出人力資源投入的最小值。然而，通過分析發(fā)現(xiàn)，由于同種人力資源中每個個體之間不存在差異性，因此對于k類人力資源，總有：

性質(zhì)1 考慮排班約束下的總投入總是等于不考慮排班約束下最大的連續(xù)3個班次的總投入。即，其中l(wèi)kw為第k種人力資源在班次w的投入數(shù)量。

證明 假設(shè)所有作業(yè)的開始和結(jié)束時間已經(jīng)確定，對于k類人力資源，假設(shè)有，其中w'為一個特定的班次，令。首先證明lkw'+lk(w'+1)+lk(w'+2)的人數(shù)在滿足工人休息的情況下能夠滿足作業(yè)要求，即lkw'+lk(w'+1)+lk(w'+2)≥mk。由已知可得：lkw'≥lk(w'+3)，表示對于w'+3班次對人力資源的需求可以由w'班次釋放的工人來滿足，從而可以推理得到lk(w'+4)≤lkw'+lk(w'+1)-lk(w'+3)，lk(w'+5)≤lkw'+lk(w'+1)+lk(w'+2)-lk(w'+3)-lk(w'+4)，由數(shù)學(xué)歸納法可以得到，對于w∈W，lk(w)≤lkw'+lk(w'+1)+lk(w'+2)-lk(w-1)-lk(w-2)，即lkw'+lk(w'+1)+lk(w'+2)≥mk，得證。第二步，證明lkw'+lk(w'+1)+lk(w'+2)≤mk，使用反正法證明。若lkw'+lk(w'+1)+lk(w'+2)＞mk，由于不等式兩邊都是正整數(shù)，可以假設(shè)mk=lkw'+lk(w'+1)+(lk(w'+2)-1），此時在w'+2班次中由于人力資源不足，無法進行作業(yè)，則是錯誤的，即，得證。從而可得。

根據(jù)性質(zhì)1，發(fā)現(xiàn)求解原問題P1可以轉(zhuǎn)化為：先根據(jù)項目調(diào)度計算每個班次需要投入人力資源的數(shù)量，進而計算最終的人力資源投入。本文將這個問題稱之為問題P2。得到最優(yōu)的人力投入之后，再根據(jù)每個班次的需求量對人力資源進行排班，這個問題稱之為問題P3。因此，對原問題P1的求解，變成了求解問題P2與問題P3。針對問題P2，建立如下的數(shù)學(xué)模型。

定義決策變量如下：

xjd——0，1變量，作業(yè)j在d時刻處于執(zhí)行狀態(tài)為1，否則為0；

ykd——整數(shù)變量，第k種人力資源在時間d的投入數(shù)量。

定義中間變量如下：

lkw——整數(shù)變量，第k種人力資源在班次w的投入數(shù)量。

目標(biāo)函數(shù)：

其中，式（11）為最小化人力資源投入；式（12）表示作業(yè)的執(zhí)行時間等于作業(yè)工期；式（13）為優(yōu)先關(guān)系約束；式（14）為工期約束；式（15）表示任務(wù)一旦開始就不能中斷；式（16）為資源約束；式（17）表示中間變量lkw與決策變量ykd之間的關(guān)系；式（18）表示決策變量xjd、ykd和中間變量lkw的定義域。

問題P3是對工人的工作班次進行分配，在不考慮資源均衡的情況下，并沒有目標(biāo)函數(shù)。問題的決策變量和模型如下：

λwkm——0，1變量，第k種工人中的第m號工人在第w班次中工作則為1，否則為0。

其中，式（19）表示單個工人在連續(xù)3個班次內(nèi)只能工作1個班次；式（20）表示決策變量λwkm與問題P2中間變量lkw的關(guān)系。

為了驗證問題簡化的有效性，使用CPLEX對測試問題庫中的小算例進行求解，來對比兩種建模方式求解的速度。設(shè)定資源種類K=4，任務(wù)工期-T設(shè)置為由關(guān)鍵鏈方法（critical path method，CPM）得出的項目工期的1.2倍。表1和表2分別表示在10 jobs、14 jobs下兩種建模方式求解結(jié)果。其中，jobs表示項目的作業(yè)數(shù)量。A1和A2分別為對問題P1和轉(zhuǎn)化后問題P2、P3計算所得的目標(biāo)函數(shù)值。T1為求解P1花費的時間，T2為求解P2和P3一共花費的時間，設(shè)置算法的最大運行時間為3 600 s。表2中，A列中“—”表示CPLEX沒有求出最優(yōu)解，T列中“—”表示CPLEX運行時間超過3 600 s自動停止。

表1 10 jobs實驗結(jié)果Tab.1 Scheduling result of 10 jobs

表2 14 jobs實驗結(jié)果Tab.2 Scheduling result of 14 jobs

從實驗對比可以發(fā)現(xiàn)，將問題轉(zhuǎn)換之后，使用CPLEX求解的速度顯著提升，因此將原問題轉(zhuǎn)換為問題P2與問題P3在小規(guī)模的求解中是很有必要的。

3 算法設(shè)計

針對RIP-ET的特點，本文設(shè)計了一種對作業(yè)開始時間進行搜索的遺傳算法，可以有效避免RIP在考慮工人排班時帶來的難點。采用這種編碼方式可以通過解碼直接求出各個作業(yè)的開始時間，進而根據(jù)式（11）求出人力資源的投入量，解碼過程中并不需要通過控制可用資源和作業(yè)的優(yōu)先級來決策作業(yè)的開始時間。

Najafi等［24］通過CPM求出所有作業(yè)的最早開始時間，提出了對作業(yè)最早開始時間的浮動時間的編碼方法。這種編碼方法解決了基于現(xiàn)金折現(xiàn)的RIP，同時還提出了如何在解生成中避免出現(xiàn)不可行解。對作業(yè)開始時間的浮動時間進行編碼，雖然可以有效避免排班帶來的資源搶占問題，但是在生成下一代解時，變動性較小，容易陷入局部最優(yōu)解。因此，本文采用對作業(yè)延遲時間進行編碼的方式，并對作業(yè)延遲時間和開始時間同時進行局部優(yōu)化。基于該問題設(shè)計了新的遺傳算法，有效地解決了該問題。對比文獻［24］的編碼方式，這種編碼方式能夠有效地避免解陷入局部最優(yōu)。需要強調(diào)的是，下文算法優(yōu)化的是總?cè)肆Y源投入，即針對問題P2所設(shè)計的算法，由于問題P3是一個簡單問題，因此求解不加以贅述。

3.1 染色體編碼

本文采用實數(shù)編碼方式，對每個作業(yè)的延遲開始時間進行編碼，編碼長度為n，分別對應(yīng)每一個作業(yè)的延遲開始時間，如圖1所示。通過確定每個作業(yè)的延遲開始時間調(diào)度項目中的所有作業(yè)。

圖1 作業(yè)延遲時間編碼Fig.1 Coding with work delay time

關(guān)于延遲開始時間的相關(guān)定義如下：

定義1 在作業(yè)1～（i-1）已經(jīng)調(diào)度的基礎(chǔ)上，作業(yè)i的延遲時間等于作業(yè)i的最早開始時間與實際開始時間tSTi的差值，即

式中：tSTi、tFTi表示作業(yè)i實際的開始、結(jié)束時間。

定義2 在所有作業(yè)的延遲時間D給定的情況下，作業(yè)i的最早開始時間tESi等于其最晚緊前任務(wù)的結(jié)束時間，即令D[i]=0時，作業(yè)i的開始時間，即

定義3 在所有作業(yè)的延遲時間D給定的情況下，作業(yè)i的最晚開始時間tLSi等于令最后一個任務(wù)的結(jié)束時間為項目工期，倒序所求出的作業(yè)i的開始時間，即

式中：Ssucc(i)表示作業(yè)i緊后任務(wù)的集合。

當(dāng)所有的延遲時間D都為0時，或者未賦值時，所有作業(yè)的最早（晚）開始時間tESi（tLSi）為不考慮資源使用的情況下，由關(guān)鍵鏈方法所求得的最早（晚）開始時間，當(dāng)某個作業(yè)延遲時間D給定時，其他作業(yè)的最早（晚）開始時間也會發(fā)生改變。

對于圖2所示的例子，假設(shè)作業(yè)的延遲時間為(0，2，1，1，0，1，0，0)，可以得到如圖 3 所示的項目調(diào)度。

圖2 項目的AON網(wǎng)絡(luò)的一個實例Fig.2 An example of AON network of a project

圖3 項目調(diào)度時間圖Fig.3 Scheduling time map of a given project

假設(shè)此項目的工期為15，通過逆向調(diào)度，將截止時間視為開始時間，結(jié)束任務(wù)作為開始任務(wù)，可得到項目逆向調(diào)度圖，如圖4所示。圖中作業(yè)的開始時間，即為上文所定義的最晚開始時間。

于是，項目中所有作業(yè)的最早開始時間、實際開始時間等見表3。

此外，考慮到解的可行性，對于一組延遲時間D，它必須滿足：對于任意作業(yè)i，該作業(yè)的延遲時間不能超過該作業(yè)的最晚開始時間與最早開始時間之差，即

圖4 項目逆向調(diào)度時間圖Fig.4 A project time map with reverse scheduling

表3 項目中各作業(yè)的時間Tab.3 Time of all works

對于染色體的評估，可以根據(jù)目標(biāo)函數(shù)計算染色體的適應(yīng)值。本文所采用的對作業(yè)延遲時間編碼的方式，可以有效地搜索所有作業(yè)可能的開始時間，通過確定所有作業(yè)的開始時間，來確定每個班次需要分配的資源。

3.2 初始解生成

采用正向和逆向兩種方法生成初始的染色體群。根據(jù)上文所提到的，要保證解的可行性，基因D[i]∈[0，tLSi-tESi]。于是，需要先求得作業(yè)i的最早開始時間與最晚開始時間，然后再給基因D[i]隨機賦值。為了防止先生成的D[i]過大，導(dǎo)致后續(xù)D[i]的取值受限。本文采用如圖5所示的三角分布對基因進行隨機賦值。下文中采用三角分布都是這個原因。

圖5 產(chǎn)生基因i的三角分布圖Fig.5 Triangular distribution for gene i generation

3.2.1 正向生成染色體

從作業(yè)1到作業(yè)n順序生成每個基因的值。算法步驟如下：

步驟 1 初始化D[i]=0，?i∈J，計算所有的tESi、tLSi。

步驟2 令i=1，在[0，1]中隨機選取一個小數(shù)θ

步驟3i=i+1，計算作業(yè)i的最早開始時間tESi，在 [0，1]中隨機選取一個小數(shù)θ，令

步驟4 若i=n，則停止運算，否則轉(zhuǎn)步驟3。

3.2.2 逆向生成染色體

從作業(yè)n到作業(yè)1逆向生成每個基因的值，算法的具體操作與正向生成染色體的操作類似。

3.3 染色體交叉

選取父代染色體P1、P2進行交叉，生成子代染色體C1、C2。子代染色體中的一部分直接復(fù)制父代的染色體，另外一部分通過2條父代染色體交叉得到。

定義4 在給定的調(diào)度基礎(chǔ)上，作業(yè)延遲時間的可減少值等于作業(yè)的實際開始時間減去作業(yè)最早的開始時間，即

定義5 在給定的調(diào)度基礎(chǔ)上，作業(yè)延遲時間的可增加值等于作業(yè)的最晚開始時間減去作業(yè)的實際開始時間，即

染色體交叉的算法步驟如下：

步驟1令C1［i］=P1［i］，C2［i］=P2［i］，?i∈J。

步驟2 對于父代P1、P2，計算所有作業(yè)延遲時間的可減少值和可增加值，記為NP1、FP1、NP2、FP2。

步驟3 在范圍[2，n-1]內(nèi)隨機生成一個整數(shù)q。

步驟4 在范圍[0，1]隨機生成一個小數(shù)ρ。若ρ＞0.5，轉(zhuǎn)步驟5，反之轉(zhuǎn)步驟9。

步驟5 令i=q。

步驟6 令i=i+1，對于子代C1、C2，計算作業(yè)i延遲時間的可減少值和可增加值，記為NC1[i]、FC1[i]、NC2[i]、FC2[i]。

步驟7 染色體的交叉步驟，根據(jù)上面得到的結(jié)果不同，可以分為幾下幾種情形。

情形1 當(dāng)NP2[i]＞0，F(xiàn)P2[i]＞0，即父代P2中作業(yè)i的可減少與可增加時間都大于0，令

情形 2 不滿足情形 1，并且NC2[i]＞0，F(xiàn)C2[i]＞0時。此時與C2交叉。即令

情形3 即不滿足情形1與情形2，此時DC1[i]取[0，NC1[i]+FC1[i]]中的隨機一個整數(shù)。

按照生成DC1[i]的交叉操作生成子代C2的第i個基因DC2[i]。

步驟8 若i=n停止運算，否則轉(zhuǎn)步驟6。

步驟9 令i=q。

步驟10 對于子代C1、C2，計算作業(yè)i延遲時間的可減少值和可增加值，記為NC1[i]、FC1[i]、NC2[i]、FC2[i]。

步驟11 重復(fù)步驟7的操作。

步驟12 若i=1則停止運算，否則令i=i-1轉(zhuǎn)步驟10。

3.4 染色體變異

選取染色體C進行變異，隨機選擇該染色體一部分的基因進行變異，其他部位的基因保持不變。與染色體的生成相似，計算作業(yè)i的F[i]、N[i]。采用三角分布對D[i]重新賦值。

染色體變異的算法步驟如下：

步驟1 從[1，n-1]隨機選擇兩個整數(shù)q1、q2，其中q2＞q1。

步驟2 從[0，1]隨機選取一個小數(shù)ρ，若ρ＞0.5，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟7。

步驟3 令i=q1。

步驟4i=i+1，對于染色體C，計算所有任務(wù)延遲時間的可減少值和可增加值，記為NC[i]、FC[i]。

步驟5 在[0，1]中隨機生成一個小數(shù)θ，D[i]=θ2·(FC[i]+NC[i])。

步驟6 若i=q2，運算結(jié)束，否則轉(zhuǎn)步驟4。步驟7 令i=q2。

步驟8 對于染色體C，計算作業(yè)i延遲時間的可減少值和可增加值，記為NC[i]、FC[i]。

步驟9 在[0，1]中隨機生成一個小數(shù)θ，。

步驟10 若i=q1，則停止運算，否則令i=i-1，轉(zhuǎn)步驟8。

3.5 局部優(yōu)化

為了提高解的適應(yīng)性，本節(jié)采用兩種局部優(yōu)化方法對作業(yè)的延遲時間和作業(yè)的開始時間進行優(yōu)化。

3.5.1 對作業(yè)延遲時間優(yōu)化

對于一個已經(jīng)給定的調(diào)度，每個作業(yè)都有一個延遲開始時間，改變作業(yè)延遲時間可以改變目標(biāo)函數(shù)的值。例如，對于圖3所示的項目調(diào)度時間圖，作業(yè)的延遲時間為(0，2，1，1，0，1，0，0)，作業(yè)2延遲時間的可增加值和可減少值分別為5和2。減少或者增加作業(yè)2的延遲時間，可以得到一個新的目標(biāo)函數(shù)值。

該局部優(yōu)化的算法步驟如下：

步驟1 令i=1，計算當(dāng)前調(diào)度下目標(biāo)函數(shù)值為A。

步驟2 計算作業(yè)i延遲時間的可增加值和可減少值F[i]、N[i]。

步驟3 從D[i]∈[0，F(xiàn)[i]+D[i]]中選擇使得目標(biāo)函數(shù)值最優(yōu)的D[i]，更新D[i]，A。若i=n，停止運算，否則令i=i+1轉(zhuǎn)步驟2。

3.5.2 對作業(yè)開始時間優(yōu)化

對于一個給定的調(diào)度，提前或推遲作業(yè)的開始時間可以改變目標(biāo)函數(shù)的值，通過對每個任務(wù)開始時間的優(yōu)化可以優(yōu)化整個項目的資源投入。

定義6 表示作業(yè)i在不影響其他作業(yè)的基礎(chǔ)上最早的可開始時間，等于所有緊前任務(wù)最晚的完成時間，即

式中：tFTj表示作業(yè)的實際完成時間。

定義7tlsi表示作業(yè)i在不影響后續(xù)作業(yè)開始時間的基礎(chǔ)上最晚可開始的時間，等于所有緊后任務(wù)最早的開始時間減去作業(yè)i的持續(xù)時間，即

該局部優(yōu)化的算法步驟如下：

步驟1 令i=1，計算當(dāng)前調(diào)度下目標(biāo)函數(shù)值為A。

步驟2 計算作業(yè)i最早開始時間和最晚開始時間tesi、tlsi。

步驟3 從tSTi∈[tesi，tlsi]中選擇使得目標(biāo)函數(shù)值最優(yōu)的tSTi，更新tSTi、A。若i=n，停止運算，否則令i=i+1轉(zhuǎn)步驟2。

4 數(shù)據(jù)實驗

為了驗證本文設(shè)計的采用對作業(yè)延遲時間編碼的遺傳算法（DTGA）的有效性，選取10 jobs、14 jobs、18 jobs、30 jobs、60 jobs、90 jobs，各10個算例進行數(shù)值實驗，與文獻中對采用作業(yè)浮動時間進行編碼的遺傳算法（FTGA）［24］進行比較。數(shù)值實驗在C#（Visual Studio 2017）語言環(huán)境下編程實現(xiàn)，測試平臺為Intel Core i5 4th處理器，2.40 GHz主頻，4G內(nèi)存，結(jié)果如表4至表7所示。其中，AD、AF、AC分別為該組算例在DTGA、FTGA和CPLEX下所求得平均目標(biāo)函數(shù)值，TD、TF、TC分別為平均運算時間，G1、G2分別為DTGA、FTGA所求目標(biāo)函數(shù)值與CPLEX最優(yōu)解的差距，G為DTGA和FTGA之間的差距。遺傳算法的種群數(shù)為50，交叉概率為0.8，變異概率為0.3。

表4 10 jobs實驗結(jié)果Tab.4 Scheduling result of 10 jobs

表4至表6顯示了小規(guī)模的算例結(jié)果，算例規(guī)模分別為10 jobs、14 jobs、18 jobs，每組包含10個案例。從表中可得到：當(dāng)作業(yè)數(shù)量為10 jobs和14 jobs時，本文所設(shè)計的算法求得的最優(yōu)解基本等于CPLEX得到的最優(yōu)解，而對比算法的結(jié)果與最優(yōu)解有明顯的偏差，在求解時間上3個算法都在同一個數(shù)量級范圍。當(dāng)作業(yè)數(shù)量為18 jobs時，本文所設(shè)計的算法與CPLEX得到的最優(yōu)解僅為1.6%，對比算法的偏差卻達到了10%，而求解時間上本文算法與對比算法在同一個數(shù)量級內(nèi)，遠遠小于CPLEX的求解時間。因此，得出以下結(jié)論：在小規(guī)模的算例中，本文所提出的遺傳算法在一定誤差范圍內(nèi)均能求解出較好的結(jié)果。

表5 14jobs實驗結(jié)果Tab.5 Scheduling result of 14 jobs

表6 18 jobs實驗結(jié)果Tab.6 Scheduling result of 18 jobs

表7 中規(guī)模、大規(guī)模案例實驗結(jié)果Tab.7 Scheduling result of middle and large scale

為了對比兩種算法的優(yōu)劣性，在其他設(shè)置參數(shù)相同的情況下，對比兩種算法在不同的迭代次數(shù)下的求解結(jié)果。在3種不同規(guī)模下，各取10個案例，記錄每個案例在不同迭代次數(shù)下的平均值，再對10個案例取平均值。圖6至圖8表示作業(yè)數(shù)目為30 jobs、60 jobs、90 jobs的情況下，兩種不同算法的比較。橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為10個算例的平均值。通過圖可以發(fā)現(xiàn)，隨著迭代次數(shù)增加，兩種算法的值逐漸降低，并且在不同的迭代次數(shù)下，本文設(shè)計的算法DTGA都明顯優(yōu)于對比算法FTGA。

表7顯示了30 jobs、60 jobs、90 jobs 3種情況下本文設(shè)計算法與CPLEX及對比算法之間的對比。兩種遺傳算法的設(shè)置參數(shù)相同，迭代次數(shù)均為200。每組選擇10個案例，為了實驗結(jié)果更具代表性，每個案例求解10次并取平均值。針對大部分大規(guī)模算例，由于CPLEX無法求得精確解，因此與CPLEX在7 200 s內(nèi)所求上界UB進行對比。從表7中的數(shù)據(jù)可以看出，在作業(yè)數(shù)目為30 jobs情況下，CPLEX能求得一部分算例的精確解，本文算法與精確解之間相差百分比平均約為4.75%，而對比算法與精確解之間相差百分比平均約為12.15%。與對比算法相比，本文算法在求解大規(guī)模算例問題上更加有效。

圖6 30 jobs實驗數(shù)據(jù)對比Fig.6 Comparison of scheduling result of 30 jobs

圖8 90 jobs實驗數(shù)據(jù)對比Fig.8 Comparison of scheduling result of 90 jobs

5 總結(jié)與展望

本文在考慮實際生產(chǎn)過程中存在的換班情況下，提出了以最小化人力成本投入為目標(biāo)的考慮排班的人力資源投入問題，建立了人力成本投入最小化為目標(biāo)的數(shù)學(xué)模型。此外，本文將所提出的數(shù)學(xué)模型進行拆分，使得小規(guī)模問題可以直接用CPLEX進行求解。為了解決大規(guī)模問題，本文又提出了對作業(yè)延遲開始時間進行解碼的遺傳算法，并且對作業(yè)開始時間和延遲時間進行局部優(yōu)化，從而得到最佳目標(biāo)值。算例實驗結(jié)果表明，無論是小規(guī)模的模型拆分還是大規(guī)模算法的構(gòu)建都取得不錯的效果。

在實際中，同一種人力資源之間，由于個體的不同也可能存在差異，然而本文中并沒有考慮這種差異性，這也是本文未來的研究方向之一。