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

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

印制電路板(printed circuit board，PCB)是電子工業(yè)的重要部件之一，其加工工藝復(fù)雜，鉆孔是其核心工序之一。在工程實際中，PCB鉆孔任務(wù)通常是集中在每個班次開始的時段隨機到達，不同任務(wù)之間在板數(shù)、孔數(shù)、孔徑、板材等方面具有較大差異。每臺鉆孔機器是多軸同步運動，每次只能加工同一訂單。由于單次疊板數(shù)量有限，一個訂單往往無法在同臺機器一次完成加工。為了縮短交貨期，可能需要將一個訂單拆分成多個子任務(wù)，由多臺機器同時加工。此外，為了降低加工錯誤風(fēng)險，在每臺機器首次加工一個訂單時需要進行首板加工與檢測。上述任務(wù)特征和工藝要求導(dǎo)致PCB鉆孔任務(wù)調(diào)度問題與傳統(tǒng)機器調(diào)度問題不同，優(yōu)化求解難度相對更大。當(dāng)前企業(yè)主要是依據(jù)人工經(jīng)驗進行PCB鉆孔任務(wù)調(diào)度，很難有效控制訂單交貨期和設(shè)備利用率。

PCB鉆孔任務(wù)調(diào)度問題本質(zhì)上屬于具有任務(wù)可拆分特性的并行機調(diào)度問題(parallel machines scheduling problem, PMSP)，其在最小總拖期目標(biāo)下為NP-難問題[1]。當(dāng)前國內(nèi)外學(xué)者都是在靜態(tài)環(huán)境下研究這類問題，即假定所有任務(wù)在初始時刻均已到達，且資源和任務(wù)信息是確定的。任務(wù)可拆分PMSP相關(guān)研究可以按照決策目標(biāo)進行分類。在最小化總拖期目標(biāo)方面，Kim等[2]提出首先在不考慮拆分的情形下獲得每臺機器加工序列，接著對每臺機器上的任務(wù)進行拆分和重排序。Shim等[3]提出了3種優(yōu)勢定理和多種下界計算方法，并據(jù)此構(gòu)建了分支定界算法。Sari?i?ek等[4]構(gòu)建了一個基于序列位置變量的整數(shù)規(guī)劃模型，并發(fā)現(xiàn)模擬退火(simulated annealing,SA)算法表現(xiàn)優(yōu)于禁忌搜索。類似的，Kim等[5]也建立了相應(yīng)的整數(shù)規(guī)劃模型，并發(fā)現(xiàn)SA算法表現(xiàn)優(yōu)于遺傳算法。在最小化最大完工時間目標(biāo)方面，Yalaoui等[6]、Nait等[7]、Wang等[8]分別提出了相應(yīng)的啟發(fā)式算法。Wang等[9]和Liu等[10]提出了考慮學(xué)習(xí)效應(yīng)的優(yōu)勢定理，據(jù)此建立了基于序列位置變量的數(shù)學(xué)模型和分支定界算法。此外，Liang等[11]以總拖期和最大完工時間作為聯(lián)合目標(biāo)，發(fā)現(xiàn)變鄰域搜索(variable neighborhood search, VNS)算法表現(xiàn)優(yōu)于多重蟻群優(yōu)化算法。

