金騰飛，胡小鋒，蔣 淳

(上海交通大學 機械與動力工程學院智能制造所，上海 200240)

0 引言

項目型產品通常為面向訂單設計(Engineering to Order, ETO)的小批量產品，具有造價高昂、體積龐大、結構復雜、裝配周期長的特點[1]。在項目型產品的裝配過程中，常出現因物料供應不及時、零部件質量不合格、工人操作延時等不確定因素導致項目超期而給企業(yè)帶來重大的經濟損失。為此，在原計劃受不確定因素干擾后，需及時實施重調度過程，以保持生產連續(xù)性、降低干擾造成的負面影響[2]。

近年來對于重調度的研究主要集中于單機系統(tǒng)[3]、Flow shop[4]以及Job Shop[5]領域。以上研究著重進行工作序列的重調度，生產擾動主要是新工作的插入，工作的執(zhí)行時間都是固定的，沒有考慮資源變動對于工作執(zhí)行時間的影響。而目前為止僅有文獻[6-7]進行了項目資源調度(RCPSP)類問題的重調度研究。在裝配領域，Sabar等[8]研究了柔性裝配線的人員排班重調度；Abd等[9]提出了田口模糊邏輯推理方法來解決機器人柔性裝配重調度問題；Jung等[10]為雙階段裝配流水車間調度問題建立了整數規(guī)劃模型，并設計了三類不同編碼方式的遺傳算法進行求解。以上研究僅考慮了最小化完工時間這一目標，而項目型產品通常具有嚴格的交貨期限，在交貨期限內控制成本才是企業(yè)關心的重點。此外，上述關于重調度的文獻大多沒有考慮計劃的穩(wěn)定性，而工人配置的變化會帶來額外的啟動成本[11]。所以要求工人配置的調整盡可能?。还ば蜷_工時間的調整又會對物料配送、車間場地占用產生影響，因此，還要求工序開工時間的調整盡可能小。

根據上述分析，本文開展了針對項目型裝配系統(tǒng)的重調度問題的研究，構建了以最小化項目成本和計劃變動為目標的項目型裝配系統(tǒng)重調度數學模型，并設計了一種基于帝國競爭[12]機制的雙目標算法(MOICA)進行求解。模型和算法最終在汽輪機廠的閥門裝配系統(tǒng)實例中得到了應用。

1 項目型裝配重調度模型

1.1 問題描述

設某一項目型產品有JW道裝配工序，工序不可拆分，工序間存在嚴格的先序約束關系，即不存在并行工序。企業(yè)一共分派W位工人執(zhí)行該項目型產品的裝配生產，每道工序一般由其中的若干位工人共同裝配，裝配同一個工序的工人稱為一個裝配組。工人的生產能力存在差異，工人具有不同的技能等級。在項目型裝配系統(tǒng)中，工序的作業(yè)時間與工人配置，即裝配組內工人數量與等級有關。增加工人或使用更高等級的工人能夠縮短裝配工序的作業(yè)時間，但同時意味著更多的成本投入。

1.2 條件假設

針對項目型裝配系統(tǒng)有如下假設：

(1)車間內各類工裝設備、零部件能滿足制造要求；

(2)工序執(zhí)行過程中裝配組內的人員不發(fā)生變動；

(3)正常情況下工序一旦開始便不可中斷，異常發(fā)生后，該工序的裝配時間需重新計算；

(4)由于空間限制，同一時刻只能執(zhí)行一道工序，即不存在并行工序；

(5)工序間存在嚴格的先序約束關系，所以重調度前后裝配工序的順序不發(fā)生變化；

(6)不同工人配置的裝配組進行每一道工序裝配的作業(yè)時間已知。

1.3 模型構建

1.3.1 參數定義

基本參數與變量定義如下：

(1)參數

(2)決策變量

(1)

Sj∈[0,D),j=1,2,…,J

(2)

1.3.2 重調度模型

(3)

(4)

s.t.Sj≥Si+di∥Si≥Sj+dj,?i≠j

(5)

(6)

Sj+dj≤D,?j

(7)

(8)

dj=φ(x11,…,x1w,x21,…,xJ1,…,xJW)

(9)

xjw∈{0,1},?j,?w

