付 梅，謝 懷，王蓀馨，申高攀

（1.中國航發(fā)西安動力控制科技有限公司，西安 710077；2.西安理工大學，西安 710048；3.西北工業(yè)大學，西安 710072）

航空發(fā)動機生產(chǎn)具有典型的多品種、小批量特征，而不同型號任務(wù)之間的頻繁切換使得生產(chǎn)組織、生產(chǎn)準備、作業(yè)調(diào)度、現(xiàn)場協(xié)調(diào)等都更為復雜和困難。隨著航空發(fā)動機型號研制任務(wù)量的不斷攀升，以及中國航發(fā)AEOS（Aero-engine corporation of China operation system）生產(chǎn)制造體系在各生產(chǎn)企業(yè)的深入推進，構(gòu)建流水作業(yè)生產(chǎn)單元、實現(xiàn)精益化轉(zhuǎn)型、強化生產(chǎn)現(xiàn)場執(zhí)行和管控機制已成為航空發(fā)動機制造企業(yè)的普遍共識。

近年來，各生產(chǎn)單位進行了大規(guī)模的產(chǎn)線改造和產(chǎn)能提升工程，“專業(yè)化、小流水”已成為航發(fā)制造企業(yè)的主流生產(chǎn)組織方式。在依據(jù)精益生產(chǎn)單元、成組技術(shù)所形成的流水作業(yè)車間內(nèi)，不同零件沿單元內(nèi)不同設(shè)備流轉(zhuǎn)加工的工藝路線類似，但同一機器上不同工序的加工順序沒有特殊要求。非置換流水車間調(diào)度（Nonpermutation flow-shop scheduling，NPFS）是傳統(tǒng)置換流水車間調(diào)度的一種推廣，它允許在不同機器上改變工件的加工順序[1]。因此，航空發(fā)動機精益制造單元生產(chǎn)方式屬于典型的非置換流水車間類型。

另外，航空發(fā)動機制造企業(yè)長期以來沿用“早完工、早入庫、保交付”的生產(chǎn)管控模式，這一較為粗放型的生產(chǎn)管控方式與精益生產(chǎn)、成本理念相距甚遠；作業(yè)調(diào)度作為精益單元現(xiàn)場組織生產(chǎn)的指揮棒，直接決定著零部件生產(chǎn)現(xiàn)場的生產(chǎn)準備、資源配置和人員安排等事宜，因此，精益調(diào)度、JIT（Just-in-time）調(diào)度則成為航發(fā)制造企業(yè)落地精益生產(chǎn)的重要抓手。考慮到航發(fā)制造企業(yè)的現(xiàn)實情況，細化到工序級交貨期的JIT 調(diào)度目前還不具備實施條件，而以零部件交付節(jié)點為關(guān)注重點的提前/拖期（Earliness/tardiness，E/T）調(diào)度則成為現(xiàn)階段實施精益調(diào)度的有效方式。

提前/拖期調(diào)度要求零部件在各自既定的交付節(jié)點準時完工，而零部件的提前或拖期完工都會產(chǎn)生相應的懲罰成本。零部件早于所要求的交付節(jié)點提前完工，勢必導致占用有限的制造資源，同時也帶來了不必要的在制品積壓成本；而零部件的拖期完工則會打亂整個制造鏈的生產(chǎn)節(jié)拍，使得下游生產(chǎn)環(huán)節(jié)出現(xiàn)整機配套缺件、停工待料、設(shè)備閑置等諸多問題。因此，關(guān)注零部件的交付節(jié)點（交貨期），以滿足零部件的準時化交付為目的，通過E/T 調(diào)度來實現(xiàn)制造單元的精細運作和低成本運營，對于改善目前航空發(fā)動機制造企業(yè)存在的高投入、低產(chǎn)出、利潤率低等問題具有一定的現(xiàn)實意義。

航空發(fā)動機燃油控制系統(tǒng)復雜殼體的生產(chǎn)制造過程屬于典型的多品種小批量、專業(yè)化小流水生產(chǎn)方式，其具有工藝過程復雜、檢測項目多、加工周期長等顯著特征。在這類殼體零件工藝設(shè)計階段，綜合考慮殼體零件的工藝特殊性和加工設(shè)備的利用率等因素，零件內(nèi)的部分工序需充分考慮工序順序柔性這一特殊要求，即在不影響產(chǎn)品質(zhì)量和工藝規(guī)范要求的前提下，殼體加工過程中部分工序加工順序可以相互超越。復雜殼體零件在工藝設(shè)計階段引入工序順序柔性后，為下游的生產(chǎn)調(diào)度優(yōu)化提供了操作空間。

