靜態(tài)知識(shí)化制造環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間周期性自進(jìn)化研究

姜天華　嚴(yán)洪森　汪　崢

東南大學(xué)復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室,南京,210096

靜態(tài)知識(shí)化制造環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間周期性自進(jìn)化研究

姜天華嚴(yán)洪森汪崢

東南大學(xué)復(fù)雜工程系統(tǒng)測量與控制教育部重點(diǎn)實(shí)驗(yàn)室,南京,210096

針對靜態(tài)知識(shí)化制造環(huán)境下的航空發(fā)動(dòng)機(jī)裝配車間，研究了知識(shí)化制造系統(tǒng)自進(jìn)化問題，采用滾動(dòng)時(shí)域方法實(shí)現(xiàn)了該裝配車間的周期性自進(jìn)化。根據(jù)問題的特點(diǎn)，建立了系統(tǒng)在每個(gè)決策時(shí)刻的靜態(tài)子問題的數(shù)學(xué)模型，提出了基于初始決策方案的滾動(dòng)規(guī)則，進(jìn)而給出了一種求解自進(jìn)化問題的兩階段算法。針對所建立的數(shù)學(xué)模型，設(shè)計(jì)了一種具有雙層結(jié)構(gòu)的遺傳算法(BiGA)。最后通過仿真驗(yàn)證了模型和算法的有效性和可行性，并分析了滾動(dòng)窗口和滾動(dòng)步長的大小對生產(chǎn)性能的影響。

靜態(tài)知識(shí)化制造環(huán)境；自進(jìn)化；滾動(dòng)時(shí)域；雙層遺傳算法；兩階段算法

0　引言

知識(shí)化制造系統(tǒng)(knowledgeable manufacturing system,KMS)[1]自被提出以來，已得到了廣泛的關(guān)注。自進(jìn)化是知識(shí)化制造系統(tǒng)的重要特征之一，其含義為對于一個(gè)特定的制造系統(tǒng)， 在不改變生產(chǎn)控制策略的前提下，通過對系統(tǒng)自身的調(diào)整來提高生產(chǎn)性能、實(shí)現(xiàn)預(yù)期生產(chǎn)目標(biāo)，并快速響應(yīng)生產(chǎn)環(huán)境的變化。自進(jìn)化與自適應(yīng)[2]不同，它所強(qiáng)調(diào)的是制造系統(tǒng)的“自變”，即自身的調(diào)整。

航空發(fā)動(dòng)機(jī)的裝配是整個(gè)發(fā)動(dòng)機(jī)制造過程的龍頭，其裝配成本大約占生產(chǎn)總成本的40%，這使得先進(jìn)的裝配數(shù)字化技術(shù)在航空發(fā)動(dòng)機(jī)裝配生產(chǎn)中的地位越來越重要[3]。航空發(fā)動(dòng)機(jī)的裝配可以用一種樹形圖表示。為了表述方便，將零件的加工及零部件之間的裝配統(tǒng)稱為“加工”。這類產(chǎn)品的生產(chǎn)調(diào)度問題通常被認(rèn)為是裝配作業(yè)車間調(diào)度問題(assembly job shop scheduling problem,AJSSP)[4-7]。目前關(guān)于AJSSP的文獻(xiàn)大都針對一般的裝配作業(yè)車間，很少涉及航空發(fā)動(dòng)機(jī)裝配車間，并且上述文獻(xiàn)中都假設(shè)制造系統(tǒng)自身的參數(shù)是固定不變的，而在實(shí)際生產(chǎn)中制造系統(tǒng)的某些參數(shù)(如機(jī)器上的工人數(shù)、燃?xì)饬俊㈦娏Φ?是可調(diào)的，它們往往會(huì)影響整體性能。在航空發(fā)動(dòng)機(jī)裝配車間中，裝配組內(nèi)的工人數(shù)可以視為系統(tǒng)的參數(shù)，并且工序的加工時(shí)間是可控的，其大小由工人數(shù)決定。目前在很多有關(guān)系統(tǒng)參數(shù)可調(diào)、加工時(shí)間可控的車間調(diào)度問題的文獻(xiàn)中，系統(tǒng)參數(shù)和調(diào)度方案一旦確定，則在整個(gè)生產(chǎn)過程中都是不變的[8-9]。然而，在實(shí)際生產(chǎn)中生產(chǎn)決策往往是分段進(jìn)行的，如一月、一周、一天或一個(gè)班次等[10]。受此啟發(fā)，可采用周期性自進(jìn)化操作觸發(fā)機(jī)制，根據(jù)實(shí)際生產(chǎn)情況動(dòng)態(tài)地調(diào)整系統(tǒng)參數(shù)，并在新參數(shù)的基礎(chǔ)上安排生產(chǎn)，直到所有生產(chǎn)任務(wù)完成為止。