盡管目前尚未見到關(guān)于PCB鉆孔任務(wù)動態(tài)調(diào)度的相關(guān)研究，但是國內(nèi)外學(xué)者對其他類型的動態(tài)調(diào)度問題進行了一定研究，詳見綜述文獻[12]?？傮w來說，現(xiàn)有動態(tài)調(diào)度方法可分為反應(yīng)式、前攝式以及前攝?反應(yīng)式3類[13]。反應(yīng)式調(diào)度不預(yù)先生成固定的調(diào)度方案，而是實時地在局部作出決策。這類方法適用于應(yīng)對不可預(yù)期事件，常采用啟發(fā)式規(guī)則等實時性高的方法[14-15]。前攝式調(diào)度是指在制定計劃時提前預(yù)測潛在隨機干擾，從而令所得調(diào)度方案在執(zhí)行過程中具有較高的魯棒性，適用于應(yīng)對可預(yù)知隨機事件[16]。前攝?反應(yīng)調(diào)度則是綜合了前攝與反應(yīng)兩種方法的優(yōu)點，一方面采用前攝方法制定出能夠應(yīng)對可預(yù)知隨機事件的魯棒調(diào)度方案，另一方面采用反應(yīng)調(diào)度方法根據(jù)實時事件對調(diào)度方案進行修改[17]。此外，動態(tài)調(diào)度有事件驅(qū)動、定周期，以及兩者混合3種再調(diào)度機制[18]。所謂事件驅(qū)動是指當(dāng)出現(xiàn)使得系統(tǒng)狀態(tài)發(fā)生改變的事件時就觸發(fā)再調(diào)度，而定周期是指每隔一個周期調(diào)度一次。事件驅(qū)動機制能及時應(yīng)對突發(fā)事件，定周期機制能提高生產(chǎn)穩(wěn)定性。兩者混合機制能夠綜合兩者的優(yōu)點，因而應(yīng)用更為廣泛[19]。

由于PCB鉆孔任務(wù)動態(tài)到達過程為不可預(yù)期事件，任務(wù)必須及時處理以滿足交貨期要求，因此本文將采用基于事件驅(qū)動的反應(yīng)式調(diào)度方法加以解決。

1 問題描述

本文研究的PCB鉆孔任務(wù)動態(tài)調(diào)度問題由n個動態(tài)到達的任務(wù)和m臺具有同等能力的機器構(gòu)成，并考慮任務(wù)可拆分特性和因首板檢測而導(dǎo)致的切換時間。假定任務(wù)j在時刻rj到達，其交貨期dj、權(quán)重wj、 切換時間sj、 單位任務(wù)數(shù)uj，以及單位任務(wù)的工期pj均已知。所謂單位任務(wù)是指機器單次加工的任務(wù)，將一批在同一臺機器上連續(xù)加工且屬于相同任務(wù)的單位任務(wù)稱為子任務(wù)。切換時間是指機器在切換加工不同子任務(wù)時，所需額外準備時間。任務(wù)j的完工時間cj是由其最晚完工子任務(wù)確定的，對應(yīng)拖期為Tj=max(0,cj?dj)。

由于不同PCB企業(yè)在進行鉆孔任務(wù)調(diào)度時可能采用不同的決策目標(biāo)，因此本文將分別考慮如下5種典型的決策目標(biāo)：最小化總拖期時間(total tardiness,TT)(如式(1)所示)，最小化總加權(quán)拖期時間total weighted tardiness,TWT)(如式(2)所示)，最小化最大完工時間(maximum completion time,Cmax)(如式(3)所示)，最小化總流水作業(yè)時間(total flowtime,TF)(如式(4)所示)，最小化總加權(quán)完工時間(total weighted completion time,TWC)(如式(5)所示)。

2 事件驅(qū)動的再調(diào)度方法

本文所研究的PCB鉆孔任務(wù)動態(tài)調(diào)度問題，面臨新任務(wù)到達和在制任務(wù)完工兩類事件。當(dāng)有新任務(wù)到達且存在空閑資源時，才會觸發(fā)相應(yīng)的調(diào)度方法來獲取當(dāng)前時刻的決策。為了既快速響應(yīng)動態(tài)事件又保證調(diào)度優(yōu)化效果，本節(jié)將描述優(yōu)先規(guī)則和智能算法兩類再調(diào)度方法。

2.1 優(yōu)先規(guī)則

優(yōu)先規(guī)則的優(yōu)點是簡單高效，在工程實際中應(yīng)用非常廣泛。目前，有大量面向各類生產(chǎn)調(diào)度和項目調(diào)度問題的優(yōu)先規(guī)則，規(guī)則的表現(xiàn)與調(diào)度環(huán)境密切相關(guān)，沒有哪一種規(guī)則在所有環(huán)境下都表現(xiàn)最優(yōu)[20]。由于本文考慮了如式(1)～(5)所示5種決策目標(biāo)，因此將從現(xiàn)有文獻中選取適用于這些決策目標(biāo)的規(guī)則。從文獻[14]中選取8種規(guī)則，從文獻[21]中選取了MDD和WMDD兩種規(guī)則，另外還考慮了FCFS、WEDD和SPT3種規(guī)則。本文所選取的13種優(yōu)先規(guī)則如表1所示。

