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

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

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

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

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

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

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

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

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

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

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

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

工序順序柔性是指工件的若干加工工序在滿足工藝約束和產品質量的前提下仍可以具有不同的加工順序[9]。按照文獻[9]中的分類方式，復雜殼體零件屬于工藝順序非完全確定性工件，即該工件的所有工藝可分為若干個柔性工序組，在同一工序組內，所有工藝之間不具有先后加工的工藝約束，但不同組之間具有先后加工的工藝約束。圖2 為某燃油控制器殼體零件的部分工藝流程圖，其中包含有4 個柔性工序組，工序組內工序無先后加工順序的要求，可以相互超越加工。該工藝流程圖中的柔性工序組可表示為{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調度模型

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

帶有工序順序柔性的非置換流水車間E/T 調度問題可以描述為：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加工過程中的柔性工序組，柔性工序組內的各工序之間無加工先后次序約束；對于工件Ji，其交貨期為ddi，完工時間為Ci，提前完工的單位時間懲罰系數為ei，拖期完工的單位時間懲罰系數為ti，工件的提前完工懲罰成本為Ei，工件的拖期完工懲罰成本為Ti；對于工件Ji的任一工序Oi，j，其開工時間為si，j，加工時間為pi，j，完工時間為Ci，j，承制機床為M（Oi，j）∈M。調度任務是在滿足工件工藝路線和機床能力約束的條件下，使得所有工件的提前/拖期完工懲罰總成本（Schedule cost）最小。

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

3 改進型遺傳算法

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

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

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

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

3.1 兩段式編碼

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

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

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

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

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

3.2 三階段解碼

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

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

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

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

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

3.3 分段交叉算子

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

3.4 逆轉變異算子

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

4 實例驗證

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

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

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

圖8 逆轉變異算子Fig.8 Inversion mutation operator

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

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

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

表3 改進型遺傳算法參數設置表Table 3 Improved genetic algorithm parameter settings

圖9 殼體實例調度甘特圖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

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

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

5 結論

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

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

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

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