系統(tǒng)參數(shù)調(diào)整是制造系統(tǒng)自身調(diào)整的途徑之一，本文以此來研究靜態(tài)生產(chǎn)環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間的自進(jìn)化問題。采用滾動(dòng)時(shí)域方法實(shí)現(xiàn)該裝配車間周期性自進(jìn)化，構(gòu)建了系統(tǒng)在各決策時(shí)刻靜態(tài)決策子問題的數(shù)學(xué)模型，提出了一種基于初始決策方案的滾動(dòng)規(guī)則，并給出了一種解決靜態(tài)環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間自進(jìn)化問題的算法。根據(jù)模型的結(jié)構(gòu)和裝配生產(chǎn)的特點(diǎn)，提出了一種雙層遺傳算法(bi-level genetic algorithm,BiGA)對模型進(jìn)行求解。用實(shí)例驗(yàn)證了模型與算法的有效性和可行性，最后通過仿真對滾動(dòng)窗口規(guī)模和滾動(dòng)步長對生產(chǎn)性能的影響進(jìn)行了初步分析。

1　自進(jìn)化問題相關(guān)定義

定義1靜態(tài)知識(shí)化制造環(huán)境下，在初始時(shí)刻只通過一次決策活動(dòng)得到的制造系統(tǒng)自身調(diào)整方案和生產(chǎn)調(diào)度方案，稱為初始決策方案。

定義2根據(jù)當(dāng)前已知的生產(chǎn)信息，重新調(diào)整制造系統(tǒng)自身并制定調(diào)度方案的一系列動(dòng)作，稱為自進(jìn)化操作。周期性自進(jìn)化操作觸發(fā)機(jī)制是指系統(tǒng)每隔一段時(shí)間或每加工完一定數(shù)量的工件、工序就執(zhí)行自進(jìn)化操作。

定義3通過自進(jìn)化操作得到的制造系統(tǒng)自身調(diào)整方案和調(diào)度方案，稱為自進(jìn)化決策方案。

2　航空發(fā)動(dòng)機(jī)裝配車間介紹

圖1　航空發(fā)動(dòng)機(jī)裝配過程

航空發(fā)動(dòng)機(jī)的裝配過程比較復(fù)雜，每臺(tái)發(fā)動(dòng)機(jī)至少要經(jīng)歷兩次裝配才能出廠，如圖1所示。整個(gè)裝配過程分為一次裝配和二次裝配。一次裝配完的發(fā)動(dòng)機(jī)在工廠試車合格后，需經(jīng)歷分解洗滌和故障檢驗(yàn)兩個(gè)環(huán)節(jié)，進(jìn)入二次裝配階段重新裝配，并進(jìn)行檢驗(yàn)試車，若試車合格，即可出廠。若在任一裝配階段內(nèi)試車不合格，則重新進(jìn)行分解洗滌和故障檢驗(yàn)，并替換故障件，然后重復(fù)該階段裝配操作，直到合格為止。

裝配車間內(nèi)有多個(gè)裝配班，如前后機(jī)匣班、機(jī)加班、傳裝班等，每個(gè)裝配班由一個(gè)或多個(gè)功能相同的裝配組組成，每個(gè)裝配組內(nèi)都配有工人、專用工具和設(shè)備。此外，根據(jù)生產(chǎn)量的大小，車間內(nèi)還配備多種裝配車，如總裝配車、部件裝配車，裝配車可按照工序的不同在裝配組之間移動(dòng)[11]。

3　靜態(tài)環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間自進(jìn)化

滾動(dòng)時(shí)域方法常被用于處理具有計(jì)算復(fù)雜性和動(dòng)態(tài)不確定性大規(guī)模調(diào)度問題，它是一種在時(shí)間上滾動(dòng)前進(jìn)的多次決策方法[12-13]。本文結(jié)合滾動(dòng)時(shí)域方法將全局問題分解成若干個(gè)局部子問題，每個(gè)局部子問題對應(yīng)一個(gè)滾動(dòng)窗口。采用基于工序數(shù)的周期性自進(jìn)化操作觸發(fā)機(jī)制，每加工完一定數(shù)量的工序就執(zhí)行自進(jìn)化操作，生成新的決策方案，如此循環(huán)迭代下去，直到所有工序完工為止。由此可見，整個(gè)自進(jìn)化的過程是動(dòng)態(tài)的，但由于每個(gè)決策時(shí)刻的相關(guān)生產(chǎn)信息(如待調(diào)度的工序、裝配組的狀態(tài)(忙/閑)等)都是確定可知的，故每個(gè)子問題仍是一個(gè)靜態(tài)的決策問題。

定義4靜態(tài)決策子問題中包含的工序的集合稱為滾動(dòng)窗口。滾動(dòng)窗口的規(guī)模ε為靜態(tài)決策子問題中參與優(yōu)化的工序的數(shù)目。

定義5知識(shí)化制造系統(tǒng)在自進(jìn)化的過程中每加工完η(η=1，2，…，ε)道工序就執(zhí)行自進(jìn)化操作，我們將η稱為滾動(dòng)步長。

