劉海潮, 王 陽, 范瓊瑜

(西北工業(yè)大學(xué) 管理學(xué)院,陜西 西安 710129)

0 引言

全球經(jīng)濟(jì)的快速發(fā)展已經(jīng)使得世界市場的競爭變得愈來愈烈，大多數(shù)企業(yè)通過提高產(chǎn)品質(zhì)量并降低成本來提高企業(yè)競爭力。近年來，隨著我國人口紅利逐漸降低，勞動密集型企業(yè)的勞動力成本快速增長，導(dǎo)致這些企業(yè)的盈利水平和競爭力顯著下降[1]，典型企業(yè)包括家居企業(yè)、紡織企業(yè)和建筑企業(yè)等。為了降低勞動力成本，國內(nèi)外許多企業(yè)會雇傭部分兼職員工。公司管理層每周會根據(jù)需要為兼職員工提前分配任務(wù)，并訓(xùn)練員工學(xué)習(xí)并掌握特定的工作技能，以便他們能夠順利開展工作。此外，對于服務(wù)型企業(yè)，優(yōu)質(zhì)的客戶服務(wù)也對提高企業(yè)競爭力有著重要作用。一般來講，客戶基本的服務(wù)要求是企業(yè)的服務(wù)時間要滿足其時間偏好。因此，企業(yè)在制定服務(wù)計劃時，如何根據(jù)客戶指定的服務(wù)時間，對員工高效地分配任務(wù)并安排相關(guān)培訓(xùn)，則是需要解決的關(guān)鍵問題。

傳統(tǒng)的經(jīng)驗式排班方式往往效率低下，且質(zhì)量不佳，因此為了獲得高效的任務(wù)指派方案，需要借助已有的優(yōu)化方法。任務(wù)指派問題是典型的組合優(yōu)化問題，有著廣泛的應(yīng)用價值。經(jīng)典的指派問題以及其衍生的問題都是尋找使得目標(biāo)函數(shù)最優(yōu)的任務(wù)指派方案。廣義指派問題最早由Ross和Soland[2]提出，每個工人僅消耗單一類型的資源，被證明是一個NP-hard問題。該問題被廣泛應(yīng)用于設(shè)施選址[3]和供應(yīng)鏈之中[4]。多資源廣義指派問題是廣義指派問題的重要拓展之一，該問題中工人消耗的資源由單一類型擴(kuò)展到了多種類型。多資源廣義指派問題的求解更為困難，并被廣泛應(yīng)用于各個領(lǐng)域，如多機(jī)器人任務(wù)分配[5]，車間調(diào)度問題[6]和通信網(wǎng)絡(luò)設(shè)計[7]等。Alidaee等[8]提出了通用的廣義指派問題，該問題中完成一個任務(wù)需要執(zhí)行多個操作。

本文研究中國一家家居企業(yè)，該家居企業(yè)的服務(wù)流程如下：從家具制造商處提取貨物，將貨物轉(zhuǎn)運并存儲到企業(yè)倉庫中，派送貨物給顧客，培訓(xùn)兼職雇員的操作技能并安排其上門安裝。本文研究拓展了廣義指派問題，并且具有以下新特點：(1)考慮多日任務(wù)指派，并且每個任務(wù)有多個日期可以選擇；(2)每個任務(wù)包含多個子任務(wù)，每個子任務(wù)可供選擇的工人有多個；(3)一旦任務(wù)被安排，則該任務(wù)包含的所有子任務(wù)會在同一天內(nèi)被完成，并會產(chǎn)生相關(guān)收益；(4)工人能被派去執(zhí)行任務(wù)當(dāng)且僅當(dāng)該工人已經(jīng)被培訓(xùn)過。與文獻(xiàn)中相關(guān)任務(wù)指派問題相比，本文研究的任務(wù)指派問題包含更多的決策變量和約束條件，求解難度更大。