(10)

式(3)、式(4)為模型目標，式(3)表示最小化項目成本，包含了工人工資成本和額外啟動成本兩部分，式(4)表示最小化重調度前后項目開工時間的總偏差；式(5)表示任一時刻只有一道工序在執(zhí)行；式(6)表示不改變預調度計劃下的工序執(zhí)行順序；式(7)表示工作要在項目交貨期之前完成；式(8)表示各道工序的人員數量限制；式(9)表示工序作業(yè)時間dj是工人配置的函數；式(10)表示xjw為0～1變量。

2 基于帝國競爭機制的重調度算法

2.1 快速非支配排序方法

本文引入文獻[13]中提出的快速非支配排序方法來計算各個解在解集中的非支配序，從而比較解的優(yōu)劣，并形成Pareto解集?，F設P為當前的解集，則對于P中的任意解p，首先計算如下兩個指標：

np為集合P中支配p的解的數量；

Sp為p所支配的解的集合。

然后將所有np=0的解移出P并放入集合F1中，且F1中解的非支配序為1；此時對于F1中的每個解q，遍歷Sq中的所有成員j并將其nj值減一；此時P中又會出現np=0的解，再將其放入集合F2中，且F2中解的非支配序為2。重復以上過程直到所有解的非支配序被確定。

2.2 算法主體

本文根據所研究對象的特點設計了一種基于帝國競爭機制的算法，算法流程如圖1所示。

2.2.1 編碼方式

本算法中個體編碼的長度為參與重調度的工序數量J，式(11)所示為編碼具體形式，其中每個點位cj稱為基因片段，代表該道工序的工人配置情況，其與決策變量xjw(w=1,2…,W)的轉換關系如式(12)。

圖1 算法流程

(11)

cj=2W-1xj1+2W-2xj2+…+20xjW

(12)

2.2.2 帝國初始化

帝國初始化的過程如下：

步驟1：根據公式(11)隨機生成N個國家作為初始群體；

步驟2：根據解碼規(guī)則計算各國的目標函數值(f1,f2)，使用快速非支配排序算法計算各國在群體中的非支配序，并將各國的代價函數值取為其非支配序。非支配序為1的解集中刪除重復的解構成初始的Pareto集合。在競爭算法中，代價函數越小的國家勢力越大。取勢力較大的前Nimp個國家作為帝國，其余Nicol個國家作為殖民地，其中Nicol=N-Nimp。按照式(13)～式(15)計算每個帝國擁有的殖民地個數：

Cn=cn-1.3×max{ci}

(13)

(14)

NCn=round{pn×Nicol}

(15)

其中，cn是第n個帝國的代價函數值，Cn是標準化代價，pn是標準勢力大小，round為取整函數，NCn表示第n個帝國的初始殖民地個數。

步驟3：從Ncol個殖民地中隨機選擇相應的個數分配給Nimp個帝國組成Nimp個帝國集團。

2.2.3 帝國內同化

步驟1：采用殖民地向帝國的移動來模擬帝國同化的機制，通過置換算子來實現移動的過程：即隨機選取殖民地國家中半數基因片段，將其片段值置換為殖民地所屬帝國相應基因片段上的值，移動過程如圖2所示，灰色片段為隨機選取的置換片段。

圖2 帝國同化過程

步驟2：通過公式(16)來判斷帝國與殖民地之間的相對勢力大小，其中f1c與f2c分別為國家的兩個目標函數值，Meanfk(k=1,2)分別為帝國集團內所有國家目標函數的均值。計算帝國集團內所有國家的γ值，若γ值最小的殖民地的γ值小于帝國的γ值，則交換帝國與該殖民地之間的位置。

(16)

2.2.4 帝國競爭及殖民地改革

帝國競爭過程如下：

步驟2：根據式(17)計算各帝國的總代價函數值，函數值越小，帝國勢力越大。式中μ為勢力因子，一般取小于1的正實數；

(17)

步驟3：根據2.2.4中計算的γ值，取出各帝國集團中γ值最大的殖民地放入“自由國家”集合FC中；除去最弱帝國，將其余帝國放入“帝國集合”IC中；

