黎英杰，劉建軍，陳慶新，毛 寧

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

0 引言

裝配作業(yè)車間是作業(yè)車間的一類現(xiàn)實化擴展，經由加工和組裝兩個階段完成裝配型產品制造，其調度問題既要考慮任務的工藝順序約束，還要考慮任務間的裝配關聯(lián)約束，即關聯(lián)零部件只有齊套才能開始裝配[1]。相比作業(yè)車間調度問題(Job-shop Scheduling Problem, JSP)研究，裝配作業(yè)車間調度問題(Assembly JSP, AJSP)的研究相對較少，且其生產調度更具挑戰(zhàn)性[2]，目前主要分為不對裝配體調度[3-4]和對裝配體調度[5-8]兩大類，前者假定最終產品的所有零部件齊套之后才開始裝配作業(yè)，調度時只需附加一定的裝配工期，不涉及具體的裝配工序調度，適用于產品結構簡單或裝配時間相對加工時間較短的情況；后者需要同時考慮多層級物料清單(Bill of Material, BOM)結構中所有零部件的加工工序和裝配工序調度，因此具有更高的復雜度。

多層級AJSP是將加工和裝配一同處理的綜合調度問題，也是一類典型的分層耦合約束(Hierarchically Coupled Constraint, HCC)優(yōu)化問題[8]，其最終產品的總裝開工時間受制于所需部件的完工時間，而上級部件的裝配開工時間又受制于其直屬零件/子部件的完工時間。隨著產品復雜度的上升，多層級AJSP所含零部件工藝路徑和工時需求也將呈現(xiàn)高度的差異性，導致滿足此類分層耦合約束的進度協(xié)同更加復雜，現(xiàn)實生產中常表現(xiàn)為嚴重的裝配前等待問題。因此，研究構建高效的多層級裝配作業(yè)車間調度算法具有重要的意義，遺傳算法因在理論研究和實際應用上基礎很深而被廣泛采用。然而，各級零部件間的制約關系使得基于傳統(tǒng)遺傳算法的全域搜索算法的搜索過程產生大量不可行解，需要額外的解碼和修復操作，因此求解效率極低，難以滿足現(xiàn)實需求。目前已有少量研究將搜索限定在可行域內，例如ZHAO等[5]設計了基于虛擬零部件級別的分區(qū)編碼方式，但是給不存在順序約束關系的零部件之間強加約束，縮小了算法的搜索空間；SHI等[6]提出一種基于工序約束鏈編碼的遺傳算法，保證了初始解的可行性與完備性；王福吉等[7]和ZOU等[8]針對AJSP，通過設計編碼方式和遺傳進化算子將算法限定在可行域內進行搜索，并與標準遺傳算法進行對比，驗證了算法的合理性和優(yōu)越性。

然而，上述針對裝配產品算法的研究均未考慮任務分批，實際生產中的產品往往具有一定批量，批量生產中的任務通常被允許分批生產和傳輸，該類問題被稱為分批調度問題[9]，其涉及任務分批和子批調度兩個子問題。已有研究將裝配作業(yè)車間與分批調度結合，發(fā)現(xiàn)分批生產能夠提高車間流動性，實現(xiàn)更靈活的進度協(xié)同并提升車間性能[10-12]。但是此時對多層級裝配型產品進行任務分批調度時，子批任務之間不僅需要滿足裝配順序約束，還需滿足裝配子批的批量需求，即各裝配子批只有等到有相應批量的子屬工件完工才可開工，由于零部件子批之間存在動態(tài)變化的分層耦合約束，導致上述傳統(tǒng)遺傳算法的進化算子不再適用，本文給出多層級裝配作業(yè)車間分批調度模型，提出該類車間基于可行域搜索的遺傳算法，其設計初始種群生成方式和交叉變異算子時考慮了批量變化導致的分層耦合約束的動態(tài)性，驗證了算法的基礎性能表現(xiàn)，并基于等量分批策略提出加工/裝配兩階段分批策略，最后通過實驗揭示了各分批策略下3類典型結構產品調度性能的差異性，對比了協(xié)同復雜性導向策略和隨機搜索策略下算法求解性能的差異。

1 研究問題及數(shù)學模型

1.1 多層級裝配作業(yè)車間分批調度問題描述

多層級裝配產品BOM以不同復雜程度裝配樹的形式生成，F(xiàn)RY等[13]基于結構共性抽取3類典型結構：①Flat型，包括單層樹形結構，由零件直接裝配成產品；②Tall型，包括多層樹形結構，但其中每個父節(jié)點有且僅有兩個子節(jié)點；③Complex型，是由Flat型和Tall型產品結構復合而成的多層樹形產品結構，其中至少有一個父節(jié)點包含兩個以上子節(jié)點，如圖1所示。