自進(jìn)化過程可表述如下：初始零時(shí)刻利用當(dāng)前已知信息確定一個(gè)滾動(dòng)窗口，對窗口內(nèi)的靜態(tài)決策子問題進(jìn)行求解，得到一個(gè)自進(jìn)化決策方案。按照該方案進(jìn)行生產(chǎn)，將窗口內(nèi)前η道工序的完工時(shí)間T作為下一個(gè)決策時(shí)刻。由于裝配車間內(nèi)的各工序在不同裝配組內(nèi)并行地加工，故在T時(shí)刻可能有多道工序同時(shí)完工。假設(shè)此時(shí)窗口內(nèi)實(shí)際已加工完的工序數(shù)為σ， 則σ≥η。此外，T時(shí)刻當(dāng)前窗口內(nèi)還可能會(huì)有β(β≥0)道工序處于正在加工狀態(tài)，因此，當(dāng)前窗口內(nèi)剩余未加工工序數(shù)為ε-σ-β。構(gòu)造新的滾動(dòng)窗口時(shí)，首先需去除當(dāng)前窗口內(nèi)已完工和正在加工的σ+β道工序，然后從當(dāng)前窗口外選取σ+β道未加工工序與當(dāng)前窗口內(nèi)剩余的ε-σ-β道未加工工序一起構(gòu)成新的優(yōu)化工序集。由于車間內(nèi)總工序數(shù)有限，最后一個(gè)滾動(dòng)窗口內(nèi)的工序數(shù)可能小于ε，此時(shí)將窗口內(nèi)所有工序加工完，滾動(dòng)結(jié)束。

3.1靜態(tài)決策子問題

3.1.1問題描述

由于每個(gè)滾動(dòng)窗口內(nèi)所優(yōu)化的工序集不同，故首先要根據(jù)工序所需的裝配班確定本次進(jìn)化的裝配班的集合。各裝配班內(nèi)包含固定數(shù)目的工人和若干個(gè)功能相同的裝配組。裝配組的工人數(shù)可在一定的范圍內(nèi)進(jìn)行調(diào)整。靜態(tài)決策子問題的目標(biāo)是確定各裝配組內(nèi)的工人數(shù)并制定生產(chǎn)調(diào)度方案，使得人員變動(dòng)成本和調(diào)度成本的加權(quán)和(即生產(chǎn)成本)最小。需要說明的是，人員變動(dòng)意味著裝配組從一種加工模式切換到另一種加工模式，人員變動(dòng)成本是指加工模式的切換成本，例如，當(dāng)加工模式切換時(shí)，需要在工人之間選擇一種新的協(xié)作方式，并且裝配組內(nèi)某些專用工具或設(shè)備需要重新布置，這些都會(huì)產(chǎn)生一定的成本。調(diào)度成本是指與各工序完工時(shí)間相關(guān)的成本。針對該系統(tǒng)作以下假設(shè)：①工序一旦開始就不能被中斷；②同一時(shí)刻一個(gè)裝配組內(nèi)只能加工一道工序；③工序加工時(shí)間與工人數(shù)之間具有單調(diào)遞減的函數(shù)關(guān)系，且工序的最大加工時(shí)間已知；④工序所在的裝配組一旦確定，就一直保持到該道工序完工；⑤受工人技能的限制，不同裝配班之間不允許人員流動(dòng)；⑥每個(gè)裝配階段內(nèi)發(fā)動(dòng)機(jī)均被檢驗(yàn)為合格，即每臺(tái)發(fā)動(dòng)機(jī)經(jīng)歷兩次裝配即可出廠；⑦工廠試車、分解洗滌、故障檢驗(yàn)的能力充足，每臺(tái)發(fā)動(dòng)機(jī)兩次裝配之間的時(shí)間間隔固定已知；⑧車間內(nèi)各種裝配車的數(shù)量充足；⑨裝配組內(nèi)工人數(shù)一旦確定，則一直保持到下一次自進(jìn)化；⑩裝配組調(diào)整時(shí)間和工人遷移時(shí)間忽略不計(jì)；11○允許各裝配班內(nèi)有空閑的工人。

3.1.2模型的建立

靜態(tài)決策子問題可分為人員分配問題和生產(chǎn)調(diào)度問題。各裝配組內(nèi)的工人數(shù)決定了工序加工時(shí)間，進(jìn)而影響生產(chǎn)調(diào)度的結(jié)果，反之，生產(chǎn)調(diào)度的結(jié)果又會(huì)影響人員的分配方案。 因此，靜態(tài)決策子問題是一種雙層規(guī)劃問題，人員分配問題應(yīng)處于模型的上層，生產(chǎn)調(diào)度問題應(yīng)處于模型的下層。

靜態(tài)決策子問題的數(shù)學(xué)模型為

上層：

(1)