表1 所選13種優(yōu)先規(guī)則的形式化描述Table1 Formalization of selected 13 priority rules

優(yōu)先規(guī)則只能實現(xiàn)對當(dāng)前等待任務(wù)排序，在按照優(yōu)先級順序安排任務(wù)開工時還需要進一步考慮如何對其進行拆分的問題。為此，本文考慮一種能夠最快完成開工任務(wù)的拆分策略，也就是將當(dāng)前開工任務(wù)的所有單位任務(wù)盡可能均勻地安排至當(dāng)前所有擔(dān) ?uj/mt」+1個 單位任務(wù)，其余空閑機器承擔(dān)?uj/mt」個單位任務(wù)，其中?·」表示向下取整函數(shù)?？臻e機器中。例如，假定t時刻有mt臺空閑機器，當(dāng)前具有最高優(yōu)先級的任務(wù)j含有uj個單位任務(wù)，那么將有ujmodmt(表示uj除以mt的余數(shù))臺空閑機器承

2.2 智能算法

與優(yōu)先規(guī)則通過簡單排序和任務(wù)拆分進行決策不同，智能算法可完整表達任務(wù)開工方案，在算法停止時只需令每臺空閑機器加工序列中的首個子任務(wù)開工。然而，在動態(tài)調(diào)度過程中的某些決策時刻可能等待任務(wù)數(shù)較少，此時若直接將式(1)～(5)所示決策目標(biāo)作為智能算法的目標(biāo)函數(shù)，會導(dǎo)致大量局部最優(yōu)解。為此，本文提出將式(1)～(5)所示決策目標(biāo)作為智能算法的第一目標(biāo)，將當(dāng)前參與調(diào)度的任務(wù)的最大完工時間或總切換時間最小作為智能算法的第二目標(biāo)。經(jīng)過這樣處理之后，智能算法將以更貪婪的方式獲得全局更優(yōu)的調(diào)度方案。

2.2.1算法編碼

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

證明見Shim等[3]提出的Proposition1、Kim等[5]提出的Property1以及Wang等[9]提出的Theorem2。

本文將基于該定理來構(gòu)建相應(yīng)的智能算法，提高其求解效率。需要強調(diào)的是，該定理在動態(tài)環(huán)境下并不能保證最優(yōu)性，而是一種局部最優(yōu)定理。在此基礎(chǔ)上，本文參考Sari?i?ek等[4]的SA算法編碼方法，定義每臺機器的子任務(wù)序列以及各子任務(wù)的單位任務(wù)數(shù)量。如圖1所示，Jkl表 示在機器k的 第l個位置上加工的子任務(wù)，SJkl表 示子任務(wù)Jkl的單位任務(wù)數(shù)量，nk表 示在機器k上的子任務(wù)總數(shù)。該方法的優(yōu)點是解碼過程簡單，很容易嵌入優(yōu)勢定理1以及計算目標(biāo)函數(shù)值。

圖1 算法編碼規(guī)則Figure1 Algorithm coding rule

2.2.2鄰域算子

本文采用智能算法常用的3種鄰域算子來構(gòu)造鄰域解，即同臺機器子任務(wù)交換、兩臺機器單位子任務(wù)插入和交換算子。與常規(guī)鄰域算子不同之處在于，本文在鄰域構(gòu)造過程中始終遵循優(yōu)勢定理1。例如，若將機器k中的任務(wù)j的一個單位任務(wù)插入或者交換到機器k′上，那么將先判斷機器k′上是否存在屬于任務(wù)j的子任務(wù)，若存在就直接將該單位任務(wù)并入該子任務(wù)中，否則隨機插入或者交換到機器k′。

2.2.3模擬退火與變鄰域搜索