不同結構的裝配產品具有不同的裝配層級和零部件裝配關系，其操作優(yōu)先級結構與生產任務間的協(xié)同性均不同[14]，且在實際生產中對交貨期設置規(guī)則選用[15]、調度方案設定[16]等的需求也存在差異化，因此在調度時考慮產品結構具有重要的現(xiàn)實意義。本文將重點面向上述3類不同結構復雜程度的多層級裝配作業(yè)車間分批調度問題展開研究，即在AJSP基礎上考慮零件分批加工和部件分批組裝，實現(xiàn)同類零件/部件的分批傳輸和并行生產，從而協(xié)同生產進度并縮短生產周期。該分批調度問題描述為：有p個待交付產品，P={Ph|h=1,2,…,p}，每個產品Ph的需求數(shù)量為DMh，其BOM結構屬于3類典型結構中的一種，產品Ph所含零件在a臺加工機器M={Mi|i=1,2,…,a}上加工，所含部件在b個裝配單元F={Fi|i=1,2,…,b}中組裝，其中零件(部件)每道加工工序(裝配工序)只能由1臺加工機器(1個裝配單元)完成；優(yōu)化問題是如何對所有產品包含的所有零部件類進行分批，并為劃分而得的子批確定其在相應機器/單元上的加工/組裝序列，以最小化所有產品的最大完成時間。

在生產調度過程中有以下基本假定：①在零時刻，所有零件子批均可被加工；②加工機器與裝配單元在生產過程中正常運行，不會出故障；③不同種類工件加工或裝配時需要工序準備時間，同類零部件連續(xù)加工/裝配時不需要工序準備時間(第1個工件除外)，工序準備時間是與工序有關的常量，與每批工件包含的工件個數(shù)無關；④批次的裝卸時間并入加工時間；⑤不同子批工件的工序之間沒有先后約束；⑥每個工件在任意一臺機器上的加工/裝配工序有且只有一個；⑦每臺機器(每個裝配單元)任一時刻只能加工(裝配)一個工件，任一工件同一時刻只能被一臺機器加工；⑧工序一旦開工就不能中斷。

1.2 多層級裝配作業(yè)車間分批調度模型的構建

1.2.1 模型相關參數(shù)及定義

模型構建過程中涉及的參數(shù)符號及含義說明如下：

p為待交付產品類型數(shù)；

Ph為第h類產品；

DMh為產品h的需求數(shù)量；

CNh為產品h下屬所有零部件的類型數(shù)；

a為加工機器數(shù)量；

b為裝配單元數(shù)量；

M為加工機器集合；

F為裝配中心集合；

TM為加工任務集合；

TA為裝配任務集合；

CFi為加工機器Mi或裝配中心Wi上的裝夾類型；

Lhj為產品h的第j類工件批次；

mhj為產品h的第j類工件批的工序數(shù)量；

Pthjk為Lhj第k道工序的零件加工或部件裝配時間；

SUhjk為Lhj第k道工序的準備時間,同一個批次的各個工件之間可共享準備時間；

Qhj為Lhj的批量大??；

SNhj為Lhj的子批數(shù)量；

Fhj為Lhj的裝夾類型，同一類工件的子批在各道工序的裝夾類型均相同，否則不同；

Lhjs為Lhj的第s個子批任務；

Qhjs為Lhjs的批量大?。?/p>

Pthjsk為Lhjs第k道工序的加工或裝配時間；

SUhjsk為Lhjs第k道工序的準備時間;

Sthjsk為Lhjs第k道工序的開始時間；

Cthjsk為Lhjs第k道工序的完工時間；

Vhjsk表示工件子批裝夾類型與機器當前裝夾類型是否相同，即能否共享準備時間，是則Vhjsk=0，否則Vhjk=1；

MShjsk為Lhjs第k道工序所對應的加工機器或裝配單元，MShjsk∈M，F(xiàn)；

Zhjsk表示MShjsk上進行加工或裝配的子批是否為Lhjs,是則Zhjs=1，否則Zhjs=0；

Lh′j′s為Lhjs在同一加工機器或裝配中心(MShjsk=MSh′j′s′k′)上的緊后任務;

QUhj為Lhj直接子節(jié)點上工件類型的數(shù)量，即該部件由幾種工件組裝而成，Lhj∈TA；

Uhj為Lhj直接子節(jié)點上工件的集合，表示該部件直屬工件的具體構成，Lhj∈TA；

Thjq為Lhj直屬工件中的第q類工件，q=1,2,…,QUhj，Lhj∈TA，Thjq∈Uhj；

Thjqx為Lhj直屬工件中第q類工件的第x個子批；

Qhjqx為Thjqx的批量大?。?/p>

