朱松平，王小明，鄢敏杰，陳慶新，毛 寧

(廣東工業(yè)大學 廣東省計算機集成制造重點實驗室, 廣東 廣州 510006)

盡管國內(nèi)外學者對并行機調(diào)度問題 (parallel machines scheduling problem, PMSP)開展了廣泛研究，但是大部分文獻未考慮任務拆分特性，經(jīng)典PMSP研究詳見綜述文獻[4-5]。針對任務可以任意拆分的PMSP，Serafini[6]以紡織行業(yè)為工程背景，提出了以最大加權(quán)拖期最小為決策目標的網(wǎng)絡(luò)流模型與多項式算法。Xing等[7]證明了最小總拖期目標下的任務可拆分PMSP為NP-難問題。針對目標為總拖期最小的具有任務拆分特性與簇準備時間的PMSP，Kim等[1]提出一個兩階段啟發(fā)式算法，第1階段在不考慮任務拆分的情形下，基于現(xiàn)有的并行機調(diào)度啟發(fā)式方法獲得每臺機器的加工序列，第2階段將任務拆分成多個子任務并重新在機器上排序。Shim等[8]針對該問題提出3種優(yōu)勢定理和多種下界計算方法，并據(jù)此構(gòu)建分支定界 (branch and bound, B&B)算法，然而該算法求解10個任務需耗時1 h左右，求解25個任務則需耗時10 h。Saricicek等[3]基于序列位置 (sequence position, SP)變量構(gòu)建一個面向該問題的數(shù)學模型，對比禁忌搜索和模擬退火算法 (simulated annealing, SA)求解該問題的表現(xiàn)，結(jié)果表明SA算法更優(yōu)。

簇準備時間屬于序列相關(guān)準備時間的一種特例，而考慮序列相關(guān)準備時間的PMSP是調(diào)度領(lǐng)域的研究熱點之一。在最小化最大完工時間目標下，Yalaoui等[9]、Tahar等[10]、鄭秋亞等[11]、Wang等[12]分別提出相應的啟發(fā)式算法。此外，Wang等[13]和Liu等[14]提出考慮學習效應的優(yōu)勢定理，據(jù)此建立基于SP變量的數(shù)學模型和分支定界算法。在最小化總拖期目標下，Kim等[15]建立數(shù)學模型并基于遺傳算法 (genetic algorithm，GA)和SA算法提出多種編碼和種解碼方法，其實驗結(jié)果表明商業(yè)求解器CPLEX在1 h內(nèi)僅能精確求解少數(shù)包含10個任務和2臺機器的算例，SA算法的總體表現(xiàn)優(yōu)于GA算法。

1 問題描述

本文作如下假設(shè)。1) 所有任務在0時刻到達，任務以及子任務之間相互獨立；2) 每臺機器同一時間只能加工同一個任務的子任務。

對于上述問題，Shim等[8]、 Wang等[13]和Kim等[15]提出兩個優(yōu)勢定理。本文后續(xù)將基于這兩個優(yōu)勢定理來構(gòu)建相應的數(shù)學模型和算法。從理論角度來說，由于優(yōu)勢定理能夠直接排除部分非最優(yōu)解空間，因而必然能夠提升優(yōu)化方法的求解效率。

優(yōu)勢定理1 在最優(yōu)調(diào)度方案中，同一臺機器上最多存在一個屬于同一任務的子任務。

該定理的證明見Shim等[8]提出的 Proposition 1，Wang等[13]提出的Theorem 2，以及Kim等[15]提出的Property 1。

優(yōu)勢定理2 在最優(yōu)調(diào)度方案中，所有任務在各臺機器上的加工順序相同。

該定理的證明見Wang等[13]提出的 Theorem 3。雖然Wang等[13]研究的是最小化總完工時間的考慮任務拆分特性與學習效應的PMSP，但是該優(yōu)勢定理同樣適用本文所研究的問題。

2 數(shù)學模型

2.1 符號說明

除了在問題描述中已定義的符號之外，本文還引入如下符號。