現(xiàn)有關(guān)于靜態(tài)PCB鉆孔任務(wù)調(diào)度的研究表明，SA算法表現(xiàn)優(yōu)于禁忌搜索和遺傳算法[4-5]，VNS算法表現(xiàn)優(yōu)于多重蟻群算法[11]。因此，本文將直接采用SA算法和VNS算法進行再調(diào)度，并對比這兩種算法在動態(tài)環(huán)境下的表現(xiàn)。SA算法的偽代碼如圖2所示，其中，X0為 初始解；X為當(dāng)前解；E0為初始溫度；E為當(dāng)前溫度；Ef為 截止溫度；Y為鄰域解；α為溫度衰減系數(shù)；C(X)表 示X對應(yīng)的目標(biāo)函數(shù)值；Neighborhood(X)表示等概率選用3種鄰域操作構(gòu)造X的鄰域解。

圖2 SA算法偽代碼Figure2 Pseudocode of SA algorithm

由于傳統(tǒng)VNS需要耗費大量計算時間進行局部搜索，無法滿足PCB鉆孔任務(wù)快速調(diào)度需求，因此本文采用摒棄局部搜索的ReducedVNS(RVNS)?，F(xiàn)有研究表明，RVNS在求解大規(guī)模問題時的優(yōu)化效果與傳統(tǒng)VNS相當(dāng)，但是計算速度可提升十幾倍[23]。RVNS偽代碼如圖3所示，其中，I為當(dāng)前迭代次數(shù)；Imax為 最大迭代次數(shù)；q為 鄰域算子索引；qmax為最大鄰域算子索引(本文采用了3種鄰域算子，故qmax=3)；Neighborhood(X,k)表示采用第q個鄰域算子來構(gòu)造X的鄰域解。

圖3 RVNS算法偽代碼Figure3 Pseudocode of RVNS algorithm

3 計算實例

為了驗證本文所提出的PCB鉆孔任務(wù)動態(tài)調(diào)度短視策略的有效性，本節(jié)將參照企業(yè)實際數(shù)據(jù)生成測試算例，對比分析優(yōu)先規(guī)則及不同版本的SA、VNS算法在不同環(huán)境下的優(yōu)化效果和計算效率。所有算法采用C#語言編程實現(xiàn)，實驗結(jié)果由計算程序在配置為2.20 GHz處理器和32.0 GB內(nèi)存的服務(wù)器上運行所得。

3.1 算例數(shù)據(jù)

通過對廣東某PCB企業(yè)調(diào)研，發(fā)現(xiàn)該企業(yè)共有24臺鉆孔機器，平均每天加工100個任務(wù)，每個任務(wù)的子任務(wù)數(shù)大致服從均勻分布U[1,9]。為了更全面地測試本文調(diào)度策略的有效性，進一步考慮兩種工期和3種交貨期環(huán)境。在短工期環(huán)境下，加工工時和切換時間分別服從分布U[5,60]和U[3,10]；在長工期環(huán)境下，加工工時和切換時間分別服從分布U[60,120]和U[3,20]。參照文獻[2-4]中的實驗設(shè)計，設(shè)定任務(wù)的交貨期服從分布

其中，參數(shù)β為交貨期緊急系數(shù)，在緊急、一般、寬松3種交貨期環(huán)境下的分別取值為0.4、0.8和1.2。此外，設(shè)置任務(wù)的到達時間服從分布

其中參數(shù)a、b用于控制任務(wù)在早、中、晚3個班次集中到達的特性。對于任意任務(wù)，其到達時間分別有30%的概率落于(a,b)=(0,1/12)、(a,b) = (11/24,13/24)、 (a,b)=(11/12,1)對 應(yīng) 的3個 區(qū) 間，另 有10%的概率落于 (a,b)=(0,1)對應(yīng)的區(qū)間。在每種參數(shù)組合下隨機生成25個算例，共有150個算例。

