曾創(chuàng)鋒，劉建軍，陳慶新，毛 寧

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

家電企業(yè)總裝車間中，來自客戶的工單具有多品種、小批量的特征，每一張工單都將生產(chǎn)某一型號的一款產(chǎn)品，生產(chǎn)該型產(chǎn)品需要指定的型號物料；加工單元由多條異構的并行加工線體構成，加工線體所采用的技術、線體新舊程度有所不同，部分型號的物料只能在指定的部分線體上進行加工，同時，根據(jù)相鄰工單所加工的產(chǎn)品型號及其使用的物料型號的異同，需要對線體的設置進行相關調整。這類問題屬于典型的帶工單加工約束和序相關設置時間的無關并行機調度問題(unrelated parallel machine scheduling problem with job processing constraints and sequence-dependent setup times，UPMSP_JPCSST)，即同一張工單在不同線體上的加工時間不盡相同，且工單只能在特定的部分線體上進行加工，同時，工單上機的設置時間取決于前后相鄰工單的順序。該問題以極小化最大完工時間(Cmax)為優(yōu)化目標，使用三元組[1-2]可以將其描述為Rm|si,j,Mj|Cmax。UPMSP_JPCSST是UPMSP中非常復雜的一類，屬于NP完全問題，對其進行求解非常困難。因此，對UPMSP_JPCSST求解算法的研究具有較高的理論和應用價值。

目前對于UPMSP_JPCSST的求解方法主要有精確算法、啟發(fā)式規(guī)則和元啟發(fā)式方法。其中，精確算法經(jīng)常使用混合整數(shù)規(guī)劃(mixed integer programming, MIP)模型、分枝定界[3]等方法以求得問題的最優(yōu)解，但求解費時并受限于問題的規(guī)模，難以對問題進行快速求解；而啟發(fā)式規(guī)則[4]雖然易于實施，但所得解的質量難以保證；而元啟發(fā)式方法則有較大的塑性空間，其求解速度與求解質量取決于對算法本身的挖掘，一個優(yōu)異的元啟發(fā)式方法能在合理的時間內得到盡可能好的滿意解[5]，因此得到越來越多的關注[3,6-8]，如遺傳算法(genetic algorithm, GA)、模擬退火算法(simulated annealing, SA)、禁忌搜索算法(tabu search, TS)等。作為一種廣泛應用于求解車間調度問題的方法，GA算法通過選擇和交叉操作從父代種群獲取優(yōu)良的遺傳信息，進而對問題的解空間中可能存在優(yōu)良解的區(qū)域進行搜索，這使得GA具有全局搜索能力，但正是過于注重搜索的廣度反而導致挖掘深度不足。而將具有概率突跳機制的SA、具有記憶禁忌機制的TS等注重局部信息深度挖掘的搜索算法與GA算法相結合，能彌補GA算法局部優(yōu)化能力的不足，且能幫助其跳出或避免陷入局部最優(yōu)，增強搜索性能。因此，相關改進型混合算法[9-12]，如GASA、GATS等得到廣泛的重視。但是該類算法自身框架復雜性可能會導致其單代運行時間較長，使得這類算法具有運行時間依賴性，仍難以對問題進行快速求解。

迭代貪心算法(iterated greedy algorithm, IG)[13]是一種新穎的、基于單解的、包含破壞與構建2個階段的啟發(fā)式算法。IG涉及極少控制參數(shù)，計算速度極快，優(yōu)化效果優(yōu)異，得到廣泛重視，并應用到UPMSP中[14]。算法的破壞、構建操作可能會因為其機制及其鄰域的契合性、算法的快速性而適合UPMSP_JPCSST IG中序相關設置時間角度的優(yōu)化。因此，將傳統(tǒng)GA與計算速度快、側重從局部層面對解空間進行搜索的IG算法進行合理融合，具有較高的研究價值。根據(jù)文獻調研，對于UPMSP，基于GA和IG的混合求解算法的研究尚無文獻報道。

本文提出一種遺傳?迭代貪心算法(genetic algorithm-iterated greedy algorithm, GAIG)，用以求解最小化最大完工時間Cmax指標下的UPMSP_JPCSST。

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