2.2 SP模型

其中，式(1)是目標函數(shù)表達式，優(yōu)化目標為總拖期時間最??；式(2)確保每個任務只能安排到一個位置上 (嵌入優(yōu)勢定理1)；式(3)確保每個位置上只能安排一個任務；式(4)確保每個任務的所有單位任務都安排到機器上，且在每臺機器安排的位置相同且唯一 (嵌入優(yōu)勢定理2)；式(5)和式(6)表示變量yjkl和變量zjkl之間的關(guān)系；式(7)是計算每臺機器的每個位置上的子任務拖期時間；式(8)和式(9)表示計算任務的拖期時間。

2.3 LO模型

基于線性序列 (linear ordering, LO)變量的機器調(diào)度模型最早出現(xiàn)在Dyer等[16]的研究中。Unlu等[17]將基于LO變量的并行機調(diào)度模型與其他模型進行對比，結(jié)果表明該模型具有較好的表現(xiàn)。本節(jié)將基于LO變量構(gòu)建嵌入優(yōu)勢定理1和2的數(shù)學模型，并在后續(xù)實驗部分將其與現(xiàn)有SP模型進行對比。

其中，式(13)是目標函數(shù)表達式，優(yōu)化目標為總拖期時間最??；式(14)確保任意兩個任務存在先后加工關(guān)系；式(15)表示任意3個任務之間存在線性關(guān)系；式(16)將優(yōu)勢定理1嵌入模型中，表示每個任務在每臺機器中最多安排一個子任務；式(17) 確保每個任務的所有單位任務都安排到機器上加工；式(18)和式(19)是計算在每臺機器上加工的子任務的完工時間；式(14)、式(15)和式(19)將優(yōu)勢定理2嵌入模型中，表示所有任務在每臺機器上的加工順序相同；式(20)和式(21)是計算任務的拖期時間。

3 模擬退火算法

由于問題的NP難屬性，導致數(shù)學規(guī)劃方法難以精確求解大規(guī)模問題?，F(xiàn)有研究表明，SA算法在求解該問題時表現(xiàn)較好[3,15]。為此，本文將描述一種嵌入優(yōu)勢定理的SA算法，以高效求解實際規(guī)模的問題。SA的偽代碼如圖1所示。其中，X0為初始解；X為當前解；Y為鄰域解；E0為初始溫度；E為當前溫度；Ef為截止溫度， α為溫度衰減系數(shù)；C(X)表示解X對應的總拖期。

圖1 模擬退火算法偽代碼Figure 1 Pseudocode of SA algorithm

3.1 編碼規(guī)則

Saricicek等[3]的SA算法編碼方法是定義每臺機器的子任務序列以及子任務的單位任務數(shù)量。該方法解碼過程簡單，很容易計算目標值，但解空間很大。Kim等[15]的SA算法編碼方法是采用一條總?cè)蝿招蛄刑娲鷐條每臺機器的子任務序列，解碼時按照總序列中的任務依次將任務分解，并分配到機器上。這樣處理可以減小解空間，但是解碼過程太復雜。綜合以上編碼方法的優(yōu)缺點，本文提出一種嵌入優(yōu)勢定理1和優(yōu)勢定理2的編碼方式，即定義一條總?cè)蝿招蛄?，以及每個任務在每臺機器上的單位任務數(shù)量。這樣既能保證每臺機器子任務序列與總?cè)蝿招蛄幸恢?，也能直接確定各臺機器加工子任務的單位任務數(shù)量，從而避免上述解空間過大以及復雜解碼的問題。

本文將Saricicek等[3]的編碼方法稱為基于子任務的編碼規(guī)則，基于優(yōu)勢定理1和優(yōu)勢定理2的改進編碼規(guī)則稱為基于任務的編碼規(guī)則，兩者詳細描述如下。

基于子任務的編碼規(guī)則如圖2所示。Jkl表示在機器k的第l個位置上加工的子任務； SJkl表示子任務Jkl的單位任務數(shù)量；nk表示在機器k上的子任務數(shù)量。

