考慮排班的人力資源投入問(wèn)題的建模與優(yōu)化

陸志強(qiáng)，許則鑫，任逸飛

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

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

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

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

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

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

1 問(wèn)題描述及建模

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

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

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

定義決策變量如下：

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

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

定義中間變量如下：

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

?km——0，1變量，第k種人力資源中的第m號(hào)工人投入了整個(gè)項(xiàng)目則為1，否則為0。

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

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

傳統(tǒng)RIP約束為

排班約束為

決策變量可行域?yàn)?/p>

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

2 問(wèn)題分析與簡(jiǎn)化

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

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

證明 假設(shè)所有作業(yè)的開(kāi)始和結(jié)束時(shí)間已經(jīng)確定，對(duì)于k類(lèi)人力資源，假設(shè)有，其中w'為一個(gè)特定的班次，令。首先證明lkw'+lk(w'+1)+lk(w'+2)的人數(shù)在滿(mǎn)足工人休息的情況下能夠滿(mǎn)足作業(yè)要求，即lkw'+lk(w'+1)+lk(w'+2)≥mk。由已知可得：lkw'≥lk(w'+3)，表示對(duì)于w'+3班次對(duì)人力資源的需求可以由w'班次釋放的工人來(lái)滿(mǎn)足，從而可以推理得到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é)歸納法可以得到，對(duì)于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），此時(shí)在w'+2班次中由于人力資源不足，無(wú)法進(jìn)行作業(yè)，則是錯(cuò)誤的，即，得證。從而可得。

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

定義決策變量如下：

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

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

定義中間變量如下：

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

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

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

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

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

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

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

表1 10 jobs實(shí)驗(yàn)結(jié)果Tab.1 Scheduling result of 10 jobs

表2 14 jobs實(shí)驗(yàn)結(jié)果Tab.2 Scheduling result of 14 jobs

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

3 算法設(shè)計(jì)

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

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

3.1 染色體編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

于是，項(xiàng)目中所有作業(yè)的最早開(kāi)始時(shí)間、實(shí)際開(kāi)始時(shí)間等見(jiàn)表3。

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

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

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

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

3.2 初始解生成

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

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

3.2.1 正向生成染色體

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

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

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

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

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

3.2.2 逆向生成染色體

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

3.3 染色體交叉

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

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

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

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

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

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

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

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

步驟5 令i=q。

步驟6 令i=i+1，對(duì)于子代C1、C2，計(jì)算作業(yè)i延遲時(shí)間的可減少值和可增加值，記為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的可減少與可增加時(shí)間都大于0，令

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

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

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

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

步驟9 令i=q。

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

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

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

3.4 染色體變異

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

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

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

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

步驟3 令i=q1。

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

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

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

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

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

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

3.5 局部?jī)?yōu)化

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

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

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

該局部?jī)?yōu)化的算法步驟如下：

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

步驟2 計(jì)算作業(yè)i延遲時(shí)間的可增加值和可減少值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，停止運(yùn)算，否則令i=i+1轉(zhuǎn)步驟2。

3.5.2 對(duì)作業(yè)開(kāi)始時(shí)間優(yōu)化

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

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

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

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

該局部?jī)?yōu)化的算法步驟如下：

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

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

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

4 數(shù)據(jù)實(shí)驗(yàn)

為了驗(yàn)證本文設(shè)計(jì)的采用對(duì)作業(yè)延遲時(shí)間編碼的遺傳算法（DTGA）的有效性，選取10 jobs、14 jobs、18 jobs、30 jobs、60 jobs、90 jobs，各10個(gè)算例進(jìn)行數(shù)值實(shí)驗(yàn)，與文獻(xiàn)中對(duì)采用作業(yè)浮動(dòng)時(shí)間進(jìn)行編碼的遺傳算法（FTGA）［24］進(jìn)行比較。數(shù)值實(shí)驗(yàn)在C#（Visual Studio 2017）語(yǔ)言環(huán)境下編程實(shí)現(xiàn)，測(cè)試平臺(tái)為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分別為平均運(yùn)算時(shí)間，G1、G2分別為DTGA、FTGA所求目標(biāo)函數(shù)值與CPLEX最優(yōu)解的差距，G為DTGA和FTGA之間的差距。遺傳算法的種群數(shù)為50，交叉概率為0.8，變異概率為0.3。

表4 10 jobs實(shí)驗(yàn)結(jié)果Tab.4 Scheduling result of 10 jobs

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

表5 14jobs實(shí)驗(yàn)結(jié)果Tab.5 Scheduling result of 14 jobs

表6 18 jobs實(shí)驗(yàn)結(jié)果Tab.6 Scheduling result of 18 jobs

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

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

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

圖6 30 jobs實(shí)驗(yàn)數(shù)據(jù)對(duì)比Fig.6 Comparison of scheduling result of 30 jobs

圖8 90 jobs實(shí)驗(yàn)數(shù)據(jù)對(duì)比Fig.8 Comparison of scheduling result of 90 jobs

5 總結(jié)與展望

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

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