綜合上述，精益單元的流水生產(chǎn)方式、零件粒度的E/T 調(diào)度和工序順序柔性約束這3 個特點，形成了本文的研究對象，即帶有工序順序柔性約束的非置換流水車間E/T調(diào)度問題。在非置換流水車間調(diào)度方面，Liao等[2]以最小化總延遲為調(diào)度目標提出一種禁忌搜索算法；肖鵬飛[3]提出一種基于時序差分法的深度強化學習算法用于求解以Makespan 為調(diào)度目標的非置換流水車間調(diào)度問題。在工序順序柔性方面，黃學文等[4]在常用的基于工序順序的編碼方法上融入了基于柔性工序順序的編碼方法，以Makespan 為調(diào)度目標對帶有工序順序柔性的作業(yè)車間調(diào)度問題進行了研究；朱文凡等[5]提出了基于柔性工序和機器選擇的兩段編碼方式，并在此基礎(chǔ)上改進遺傳算法求解帶有工序順序柔性的作業(yè)車間調(diào)度問題。在E/T 調(diào)度方面，楊宏安等[6]提出一種基于兩階段調(diào)度策略的改進遺傳算法求解作業(yè)車間調(diào)度問題，可以有效降低提前/拖期調(diào)度總成本；Ahmadian等[7]設(shè)計了一種變鄰域搜索算法用于求解作業(yè)車間JIT 調(diào)度問題。

目前的研究中，缺少針對工序順序柔性的非置換流水車間E/T 調(diào)度問題的研究。因此，本文針對該問題的特點，以最小化提前/拖期懲罰總成本為調(diào)度目標，設(shè)計了一種“兩段式編碼”、“三階段解碼”的改進型遺傳算法，并通過復雜殼體零件制造車間的實際數(shù)據(jù)驗證了算法的實用性。

1 燃油控制系統(tǒng)復雜殼體及其典型工藝路線圖

作為航空發(fā)動機燃油控制系統(tǒng)中的核心關(guān)鍵零件，殼體是各類油泵、調(diào)節(jié)器和分布器產(chǎn)品各類元件的載體，它在燃油系統(tǒng)中主要起支撐各控制元件和高中低壓油路的導引作用（圖1）[8]。該零件外形及鑄造內(nèi)腔基本由圓弧、平面過渡面組成，凸凹相間，孔系眾多，空間細長油路孔多達100 個，特征尺寸達到2000 個左右，較為復雜的殼體零件需要進行150～200 道工序。復雜殼體類零件的工藝過程復雜，工藝、工裝及檢測協(xié)同環(huán)節(jié)多。主要工藝類型包括銑、鏜、鉆、車、特種加工等，其加工設(shè)備以加工中心、數(shù)控車床為主。

圖1 航空發(fā)動機燃油控制系統(tǒng)殼體零件Fig.1 The shell part of aero-engine fuel control system

工序順序柔性是指工件的若干加工工序在滿足工藝約束和產(chǎn)品質(zhì)量的前提下仍可以具有不同的加工順序[9]。按照文獻[9]中的分類方式，復雜殼體零件屬于工藝順序非完全確定性工件，即該工件的所有工藝可分為若干個柔性工序組，在同一工序組內(nèi)，所有工藝之間不具有先后加工的工藝約束，但不同組之間具有先后加工的工藝約束。圖2 為某燃油控制器殼體零件的部分工藝流程圖，其中包含有4 個柔性工序組，工序組內(nèi)工序無先后加工順序的要求，可以相互超越加工。該工藝流程圖中的柔性工序組可表示為{25，30，35}，{45，50，55}，{65，70，75，80}和{95，100，105}。

圖2 燃油控制器殼體零件的部分工藝流程圖Fig.2 Partial process flow chart of a fuel control system shell part

2 帶有工序順序柔性的非置換流水車間E/T調(diào)度模型

