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

姜天華　嚴洪森　汪　崢

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

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

姜天華嚴洪森汪崢

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

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

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

0　引言

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

航空發(fā)動機的裝配是整個發(fā)動機制造過程的龍頭，其裝配成本大約占生產(chǎn)總成本的40%，這使得先進的裝配數(shù)字化技術(shù)在航空發(fā)動機裝配生產(chǎn)中的地位越來越重要[3]。航空發(fā)動機的裝配可以用一種樹形圖表示。為了表述方便，將零件的加工及零部件之間的裝配統(tǒng)稱為“加工”。這類產(chǎn)品的生產(chǎn)調(diào)度問題通常被認為是裝配作業(yè)車間調(diào)度問題(assembly job shop scheduling problem,AJSSP)[4-7]。目前關(guān)于AJSSP的文獻大都針對一般的裝配作業(yè)車間，很少涉及航空發(fā)動機裝配車間，并且上述文獻中都假設(shè)制造系統(tǒng)自身的參數(shù)是固定不變的，而在實際生產(chǎn)中制造系統(tǒng)的某些參數(shù)(如機器上的工人數(shù)、燃氣量、電力等)是可調(diào)的，它們往往會影響整體性能。在航空發(fā)動機裝配車間中，裝配組內(nèi)的工人數(shù)可以視為系統(tǒng)的參數(shù)，并且工序的加工時間是可控的，其大小由工人數(shù)決定。目前在很多有關(guān)系統(tǒng)參數(shù)可調(diào)、加工時間可控的車間調(diào)度問題的文獻中，系統(tǒng)參數(shù)和調(diào)度方案一旦確定，則在整個生產(chǎn)過程中都是不變的[8-9]。然而，在實際生產(chǎn)中生產(chǎn)決策往往是分段進行的，如一月、一周、一天或一個班次等[10]。受此啟發(fā)，可采用周期性自進化操作觸發(fā)機制，根據(jù)實際生產(chǎn)情況動態(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ā)動機裝配車間的自進化問題。采用滾動時域方法實現(xiàn)該裝配車間周期性自進化，構(gòu)建了系統(tǒng)在各決策時刻靜態(tài)決策子問題的數(shù)學(xué)模型，提出了一種基于初始決策方案的滾動規(guī)則，并給出了一種解決靜態(tài)環(huán)境下航空發(fā)動機裝配車間自進化問題的算法。根據(jù)模型的結(jié)構(gòu)和裝配生產(chǎn)的特點，提出了一種雙層遺傳算法(bi-level genetic algorithm,BiGA)對模型進行求解。用實例驗證了模型與算法的有效性和可行性，最后通過仿真對滾動窗口規(guī)模和滾動步長對生產(chǎn)性能的影響進行了初步分析。

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

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

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

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

2　航空發(fā)動機裝配車間介紹

圖1　航空發(fā)動機裝配過程

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

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

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

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

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

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

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

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

3.1.1問題描述

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

3.1.2模型的建立

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

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

3.2滾動規(guī)則

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

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

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

(15)

3.3兩階段求解算法

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

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

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

4　雙層遺傳算法

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

4.1上層遺傳算法

圖2上層編碼方案

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

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

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

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

4.2下層遺傳算法

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

樹上每個節(jié)點都代表一道工序，為了明顯地區(qū)分各工序，將工序的代號表示為：發(fā)動機編號|裝配階段|工序編號。圖3所示為發(fā)動機A和B的產(chǎn)品加工樹，B|1|2表示處于一次裝配階段的發(fā)動機B的2號工序。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ā)動機A和B的產(chǎn)品加工樹

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

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

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

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

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

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

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

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

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

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

圖5　次序交叉法

圖6　逆序操作

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

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

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

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

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

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

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

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

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

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

5　實例研究

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

表1　BiGA參數(shù)

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

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

表3　發(fā)動機C的部分數(shù)據(jù)

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

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

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

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

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

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

實驗次數(shù)BFZ121650316352862251532113732332065213036553418750980357425266527593701161995064935514724452304366868299518083635592085115235869103245364137786平均值2405189536413

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

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

6　結(jié)語

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

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

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

[2]汪浩祥,嚴洪森.基于多Agent可互操作知識化制造動態(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ā)動機裝配數(shù)字化關(guān)鍵技術(shù)研究與實現(xiàn)[D].西安:西北工業(yè)大學(xué),2006.

[4]王福吉,趙國凱,賈振元,等.基于可行域遺傳算法的裝配作業(yè)調(diào)度[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)工程理論與實踐,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]航空制造工程手冊總編委會.航空制造工程手冊—發(fā)動機裝配與試車[M].北京:航空工業(yè)出版社,1996.

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

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

[13]張國輝,高亮,劉文君.基于Memetic算法的車間動態(tài)調(diào)度策略研究[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é)基金資助重點項目(60934008)；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目 (2242014K10031)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目

TH165< class="emphasis_italic">DOI

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

姜天華，男，1983年生。東南大學(xué)自動化學(xué)院博士研究生。主要研究方向為知識化制造系統(tǒng)自進化。嚴洪森，男，1957年生。東南大學(xué)自動化學(xué)院教授、博士研究生導(dǎo)師。汪崢，男，1973年生。東南大學(xué)自動化學(xué)院教授、博士研究生導(dǎo)師。