如2.2節(jié)所述，本文提出將當(dāng)前參與調(diào)度的任務(wù)的最大完工時間或總切換時間最小作為SA和RVNS算法的第二目標(biāo)。為了對比兩種第二目標(biāo)的優(yōu)劣，本文將以最大完工時間最小為第二目標(biāo)的SA和RVNS，標(biāo)記為SA1和RVNS1，將以總切換時間最小作為第二目標(biāo)的SA和RVNS，標(biāo)記為SA2和RVNS2。此外，參照現(xiàn)有文獻的調(diào)參結(jié)果來合理設(shè)置SA和RVNS算法的參數(shù)。具體來說，參照文獻[5]設(shè)置SA算法參數(shù)E0= 300，Ef= 0.001，α=0.999，參照文獻[11]設(shè)置VNS參數(shù)Imax=10 000。

3.2 評價指標(biāo)

本文采用如式(6)所示的相對偏差百分比作為評價各調(diào)度方法優(yōu)化效果的指標(biāo)。

其中， O bjz表示方法z求解某個算例所得目標(biāo)函數(shù)值； O bj?表示所有方法求解該算例得到的最好目標(biāo)函數(shù)值。

3.3 結(jié)果分析

在上述實驗數(shù)據(jù)和評價指標(biāo)設(shè)置下，采用13種優(yōu)先規(guī)則和兩種版本的SA及RVNS算法求解150個算例?？傮w來說，優(yōu)先規(guī)則求解單個算例的速度非?？欤浜臅r可以忽略不計。SA和RVNS算法求解單個算例所需平均時間分別為25 s和49 s，但是單次決策所需耗時均在1 s以內(nèi)。所有調(diào)度方法在決策效率方面，都能夠滿足企業(yè)實際再調(diào)度要求。各調(diào)度方法的優(yōu)化效果對比結(jié)果如表2 ～ 4所示，具體分析如下。

表2 各方法在5種決策目標(biāo)下的平均Dev%Table2 The average Dev% of each method under 5 decision objectives

表2展示了各調(diào)度方法在不同決策目標(biāo)下的綜合表現(xiàn)?？梢钥闯?，各優(yōu)先規(guī)則的表現(xiàn)差異性較大，5種決策目標(biāo)下表現(xiàn)最好的優(yōu)先規(guī)則都不同。具體來說，在TT決策目標(biāo)下綜合表現(xiàn)最好的是MDD，而WMDD則在TWT決策目標(biāo)下綜合表現(xiàn)最優(yōu)(COVERT和ATC表現(xiàn)與之非常接近)。值得一提的是，在Cmax決策目標(biāo)下LPT表現(xiàn)遠優(yōu)于其他規(guī)則，優(yōu)化效果普遍高出20%以上。這是由于LPT優(yōu)先安排工作量大的任務(wù)，這些任務(wù)平攤到各臺空閑機器上的單位任務(wù)數(shù)多，從而縮短了切換時間。但與此同時，LPT在其他決策目標(biāo)下的表現(xiàn)都是最差的。SPT與LPT相反，優(yōu)先安排工作量小的任務(wù)，這些任務(wù)的加工速度很快，因而在TF決策目標(biāo)下表現(xiàn)最優(yōu)。此外，在TWC決策目標(biāo)下表現(xiàn)最好的是WSPT。上述結(jié)論與文獻[14]中的結(jié)論基本一致。

相比之下，4種智能算法的優(yōu)化效果在除Cmax之外的決策目標(biāo)下平均提升了20%。對于SA和RVNS，可以看出RVNS在所有目標(biāo)下都稍微優(yōu)于SA，但是這種差別并不明顯。對于SA和RVNS所用兩種第二目標(biāo)，可以看出在TT和TWT目標(biāo)下采用最小化最大完工時間為第二目標(biāo)更優(yōu)(SA1和RVNS1分別優(yōu)于SA2和RVNS2)，在Cmax目標(biāo)下采用最小化總切換時間為第二目標(biāo)更優(yōu)，而兩者在TF和TWC目標(biāo)下則無顯著區(qū)別。