文獻(xiàn)中，關(guān)于指派問題的求解方法可以分為精確算法和啟發(fā)式算法兩類。精確算法主要采用分支定界法[9]，但對于大規(guī)模問題，精確算法在短時間內(nèi)很難找到高質(zhì)量的可行方案。這就促使了啟發(fā)式算法的應(yīng)用，文獻(xiàn)中較為成功的啟發(fā)式算法包括禁忌搜索[10]，大規(guī)模變鄰域算法[11]，混合禁忌搜索和分支定界算法[12]等。數(shù)學(xué)啟發(fā)式方法結(jié)合了元啟發(fā)式方法和數(shù)學(xué)規(guī)劃方法各自的優(yōu)點，非常適合于求解復(fù)雜的組合優(yōu)化問題，是當(dāng)前運籌學(xué)領(lǐng)域的熱點與前沿課題[13]。

本文采用數(shù)學(xué)啟發(fā)式算法的經(jīng)典算法—局部分支，通過選擇合適的分支變量，并在原模型中不斷添加關(guān)于此變量的局部分支約束來獲得當(dāng)前解的鄰域，從而有效定義求解子空間，并使用求解器Gurobi進(jìn)行搜索。本文根據(jù)一家家居公司的實際情況生成了三組不同類型的問題實例，此外還分析了不同分支變量以及參數(shù)設(shè)置對算法性能的影響。最后，本文還將局部分支算法與Gurobi進(jìn)行對比，驗證了算法的有效性。

1 問題描述與模型建立

1.1 問題描述與假設(shè)

假設(shè)有一個待安排家裝任務(wù)為J的家裝公司，一個計劃期D內(nèi)要將各項作業(yè)的所有子任務(wù)分配給多技能工人I完成。每項家裝任務(wù)對應(yīng)一位客戶，每項任務(wù)由多個子任務(wù)組成，子任務(wù)種類為T，每種子任務(wù)對應(yīng)一種操作技能。家裝任務(wù)j的子任務(wù)組合為Nj={t|t∈T}，多技能工人的技能組合為Mi={t|t∈T}。由于每個多技能工人和子任務(wù)之間存在多對多匹配關(guān)系，每個子任務(wù)可選的工人也有多個。安裝任務(wù)需要在客戶指定的日期Dj∈D內(nèi)進(jìn)行，并且同一項任務(wù)的所有子任務(wù)必須在同一天內(nèi)完成。一個多技能工人一天之內(nèi)可以負(fù)責(zé)多項任務(wù)的多個子任務(wù)，但同一時間只能負(fù)責(zé)一個子任務(wù)。工人在執(zhí)行子任務(wù)前，必須進(jìn)行一次培訓(xùn)以掌握對應(yīng)的技能，而安排工人學(xué)習(xí)特定操作技能時，需要根據(jù)其專長和意愿。培訓(xùn)會產(chǎn)生相應(yīng)的培訓(xùn)費用。每個工人每天的可用時間是有限的，在同一天完成指定操作所需的時間不能超過該工人的最大工作時間限制。本問題的優(yōu)化目標(biāo)是最大化加權(quán)分配的任務(wù)數(shù)量和總利潤，其中利潤為執(zhí)行任務(wù)產(chǎn)生的收入與相關(guān)子任務(wù)技能培訓(xùn)和員工雇傭成本之間的差額。

本文研究的問題包含以下假設(shè):

(1)每個子任務(wù)僅由一個工人執(zhí)行完畢；

(2)工人接受技能培訓(xùn)的日期為第一次執(zhí)行該技能對應(yīng)的任務(wù)當(dāng)天；

(3)工人培訓(xùn)的時間忽略不計；

(4)工人在不同任務(wù)間切換的時間忽略不計。

1.2 符號定義

(1) 下標(biāo)和參數(shù)：

j：任務(wù)；t：子任務(wù)；i：工人；l,d：日期；：djt任務(wù)j中子任務(wù)t預(yù)計執(zhí)行時長，j∈J,t∈Nj;qid工人i在第d天的最大工作時長，i∈I,d∈D；cjtid：工人i在第d天執(zhí)行任務(wù)j的子任務(wù)t的成本，?∈J,i∈I,t∈Mi∩Nj,d∈Dj；fit：培訓(xùn)工人i學(xué)習(xí)操作子任務(wù)t的技能花費，i∈I,t∈M；Ejd：第d天執(zhí)行任務(wù)j的收益，j∈J,d∈Dj；α：任務(wù)的權(quán)重，α>0。