步驟4：取出FC中代價函數值最大的國家，IC中帝國依據式(18)給出的概率計算公式占有該國家，并將得到新殖民地的帝國從IC中去除，重復該步驟直至IC=φ；

(18)

步驟5：重新將除最弱帝國外的帝國放入IC中，依據式(18)給出的公式將FC中最后一個國家分配給IC中的帝國。

為進一步提高全局搜索能力，在帝國競爭后增加殖民地改革操作：首先重新計算各帝國集團內國家的γ值，選取每個帝國集團中γ值最大的殖民地，然后以一個隨機解來代替它。

2.2.5 帝國消亡

帝國競爭之后，帝國集團之間的勢力差距會越來越大，最終會有帝國失去所有的殖民地而消亡。帝國消亡后，隨機將其分配給其余帝國。

2.2.6 終止準則

滿足如下3個條件之一即終止循環(huán)：①帝國集團的數量為1；②所有國家的非支配序為1；③循環(huán)次數達到限定值。

3 算法測試

3.1 實驗數據

結合現場數據生成3類不同規(guī)模的數據，表1顯示了3大類不同規(guī)模數據的工序數量、執(zhí)行模式以及發(fā)生問題工序的組合情況。

表1 實驗數據歸類

工序的啟動成本和執(zhí)行模式成本分別從區(qū)間(2，7)以及(20，100)中的均勻分布隨機生成。生成工序時長時，首先從區(qū)間(20，200)中的均勻分布隨機生成工序平均時長，設為T，則不同執(zhí)行模式下的工序時長由區(qū)間(0.8×T,1.2×T)中的均勻分布隨機生成，并與執(zhí)行模式一一對應(執(zhí)行成本越高的時長越短)。

生成延誤時長時，首先計算案例的延誤容許量，即未執(zhí)行工序的最小作業(yè)時長總和減去初始計劃中未執(zhí)行工序的時長總和，則延誤時間取為延誤容許量的0.1、0.3以及0.5倍。

表2 初始數據

綜上，首先為表1中的每種組合生成2組案例，每組案例均有三種不同的延誤時間，所以共生成12×2×3 = 72個案例。其中小、中、大規(guī)模案例均為24個。

3.2 評價指標

3.2.1 最優(yōu)覆蓋率

小規(guī)模問題可在LINGO中求得最優(yōu)解集，使用最優(yōu)覆蓋率對算法得到的解集進行評價。最優(yōu)覆蓋率(R)為一個算法所得解中Pareto最優(yōu)解所占比例。式(19)中，P為算法得到的解集；Ppe為Pareto最優(yōu)解集；|·|為解集中解的個數。

(19)

3.2.2 Hypervolume指標

在無法獲得最優(yōu)解集的中大規(guī)模問題上采用Hypervolume指標(IH)[14]對Pareto近似解集進行評價。

一般地，當歸一化解集P={pi|1≤i≤n}，p0為參考點時，可按公式(20)計算IH(P)：

(20)

為使不同案例下得到的IH值進行比較，引入相對百分誤差(relative percentage deviation, RPD)[1]作為方差分析的唯一因變量，如式(21)所示：

(21)

其中,Algsol表示單次算法運行得到的IH值，Maxsol表示得到的(當前案例)最大IH值。顯然，RPD值越小代表結果越好。

3.3 算法性能測試

將本文的帝國競爭算法(ICA)與文獻[13]中提出的快速非支配排序遺傳算法(NSGA II)以及文獻[14]中提出的加強Pareto進化算法(SPEA)進行了對比。測試數據為3.1節(jié)中生成的全部72個案例。

3.3.1 小規(guī)模案例測試

將24個小規(guī)模案例放入LINGO中進行求解得到了它們的精確解集。3個算法在擾動工序號為6的12個案例中均能求出最優(yōu)解，表3顯示了3個算法求解擾動工序號為2的12個案例得到的結果(以最優(yōu)覆蓋率顯示)，可見本文提出的算法提供了最好的結果。

表3 小規(guī)模案例求解結果(最優(yōu)覆蓋率)

3.3.2 中大規(guī)模案例測試