(2)

(3)

下層：

(4)

s.t.Ci δ j-Si δ j=pi δ j

(5)

?δi∈Ij∈Ji δ

(6)

SP(i δ j)-Ci δ j≥0

(7)

Si2j≥Ci1+ti

(8)

Ci δ j-Ci′δ′j′+φyi δ ji′δ′j′m≥pi δ j

(9)

?δ,δ′i,i′∈Ij,j′∈Ji δ

Ci′δ′j′-Ci δ j+φ(1-yi δ ji′δ′j′m)≥pi′δ′j′

(10)

(11)

(12)

(13)

(14)

xi δ jm∈{0,1}

(15)

yi δ ji′δ′j′m∈{0,1}

(16)

式(1)為上層目標(biāo)，目的是使生產(chǎn)成本最小；式(2)表示裝配組內(nèi)工人數(shù)之和不能大于其所在裝配班的工人總數(shù)；式(3)表示裝配組內(nèi)工人數(shù)的可調(diào)整范圍；式(4)為下層目標(biāo)，目的是使工序的完工時(shí)間總成本最小；式(5)表示工序開始后不能被中斷； 式(6)表示工序開始時(shí)間不能小于決策時(shí)刻T與工序所在裝配組內(nèi)T時(shí)刻正在加工工序的剩余加工時(shí)間之和；式(7)表示父工序必須在其子工序完工之后才能開始加工；式(8)表示二次裝配階段內(nèi)的工序一定要在發(fā)動(dòng)機(jī)一次裝配階段結(jié)束并完成工廠試車、分解和故障檢測之后才能開始加工；式(9)和式(10)表示同一時(shí)刻一個(gè)裝配組內(nèi)只能加工一道工序；式(11)表示工序一旦被分配至某個(gè)裝配組，就一直保持到該工序完工；式(12)表示加工時(shí)間是關(guān)于工人數(shù)的單調(diào)遞減函數(shù)；式(13)表示工序的實(shí)際加工時(shí)間；式(14)表示決策時(shí)刻裝配組內(nèi)正在加工的工序在新的工人分配方案下的剩余加工時(shí)間，根據(jù)式(12)容易得到。

初始決策問題是靜態(tài)決策子問題在全局下的體現(xiàn)。若滾動(dòng)窗口的規(guī)模ε足夠大，其大小等于車間內(nèi)總工序數(shù)，則第一個(gè)滾動(dòng)窗口內(nèi)的靜態(tài)決策子問題就是初始決策問題。因此，初始決策問題具有與上述類似的問題描述和數(shù)學(xué)模型。

3.2滾動(dòng)規(guī)則

定義6相鄰的兩個(gè)決策時(shí)刻之間以及最后一個(gè)決策時(shí)刻與所有工序最大完工時(shí)間之間的時(shí)間區(qū)間稱為進(jìn)化區(qū)間。

定義7自進(jìn)化的過程中，在每個(gè)決策時(shí)刻選取工序進(jìn)入滾動(dòng)窗口需要遵從一定的規(guī)則，我們將這一規(guī)則稱為滾動(dòng)規(guī)則。

本文提出了一種基于初始決策方案的滾動(dòng)規(guī)則。在每個(gè)決策時(shí)刻根據(jù)未加工工序在初始決策方案中的完工時(shí)間計(jì)算其工序緊迫度，即

(15)

3.3兩階段求解算法

本文提出了一種靜態(tài)環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間自進(jìn)化問題的兩階段求解算法，具體步驟如下。

(1)第一階段——初始決策。①獲取產(chǎn)品信息，構(gòu)造產(chǎn)品加工樹。②執(zhí)行BiGA，生成初始決策方案。

(2)第二階段——自進(jìn)化決策。①初始化滾動(dòng)窗口規(guī)模ε和滾動(dòng)步長η；②根據(jù)初始決策方案，計(jì)算未加工工序的緊迫度；③選擇一定數(shù)量的工序進(jìn)入滾動(dòng)窗口，執(zhí)行BiGA，確定裝配組內(nèi)工人數(shù), 并生成調(diào)度方案，若窗口內(nèi)工序數(shù)小于ε，則將所有工序加工完后，轉(zhuǎn)到步驟⑤，否則，執(zhí)行步驟④；④判斷當(dāng)前窗口內(nèi)前η道工序是否加工完，若是，則統(tǒng)計(jì)裝配組的狀態(tài)(忙/閑)，記錄各裝配組內(nèi)正在加工的工序的剩余加工時(shí)間，轉(zhuǎn)到步驟②，否則，按照步驟③原有決策方案繼續(xù)生產(chǎn)；⑤算法結(jié)束。

4　雙層遺傳算法

本文提出了一種具有雙層結(jié)構(gòu)的遺傳算法對靜態(tài)決策子問題進(jìn)行求解，上層算法的作用是解決工人分配問題，下層算法的作用是在上層個(gè)體提供的參數(shù)基礎(chǔ)上獲得各工序的加工順序。