(2)決策變量：

yjd：若任務(wù)j被安排在第d天則yjd=1，否則yjd=0，?j∈J,d∈Dj；xjtid：若任務(wù)j的子任務(wù)t由工人i在第d天執(zhí)行則xjtid=1，否則xjtid=0，?j∈J,i∈I,t∈Mj∩Nj,d∈Dj；zitd：若工人i被安排在第d天培訓(xùn)操作子任務(wù)t的技能則zitd=1，否則zitd=0，?i∈I,t∈Mi,d∈D。

1.3 數(shù)學(xué)模型

(1)

(11)

式(1)表示目標(biāo)函數(shù)，最大化加權(quán)后的任務(wù)數(shù)量和任務(wù)指派所產(chǎn)生的效益。式(2)表示每項任務(wù)至多只被安排一次；式(3)表示若任務(wù)被安排，則其所包含的每項子任務(wù)均被安排；式(4)表示每項任務(wù)的所有子任務(wù)被安排在同一天；式(5)表示工人在計劃期內(nèi)第一次執(zhí)行子任務(wù)當(dāng)天接受相關(guān)培訓(xùn)；式(6)確保工人在進(jìn)行子任務(wù)時已接受過相關(guān)培訓(xùn)；式(7)表示工人在計劃期內(nèi)掌握操作每項子任務(wù)的技能至多只接受一次培訓(xùn)；式(8)表示工人的工作時長不會超過其最大工作時間。式(9)～(11)表示決策變量xjtid,yjd,zitd,屬于0-1變量。

2 算法設(shè)計

本文所提出的混合整數(shù)規(guī)劃模型比文獻(xiàn)中已有的指派模型包含更多的決策變量和約束，通用求解器可以有效求解小規(guī)模算例，但無法有效求解大規(guī)模算例。因此，本文設(shè)計了基于局部分支的數(shù)學(xué)啟發(fā)式算法。

局部分支算法由Fischetti和Lodi[14]提出，該算法由局部搜索改進(jìn)而來，由于搜索過程形如一個樹狀的分支結(jié)構(gòu)(如圖 1)，且各分支節(jié)點之間依次連接，因此被稱為局部分支。其主要思想是利用一個外部分支框架將原問題的解空間分解成一系列相互聯(lián)系的子空間，并使用通用求解器快速依次搜索各子空間，子空間的生成與搜索同步進(jìn)行，從而在較短時間內(nèi)發(fā)現(xiàn)高質(zhì)量的解。

圖1 局部分支算法搜索示意圖

局部分支算法的具體實現(xiàn)則是通過快速求得一個鄰域內(nèi)的局部最優(yōu)解，然后以此局部最優(yōu)解為中心，搜索其鄰域內(nèi)新的局部最優(yōu)解，并重復(fù)操作直到滿足停止條件。下面，介紹該算法的基本要素及實現(xiàn)步驟。

2.1 鄰域定義

(12)

(13)

(14)

2.2 算法步驟

以變量yjd為分支變量為例，算法的主要步驟可以歸納如下:

步驟1初始化令iter=0，利用求解器快速求得一個初始解(x1,y1,z1)；

步驟2鄰域首次生成更新iter=iter+1，并在模型Mod中添加左分支約束Δ(y,yiter)≤k生成新模型Moditer；

步驟3集中性搜索利用通用求解器在給定時間node_time內(nèi)求解Moditer，獲得一個新的局部最優(yōu)解(xiter+1,yiter+1,ziter+1)，根據(jù)結(jié)果判定附加操作，并判定是否進(jìn)行疏散性搜索，若是，則轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟5；

步驟4疏散性搜索增大模型Moditer中的鄰域規(guī)模，利用通用求解器求解。根據(jù)結(jié)果判定是否再次進(jìn)行疏散性搜索，若是，則再次執(zhí)行步驟4，否則轉(zhuǎn)步驟5；

步驟5鄰域切換將模型Moditer中的左分支約束Δ(y,yiter)≤k修改為右分支約束Δ(y,yiter)≥k+1，更新iter=iter+1，并添加新的左分支約束Δ(y,yiter)≤k,生成一個新模型Moditer；