1.1 問題描述

設工單集合J有n個相互獨立的工單，這些工單在時間為0時可用；m臺加工線體(m＞1)構成一個制造系統(tǒng)；工單j (j∈J)需加工數(shù)量不等的某一款產(chǎn)品，該款產(chǎn)品只需1道工序即可完工，且只能由滿足工單加工約束的線體加工；工單的加工時間取決于加工線體及該工單需加工產(chǎn)品的數(shù)量，任何線體k同一時刻只能加工1個工單；在線體上加工不同產(chǎn)品時需要設置時間，設置時間依賴于相鄰工單所加工產(chǎn)品的產(chǎn)品類型和物料類型屬性。

1.2 假設條件

1) 工單數(shù)量及其對應需生產(chǎn)的產(chǎn)品數(shù)量已知且確定；

2) 每個工單只生產(chǎn)一款產(chǎn)品，且不能被分割；

3) 每個工單將加工的產(chǎn)品型號及其物料型號已知且確定；

4) 各種物料型號的線體適用集合已知且確定；

5) 對于每一種物料型號，至少存在一條線體可以完成加工；

6) 工單一旦在線體上開始加工，就不允許中途停止而加工其他工單；

7) 同一條線體同一時刻只能加工一張工單；

8) 所有的工單和線體在0時刻可用。

1.3 符號定義

模型相關變量如表1所示。

表1 模型參數(shù)符號及其說明Table 1 Model parameter symbols and descriptions

1.4 數(shù)學模型

根據(jù)以上假設與條件，對Rm|si,j,Mj|Cmax建立的數(shù)學模型如下。

其中，式(1)為目標函數(shù)；約束(2)表示每一個工單只能被分派到一個線體上加工；約束(3)表示每一個工單只能被加工1次；約束(4)確定每一個工單的完工時間，并確保工單j不會先于本身、晚于本身完工，且緊鄰工單之間存在序相關的設置時間；約束(5)表示任何線體上有且只有1個工單屬于該線體第1個上機工單；約束(6)表示Cmax為所有工單的最大完工時間；約束(7)表示虛擬工單不占用線體使用時間且其完工時間為0；約束(8)表示工單j完工時間的可行域約束；約束(9)為工單加工約束，工單不允許被指派到不可加工的線體上；約束(10)為決策變量的取值約束。

2 混合遺傳算法實現(xiàn)

本文針對UPMSP_JPCSST提出將GA算法和IG算法的破壞與構建操作相結合，從而設計兼?zhèn)淙謨?yōu)化能力和局部優(yōu)化能力的求解算法。該操作側重于解的局部探索，可以很好地和GA算法的全局搜索相結合，并由GA算法的進化操作保留執(zhí)行構建操作得到的優(yōu)良染色體片段。此外，把破壞、構建機制嵌入變異操作，從而保證種群的多樣性。GAIG的求解框架如圖1所示。

2.1 編碼設計

根據(jù)UPMSP_JPCSST的特性，可加工線體限制會使調度解空間中存在不可行解。為避開不可行解，提高求解效率，本文采用一種前后雙層的整數(shù)染色體編碼方式表示一個可行的調度計劃，即工單排序向量(job sequence vector，JV)、線體選擇向量(machine assignment vector，MV)。其中，JV層基因必須滿足工單唯一性約束，MV層基因必須滿足工單加工約束。以圖2中5張工單、3條線體的問題為例，如果該染色體是合法的，那么表示在線體1上加工的工單序列為4；在線體2上加工的工單序列為2→5；在線體3上加工的工單序列為1→3。

2.2 帶修復交叉操作

交叉算子作用于染色體的JV層。要保證交叉后的新染色體仍然可行，要求新染色體必須滿足上述2個約束。

圖1 GAIG求解框架Figure 1 Framework of GAIG

圖2 染色體的編碼方法Figure 2 A coding solutions of chromosome