4.1上層遺傳算法

圖2上層編碼方案

(2)初始種群的生成。在滿足式(2)的前提下，從各基因取值范圍內(nèi)任取一個(gè)整數(shù)得到染色體個(gè)體，直至生成整個(gè)種群。

(3)選擇算子。采用經(jīng)典的輪盤賭法進(jìn)行選擇操作。

(4)交叉算子。在染色體中隨機(jī)選取某個(gè)基因塊，然后互換兩父代個(gè)體中該基因塊的基因值，得到兩條新的染色體。

(5)變異算子。隨機(jī)選取一個(gè)變異基因，在該變異基因的取值范圍內(nèi)隨機(jī)選取一個(gè)整數(shù)替代原基因值，若變異基因所在基因塊滿足式(2)，則變異成功；否則，重新選取一個(gè)整數(shù)，直到變異成功為止。

4.2下層遺傳算法

定義8由各工序的裝配約束關(guān)系映射而成的樹狀結(jié)構(gòu)圖，稱為產(chǎn)品加工樹。

樹上每個(gè)節(jié)點(diǎn)都代表一道工序，為了明顯地區(qū)分各工序，將工序的代號(hào)表示為：發(fā)動(dòng)機(jī)編號(hào)|裝配階段|工序編號(hào)。圖3所示為發(fā)動(dòng)機(jī)A和B的產(chǎn)品加工樹，B|1|2表示處于一次裝配階段的發(fā)動(dòng)機(jī)B的2號(hào)工序。B|1|2的子工序包括B|1|3和B|1|4，后代工序包括B|1|3、B|1|4、B|1|5、B|1|6和B|1|7。

圖3　發(fā)動(dòng)機(jī)A和B的產(chǎn)品加工樹

定義9滿足工序裝配約束，并能保證工序都被分配到可加工裝配組內(nèi)的染色體稱為下層可行染色體。下層染色體中工序裝配約束具體體現(xiàn)如下：①同一臺(tái)發(fā)動(dòng)機(jī)二次裝配階段的工序排在一次裝配階段的工序之后；②同一臺(tái)發(fā)動(dòng)機(jī)父工序排在子工序之后。

上層參數(shù)給定后，工序在每個(gè)裝配組內(nèi)的加工時(shí)間即可確定。由于本文的下層AJSSP中只對滾動(dòng)窗口內(nèi)的工序進(jìn)行局部調(diào)度，故很可能出現(xiàn)以下情況：窗口內(nèi)的工序不能構(gòu)成各產(chǎn)品完整的產(chǎn)品加工樹，只能構(gòu)成一些子樹。文獻(xiàn)[4]給出了基于可行域搜索的遺傳算法，但其各遺傳算子是針對所有工序的全局調(diào)度進(jìn)行設(shè)計(jì)的，而本文提出的遺傳算法能夠同時(shí)適用于初始決策問題中的全局調(diào)度和靜態(tài)決策子問題中的局部調(diào)度。航空發(fā)動(dòng)機(jī)裝配車間內(nèi)一道工序可以在多個(gè)裝配組內(nèi)加工。因此，若仍采用文獻(xiàn)[4，7]中基于工序的編碼方式顯然是不可行的。本文采用基于工序和裝配組的編碼方式，并根據(jù)航空發(fā)動(dòng)機(jī)裝配的特點(diǎn)設(shè)計(jì)了各遺傳算子。假設(shè)車間內(nèi)有圖3中A和B兩臺(tái)發(fā)動(dòng)機(jī)，某個(gè)滾動(dòng)窗口內(nèi)的工序以及工序所需的裝配組如圖4所示。

(a)基于工序的編碼方式

(b)基于裝配組的編碼方式
圖4下層編碼方案

(1)編碼方案。染色體分為長度相同的兩段，每段的長度均為參與優(yōu)化的工序的數(shù)目。前半段染色體采用基于工序的編碼方式，基因值為工序代號(hào)，如圖4a所示。后半段染色體采用基于裝配組的編碼方式，基因值為工序所在裝配組的編號(hào)，按照各工序在優(yōu)化工序集內(nèi)的順序存放在后半段染色體中，如圖4b所示。

(2)初始種群的生成。前半段染色體根據(jù)參與優(yōu)化的工序數(shù)目隨機(jī)生成，后半段染色體則從各工序的可加工裝配組內(nèi)任意選擇一個(gè)裝配組，將該裝配組的編號(hào)作為基因值。

(3)選擇算子。采用經(jīng)典的輪盤賭法進(jìn)行選擇操作。

(4)交叉算子。前半段染色體采用文獻(xiàn)[14]中的次序交叉法，如圖5所示。后半段染色體采用經(jīng)典的雙點(diǎn)交叉法。