中大規(guī)模案例無法在可承受時間內進行精確求解，我們使用解集的IH值來評價求解結果。同上一小節(jié)，為使不同案例下得到的IH值進行比較，計算單次運行結果的RPD值。表4所示為以初始工序數分組的求解RPD均值。進一步地，以算法為因子，RPD值為應變量進行方差分析以及LSD檢驗，圖3所示為各個算法得到的RPD均值以及LSD誤差范圍，可見算法求解結果之間存在顯著性差異，本文提出的帝國競爭算法能得到更好的結果。

表4 中大規(guī)模案例求解結果(RPD均值)

圖3 不同算法得到的RPD均值及其LSD誤差范圍

4 工程案例

4.1 案例背景

本案例來源于某汽輪機閥門裝配系統(tǒng)，該裝配系統(tǒng)共包含24道裝配工序，由閥門裝配班組執(zhí)行裝配任務。閥門裝配班組中共有兩類不同技能等級的工人，其中有4名普工(A等級)，兩名高工(B等級)。根據實際薪資水平，普工與高工單位時間的工人成本設置為1與1.3。實際生產時從裝配班中選取若干人組成裝配組執(zhí)行裝配工序，不同配置的工人組執(zhí)行工序的時間不同。

4.2 擾動場景生成及求解

基于以上案例背景，現設有如下3種擾動事件：

(1)工序4處發(fā)生因零件返工問題導致項目有20單位時間的延誤(J=20)；

(2)工序7因工藝更改造成工序時間翻倍(J=18)；

(3)工序9因液氮配送不及時造成35單位時間的延遲(J= 16)；

運行本文算法得到的Pareto近似解集，表5列出了Pareto近似解集在目標空間中的像，以(f1,f2)的形式表示，f1和f2分別表示項目成本和時間總偏差的值。

表5 Pareto近似解集對應的目標函數值

表6給出了事件目標函數為(1446,489)、(1484,108)、(1537,90) 的解重調度人員配置以及工序作業(yè)時長的變化情況(只列出了發(fā)生變化的工序，1A1B/33表示該道工序由1名A工人、2名B工人參與裝配，工序時長為37)。圖4為預調度計劃以及以上3個重調度計劃的甘特圖，其工序方框內標有工序作業(yè)時長。

表6 重調度前后人員配置變化

定性分析模型中的兩個目標，由于時間總偏差(目標2)總是在把資源投入越前置的工序時越小，而項目成本(目標1)則是在把資源投入邊際成本與邊際時間的比值越小的工序上達到越小的值。

結合表6以及圖4給出的結果，情形2中前置工序投入了可支配的最大人力資源，其開工時間總偏差最小，但會導致高昂的項目成本；而情形1中項目成本最小，但若僅靠最后工序的資源重新配置來趕上項目交期，中間的大量工序開工時間都會延遲，會很大程度上擾亂車間的物流計劃。在給出不同的重調度方案后，還需要根據現場的實際情況來確定最終的重調度方案。

圖4 預調度計劃及事件3中3種重調度計劃的甘特圖

5 結論

本文研究了不確定環(huán)境下的項目型裝配系統(tǒng)中的工人重調度問題，構建了最小化成本和最小化重調度后計劃較初始計劃的偏離程度為目標的數學模型，并設計了多目標改進的帝國競爭算法進行求解，力求在優(yōu)化目標的同時，保證項目按期交貨。本文算法對帝國初始殖民地分配、同化以及消亡機制進行了優(yōu)化，并增加了殖民地改革操作以增加算法的全局搜索能力。

算法測試結果顯示本文算法在大小規(guī)模案例下均顯著地優(yōu)于NSGA II以及SPEA從而驗證了本文提出的算法在求解本文模型時具有很好的性能。最后以汽輪機廠的閥門裝配系統(tǒng)作為實例進行驗證，得到了能有效執(zhí)行的幾個不同重調度方案，以供決策者選擇。

雖然本文提出的模型和算法能夠有效解決項目型裝配的重調度問題，但該模型本質是針對單項目和無并行工位的裝配系統(tǒng)的。在實際的項目型裝配現場中，往往存在多項目同時執(zhí)行(多閥門)以及存在并行工位的項目型裝配系統(tǒng)(如汽缸裝配)，因此，考慮多項目、并行工位將是后續(xù)研究的重點內容。