綜合以上分析，航空發(fā)動機燃油控制系統(tǒng)復雜殼體制造單元的生產(chǎn)調(diào)度為一種帶有工序順序柔性的非置換流水車間E/T 調(diào)度問題。該調(diào)度問題可以描述為：一批殼體零件生產(chǎn)任務(wù)以相似的工藝路線在殼體制造單元內(nèi)的多臺機器上依次流轉(zhuǎn)加工，其中，每道工序有固定的加工機器和加工時間，且加工過程一旦開始則不容許中斷；另外，每個殼體零件含有一個或多個柔性工序組，且柔性工序組內(nèi)的各道工序無固定的加工順序要求。作業(yè)調(diào)度的主要任務(wù)是合理安排各個零件在機器上的加工序列和起止時間，同時使得該批殼體零件的提前/拖期完工懲罰總成本最小，以此確保各個零件盡可能在各自的交付節(jié)點完工，以期從生產(chǎn)管控角度來支撐殼體零件的精益生產(chǎn)和低成本運行。

帶有工序順序柔性的非置換流水車間E/T 調(diào)度問題可以描述為：n個工件J={J1，J2，…，Jn}在m臺機器M={M1，M2，…，Mm}上依次加工；任一工件Ji包含ni道工序，Ji的工藝路線為{Oi，1，Oi，2，…，{Oi，j，Oi，j+1，Oi，j+2}，…，Oi，ni}，其中，{Oi，j，Oi，j+1，Oi，j+2}為工件Ji加工過程中的柔性工序組，柔性工序組內(nèi)的各工序之間無加工先后次序約束；對于工件Ji，其交貨期為ddi，完工時間為Ci，提前完工的單位時間懲罰系數(shù)為ei，拖期完工的單位時間懲罰系數(shù)為ti，工件的提前完工懲罰成本為Ei，工件的拖期完工懲罰成本為Ti；對于工件Ji的任一工序Oi，j，其開工時間為si，j，加工時間為pi，j，完工時間為Ci，j，承制機床為M（Oi，j）∈M。調(diào)度任務(wù)是在滿足工件工藝路線和機床能力約束的條件下，使得所有工件的提前/拖期完工懲罰總成本（Schedule cost）最小。

式（1）為調(diào)度目標函數(shù)，即要求所有工件的提前/拖期完工懲罰的總成本最小，以期各工件在各自交貨期準時完工。式（2）為工件Ji的提前完工懲罰成本。式（3）為工件Ji的拖期完工懲罰成本。式（4）為工藝路線約束，工件Ji的兩工序Oi，j、Oi，j+1需滿足工件內(nèi)的工藝先后順序約束。式（5）為機床析?。芰Γ┘s束，即同一臺機床在同一時刻只能加工一個工序任務(wù)。式（6）為工序順序柔性約束，若Oi，j、Oi，j+1在同一柔性工序組內(nèi)，則二者無先后順序約束。

3 改進型遺傳算法

求解帶有工序順序柔性的非置換流水車間調(diào)度問題時，需要在實際生產(chǎn)環(huán)境中為含有柔性工序組的工件選擇較優(yōu)的工藝路線，并對所有工件的加工工序進行排序，確定每臺機器上工件的加工順序。與傳統(tǒng)的非置換流水車間調(diào)度問題相比，工件具有的工序順序柔性特性擴展了可行解的搜索范圍，大大提高了調(diào)度求解的難度。

針對工序順序柔性特性，提出一種兩段式編碼方法，即在基于工序的編碼的基礎(chǔ)上增加一段基于柔性工序組的編碼用于描述工件的工藝路線，并設(shè)計了該段染色體對應的交叉和變異算子。針對工件準時化交付問題，提出一種三階段解碼方式以盡可能降低工件提前/拖期完工懲罰的總成本。

在改進型遺傳算法設(shè)計中，種群初始化采用基于最早交貨期規(guī)則的初始種群生成方法[6]；染色體編碼采用兩段式編碼方法；解碼操作選擇三階段解碼方式；選擇操作采用精英保留和錦標賽方法；交叉操作采用分段交叉策略；變異操作采用逆轉(zhuǎn)變異策略。改進型遺傳算法的整體框架如圖3 所示。

以下重點對改進型遺傳算法中染色體的兩段式編碼與三階段解碼方式、分段交叉算子和逆轉(zhuǎn)變異算子進行闡述。