(5)變異算子。前半段染色體采用逆序操作[14]，如圖6所示。后半段染色體的變異過程為在變異基因?qū)?yīng)工序的可加工裝配組集合中隨機(jī)選取一個(gè)裝配組，用該裝配組的編號(hào)替代原基因值。

(6)修復(fù)算子。根據(jù)前述初始種群的生成方法和交叉變異的方法，后半段染色體各基因的基因值總是在工序的可加工的裝配組集合內(nèi)選取，因此必是可行的；而前半段染色體很可能有違反裝配約束的情況出現(xiàn)，因此，必須對前半段染色體進(jìn)行修復(fù)。

圖5　次序交叉法

圖6　逆序操作

前半段染色體修復(fù)的具體步驟如下：

(1)設(shè)置k1=1，進(jìn)行第一次修復(fù)。

(2)判斷染色體中是否有代表發(fā)動(dòng)機(jī)k1的工序的基因。若沒有，執(zhí)行步驟(3)；否則將所有代表發(fā)動(dòng)機(jī)k1的工序的基因從染色體中抽出，同時(shí)保持其他基因位置不變。重新排列抽出的基因的順序，把二次裝配的工序放在一次裝配的工序之后，然后將調(diào)整好順序的基因按該順序放回染色體。

(3)令k1←k1+1，判斷k1是否大于發(fā)動(dòng)機(jī)的總數(shù)I，若是，則執(zhí)行步驟(4)；否則轉(zhuǎn)到步驟(2)。

(4)設(shè)置k2=1，進(jìn)行第二次修復(fù)。k2為工序在參與優(yōu)化的工序集合內(nèi)的編號(hào)。

(5)判斷工序k2在產(chǎn)品加工樹中是否為葉子結(jié)點(diǎn)(即無子工序)，若是，則轉(zhuǎn)到步驟(6)；否則，將代表工序k2及其后代工序的基因從染色體中抽出，并保持其他基因位置不變。重新排列抽出的基因的順序，將工序k2放在其所有后代工序的后面，然后將調(diào)整好順序的基因按該順序放回染色體。

(6)令k2←k2+1，判斷k2是否大于參與優(yōu)化的工序個(gè)數(shù)，若是，則終止修復(fù)操作；否則轉(zhuǎn)到步驟(5)。

根據(jù)定義9，圖4中的染色體為一條不可行染色體, 經(jīng)過修復(fù)后得到一條可行染色體，如圖7所示。

(a)基于工序的編碼方式

(b)基于裝配組的編碼方式圖7　修復(fù)后的染色體

5　實(shí)例研究

本文采用Fortran和MATLAB語言混合編程，對靜態(tài)環(huán)境下某航空發(fā)動(dòng)機(jī)裝配車間自進(jìn)化問題的算例進(jìn)行仿真。程序在內(nèi)存為4GB、CPU為IntelCore(TM)i5-2400 3.10GHz的計(jì)算機(jī)上運(yùn)行。BiGA參數(shù)見表1。

表1　BiGA參數(shù)

根據(jù)某航空發(fā)動(dòng)機(jī)裝配車間的實(shí)際情況，在不影響合理性的基礎(chǔ)上對相關(guān)數(shù)據(jù)進(jìn)行了修改。該車間共有11個(gè)裝配班、20個(gè)裝配組，資源配置情況見表2。假設(shè)初始零時(shí)刻車間內(nèi)裝配組處于空閑狀態(tài)，裝配組內(nèi)的工人數(shù)分別為{4,5,5,4,4,6,3,3,4,3,3,3,6,5,5,4,4,3,3,4}。現(xiàn)有C、D、E三臺(tái)發(fā)動(dòng)機(jī)需要裝配，此處只給出發(fā)動(dòng)機(jī)C的部分?jǐn)?shù)據(jù)，見表3。圖8所示為處于一次裝配階段內(nèi)的發(fā)動(dòng)機(jī)C經(jīng)簡化后的產(chǎn)品加工樹。圖9所示為初始決策方案中的調(diào)度結(jié)果，此時(shí)車間內(nèi)的人員配置情況為{3,5,5,3,4,5,4,3,3,3,4,2,5,3,6,4,4,3,3,3}。分別取ε=60,η=40(選取該參數(shù)時(shí)，須確保ε小于或等于車間內(nèi)總工序數(shù)，并且還需滿足η≤ε)，圖10所示為整個(gè)自進(jìn)化過程的最終調(diào)度結(jié)果，圖10中豎線所在時(shí)刻為決策時(shí)刻。由圖10可以看出，系統(tǒng)在整個(gè)生產(chǎn)過程中經(jīng)歷了多次進(jìn)化，并且最終完工時(shí)間比初始決策方案中的最終完工時(shí)間縮短了約40 h。因此，本文提出的模型和算法是有效可行的。圖9和圖10中每個(gè)方框均代表一道工序，方框下面則對應(yīng)為工序的名稱。

表2　裝配班內(nèi)資源配置