CThjqx為Thjqx的完工時間。

1.2.2 數(shù)學模型

基于上述的符號定義，本文構建了以最小化工件最大完工時間為目標函數(shù)的多層級裝配作業(yè)車間分批調度模型：

min(C)=maxCthjsk。

(1)

s.t.

(2)

1≤SNhj≤Qhj,SNhj∈N+,h∈[1,p],

j∈[1,CNh]；

(3)

h∈[1,p],j∈[1,CNh]；

(4)

Sthjs0=Cthjs0=0,h∈[1,p],

j∈[1,CNh],s∈[1,SNhj],Lhjs∈TM；

(5)

j∈[1,CNh],s∈[1,SNhj],k∈[1,mhj]；

(6)

Sthjs(k+1)≥Sthjsk+PthjskQhjs+VhjskSUhjsk,h∈[1,p],

j∈[1,CNh],s∈[1,SNhj],k∈[1,mhj]；

(7)

h∈[1,p],j∈[1,CNh],s∈[1,SNhj],

q∈[1,QUhj],Thjq∈Uhj,Lhj∈TA；

(8)

Sthjs(k+1)≥Cthjsk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]；

(9)

s∈[1,SNhj]；

(10)

Cthjsk≤Sth′j′s′k′,

h,h′∈[1,p],j,j′∈[1,CNh],s,

s′∈[1,SNhj],

k,k′∈[1,mhj],MShjsk=MSh′j′s′k′；

(11)

Pthjsk=Pthjk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]；

(12)

SUhjsk=SUhjk,h∈[1,p],j∈[1,CNh],

s∈[1,SNhj],k∈[1,mhj]。

(13)

其中：式(1)為目標函數(shù)最大完工時間，用最晚完工的工件子批時間表示；式(2)表示產品與其所含工件的數(shù)量關系，而且工件拆分后各個子批批量的總和與拆分前的工件批量相等；式(3)為對工件拆分的子批數(shù)量的約束；式(4)表示采用等量分批的方法對工件進行拆分，當工件不可完全等量拆分時，將剩余部分工件并入最后一批工件進行加工；式(5)表示所有零件子批在零時刻均能被加工；式(6)表示只有工件裝夾類型與機器當前裝夾類型相同，即在同一個工件批的子批之間才能共享準備時間，否則不能共享準備時間；式(7)表示工件的前后工序約束關系；式(8)表示部件子批首道裝配工序的開工時間在其直屬工件相應子批批量完工之后；式(9)表示同一工件子批前工序完工與后工序開工的排隊等待時間約束；式(10)表示任意一類工件在任意一臺加工機器或裝配中心上的工序數(shù)只能有一個；式(11)限定了同一機器上緊前緊后任務的時間約束；式(12)和式(13)表示同一批工件各個子批的工序加工/裝配時間與工序準備時間相同。

2 批量劃分策略與集成優(yōu)化算法

2.1 批量劃分策略

分批調度雖然能減小多品種小批量制造車間的設備閑置時間，縮短產品完工時間，但是過小的批量也會顯著增加不同子批生產切換帶來的準備時間(準備時間占比越大，此類影響越顯著)，還會由于子批數(shù)過多而增加管控難度。根據(jù)批量劃分策略的不同，有等量分批(將任務劃分為均等批量的傳輸/生產子批，且同類任務在各道工序上的劃分方案相同)和非等量分批兩種方式，后者還可以進一步分為一致子批(任務各子批的批量可以不同，但同類任務在各道工序上的劃分方案仍需相同)和可變子批(任務的劃分方案可靈活變化且各道工序不必相同)兩類[9]。文獻[17]表明相對于可變分批策略，等量分批策略為實踐中最直接、最容易實現(xiàn)的方式，其能節(jié)省拆分設置成本和計算工作量，有利于平衡工作負荷和提高機器利用率，文獻[10-12]針對裝配作業(yè)車間的研究也支持了該結論，因此本文僅聚焦于更為實用的等量分批策略，并基于該策略對加工零件/組裝部件進行批量劃分，具體考慮以下5種策略：

(1)策略Ⅰ(基準策略1) 不對任一類零部件進行分批，即同類零部件進行整批加工和傳輸，而且同一類部件要在其所有直屬零件/子部件齊套之后才能開工，該策略用于與其他分批策略進行性能對比。

(2)策略Ⅱ(基準策略2) 對所有零部件進行隨機等量分批。該策略理論上能夠獲得全局最優(yōu)解，是結合零件加工與部件裝配兩個階段進行統(tǒng)一考量的一類策略。為了對比分析，本文考慮以下3類分批策略，以找出不同環(huán)境下分批優(yōu)化的方向，使搜索空間可預測，從而提升求解效率。