1) 隨機產(chǎn)生一個交叉點，交換父代染色體JV層(下面簡稱P)交叉點前的基因片段，以產(chǎn)生子代C1；2) 逐個尋找C1上的每一個基因在P2中的位置，將P2上該位置的基因替換為空值并將C1上的該基因替換為空值；3) 完成遍歷后，P2中剩余的基因即子代C1的缺失基因集合W2，C1中剩余的基因即子代C1的多余基因集合W1；4) 在W1內按從左到右的順序逐個取出多余的基因，并在C1中找到第1個對應的基因，在基因集合W2內按照從左到右的順序取出缺失的基因填充。5) 按交叉前P1染色體首尾2層的基因映射關系，填充交叉后C1染色體MV層的基因，得到合法的新子代染色體C1；新子代染色體C2以同樣的方法得到。假設交叉位置為3，交叉過程如圖3所示。

圖3 交叉操作示意圖Figure 3 Diagram of cross operation

2.3 變異操作

2.3.1 面向更換線體鄰域結構

本鄰域結構作用于染色體的MV層，該層每個基因位都有其特定值域，即變異后需滿足工單加工約束。其基本思想為：歷遍染色體JV層，對于JV層中被選擇的基因，在其特定值域內隨機產(chǎn)生加工線體基因，并以該線體的基因編號替換掉原有的線體基因，如圖4所示。

2.3.2 基于IG算法的破壞與構建操作

圖4 鄰域結構示意圖Figure 4 Diagram of neighborhood structure

為獲得更好的優(yōu)化解，結合該企業(yè)UPMSP_JPCSST和GA算法的特點，在求解算法的變異算子中嵌入一種基于IG[13]算法的破壞與構建機制。對交叉產(chǎn)生的新個體，以概率執(zhí)行該操作(具體如圖1和2.4節(jié)所示)，從而提高種群的多樣性。

2.4 局部優(yōu)化操作

局部優(yōu)化操作分為破壞和構建2個階段，詳細步驟如下。

破壞階段以隨機方式從個體序列中移除部分序列。文獻[13]通過試驗得到的移除長度d并沒有通用性，本文經(jīng)過測試得到較適合本案例的破壞長度d。在變異操作的破壞步驟中，初始破壞長度d0=0.1n，在迭代進程中，隨著種群多樣性的降低而線性變長dgen=dgen?1α；在局部優(yōu)化操作中，初始破壞長度隨迭代進程及種群進化情況而變化，dgen=dgen?1δεiter；每代更新d值。其中，α為上升系數(shù)，α=1.01；δ為下降系數(shù), δ=0.97；ε為種群進化停滯系數(shù)，ε=1.05；iter為種群進化停滯代數(shù)；gen為當前迭代代數(shù)；n為工單數(shù)量。

構建階段將被移除的序列按照被移除的順序逐個重新插回原保留序列，直到重新構成完整的合法序列。類似于NEH (the heuristic of NAWAZ, ENSCORE and HAM)[15]算法，定義工單的插入鄰域為已有序列中所有可能插入的位置，即將待插入工單逐個插入保留序列上的每一個可插入位置。根據(jù)目標函數(shù)值選擇最優(yōu)的位置，直到合法序列重新生成。

終止條件若執(zhí)行局部搜索的個體停滯進化代數(shù)達到5次，或個體得到進化，則結束算子，如圖5所示。

2.5 GAIG算法步驟

在GAIG中，初始種群隨機生成，選擇算子采用輪盤賭[16]方法，更新策略采用(μ＋σ)策略[17]，算法以運行時間作為終止準則，運行時間根據(jù)算例的規(guī)模而定，具體如 3.2 節(jié)所示。算法步驟如圖6所示。

圖5 局部優(yōu)化方法偽碼圖Figure 5 Pseudo-code of local optimization method

圖6 GAIG算法偽碼圖Figure 6 Pseudo-code of the proposed GAIG

3 實驗及分析

3.1 測試算例與實驗環(huán)境設定