圖2 基于子任務的編碼規(guī)則Figure 2 Coding rules based on sub-task

基于任務的編碼規(guī)則如圖3所示。其中，Jl表示總?cè)蝿招蛄械牡趌個位置上加工的任務； Sjki表示任務i在機器k上加工的單位任務數(shù)量。根據(jù)優(yōu)勢定理1和優(yōu)勢定理2可知，每個任務在每臺機器上最多有一個子任務，且每臺機器的子任務序列通過總?cè)蝿招蛄写_定。因此，只需要對總?cè)蝿招蛄幸约懊總€任務在每臺機器上加工的單位任務數(shù)量編碼，就可以確定每臺機器的子任務序列以及子任務的單位任務數(shù)量。

圖3 基于任務的編碼規(guī)則Figure 3 Coding rules based on task

3.2 鄰域結(jié)構(gòu)

由于上述兩種編碼方式不同，對應的調(diào)度方案鄰域構(gòu)造方法也將有區(qū)別。本文描述如下3種鄰域結(jié)構(gòu)，并構(gòu)造出對應的3種SA算法。

第1種是建立在基于子任務的編碼規(guī)則基礎(chǔ)上的常規(guī)鄰域結(jié)構(gòu)。兩者在未嵌入任何優(yōu)勢定理的情形下組合形成的SA算法稱為SA1。該鄰域結(jié)構(gòu)包括同臺機器子任務插入/交換、兩臺機器單位任務插入/交換4種典型的操作。

第2種是建立在基于子任務的編碼規(guī)則基礎(chǔ)上的改進鄰域結(jié)構(gòu)。該鄰域結(jié)構(gòu)中嵌入優(yōu)勢定理 1，組合而成的SA算法稱為SA2。該鄰域結(jié)構(gòu)具有與常規(guī)鄰域結(jié)構(gòu)相同的4種操作，不同之處在于兩臺機器單位任務插入和交換時會進一步令其滿足優(yōu)勢定理 1。例如，若將機器k中的任務j的一個單位任務插入或交換到機器k′上，則先判斷機器k′上是否存在屬于任務j的子任務，若存在就直接將該單位任務并入該子任務中，否則隨機插入或交換到機器k′，這避免了一個任務在一臺機器上存在多個子任務。

第3種是建立在基于任務的編碼規(guī)則基礎(chǔ)上的改進鄰域結(jié)構(gòu)，該編碼規(guī)則已經(jīng)嵌入優(yōu)勢定理1和2，組合而成的SA算法稱為SA3。該鄰域結(jié)構(gòu)包括總?cè)蝿招蛄兄械娜蝿詹迦?交換、兩臺機器的單位任務插入/交換4種操作。前兩種鄰域結(jié)構(gòu)中的同臺機器子任務插入/交換操作只可能改變該機器的任務順序，而這里對總?cè)蝿招蛄兄械娜蝿者M行交換/插入，相當于對所有機器的任務順序進行同步更新操作。

3.3 參數(shù)確定

SA算法參數(shù)的設(shè)置對優(yōu)化效果和計算效率有顯著影響。為合理設(shè)置SA算法參數(shù)，本文利用SA2和SA3算法，分別在不同參數(shù)組合下求解一種中等規(guī)模算例，并據(jù)此選定一組合理的參數(shù)用于后續(xù)計算實驗。

本文設(shè)置3種水平的初始溫度E0為300、400、500；5種水平的溫度衰減系數(shù)α為0.95、0.99、0.999、0.999 5、0.999 9；截止溫度Ef固定為0.001。所使用的調(diào)參算例包含40個任務和12臺機器，每個任務有6個單位任務，考慮3種交貨期、3種準備時間，每種參數(shù)下隨機生成3個算例，共27個算例。詳細的算例參數(shù)設(shè)置見本文4.1節(jié)。