(3)策略Ⅲ 僅對所有零件進行隨機等量分批，不對任一類部件進行分批，該策略用以測試在零件加工階段進行分批對生產性能的影響。在該策略下，任一類部件組裝都要等其直屬的所有零件子批完成后才能開工。

(4)策略Ⅳ 不對任一類零件進行分批，而對所有部件進行隨機等量分批，該策略用以測試在部件組裝階段進行分批對生產體性能的影響。在該策略下，任一類部件子批的組裝都要等其直屬的所有零件類全局齊套后才能開工。

(5)策略Ⅴ 為協(xié)同復雜性導向策略，是基于訂單整體協(xié)同性而提出的策略，即在調度時考慮訂單之間產品BOM結構復雜程度的不同與訂單內部零部件類之間工時工序數(shù)的差異，給不同的訂單產品與產品內不同零部件以不同的分批優(yōu)先級，來使訂單整體具有較好的協(xié)同性；本文具體以產品的裝配層級、裝配關聯(lián)工件的種類數(shù)、零部件形成不同路徑的關鍵性3個維度構造策略Ⅴ，因為裝配層級越高，裝配關聯(lián)工件數(shù)越多，零部件形成路徑的關鍵性越高，對其分批在實現(xiàn)訂單整體協(xié)同性上可能具有更大的優(yōu)化空間，所以優(yōu)先對高層級多工件類的產品及其關鍵路徑上的零部件進行分批，而低層級少工件類的產品及其非關鍵路徑上的工件則以較低優(yōu)先級進行分批或不進行分批，具體操作可見實驗部分。

2.2 基于可行域的改進型遺傳算法

分批調度問題求解算法主要包括分步優(yōu)化和集成優(yōu)化兩類，分步優(yōu)化策略將復雜的分批調度問題分解為生產批量優(yōu)化和子批調度優(yōu)化兩個問題分別加以求解，本質上屬于局部優(yōu)化方法；集成優(yōu)化策略將生產批量和生產順序統(tǒng)一編碼，通過優(yōu)化算法同時確定所有決策變量[18]?？紤]到集成優(yōu)化法能夠進行全局優(yōu)化，本文將構建一類基于可行域的改進型遺傳算法，根據(jù)不同分批策略產生各零部件子批的批量，同時確定各零件/部件子批在加工機器/裝配單元的生產順序，算法中初始種群的生產方式、交叉和變異算子設計都考慮了零部件批量劃分時帶來的分層耦合約束的動態(tài)性，可以確保進化過程中染色體的合法性，即算法在可行域內進行搜索。算法總體流程如圖2所示。

2.2.1 編碼方式

以集成優(yōu)化策略對染色體進行兩段式編碼，染色體前半段為根據(jù)不同分批策略產生的分批方案，該段染色體基因位數(shù)與工件種類數(shù)n相同，記錄每類工件所分的批次數(shù)量；染色體后半段為滿足分層耦合約束的子批調度方案，基因位數(shù)為所有工件的子批批次數(shù)量與工序數(shù)乘積之和，編碼方式為x-y型，其中x表示工件種類，y表示x類工件的第y個子批，并以x-y出現(xiàn)的頻數(shù)表示其工序數(shù)量。以圖3染色體片段為例，預先對工件種類進行編號，并在染色體的分批序列編碼段中按照編號順序記錄每類工件的分批批數(shù)。第1類工件分為2批，第2類工件分為1批(即該類工件不分批)，1-1表示第1類工件的第1個子批，1-2表示第1類工件的第2個子批，2-1表示第2類工件的第1個子批，在子批調度編碼序列中1-1，1-2，2-1分別出現(xiàn)了兩次，表示每個子批都有兩道工序。

2.2.2 初始種群生成方式的設計

以圖4所示的產品結構說明初始種群染色體生成方式，過程如圖5所示。假設工件1～5的需求數(shù)量均為12且每類工件的工序數(shù)均為1，工件1～5的分批批數(shù)依次為3，3，4，2，1。在染色體的分批方案基因段依次記錄工件分批批數(shù)即可，而在工序排列基因段先隨機生成零件1～3共10個子批，每個子批各一道工序的10個基因位，然后順序遍歷染色體基因位，找到工件1與工件2子批滿足部件4子批批量開工需求的最晚完工位置，并在該位置后插入工件4的子批基因位，因為零件1和零件2都分為3個子批，每批批量為4，部件4分為2個子批，每批批量為6，所以部件4第1個子批開工需要零件1和零件2各有兩個子批完工才能滿足批量需求，即4-1可插入1-3之后的任意基因位，此處特定插入1-3之后第1個基因位；部件4第2個子批開工要在零件1和零件2各剩余子批完工(即各自3個子批都完工)后，即4-2需插入1-2之后，也特定插入1-2之后第1個基因位。最后根據(jù)零件3將部件4的子批基因位插入部件5的子批基因位，同理將5-1插入3-3基因位之后，至此生成一條完整的染色體。