3.1 兩段式編碼

本文采用兩段式編碼方法來描述針對工序順序柔性的非置換流水車間調(diào)度問題的一個可行解，即在基于工序的編碼方式的基礎(chǔ)上，考慮工序順序柔性的特殊性，增加了基于柔性工序組編碼的染色體段，以描述各工件內(nèi)的工序加工順序，形成了兩段式編碼方法。兩段式編碼方法及其后續(xù)的遺傳操作算子是在兼顧工序順序柔性和車間調(diào)度特征基礎(chǔ)上進行的針對性設(shè)計。

在基于工序的編碼的染色體段中，工件號在染色體中出現(xiàn)的次數(shù)即為該工件工藝路線上的第幾道工序，如圖4 所示。以工件J1為例，若其工藝路線為O1，1→O1，2→ O1，3→O1，4→O1，5，數(shù)字1 在染色體段中第1 次出現(xiàn)則表示其工藝路線上的第1 道工序O1，1，第2 次出現(xiàn)則表示其工藝路線上的第2 道工序O1，2。

圖4 基于工序的編碼方法Fig.4 Encoding method based on operation

在基于柔性工序組編碼的染色體段中，將染色體分解為與工件數(shù)量相同的若干片段。每個片段用于描述其對應工件的加工工藝路線，其長度為工件的工序數(shù)量，每個工件對應片段內(nèi)的數(shù)字序列用來描述工件的工藝路線。如圖5所示，工件J1的柔性工序組為{O1，2，O1，3，O1，4}，柔性工序組內(nèi)的工序順序有多種組合方式。在編碼時，從多個組合中隨機取出一個作為柔性工序組內(nèi)工序的工藝路線，得到工件J1對應的染色體片段為{1，3，2，4，5}，即工件J1的加工工藝路線為O1，1→O1，3→O1，2→ O1，4→O1，5。

圖5 基于柔性工序組的編碼方法Fig.5 Encoding method based on flexible operation group

將兩段染色體拼接為一個染色體，即為針對工序順序柔性的非置換流水車間調(diào)度問題的一個可行解，如圖6 所示。以工件J1為例，當1 在基于工序的編碼中第2次出現(xiàn)，代表該工件工藝路線上的第2 道工序，結(jié)合基于柔性工序組編碼的染色體段中J1的工藝路線O1，1→ O1，3→O1，2→O1，4→O1，5，可知此處1 代表工序O1，3。

3.2 三階段解碼

首先，對基于柔性工序組編碼的染色體段進行解碼得到各工件的工藝路線，對基于工序編碼的染色體進行解碼得到各基因位對應的工序序號。然后，采用三階段解碼方式進行解碼操作，以降低提前/拖期完工懲罰總成本。采用插入式貪婪解碼算法，產(chǎn)生一個包含最優(yōu)解的活躍調(diào)度；在解碼過程中，若有工件的完工時間超出拖期寬容度約束，進行染色體修復操作，以盡可能減小工件的拖期完工懲罰；在完成前兩個操作后，進行逆向重調(diào)度適當延后工件的開工時間，以減小工件提前完工帶來的懲罰。

（1）插入式貪婪解碼。將染色體看作工序的有序序列，根據(jù)工序在該序列上的順序進行插入式貪婪解碼。序列上第1 道工序首先安排加工，然后取序列上第2 道工序，將其插入到對應機器上最早可行的加工時刻安排加工，以此方式直到序列上所有工序都安排在其最佳可行的位置。此階段的目的在于產(chǎn)生一個包含最優(yōu)解的可行活躍調(diào)度。

（2）基于拖期寬容度的染色體修復。在實際的生產(chǎn)環(huán)境中，零部件的拖期交付對生產(chǎn)活動的影響更為嚴重。因此，為盡可能降低工件拖期懲罰成本，在插入式貪婪解碼的過程中，若有工序的完工時間超出式（7）設(shè)置的拖期寬容度約束，則立即停止解碼并進行染色體修復操作。染色體修復操作采用基于關(guān)鍵路徑的染色體修復方法[6]。

其中，Ci，j為完工時間；η為拖期寬容度系數(shù)。