步驟6重復(fù)步驟3～5直到達(dá)到給定求解時間。

集中性搜索和疏散性搜索是使啟發(fā)式算法獲得優(yōu)越性能的核心，二者相輔相成，缺一不可[15]。因此，步驟3和步驟4是局部分支算法的核心步驟。

為了提高集中性搜索的效率，會將歷史最優(yōu)的目標(biāo)函數(shù)值作為目標(biāo)值下界傳遞給求解器。每次搜索新鄰域得到的局部最優(yōu)解，相比之前的局部最優(yōu)解會出現(xiàn)以下四種情況：(1)求解時間未達(dá)到給定時間node_time上限，并且目標(biāo)值得到改進(jìn)，表明找到當(dāng)前鄰域內(nèi)的局部最優(yōu)解；(2)求解時間達(dá)到給定時間node_time上限，且目標(biāo)值得到改進(jìn)，表明找到一個更優(yōu)解，但并非當(dāng)前鄰域內(nèi)的局部最優(yōu)解；(3)求解時間未達(dá)到給定時間node_time上限，并證明模型不可行，表明該鄰域不存在更優(yōu)解；(4)求解時間未達(dá)到給定時間node_time上限，但未找到一個可行解。

后兩種情況會觸發(fā)疏散性機(jī)制，而各種情況的應(yīng)對策略分別如下：情況1是期望結(jié)果，不需要應(yīng)對策略；針對情況2，將左分支約束改為禁忌約束Δ(y,yiter)≥1，并將模型Moditer的變量y的取值固定為yiter+1，在給定時間內(nèi)再優(yōu)化Moditer，以確定其他變量x，z的最佳取值；針對情況3，會放棄當(dāng)前節(jié)點的左分支；針對情況4，會減少一半的鄰域規(guī)模以加速對該鄰域的搜索。

步驟4的疏散性搜索借鑒了元啟發(fā)式算法的疏散性機(jī)制。該疏散性搜索至多連續(xù)執(zhí)行兩次，且每次執(zhí)行都會擴(kuò)大一半的鄰域規(guī)模。第一次執(zhí)行搜索時，仍使用通用求解器在給定時間node_time搜索，并傳遞最優(yōu)下界bestLB給求解器，若仍無法找到可行解時，會觸發(fā)第二次搜索。在進(jìn)行第二次搜索時，求解器沒有下界限制，并且當(dāng)首次找到可行解就停止搜索。

3 實驗結(jié)果

3.1 測試環(huán)境與算例

本文的局部分支算法采用C++編程，GNU g++編譯，在Intel CoreTM i7-8700 CPU@3.2GHz，8.00GB內(nèi)存的機(jī)器上測試，并采用Gurobi 8.1.1整數(shù)規(guī)劃求解器對模型進(jìn)行求解?；趶V州一家家居公司的實際情況，生成了13個測試算例，特點如下：計劃期為7天，任務(wù)數(shù)量分別是50和500，平均每個任務(wù)可選擇的日期有3.58天，子任務(wù)一共有8種，平均每個任務(wù)包含4.09個子任務(wù)，工人數(shù)量從10到100，每位工人的意向技能有1到7。這些算例所包含的變量數(shù)量從4542到348429，約束從4893到352080。此外，模型中α取值為100。

3.2 分支變量選擇以及算法參數(shù)設(shè)定

選擇合適的分支變量是高效應(yīng)用局部分支算法的關(guān)鍵。對于變量種類較多的數(shù)學(xué)模型，若將所有變量都作為分支變量加入局部分支約束中，由于變量之間一般存在約束關(guān)系，使得實際的搜索子空間可能小于局部分支約束所定義的子空間，導(dǎo)致無法充分探索該子空間，從而造成求解效率低下。本文提出的模型Mod中共包含三類布爾型決策變量xjtid,yjd,zitd，不存在明顯的核心決策變量。因此，本文共設(shè)計了7種分支變量的選擇方式(見表1)。

表1 分支變量的選擇方式

表2 鄰域規(guī)模與鄰域搜索時間