工序在染色體中出現(xiàn)的先后順序代表工序安排開工時間的早晚，此時分層耦合約束在染色體中的具體體現(xiàn)為，各部件子批的裝配工序基因位在其直屬工件相應子批的基因位之后。

2.2.3 改進型交叉算子的設計

為了使交叉后的子代仍然具有合法性，需要使交叉后的各個部件子批仍能滿足其裝配開工批量的需求，即參與交叉互換的基因需要使零部件之間的分層耦合約束仍能得到滿足。為此，本文提出一種將裝配關聯(lián)的零部件類進行統(tǒng)一交叉的方式，即本文的交叉算子的設計如下：

隨機選取一個節(jié)點上的部件類I*，I*及約束其裝配的所有子孫節(jié)點上的工件類構成的工件類集合為U，將U中的所有工件類(即以I*為根節(jié)點的子樹上的所有工件類)對應的工序基因位統(tǒng)一進行交叉互換，若I*不在產品總裝層，則基因交叉過程中仍需滿足交叉后其上一層部件的裝配約束。在父代1與父代2中按從左到右的順序抽出U中所含工件類對應的基因位得到集合X1和X2，并在各父代找出部件I*直接父節(jié)點上的Y*部件各子批首道工序的開工基因位，在X1和X2內將I*的各子批完工基因位分段插入子代，并能夠滿足Y*各子批裝配批量。如圖4所示的產品結構，若選中部件4，則將部件4與零件1和零件2的工序基因位一起進行交叉?；蚪徊孢^程如圖6所示，對于子代1，部件4的上層部件5的批數(shù)為1即未分批，則部件5開工需部件4的3個子批都完工，此時將X2中基因依次插入5-1之前的空白基因位；對于子代2，部件4和部件5均分為兩批，5-1和5-2各自開工都應在相應部件4的子批完工之后，在X1中則以4-1為截點將X1分為兩段，將1-1～4-1片段按順序插入5-1之前的空白基因位，刪除多余的空白基因位，將2-1～4-2片段插入5-2之前5-1之后的空白基因位，空白基因位不夠則將后續(xù)基因附著于最后一個空白基因位。若I*代表產品總裝層，則將該產品所有零部件的基因位進行統(tǒng)一交換，交叉過程中不用考慮交換基因的層級約束，只需將X1和X2中基因依次填入子代空白基因位即可。

2.2.4 改進型變異算子的設計

為了滿足分層耦合約束，變異算子設計如下：

步驟1在p種產品中隨機選取一種，并在染色體調度序列段中找出該產品所有零部件的基因位。

步驟2找出該產品所有部件所有子批的首道工序并附上標識。

步驟3附上標識的基因位將該產品整條染色體的基因序列分割為若干個子片段，在每個子片段內將基因反轉得到變異后的子代。

具體的變異操作如圖7所示，因為該染色體只包含圖4所示的一種產品的編碼信息，且各類工件的工序數(shù)量均為1，所以只需標識部件4和部件5的首道裝配工序基因位，染色體的分批方案段基因不進行任何操作，為4-1，4-2，5-1，4-3，5-2加上標識后將調度基因序列劃分成多個子片段，將子片段內基因反轉的實質是在滿足分層耦合約束的前提下，對其零件的加工基因位進行了分段反轉。

2.2.5 選擇策略

基于種群的適應度函數(shù)采用輪盤賭方法選出相應的后代，每個個體被選中的概率與其適應度成正比，一般步驟如下：

(4)產生[0,1]之間的隨機數(shù)r，若0≤r≤Q1，則選中P1；若Qi-1≤r≤Qi，則選中Pi。

3 仿真實驗

3.1 仿真參數(shù)與實驗設計

本文以圖8所示的產品BOM結構為實驗案例，根據(jù)前文3類典型產品結構的定義，將圖8a～圖8c產品結構歸為Flat型，圖8d～圖8f產品結構歸為Tall型，圖8g～圖8i產品結構歸為Complex型。

本文的多層級裝配作業(yè)車間由6個加工機器(a=6)和3個裝配單元(b=3)構成，每臺加工機器/裝配單元包含不同的加工/裝配工藝，每種BOM結構對應的產品需求數(shù)量服從離散均勻分布[4,10]，每道加工/裝配工序所需時間服從離散均勻分布[1,5]，工序準備時間與加工/裝配時間成比例，仿真參數(shù)設定總結如表1所示。

表1 仿真模型參數(shù)設定