由于廣東某大型合作家電企業(yè)對提供的兩千多條具有代表性的實際案例數(shù)據(jù)有保密性要求，本文不便公開其數(shù)據(jù)。為了驗證本文所提出的GAIG算法求解該企業(yè)車間UPMSP_JPCSST的性能，這里以該案例數(shù)據(jù)為基礎，提取案例所具備的特征，引入文獻[18]實驗設計的思想，隨機生成24組具有企業(yè)實際問題特征的測試算例，算例命名格式為n-?δγ。其中，參數(shù)n為工單數(shù)量；參數(shù)?j和δk共同確定線體k對工單j所用物料的單位產(chǎn)能，衡量加工能力的異質性。?j衡量工單j的異質性，決定同一線體對不同的工單所用物料的單位產(chǎn)能；δk衡量線體k的異質性，決定不同的線體對同一個工單所用物料的單位產(chǎn)能。對于工單j和線體k，μj～U(?j)，ξk～U(δk)，則線體k對工單j所用物料的單位產(chǎn)能σjk=μjξk；參數(shù)γ表示測試環(huán)境中所有工單將會用到的物料型號與所屬產(chǎn)品型號的種類規(guī)模，構成了換產(chǎn)的異質性；參數(shù)Lj為工單j需生產(chǎn)的產(chǎn)品數(shù)量，詳細參數(shù)如表2所示。線體上第1個上機工單其設置時間為300，相鄰工單其產(chǎn)品型號相同則不需要設置時間，相鄰工單其產(chǎn)品型號不相同但加工所需的物料型號相同，其設置時間為100，否則設置時間為300。

表2 測試算例參數(shù)Table 2 Parameters of experimental case

運行環(huán)境如下。計算機系統(tǒng)為Windows10，處理器為Intel?Core?i7-8700 @ 3.20 GHz 3.19 GHz，RAM內存為16.0 GB，算法采用Matlab R2016b編程實現(xiàn)。

3.2 各種算法性能比較

首先，為更好地測試GAIG算法在求解該企業(yè)車間UPMSP_JPCSST時的有效性，實驗以NEH[18]算法、 IG算法、GASA算法、SA算法、GA算法和GATS算法為比較對象。7種算法在每個算例組合下分別進行10次獨立實驗，將得到的最大完工時間Cmax、平均流水時間Fave和換產(chǎn)時間占比P共1個優(yōu)化指標和2個觀察指標求均值，作為算法評估的依據(jù)，結果如表3所示。其中，GAIG算法參數(shù)設置如下：種群大小為100，交叉率Pc為0.8，變異率Pm為0.05，移除長度d如2.4節(jié)所述；其他算法中SA初始溫度為100，冷卻系數(shù)為0.95；TS的禁忌長度為100，候選解個數(shù)為100個；通用參數(shù)及鄰域結構與GAIG一致。所有算法均隨機初始化初始種群。此外由于混合算法與單一算法每一代的迭代時間差異性大，且基于該企業(yè)對于算法運行時間的苛刻要求，本文以運行時間作為算法的終止條件。工單規(guī)模為50的算例，運行時間為20 s；工單規(guī)模為100的算例，運行時間為40 s；工單規(guī)模為200的算例，運行時間為80 s。表3為7種算法在各個算例組合下的測試結果。測試結果中，7種算法的性能分布和對企業(yè)實際案例數(shù)據(jù)進行計算得到的性能分布相似，表明以該方法生成的隨機測試數(shù)據(jù)具有一定的可用性。