表3　發(fā)動(dòng)機(jī)C的部分?jǐn)?shù)據(jù)

圖8　發(fā)動(dòng)機(jī)C一次裝配階段的產(chǎn)品加工樹

為了分析滾動(dòng)窗口規(guī)模ε和滾動(dòng)步長η對各種生產(chǎn)性能的影響，分別進(jìn)行了10組實(shí)驗(yàn)，每組實(shí)驗(yàn)內(nèi)均對ε分別為20、30、40、50、60和η分別為20、30、40、50、60的各種組合進(jìn)行仿真。采取公共隨機(jī)數(shù)策略(CRN)以確保同一組實(shí)驗(yàn)內(nèi)每次仿真都具有相同的初始決策方案。實(shí)驗(yàn)結(jié)果見表4和表5。表4中B、F和Z分別表示初始決策方

圖9　初始決策方案中的調(diào)度結(jié)果

根據(jù)表4和表5中的數(shù)據(jù)可以得出以下結(jié)論：

(1)大多數(shù)情況下，系統(tǒng)周期性自進(jìn)化有利于生產(chǎn)性能的改善，但是當(dāng)ε=η時(shí)，系統(tǒng)中相鄰兩個(gè)滾動(dòng)窗口之間沒有重疊，求解靜態(tài)決策子問題時(shí)只考慮了當(dāng)前滾動(dòng)窗口內(nèi)的工序信息，系統(tǒng)各項(xiàng)生產(chǎn)性能較差，甚至劣于初始決策的結(jié)果。因此，選擇ε和η時(shí)，首先應(yīng)確保η<ε。

圖10　自進(jìn)化決策方案中的調(diào)度結(jié)果

實(shí)驗(yàn)次數(shù)BFZ121650316352862251532113732332065213036553418750980357425266527593701161995064935514724452304366868299518083635592085115235869103245364137786平均值2405189536413

表5　ε和η對生產(chǎn)性能的影響

綜上所述，ε和η對生產(chǎn)性能具有一定的影響。在對ε和η取值時(shí)，我們應(yīng)當(dāng)根據(jù)生產(chǎn)的實(shí)際情況，綜合考慮算法結(jié)果和算法效率，選擇一個(gè)折中的方案。

6　結(jié)語

本文結(jié)合滾動(dòng)時(shí)域方法，采用周期性的自進(jìn)化操作觸發(fā)機(jī)制實(shí)現(xiàn)了靜態(tài)環(huán)境下的航空發(fā)動(dòng)機(jī)裝配車間的自進(jìn)化。根據(jù)航空發(fā)動(dòng)機(jī)裝配車間的生產(chǎn)特點(diǎn)，建立了系統(tǒng)在每個(gè)決策時(shí)刻靜態(tài)決策子問題的數(shù)學(xué)模型，并提出了一種基于初始決策方案的滾動(dòng)規(guī)則。在此基礎(chǔ)上，提出了一種靜態(tài)環(huán)境下航空發(fā)動(dòng)機(jī)裝配車間自進(jìn)化問題的兩階段求解算法。為了求解靜態(tài)決策問題的數(shù)學(xué)模型，提出了一種具有雙層結(jié)構(gòu)的遺傳算法。實(shí)例表明，本文提出的模型和算法是有效可行的。最后通過大量的仿真實(shí)驗(yàn)初步分析了滾動(dòng)窗口規(guī)模和滾動(dòng)步長對生產(chǎn)性能的影響。如何快速準(zhǔn)確地選擇合適的滾動(dòng)窗口規(guī)模和滾動(dòng)步長值得進(jìn)一步研究。此外，現(xiàn)實(shí)生產(chǎn)環(huán)境是動(dòng)態(tài)多變的，今后還需考慮系統(tǒng)中各種動(dòng)態(tài)因素的存在，給出相應(yīng)的處理方法，從而對動(dòng)態(tài)環(huán)境下的知識(shí)化制造系統(tǒng)自進(jìn)化問題進(jìn)行深入研究。

[1]嚴(yán)洪森, 劉飛. 知識(shí)化制造系統(tǒng)——新一代先進(jìn)制造系統(tǒng)[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2001, 7(8): 7-11.

YanHongsen,LiuFei.KnowledgeableManufacturingSystem—aNewKindofAdvancedManufacturingSystem[J].ComputerIntegratedManufacturingSystems,2001,7(8):7-11.

[2]汪浩祥,嚴(yán)洪森.基于多Agent可互操作知識(shí)化制造動(dòng)態(tài)自適應(yīng)調(diào)度策略[J].控制與決策,2013,28(2): 161-168.

WangHaoxiang,YanHongsen.InteroperableDynamicAdaptiveSchedulingStrategyinKnowledgeableManufacturingBasedonMulti-agent[J].ControlandDecision,2013,28(2):161-168.

[3]徐延鋒.航空發(fā)動(dòng)機(jī)裝配數(shù)字化關(guān)鍵技術(shù)研究與實(shí)現(xiàn)[D].西安:西北工業(yè)大學(xué),2006.

[4]王福吉,趙國凱,賈振元,等.基于可行域遺傳算法的裝配作業(yè)調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng),2010,16(1): 115-120.