續(xù)表1

本文實驗設計如下：

(1)基于可行域搜索算法的基礎性能驗證，將本文算法與文獻[7-8]同為基于可行域搜索的改進型遺傳算法在任務不分批的條件下進行對比，以驗證本文算法在處理此類含靜態(tài)分層耦合約束調度問題時的基礎性能。

(2)基于上述3類代表不同復雜程度的產品結構，探究加工/裝配兩階段4種分批策略(策略Ⅰ～策略Ⅳ)在這3種典型結構產品下的性能表現(xiàn)及隨不同梯度準備時間的變化趨勢，即通過比較4種分批策略在Flat型、Tall型、Complex型(每種產品類型下各含3種BOM結構)產品結構下的性能，分析其在3種典型產品結構下的適應性，并根據(jù)不同準備時間(t=0.2，t=0.5，t=1.0)分析各分批策略的變化情況。

(3)分批的導向性實驗。隨著任務規(guī)模的增大，算法的搜索效率和質量不可避免地會下降，為使最優(yōu)分批方案的搜索具有可操作性，探究更具方向性指導的分批策略，在p=9時即對9種BOM結構的產品進行統(tǒng)一分批調度，分析比較較大訂單規(guī)模下策略Ⅱ(隨機搜索策略)和策略Ⅴ(協(xié)同復雜性導向策略)的求解效率和質量，以探究更大規(guī)模生產任務下分批的方向性。

為評價本文不同分批策略下的調度性能，以工件最大完工時間為優(yōu)化目標，以裝配等待時間、工作中心稼動率、準備時間、算法運行時間等為觀測指標。具體評價指標與計算公式如表2所示。

表2 性能評價指標

本文的遺傳參數(shù)設置如下：種群大小為200；最大遺傳代數(shù)為60代；交叉概率為0.8；變異概率為0.05；代溝為0.9。本文數(shù)據(jù)基于MATLAB 2016b,在相同環(huán)境下對每次實驗重復運行30次取均值得到。

3.2 驗證算法的基礎性能

本文算法與文獻[7-8]算法都是針對多層級AJSP的可行域搜索算法，但文獻[7-8]算法用于求解不考慮加工/裝配任務分批生產的情況，各層級零部件之間的分層耦合約束為靜態(tài)，其算法的交叉、變異操作也考慮了這種靜態(tài)約束；若在該調度問題中考慮加工/裝配任務的分批生產，則由于子批允許分批生產和調度，各子批裝配任務開工并不需要等其直屬工件所有批次全部完成，只要等其直屬工件若干個能滿足其批量需求的子批完工即可開始，各層級零部件子批任務之間的分層耦合約束呈現(xiàn)高度動態(tài)性。因此，本文以處理靜態(tài)分層耦合約束的可行域方法為基礎，構建能夠應對獨立分批帶來的動態(tài)分層耦合約束的求解算法。鑒于本文算法與文獻[7-8]算法的適用范圍不同，后者只適用于解決不考慮分批的多層級AJSP，為本文所研究問題(即允許分批問題)的一個特例，因此本文在任務整批生產的條件下對算法進行對比，以驗證本文算法在不考慮任務分批調度環(huán)境下的基礎性能。對算法分別進行30次獨立實驗，統(tǒng)計各自的進化性能，如表3所示。本文以圖8所示的BOM結構為實驗案例，其中Flat表示對圖8a～圖8c結構產品進行統(tǒng)一調度，Tall表示對圖8d～圖8f結構產品進行統(tǒng)一調度，Complex表示對圖8g～圖8i結構產品進行統(tǒng)一調度，以30次獨立實驗最優(yōu)解的平均值、最優(yōu)值、最差值、標準差和CPU耗時進行統(tǒng)計。

表3 算法30次獨立實驗結果的比較

由表3可見，與文獻[7-8]算法相比，本文算法基于可行域的鄰域構建和搜索策略在3類實驗案例調度中的性能表現(xiàn)相當，即在不考慮任務分批的情況下，本文算法在處理包含靜態(tài)分層耦合約束的調度問題中也具有較好的適應性，求解效率與求解質量都能得到保證。因此，本文基于算法的可行域進行搜索，重點探究不同分批策略對不同產品結構調度的影響，以及大規(guī)模任務下具有一定導向型分批策略的性能表現(xiàn)。

3.3 分批策略對不同產品結構類型效果的分析實驗

為探究4種策略在3種典型產品結構下以及不同準備時間設置下的性能表現(xiàn)，采用上述目標函數(shù)、5個性能觀測指標、3種準備時間的設置、3種產品結構類型，共進行3×4×3=36組實驗。該階段算法搜索效率不是研究重點，因此不對t0進行統(tǒng)計說明。