由表3可知，1) 從{#1,#3,#5,#7}、{#2,#4,#6,#8}、{#9,#11,#13,#15}、{#10,#12,#14,#16}、{#17,#19,#21,#23}和{#18,#20,#22,#24}對比組可以看出，在加工能力異質性大的測試環(huán)境中，擁有更換線體鄰域結構的算法如SA、GASA等具有優(yōu)勢，其能夠從壓縮工單的加工時間的角度減少平均流水時間，進而提升調度性能；而相比基于部分序列構建的IG算法，NEH這類全序列構造型的算法也能夠從該角度取得更好的優(yōu)化效果。

2) {#1,#2}、{#3,#4}、{#5,#6}、{#7,#8}、{#9,#10}、{#11,#12}、{#13,#14}、{#15,#16}、{#17,#18}、{#19,#20}、{#21,#22}和{#23,#24}定量對比組可以看出，無論換產(chǎn)異質性大還是小，NEH、IG等具有構造機制的算法均能取得相對于其他算法更小的換產(chǎn)時間占比；在換產(chǎn)異質性增大的擾動下，雖然各個算法性能指標均在一定程度上得到劣化；但是相對于其他算法，NEH和IG算法的性能指標的劣化程度相對緩和，其能夠從壓縮工單之間的設置時間的角度極小化最大完工時間。

3) 從{#1,#9,#17}、{#2,#10,#18}、{#3,#11, #19}、{#4,#12,#20}、{#5,#13,#21}、{#6,#14,#22}、{#7,#15,#23}和{#8,#16,#24}定量對比組可以看出，算例規(guī)模的擾動對SA的影響較大。SA隨著算例規(guī)模的增大，性能急劇下降，只適合小規(guī)模算例。而具有并行搜索優(yōu)勢的算法如GA、GASA、GATS則隨著算例規(guī)模的增大，優(yōu)勢逐漸顯現(xiàn)，但受制于運行時間，優(yōu)勢無法完全體現(xiàn)。而IG、NEH算法基于不受運行時間節(jié)制的優(yōu)勢，隨著算例規(guī)模的增大，性能指標逐漸具有優(yōu)勢。在加工能力異質性小的環(huán)境下，IG和NEH均會在算例規(guī)模逐步增大時偶爾出現(xiàn)不同程度的性能指標劣化現(xiàn)象，十分不穩(wěn)定。

表3 7種算法實驗統(tǒng)計結果Table 3 Test statistical results of seven algorithms

4) 在各個算例組合中，GAIG算法幾乎都能得到最好的結果。首先GAIG算法具有遺傳算法并行搜索、迭代進化的特點，不但具有面向加工能力方向進行優(yōu)化的鄰域結構，又擁有針對換產(chǎn)時間方向進行優(yōu)化的機制，使GAIG算法能夠在各種復雜的算例組合中具有普遍可用性，同時，又區(qū)別于其他混合算法對運行時間的依賴性，具有更優(yōu)的調度性能。其次，以200-?UδU-γU算例為例，圖7分別給出了除確定性算法NEH以外其他6種算法在80 s內的最優(yōu)Makespan收斂曲線?？梢钥闯觯珿AIG算法的收斂速度明顯快于除IG算法以外的其他算法，運行時間非常短且優(yōu)化質量也比其他算法更高。因此，GAIG算法無論在運算時間還是運算結果上來看，都具有相對于其他算法的優(yōu)越性，能夠滿足該企業(yè)對算法的快速反應和高質量方案的要求。最后，為了說明GAIG算法的魯棒性，排除確定性算法NEH后，將6種算法在每個算例規(guī)模下的8個測試環(huán)境中多次運行所得數(shù)據(jù)繪制成箱線圖，如圖8所示。從圖8的統(tǒng)計結果不難看出，GAIG算法對各種算例組合都保持著較高的求解魯棒性，能夠滿足該企業(yè)對算法的高魯棒性要求。

圖7 收斂曲線Figure 7 Convergence curves

圖8 6種算法在不同規(guī)模算例下的箱線圖Figure 8 The boxplot of 6 algorithms in different scale case

4 結束語

本文針對家電企業(yè)總裝車間需要同時考慮工單加工約束和序相關設置時間等難點，以最小化最大完工時間為目標，設計GAIG算法。該算法結合遺傳算法全局搜索性能較優(yōu)和IG算法局部優(yōu)化性能較強且速度快的優(yōu)點，通過遺傳算法進行全局搜索尋得的較優(yōu)解作為局部搜索算法的初始解進行深度搜索，而經(jīng)過破壞與構建機制深度優(yōu)化的高質量解反過來提高遺傳算法種群的多樣性。同時，在各種具有企業(yè)實際數(shù)據(jù)特征的測試算例中與其他算法進行比較，說明該算法的有效性、穩(wěn)定性與魯棒性，符合企業(yè)實際生產(chǎn)的要求。

針對本文的不足，未來將從以下2個方面做進一步的研究。1) 考慮帶有交貨期等更為復雜的車間環(huán)境；2) 研究極小化最大完工時間、拖期率和齊套性的多目標優(yōu)化算法。