WangFuji,ZhaoGuokai,JiaZhenyuan,etal.AssemblyJob-shopSchedulingBasedonFeasibleSolutionSpaceGeneticAlgorithm[J].ComputerIntegratedManufacturingSystems,2010,16(1):115-120.

[5]CummingsDH,MckoyPJE.MinimizingProductionFlowTimeinaProcessandAssemblyJobShop[J].InternationalJournalofProductionResearch,1998,36(8):2315-2332.

[6]ParkMW,KimYD.ABranchandBoundAlgorithmforaProductionSchedulingProbleminanAssemblySystemunderDueDateConstraints[J].EuropeanJournalofOperationalResearch,2000,123(3):504-518.

[7]王林平,賈振元,王福吉,等.多產(chǎn)品綜合作業(yè)調(diào)度問題及其求解[J].系統(tǒng)工程理論與實(shí)踐,2009,29(9):73-77.

WangLinping,JiaZhenyuan,WangFuji,etal.Multi-productCompleteJob-shopSchedulingProblemandItsSolution[J].SystemsEngineering-Theory&Practice,2009,29(9):73-77.

[8]SuLH,LienCY.SchedulingParallelMachineswithResource-dependentProcessingTimes[J].InternationalJournalofProductionEconomics,2009,117(2):256-266.

[9]KlausJ,MonaldoM,RobertoSO.ApproximationSchemesforJobShopSchedulingProblemswithControllableProcessingTimes[J].EuropeanJournalofOperationalResearch,2005,167(2):297-319.

[10]左燕.大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題瓶頸分解方法研究[D].上海:上海交通大學(xué), 2007.

[11]航空制造工程手冊總編委會(huì).航空制造工程手冊—發(fā)動(dòng)機(jī)裝配與試車[M].北京:航空工業(yè)出版社,1996.

[12]張超勇,李新宇,王曉娟,等.基于滾動(dòng)窗口的多目標(biāo)動(dòng)態(tài)調(diào)度優(yōu)化研究[J].中國機(jī)械工程,2009，20(18):2190-2197.

ZhangChaoyong,LiXinyu,WangXiaojuan,etal.Multi-objectiveDynamicSchedulingOptimizationStrategyBasedonRolling-horizonProcedure[J].ChinaMechanicalEngineering,2009，20(18):2190-2197.

[13]張國輝,高亮,劉文君.基于Memetic算法的車間動(dòng)態(tài)調(diào)度策略研究[J].中國機(jī)械工程,2008,19(15):1827-1831.

ZhangGuohui,GaoLiang,LiuWenjun.DynamicSchedulingOptimizationStrategyBasedonMemeticAlgorithm[J].ChinaMechanicalEngineering,2008,19(15):1827-1831.

[14]王林平.應(yīng)用齊套概念的離散制造業(yè)生產(chǎn)調(diào)度問題研究[D].大連:大連理工大學(xué),2009.

(編輯陳勇)

Periodic Self-evolution of an Aircraft Engine Assembly Workshop under Static Knowledgeable Manufacturing Environment

Jiang TianhuaYan HongsenWang Zheng

Key Laboratory of Measurement and Control of Complex Systems of Engineering,Ministry of Education,Southeast University,Nanjing,210096

For an aircraft engine assembly workshop under static knowledgeable manufacturing environment, the self-evolution problem of knowledgeable manufacturing systems was studied. Rolling horizon method was adopted to implement the assembly workshop’s periodic self-evolution. On the basis of the characteristics of the problem, a mathematical model of the static sub-problem at each decision moment was established. A rolling rule was proposed based on the initial decision scheme, and a two-phase algorithm was given to solve the self-evolution problem. For the mathematical model, a BiGA was proposed. Finally, simulation results demonstrate that the proposed model and algorithms are effective and feasible. The influences of the sizes of rolling window and rolling step on the production performance were also analyzed.

static knowledgeable manufacturing environment; self-evolution; rolling horizon; bi-level genetic algorithm(BiGA); two-phase algorithm

2014-03-17

國家自然科學(xué)基金資助重點(diǎn)項(xiàng)目(60934008)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目 (2242014K10031)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項(xiàng)目

TH165< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.07.009

姜天華，男，1983年生。東南大學(xué)自動(dòng)化學(xué)院博士研究生。主要研究方向?yàn)橹R(shí)化制造系統(tǒng)自進(jìn)化。嚴(yán)洪森，男，1957年生。東南大學(xué)自動(dòng)化學(xué)院教授、博士研究生導(dǎo)師。汪崢，男，1973年生。東南大學(xué)自動(dòng)化學(xué)院教授、博士研究生導(dǎo)師。