觀察表3，可以發(fā)現(xiàn)：1)對于第一類測試算例，采用分支變量2和6表現(xiàn)較好；2)對于第二類測試算例，采用分支變量3表現(xiàn)最好，其次是分支變量2和6；3)對于第三類測試算例，采用分支變量3表現(xiàn)最好；此外，還可以發(fā)現(xiàn)采用分支變量7在所有測試算例上的結(jié)果均較差。因此，以yjd,zitd或yjd+zitd為分支變量是有效的。特別的，當(dāng)任務(wù)數(shù)量多于工人數(shù)量時，選擇以yjd為分支變量；當(dāng)工人數(shù)量多于任務(wù)數(shù)量時，選擇以zitd為分支變量；當(dāng)工人數(shù)量等于任務(wù)數(shù)量時，選擇以或者為分支變量。

表3 選取不同分支變量下的局部分支算法性能對比：Avg_Gap(%)

為了選擇合適的參數(shù)，我們詳細(xì)對比測試算例在不同參數(shù)設(shè)置下與Gurobi的歷史最優(yōu)解的差值。這里每類算例的分支變量選擇如下：第一類測試算例以yjd為分支變量，第二類和第三類算例以zitd為分支變量。本文給出了局部分支算法與Gurobi獲得的最好解的差值，結(jié)果如表4所示。

表4 不同參數(shù)設(shè)置下局部分支算法性能對比：Gap(%)

觀察上表，可以發(fā)現(xiàn)，對于所有類型的算例，參數(shù)組合4(鄰域規(guī)模k=20，搜索時間node_time=20)的表現(xiàn)較好。該組參數(shù)在6個測試算例中，5個算例上都取得了最好的結(jié)果，而在第1個算例上也取得了次優(yōu)解。各參數(shù)組合在6個算例上找到歷史最優(yōu)解的平均耗時分別為369.61秒，311.42秒，669.292秒，325.45秒，336.77秒，可以發(fā)現(xiàn)參數(shù)組合4的耗時也較短。

3.3 算法有效性檢驗

本文通過在多個不同規(guī)模的算例上，將局部分支算法與Gurobi進(jìn)行對比來驗證算法的有效性。相關(guān)參數(shù)設(shè)置根據(jù)3.2節(jié)得出，其中鄰域規(guī)模k=20，鄰域搜索時間node_time=20，編號為1，10，11，12，13的算例，以變量為分支變量，其他算例以變量為分支變量。

觀察表5，可以發(fā)現(xiàn)，以上13個算例中，局部分支算法在9個算例上表現(xiàn)比Gurobi好。特別的，對于最大規(guī)模的算例13，Gurobi無法求解，而局部分支算法在給定時間內(nèi)，可以找到一個質(zhì)量較高的解。此外，局部分支算法與Gurobi均在7個算例上找到了最優(yōu)解。因此，局部分支算法適合本問題的求解，特別對于問題規(guī)模較大的算例。

表5 局部分支算法與Gurobi的性能對比

4 結(jié)論

本文研究了一個新的任務(wù)指派問題，將人工培訓(xùn)費用和顧客要求的服務(wù)時間引入傳統(tǒng)的任務(wù)指派模型之中，使問題更具實際意義。本文首先構(gòu)建了一個整數(shù)規(guī)劃模型，并設(shè)計了基于局部分支的數(shù)學(xué)啟發(fā)式算法。為了選擇合適的分支變量，本文實驗分析了7種不同的局部分支變量，通過對比實驗發(fā)現(xiàn)分支變量的選擇需要根據(jù)問題的特點決定，具體如下：當(dāng)任務(wù)數(shù)量多于工人數(shù)量時，選擇yjd為分支變量有效，否則選擇變量zitd為分支變量有效。為了選擇合適的參數(shù)設(shè)置，本文分析了不同鄰域規(guī)模與鄰域搜索時間對算法性能的影響，并通過實驗發(fā)現(xiàn)當(dāng)鄰域規(guī)模和搜索時間均為20時求解效果最佳。在13個算例上的測試發(fā)現(xiàn)，局部分支算法在9個算例上表現(xiàn)比Gurobi好，驗證了算法的有效性。