金騰飛，胡小鋒，蔣 淳

(上海交通大學(xué) 機(jī)械與動(dòng)力工程學(xué)院智能制造所，上海 200240)

0 引言

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

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

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

1 項(xiàng)目型裝配重調(diào)度模型

1.1 問題描述

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

1.2 條件假設(shè)

針對(duì)項(xiàng)目型裝配系統(tǒng)有如下假設(shè)：

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

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

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

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

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

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

1.3 模型構(gòu)建

1.3.1 參數(shù)定義

基本參數(shù)與變量定義如下：

(1)參數(shù)

(2)決策變量

(1)

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

(2)

1.3.2 重調(diào)度模型

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

2 基于帝國競爭機(jī)制的重調(diào)度算法

2.1 快速非支配排序方法

本文引入文獻(xiàn)[13]中提出的快速非支配排序方法來計(jì)算各個(gè)解在解集中的非支配序，從而比較解的優(yōu)劣，并形成Pareto解集。現(xiàn)設(shè)P為當(dāng)前的解集，則對(duì)于P中的任意解p，首先計(jì)算如下兩個(gè)指標(biāo)：

np為集合P中支配p的解的數(shù)量；

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

然后將所有np=0的解移出P并放入集合F1中，且F1中解的非支配序?yàn)?；此時(shí)對(duì)于F1中的每個(gè)解q，遍歷Sq中的所有成員j并將其nj值減一；此時(shí)P中又會(huì)出現(xiàn)np=0的解，再將其放入集合F2中，且F2中解的非支配序?yàn)?。重復(fù)以上過程直到所有解的非支配序被確定。

2.2 算法主體

本文根據(jù)所研究對(duì)象的特點(diǎn)設(shè)計(jì)了一種基于帝國競爭機(jī)制的算法，算法流程如圖1所示。

2.2.1 編碼方式

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

圖1 算法流程

(11)

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

(12)

2.2.2 帝國初始化

帝國初始化的過程如下：

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

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

Cn=cn-1.3×max{ci}

(13)

(14)

NCn=round{pn×Nicol}

(15)

其中，cn是第n個(gè)帝國的代價(jià)函數(shù)值，Cn是標(biāo)準(zhǔn)化代價(jià)，pn是標(biāo)準(zhǔn)勢(shì)力大小，round為取整函數(shù)，NCn表示第n個(gè)帝國的初始殖民地個(gè)數(shù)。

步驟3：從Ncol個(gè)殖民地中隨機(jī)選擇相應(yīng)的個(gè)數(shù)分配給Nimp個(gè)帝國組成Nimp個(gè)帝國集團(tuán)。

2.2.3 帝國內(nèi)同化

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

圖2 帝國同化過程

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

(16)

2.2.4 帝國競爭及殖民地改革

帝國競爭過程如下：

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

(17)

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

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

(18)

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

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

2.2.5 帝國消亡

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

2.2.6 終止準(zhǔn)則

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

3 算法測(cè)試

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 實(shí)驗(yàn)數(shù)據(jù)歸類

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

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

表2 初始數(shù)據(jù)

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

3.2 評(píng)價(jià)指標(biāo)

3.2.1 最優(yōu)覆蓋率

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

(19)

3.2.2 Hypervolume指標(biāo)

在無法獲得最優(yōu)解集的中大規(guī)模問題上采用Hypervolume指標(biāo)(IH)[14]對(duì)Pareto近似解集進(jìn)行評(píng)價(jià)。

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

(20)

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

(21)

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

3.3 算法性能測(cè)試

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

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

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

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

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

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

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

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

4 工程案例

4.1 案例背景

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

4.2 擾動(dòng)場景生成及求解

基于以上案例背景，現(xiàn)設(shè)有如下3種擾動(dòng)事件：

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

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

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

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

表5 Pareto近似解集對(duì)應(yīng)的目標(biāo)函數(shù)值

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

表6 重調(diào)度前后人員配置變化

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

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

圖4 預(yù)調(diào)度計(jì)劃及事件3中3種重調(diào)度計(jì)劃的甘特圖

5 結(jié)論

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

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

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