陸志強，許則鑫，任逸飛

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

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

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

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

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

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

1 問題描述及建模

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

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

目標函數為

傳統RIP約束為

排班約束為

決策變量可行域為

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

2 問題分析與簡化

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

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

證明 假設所有作業(yè)的開始和結束時間已經確定，對于k類人力資源，假設有，其中w'為一個特定的班次，令。首先證明lkw'+lk(w'+1)+lk(w'+2)的人數在滿足工人休息的情況下能夠滿足作業(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)，由數學歸納法可以得到，對于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，由于不等式兩邊都是正整數，可以假設mk=lkw'+lk(w'+1)+(lk(w'+2)-1），此時在w'+2班次中由于人力資源不足，無法進行作業(yè)，則是錯誤的，即，得證。從而可得。

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

定義決策變量如下：

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

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

定義中間變量如下：

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

目標函數：

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

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

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

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

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

表1 10 jobs實驗結果Tab.1 Scheduling result of 10 jobs

表2 14 jobs實驗結果Tab.2 Scheduling result of 14 jobs

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

3 算法設計

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

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

3.1 染色體編碼

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

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

關于延遲開始時間的相關定義如下：

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

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

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

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

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

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

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

圖2 項目的AON網絡的一個實例Fig.2 An example of AON network of a project

圖3 項目調度時間圖Fig.3 Scheduling time map of a given project

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

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

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

圖4 項目逆向調度時間圖Fig.4 A project time map with reverse scheduling

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

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

3.2 初始解生成

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

圖5 產生基因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]中隨機選取一個小數θ

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

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

3.2.2 逆向生成染色體

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

3.3 染色體交叉

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

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

定義5 在給定的調度基礎上，作業(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]內隨機生成一個整數q。

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

步驟5 令i=q。

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

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

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

情形 2 不滿足情形 1，并且NC2[i]＞0，FC2[i]＞0時。此時與C2交叉。即令

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

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

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

步驟9 令i=q。

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

步驟11 重復步驟7的操作。

步驟12 若i=1則停止運算，否則令i=i-1轉步驟10。

3.4 染色體變異

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

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

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

步驟2 從[0，1]隨機選取一個小數ρ，若ρ＞0.5，轉步驟3，否則轉步驟7。

步驟3 令i=q1。

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

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

步驟6 若i=q2，運算結束，否則轉步驟4。步驟7 令i=q2。

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

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

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

3.5 局部優(yōu)化

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

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

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

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

步驟1 令i=1，計算當前調度下目標函數值為A。

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

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

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

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

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

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

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

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

步驟1 令i=1，計算當前調度下目標函數值為A。

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

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

4 數據實驗

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

表4 10 jobs實驗結果Tab.4 Scheduling result of 10 jobs

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

表5 14jobs實驗結果Tab.5 Scheduling result of 14 jobs

表6 18 jobs實驗結果Tab.6 Scheduling result of 18 jobs

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

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

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

圖6 30 jobs實驗數據對比Fig.6 Comparison of scheduling result of 30 jobs

圖8 90 jobs實驗數據對比Fig.8 Comparison of scheduling result of 90 jobs

5 總結與展望

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

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