（3）逆向重調(diào)度。通過以上兩階段解碼操作可使工件拖期懲罰成本降到最小，在保持拖期成本不變的情況下，適當延遲工件的開工時間有助于降低工件的提前完工懲罰，采用基于逆向重調(diào)度的目標值修訂方法[6]對染色體進行逆向重調(diào)度。

3.3 分段交叉算子

在進行交叉操作時，分別對前、后兩段染色體進行交叉操作（圖7）。對基于柔性工序組編碼的染色體段，隨機選中多個柔性工序組進行交叉操作，以產(chǎn)生新的工藝路線?？紤]到柔性工序組內(nèi)的工序數(shù)量較少，在各個工件的柔性工序組內(nèi)隨機選中一個交叉點，交換兩父代染色體該位置的基因，對于非交換位置的重復基因按照交換位置基因值的映射關(guān)系進行交換[10]，從而防止不可行方案的產(chǎn)生。對基于工序的編碼方式形成的染色體段，采用POX 交叉算子[11]進行交叉操作，以產(chǎn)生新的調(diào)度方案。POX 交叉算子可以很好地繼承父代優(yōu)良特征并且子代總是可行的，相較于其他的交叉算子，POX算子可以得到更好的結(jié)果。

3.4 逆轉(zhuǎn)變異算子

在進行變異操作時，分別對前、后兩段染色體進行變異操作（圖8）。對基于柔性工序組編碼的染色體段，隨機選中多個柔性工序組，采用逆轉(zhuǎn)變異的方式，將選中的柔性工序組內(nèi)的基因以逆向順序排列插入到原位置；對基于工序的編碼方式形成的染色體段，隨機選中一個基因段，采用逆轉(zhuǎn)變異的方式，將選中的基因段以逆向順序排列插入到原位置。

4 實例驗證

為了驗證上述調(diào)度模型和方法，以西控公司航空發(fā)動機燃油控制系統(tǒng)生產(chǎn)車間的7 種典型殼體零件為驗證實例。由于這類復雜殼體零件加工涉及粗加工、半精加工、精加工共計200 多道工序，本研究根據(jù)工藝相似性將部分中間工序合并，并保留了14 種典型工序參與算例驗證工作。表1 給出了7 種殼體零件在14 臺機床上的加工時間。表2 給出了7 種零件各自包含的柔性工序組和柔性工序組數(shù)量，以及對應的交貨期和提前/拖期完工懲罰系數(shù)。其中，柔性工序組內(nèi)各工序的加工先后順序不受限制；提前/拖期完工懲罰系數(shù)是由車間計調(diào)員根據(jù)工件交貨期緊迫程度、工件拖期完工的影響程度、工件提前完工的在制品積壓成本等多種因素人工設(shè)定。對于交貨期緊迫、拖期完工影響較大的工件賦予較大的拖期完工懲罰系數(shù)，適當減小提前完工懲罰系數(shù)，通過這種懲罰系數(shù)的動態(tài)調(diào)整，以驅(qū)動生產(chǎn)現(xiàn)場開足馬力盡早完工從而保證交付任務(wù)。而對于交貨期較為松弛、車間精益管理水平較高等情況，通過調(diào)高工件提前完工懲罰成本，以引導工件按需生產(chǎn)從而減少在制品庫存積壓成本。實際上，工件提前/拖期完工懲罰成本系數(shù)一定程度上定量反映了一個企業(yè)的精益管理水平。

圖6 兩段式編碼方法Fig.6 Two-segment encoding method

圖7 分段交叉算子Fig.7 Segmented crossover operator

圖8 逆轉(zhuǎn)變異算子Fig.8 Inversion mutation operator

表1 殼體工件各工序加工時間Table 1 Processing time of each operation of shell parts min

表2 工件的柔性工序組分布及提前/拖期完工懲罰系數(shù)Table 2 Distribution of flexible operation group and coefficient of earliness/tardiness penalty