表3和表4分別進一步展示了不同工期和不同交貨期環(huán)境對各調(diào)度方法表現(xiàn)的影響。由表3可以看出，各調(diào)度方法的表現(xiàn)規(guī)律與表2所示總體規(guī)律相一致。工期規(guī)模增大對優(yōu)先規(guī)則在TT和TWT目標(biāo)下的表現(xiàn)未產(chǎn)生顯著影響，但是顯著提升了優(yōu)先規(guī)則在其余目標(biāo)(尤其是Cmax)下的表現(xiàn)。這是因為在本實驗參數(shù)設(shè)置中，任務(wù)切換時間相對加工時間的占比會隨著工期規(guī)模增大而下降，由此導(dǎo)致任務(wù)拆分策略對任務(wù)完工時間的影響下降。由表4可以看出，盡管各調(diào)度方法在不同交貨期環(huán)境下的表現(xiàn)規(guī)律與表2所示總體規(guī)律也相一致，但是方法之間的差異有著顯著的變化。具體來說，隨著交貨期由緊急到寬松，幾種智能算法的表現(xiàn)較為穩(wěn)定，優(yōu)先規(guī)則之間的差距在縮小，但是優(yōu)先規(guī)則與智能算法之間的差距則顯著增加。相比較而言，交貨期環(huán)境變化對TT和TWT目標(biāo)下優(yōu)先規(guī)則的表現(xiàn)影響大于在其他目標(biāo)(尤其是Cmax)下的表現(xiàn)，這是因為這兩個目標(biāo)與交貨期直接相關(guān)。在緊急交貨期環(huán)境下大量任務(wù)將拖期，此時調(diào)度優(yōu)化空間不大，因此部分優(yōu)先規(guī)則與智能算法的差距并不大。同樣道理，在非常寬松交貨期環(huán)境下大多數(shù)任務(wù)將不會拖期，對應(yīng)的調(diào)度優(yōu)化空間也不大。然而，企業(yè)大多數(shù)時候是處于一般偏緊急的交貨期環(huán)境，此時采用智能算法進行動態(tài)調(diào)度決策能有效減少拖期。

表3 各方法在2種工期規(guī)模和5種決策目標(biāo)下的平均Dev%Table3 The average Dev% of each method under 2 duration size and 5 decision objectives

表4 各方法在3種交貨期環(huán)境和5種決策目標(biāo)下的平均Dev%Table4 The average Dev% of each method under 3 due date environments and 5 decision objectives

4 結(jié)束語

本文針對PCB鉆孔任務(wù)動態(tài)調(diào)度問題，提出基于事件驅(qū)動的再調(diào)度短視策略，對比分析了優(yōu)先規(guī)則與嵌入局部優(yōu)勢定理的SA和RVNS再調(diào)度算法在不同調(diào)度環(huán)境下的表現(xiàn)。計算實驗結(jié)果表明，各優(yōu)先規(guī)則在不同決策目標(biāo)下的表現(xiàn)差異性較大。SA和RVNS算法總體表現(xiàn)顯著更優(yōu)和更穩(wěn)定。RVNS優(yōu)化效果略好于SA，但是SA計算效率相對高一倍；工期規(guī)模和交貨期緊急程度變化對各調(diào)度方法的表現(xiàn)優(yōu)劣未產(chǎn)生顯著影響，僅在部分決策目標(biāo)下呈現(xiàn)出方法間差距的縮小和增大?？傮w來說，本文所提出的智能算法較經(jīng)典優(yōu)先規(guī)則在優(yōu)化效果方面平均提升20%以上，同時計算效率能夠滿足企業(yè)實際動態(tài)調(diào)度要求。

盡管本文發(fā)現(xiàn)基于SA和RVNS算法的再調(diào)度短視策略能夠有效解決PCB鉆孔任務(wù)動態(tài)調(diào)度問題，但是未來還有大量相關(guān)問題值得進一步研究。例如，調(diào)度方法應(yīng)當(dāng)適應(yīng)更為復(fù)雜的實際問題，包括具有多種不同能力的鉆孔機器，任務(wù)的工時難以估計以及存在一個工人看管多臺機器等情形。此外，還可以在考慮可預(yù)測部分新任務(wù)到達時間的情形下，構(gòu)建周期驅(qū)動和事件驅(qū)動相結(jié)合的再調(diào)度機制。