SA2和SA3算法的調(diào)參計算結(jié)果分別如圖4和圖5所示?？梢钥闯?，SA2和SA3算法的表現(xiàn)基本一致，其中優(yōu)化效果和計算耗時與E0相關(guān)性不明顯，但與 α顯著相關(guān)?？傮w來說， α越大計算耗時越長、優(yōu)化效果越好，但是當 α增大到0.999 5之后，計算耗時會顯著增加而優(yōu)化效果相差不大。因此，綜合考慮優(yōu)化效果和計算耗時，本文設(shè)定3種 SA算法采用相同的參數(shù)：E0=300， α=0.999 5。

圖4 SA2算法調(diào)參Figure 4 Parameter tuning for the SA2 algorithm

圖5 SA3算法調(diào)參Figure 5 Parameter tuning for the SA3 algorithm

4 實驗計算

本文基于隨機生成的算例進行多組計算實驗，以驗證所建數(shù)學模型和算法的有效性。采用C語言編程實現(xiàn)各個模型和SA算法，并調(diào)用商業(yè)優(yōu)化求解器Gurobi 8.1.0 (內(nèi)置分支切割算法)求解所有數(shù)學模型。實驗結(jié)果由計算程序運行在配置為Inter(R) Xeon CPUE5-4603 v2 2.20 GHz處理器，32.0 GB內(nèi)存的服務器上所得。

4.1 實驗設(shè)計

由于基于數(shù)學規(guī)劃的精確方法只能求解部分小規(guī)模算例，本文設(shè)定Gurobi求解每個算例限時1 h時，其他參數(shù)采用默認設(shè)置。為了對比各數(shù)學模型的求解效率，設(shè)置如下評價指標。

1) 1 h內(nèi)求出最優(yōu)解的算例數(shù)量OptN；

2) 求出最優(yōu)解的平均耗時AT；

3) 1 h內(nèi)未求出最優(yōu)解，但有可行解的算例數(shù)量FeaN；

4) 可行解的平均間隙AGap，單個算例間隙Gap的計算依據(jù)式(24)，其中，ObjVal表示最好的可行解值；ObjBound表示問題的線性松弛所得下界值。

本文采用交貨期優(yōu)先規(guī)則生成所有SA算法的初始解，其過程如下。先根據(jù)交貨期從小到大對任務排序，接著逐一將任務的所有單位任務安排到負荷最小的機器上，直到所有單位任務被安排完畢。為對比各SA算法的求解效率，設(shè)置如下評價指標。

1) 平均總拖期相對偏差ARDI；單個算例的總拖期相對偏差RDI，如式(25)所示，其中， TTe為方法e的總拖期，TTmax和TTmin分別為相同算例下所有方法對應的最大總拖期和最小總拖期。

4.2 結(jié)果分析

首先，采用Gurobi求解小規(guī)模算例對應的各個數(shù)學模型，得到如表1和表2所示結(jié)果及如下兩個主要結(jié)論。

表1 各數(shù)學模型在不同交貨期環(huán)境下的表現(xiàn)Table 1 The performance of each mathematical model under different due date environments

表2 各數(shù)學模型在不同準備時間下的表現(xiàn)Table 2 The performance of each mathematical model under different setups

1) LO模型總體表現(xiàn)最優(yōu)，SP1模型表現(xiàn)最差，改進的SP2模型優(yōu)于SP1模型。在6個任務下，LO模型和SP2模型都能夠獲得所有算例的最優(yōu)解，但LO模型耗時更短。而SP1模型有部分算例無法求解最優(yōu)解，且平均耗時最長。在10個任務下，LO模型精確求解的算例數(shù)量最多，其次是SP2模型，SP1模型最少。此外，在未能精確求解出的算例中，LO模型的平均間隙最小，其次是SP2模型，SP1模型最大。與Shim等[8]的B&B算法相比，LO模型在6個任務下、10個任務兩臺機器β=0.8和 β=1.2下、10個任務3臺機器β=1.2下的計算耗時更短。