表3 為改進型遺傳算法的參數(shù)設(shè)置表，計算機硬件參數(shù)為CPU 3.6GHz，內(nèi)存16G，采用MATLAB R2018b實現(xiàn)本文設(shè)計的改進型遺傳算法。圖9、圖10 分別為改進型遺傳算法運行20 次得到的最優(yōu)調(diào)度方案甘特圖和改進型遺傳算法收斂曲線，表4 為最優(yōu)調(diào)度方案對應的7 個殼體零件的最終加工工藝路線。在圖9 的甘特圖中，7 個零件的加工工序用7 種顏色表示，7 條豎線表示7 個零件所要求的交貨期，7 個殼體零件依次經(jīng)過14臺機床的流轉(zhuǎn)加工，并在各自的交貨期節(jié)點附近完工。該試驗結(jié)果表明，本文提出的調(diào)度模型和方法適用于專業(yè)化小流水制造車間的優(yōu)化調(diào)度，同時在精益化排產(chǎn)、準時化生產(chǎn)組織方面也有良好效果。

表3 改進型遺傳算法參數(shù)設(shè)置表Table 3 Improved genetic algorithm parameter settings

圖9 殼體實例調(diào)度甘特圖Fig.9 Gantt chart of the shell parts scheduling

圖10 改進型遺傳算法收斂曲線圖Fig.10 Convergence curve of the improved genetic algorithm

表4 7 個殼體優(yōu)化加工序列Table 4 Process route of 7 shell parts after optimizing

另外，為了驗證工序順序柔性這一特殊工況對于車間調(diào)度方案的影響情況，分別采用兩種試驗方法：一種是不考慮工序順序柔性約束，直接在柔性工序組內(nèi)依次按順序加工；另一種是按照本文在柔性工序組內(nèi)進行優(yōu)化選擇。兩種試驗方法共仿真20 次，分別得到的最優(yōu)調(diào)度方案結(jié)果見表5。可知，最優(yōu)方案的提前/拖期完工懲罰總成本為328.06 元，相較于不考慮工序順序柔性的最優(yōu)方案的提前/拖期完工懲罰總成本374.37 元，懲罰總成本降低了46.31 元，采用改進型遺傳算法后總成本下降12.37%。試驗結(jié)果表明，在工藝設(shè)計階段引入工序順序柔性，為后續(xù)的作業(yè)調(diào)度提供了優(yōu)化空間，本文設(shè)計的改進型遺傳算法對于求解考慮工序順序柔性的非置換流水車間調(diào)度問題具有顯著優(yōu)勢。

表5 柔性工序組內(nèi)的順序加工和排序優(yōu)化兩類試驗結(jié)果Table 5 Experiment results of process in sequence and operation sequence optimization in flexible operation group

5 結(jié)論

（1）針對航空發(fā)動機燃油控制系統(tǒng)殼體零件專業(yè)化小流水、精益生產(chǎn)、工藝過程復雜、制造周期長等顯著特征，將流水線生產(chǎn)、精益單元、JIT 調(diào)度等引入該類殼體零件的生產(chǎn)現(xiàn)場組織中，所形成的調(diào)度優(yōu)化模型和改進型遺傳算法對于航空制造企業(yè)實現(xiàn)精益化轉(zhuǎn)型、強化生產(chǎn)現(xiàn)場執(zhí)行與管控等具有一定的促進作用，同時也在汽車發(fā)動機殼體、減速器殼體、各類泵殼體等車間的精益生產(chǎn)與現(xiàn)場組織方面具有一定的適用性。

（2）在調(diào)度優(yōu)化模型中，以零件交貨期為控制節(jié)點，采用零件完工時間的提前/拖期懲罰成本的調(diào)節(jié)機制，通過車間決策者人工調(diào)整提前和拖期懲罰因子取值，以滿足企業(yè)不同發(fā)展階段、不同管理水平的差異化管控需求。

（3）在調(diào)度算法設(shè)計中，采用兩段式染色體編碼方式，滿足了殼體零件工藝順序柔性這一特殊要求；采用三階段解碼方式，在確保調(diào)度解可行的前提下依次降低零件的拖期成本和成品提前庫存成本，從而最終實現(xiàn)零件準時完工的精益調(diào)度目的。

（4）本文所提出的E/T 精益調(diào)度模型，都是在確定性環(huán)境下的理想調(diào)度模型。然而航空復雜產(chǎn)品屬于典型的多品種小批量生產(chǎn)方式，零部件生產(chǎn)現(xiàn)場動態(tài)隨機因素眾多。為此，下一步將機器故障、急件插入等常見例外工況引入精益調(diào)度模型中，并設(shè)計與該不確定條件下的精益調(diào)度模型相適應的智能優(yōu)化算法。