表4所示為Flat型產品結構的實驗結果，可知：

表4 Flat類型實驗結果

(1)準備時間梯度較低時(t=0.2，0.5),策略Ⅲ優(yōu)于策略Ⅰ，對加工階段進行分批能夠提高加工中心稼動率，縮短工件之間的裝配等待時間，從而縮短生成周期；當準備時間設置較高時(t=1.0)，策略Ⅲ劣于策略Ⅰ，此時分批會使準備時間大幅上升，從而降低加工中心的稼動率，使生產周期延長。

(2)策略Ⅳ劣于策略Ⅰ。由于Flat型產品結構只包含單層裝配層級，裝配任務數(shù)遠少于加工任務數(shù)，若僅對部件進行分批，則部件的各個子批在同一時刻競爭有限的裝配資源，不僅不能提升裝配中心的稼動率，反而會增加部件子批之間的準備時間。

(3)準備時間梯度設置較低(t=0.2，t=0.5)時，策略Ⅱ表現(xiàn)最優(yōu)，因為零件分批能使部件子批的裝配工序提前進行，部件子批之間不需要在同一時刻競爭有限的裝配資源，所以有效提高了工作中心稼動率。然而隨著準備時間設置的增大，分批使子批之間的準備時間增大，從而延長了生產周期，因此策略Ⅱ劣于策略Ⅰ。

表5所示為Tall類型產品的實驗結果，可知：

表5 Tall類型實驗結果

續(xù)表5

續(xù)表5

(1)策略Ⅲ和策略Ⅳ均優(yōu)于策略Ⅰ。對于具有高裝配層級且每層級裝配關聯(lián)工件類較少的Tall型產品結構，零件加工進度影響部件裝配進度，每一低層級部件裝配進度也影響高層級部件裝配進度，對零/部件分批均能使更高層級部件的裝配進度提前，有效提升加工與裝配中心的稼動率；而且此時每一裝配層級的任務齊套性約束都嚴重影響后續(xù)高層級裝配任務的開工時間，對裝配階段每一層級的部件進行批量劃分均可使后續(xù)高層級部件裝配提前開工而加速生產進程，其分批優(yōu)化空間大于零件加工階段，因此策略Ⅳ優(yōu)于策略Ⅲ。

(2)策略Ⅱ下的生產周期表現(xiàn)最優(yōu)，因其綜合零件加工與部件裝配兩階段分批收益，每一層級部件都不需要在同一時刻競爭有限的裝配資源，子批任務能夠獲得較好的流動性，從而極大縮短任務間的裝配等待時間，明顯提高工作中心稼動率。

(3)隨著準備時間設置梯度的升高，分批使加工/裝配兩階段工件子批之間的準備時間大幅度上升，其在縮短生產周期上發(fā)揮的效力有所減弱。

表6所示為Complex類型產品的實驗結果，可知：

表6 Complex類型實驗結果

(1)對于含有較高裝配層級且每層級下裝配關聯(lián)工件類較多的Complex類結構的產品，對零部件分批均能使較小的子批以更好的流動性實現(xiàn)更靈活的進度協(xié)同，從而縮短裝配等待時間，提高工作中心稼動率，并縮短生產周期。

(2)當準備時間比例設置較低(t=0.2，t=0.5)時，在加工與裝配階段進行分批均能縮短生產周期，于是策略Ⅲ和策略Ⅳ均優(yōu)于策略Ⅰ；而且在加工階段分批能促進裝配階段分批調度的效果，因此策略Ⅱ表現(xiàn)最優(yōu)；當準備時間比例設置較高時(t=1.0)，因為Complex型產品結構所含工件類較多，所以分批會大幅增加零部件子批間的準備時間，工作中心稼動率下降，導致任一階段分批都不能為生產周期帶來收益，因此策略Ⅲ和策略Ⅳ均劣于策略Ⅰ，同時策略Ⅱ因兩階段都產生大量準備時間而表現(xiàn)最差。

3.4 隨機搜索策略與協(xié)同復雜性導向策略的對比實驗

本階段實驗為探究多層級裝配作業(yè)車間下分批的方向性，以解決訂單規(guī)模增大導致最優(yōu)分批方案存在搜索空間大、求解效率低的問題。基于策略Ⅴ提出的具體實驗步驟如下：

步驟1以p個待交付產品每種產品的最高裝配層級ki層(i=1，2，…，p)為第一優(yōu)先級，由高到低進行排序，并以產品下屬工件種類數(shù)為第二優(yōu)先級，由多到少進行排序，假定產品排序后為J1，J2，…，Jp。