2) 模型的求解效率與β相關(guān)，與準備時間無顯著關(guān)系。雖然Shim等[8]的研究表明其B&B算法效率與β無關(guān)，但是表1結(jié)果表明3個模型的求解效率都與β相關(guān)。具體地，在相同的任務數(shù)和機器數(shù)下，β越大模型表現(xiàn)越好。此外，由表2可知，本文的3個模型的求解效率與準備時間并無顯著相關(guān)。

采用3種SA算法求解小規(guī)模任務算例，所得結(jié)果與表現(xiàn)最好的LO模型對比，如表3所示。在優(yōu)化效果方面，由于LO模型能夠獲得大多數(shù)算例的最優(yōu)解，因此其在ARDI指標方面表現(xiàn)最好，SA3表現(xiàn)與之最接近，而SA1則表現(xiàn)最差。在計算耗時方面，3種SA算法的耗時都遠小于LO模型耗時，且隨著任務規(guī)模增長，SA算法耗時增長并不明顯，而LO模型的求解耗時則呈指數(shù)增長。

表3 小規(guī)模算例下SA算法與精確方法對比Table 3 Comparison of SA algorithm and exact method for small-scale instances

最后，采用3種SA算法求解大規(guī)模任務算例，得到如表4、表5和圖6所示結(jié)果及如下結(jié)論。

在優(yōu)化效果方面，由表4和表5可知，SA2和SA3相差不大，且都顯著優(yōu)于SA1。SA2和SA3的優(yōu)化效果與β、準備時間之間不存在顯著相關(guān)性。由此可見，在本研究中，優(yōu)勢定理1是提升SA算法優(yōu)化效果的主要因素，優(yōu)勢定理2的提升作用相對不顯著。

表4 各SA算法在不同交貨期下的表現(xiàn)Table 4 The performance of each SA algorithm under different due date environments

表5 各SA算法在不同準備時間下的表現(xiàn)Table 5 The performance of each SA algorithm under different setups

在計算耗時方面，3種SA算法的耗時均很短，滿足工程實際要求。而SA1的耗時最長，SA2耗時最短，SA3耗時介于SA1和SA2之間。

在收斂速度方面，由于SA1算法收斂速度相對于SA2和SA3差很多，因此，圖6僅展示SA2和SA3算法的收斂曲線。可以看出，在迭代前期SA3的收斂速度略快于SA2，但是隨著迭代次數(shù)增大，SA2和SA3收斂曲線基本重合，即這兩種算法的最終優(yōu)化效果區(qū)別不大。這表明盡管優(yōu)勢定理2對于提升SA算法優(yōu)化效果不如優(yōu)勢定理1顯著，但其在算法開始階段可以進一步提升算法的收斂速度。

圖6 SA2和SA3算法的收斂速度對比Figure 6 Comparison of SA2 and SA3 algorithm on convergence rate

5 結(jié)束語

針對具有任務拆分特性與簇準備時間的并行機調(diào)度，本文改進了現(xiàn)有SP模型，建立嵌入兩種現(xiàn)有優(yōu)勢定理的LO模型，并提出嵌入優(yōu)勢定理的SA2和SA3算法。實驗結(jié)果表明，本文構(gòu)建的LO模型表現(xiàn)優(yōu)于現(xiàn)有SP模型，不僅能夠精確求解更多小規(guī)模算例、耗時更短，而且不能求解算例的平均間隙也最小。在智能算法方面，相比于無優(yōu)勢定理的現(xiàn)有SA1算法，本文基于優(yōu)勢定理提出的SA2和SA3算法能夠在更短的時間內(nèi)獲得更好的優(yōu)化效果。具體來說，SA3算法在小規(guī)模任務下優(yōu)化效果最好，SA2和SA3在大規(guī)模任務下的優(yōu)化效果相同，但是SA2計算耗時稍短，而SA3收斂速度稍快。

在下一階段工作中，將考慮非同等并行機、任務工期不確定等更貼近工程實際的因素，探索面向這類問題的優(yōu)勢定理以及高效模型和算法。