步驟2找出產品的關鍵路徑，假設一產品下的各類零部件從零件加工層到產品總裝層形成q條路徑，計算各條路徑中所含零部件的總加工時長Tj和工序總數(shù)Uj(j=1，2，…，p)，記q條路徑中的工時最大值為Tmax，工序最大值為Umax，則每條路徑的關鍵性

(14)

式中CRj值最大的路徑即為關鍵路徑。

步驟3對每類產品關鍵路徑上的工件按順序進行累加分批調度，即第1次調度僅對J2中關鍵路徑上的工件類等量分批，J1其余工件類及其余產品所含工件類均不分批；第2次調度在第1次的基礎上再對J2產品關鍵路徑上的工件類等量分批；第p次調度對所有產品(J1，J2，…，Jp)關鍵路徑上的工件等量分批，其余工件不分批。

由前一階段實驗可知，隨著準備時間比例的增大，分批效力逐漸下降，當準備時間設置為t=1.0時，分批在本文實驗設置中不能給調度性能帶來正向收益，因此用準備時間設置中間值(t=0.5)對圖8a～圖8i結構產品(p=9)進行統(tǒng)一調度，采用策略Ⅴ共進行9組實驗(實驗編號為1～9)，并與全域隨機搜索策略Ⅱ(策略Ⅱ時3種產品結構的調度性能最優(yōu))的實驗結果(實驗編號為10)進行對比。該階段的探究重點為算法搜索效率和求解質量，實驗終止條件為收斂200代，并采用訂單生產周期、算法運行時間作為觀測指標，以每組實驗重復運行30次的均值取整進行說明。

如圖9所示，協(xié)同復雜性導向策略Ⅴ在搜索質量和效率上優(yōu)于隨機搜索策略Ⅱ。在策略Ⅴ的9組實驗下，生產周期變化曲線呈明顯的先下降后上升的趨勢，搜索時間也隨分批任務數(shù)的增多呈穩(wěn)步上升趨勢，獲得的最優(yōu)調度結果為1 240 h，耗時290 s，而策略Ⅱ的調度結果為1 320 h，耗時542 s。在較大訂單規(guī)模下對所有工件類進行完全隨機搜索分批，調度結果和算法搜索效率均表現(xiàn)較差，不能滿足實際生產的需求，而策略Ⅴ以一定的導向性選擇產品和產品中具體的工件類進行優(yōu)先分批，有效地縮小了搜索范圍，保證了求解質量和效率。圖10所示為所給的策略Ⅱ和策略Ⅴ(實驗編號為3)下30次實驗中最優(yōu)值的收斂曲線，可見策略Ⅴ以更快的收斂速度獲得了更優(yōu)的解。

4 結束語

在多層級裝配作業(yè)車間中，分層耦合約束導致可行解所構成的可行域范圍小，批量劃分的隨機性使可行域的動態(tài)變化程度更高，問題的求解更復雜。本文提出改進型遺傳算法對初始種群生成方式和交叉變異算子進行設計，使問題的搜索過程始終保持合法與可行，驗證了算法的有效性，并基于可行域搜索進行了以下兩方面研究：

(1)加工/裝配兩階段的4種分批策略對3種典型產品結構適應性的研究 在產品的零件加工與部件裝配兩階段分別考慮分批，提出4種分批策略并探究其不同產品結構下的性能表現(xiàn)，以及不同準備時間設置下的變化趨勢。實驗結果表明，對每一層級工件進行分批都能使其以更好的流動性滿足后續(xù)高層級裝配任務的齊套性需求，從而優(yōu)化調度結果；在調度時對具有更高裝配層級和更多裝配關聯(lián)工件類結構的產品進行批量劃分，能夠通過更靈活的任務間進度協(xié)同來縮短生產周期；隨著準備時間設置比例的增加，批量劃分的子批之間會產生大量的準備時間，使工作中心的稼動率下降，從而減弱分批效力，甚至產生負收益。

(2)隨機搜索策略與協(xié)同復雜性導向策略的求解效果對比研究 隨著訂單規(guī)模的增大，完全隨機分批會增大搜索空間，降低算法的搜索效率和質量，本文提出一種基于任務協(xié)同性的分批策略，使批量劃分時能更有針對性地選擇產品以及產品中的具體工件類。實驗結果表明，批量劃分時優(yōu)先選擇高裝配層級、多工件類的產品及其關鍵路徑上的工件，能夠使任務之間有更好的協(xié)同性，使最優(yōu)分批調度方案的搜索更具方向性。

針對本文的不足，未來將從以下兩個方面進行研究：①從更多維度區(qū)別產品和工件類的分批優(yōu)先級，以使分批更具可操作性，如工件的需求數(shù)量、工件的種類(零/部件)；②在以交貨期、生產成本等為優(yōu)化目標的多目標調度模型中考慮分批調度，使分批方案更符合實際生產。