集成式工藝規(guī)劃與車間調(diào)度問題研究現(xiàn)狀及發(fā)展

文笑雨, 王康紅, 孫海強, 高 亮

(1.鄭州輕工業(yè)大學 a.河南省機械裝備智能制造重點實驗室;b.機電工程學院，鄭州 450002;2.華中科技大學 數(shù)字制造裝備與技術國家重點實驗室，武漢 430074)

隨著中國經(jīng)濟高速發(fā)展和人民生活水平的提高，消費者對于產(chǎn)品的需求逐漸從標準化趨向于個性化、定制化，這會對生產(chǎn)設備的柔性提出了更高的要求。為滿足不同用戶的不同需求，越來越多的企業(yè)開始進行非標準機械設備的設計和制造。這些機械設備一般具有加工靈活性高的特點，多由多個小功能單元組成復雜的系統(tǒng)，每一個功能單元的組成部分相對簡單，一般包含種類繁多的不同零件，單個零件的結構相對簡單、加工靈活性比較大，因此工藝路線可選擇性比較大。在加工生產(chǎn)這一類非標準機械設備時，制造系統(tǒng)中會包含豐富的機器柔性、工序順序柔性和加工路徑柔性，工藝規(guī)劃與車間調(diào)度環(huán)節(jié)相互制約與影響的程度較大。這些企業(yè)現(xiàn)場管理均存在工藝規(guī)劃環(huán)節(jié)與車間調(diào)度環(huán)節(jié)難以協(xié)調(diào)，生產(chǎn)調(diào)控困難的問題，實現(xiàn)工藝規(guī)劃與車間調(diào)度的集成優(yōu)化顯得極其重要。工藝規(guī)劃與車間調(diào)度是制造系統(tǒng)中重要的兩個子系統(tǒng)，工藝規(guī)劃的輸出制約著車間資源的分配，車間的實時狀態(tài)影響工藝規(guī)劃的有效性。若將工藝規(guī)劃與車間調(diào)度分成兩個獨立環(huán)節(jié)展開研究，兩者的相互制約關系將對制造系統(tǒng)整體性能的提升產(chǎn)生不良的影響[1]。隨著智能制造的興起，數(shù)字孿生[2]、網(wǎng)絡化制造[3]等新技術的發(fā)展使得工藝規(guī)劃環(huán)節(jié)和車間調(diào)度環(huán)節(jié)的數(shù)據(jù)更容易互聯(lián)互通，對不同制造環(huán)節(jié)的集成優(yōu)化以及調(diào)度方案的動態(tài)調(diào)控是保證智能制造能夠推行的重要技術。對集成式工藝規(guī)劃與車間調(diào)度(integrated process planning and scheduling, IPPS)問題進行研究可以在工藝規(guī)劃初期對后期加工現(xiàn)場的資源利用狀況進行預測，能夠有效避免加工現(xiàn)場的資源沖突，使現(xiàn)有的生產(chǎn)資源得到充分利用，滿足企業(yè)對市場需求的快速響應。

在制造業(yè)可持續(xù)發(fā)展的需求下，在進行工藝規(guī)劃及車間調(diào)度時需要考慮一些綠色指標，如噪音、能耗、碳排放等[4]。另外，制造系統(tǒng)實時運行過程中常伴隨一些無法預料的不確定擾動因素，如工件工序加工時間不確定、機器故障、交貨期變化、訂單變化等。為保證生產(chǎn)高效、低耗、有序運行，要求制造系統(tǒng)必須能夠?qū)Σ淮_定擾動因素及時響應、動態(tài)調(diào)整[5]。IPPS問題因為考慮到制造系統(tǒng)的多種柔性因素，能夠應對生產(chǎn)中一些不確定擾動因素。對IPPS問題進行研究時需要考慮如何在模型構建以及運作方法上及時應對不確定擾動事件，減少不確定性因素對調(diào)度方案帶來的影響。

在上述背景下，針對近年來IPPS問題的研究現(xiàn)狀，筆者分別從IPPS建模、IPPS求解方法兩方面進行綜述與分析，并對不確定擾動下IPPS問題以及面向綠色制造的IPPS問題研究現(xiàn)狀進行了總結與分析。在上述分析基礎上，對未來開展IPPS問題研究的一些方向進行了展望。

1 IPPS問題研究現(xiàn)狀

1.1 IPPS建模方法的研究概況

工藝規(guī)劃與車間調(diào)度一般分屬于制造企業(yè)中的不同部門，在實施集成優(yōu)化時，重點需要考慮兩環(huán)節(jié)之間信息如何進行交互。根據(jù)兩環(huán)節(jié)不同的信息交互方式，一種經(jīng)典的分類方法是將工藝規(guī)劃與車間調(diào)度的集成模型分為3種[1,6]：非線性方法、閉環(huán)式方法以及分布式方法。呂盛坪等[7]將上述3種集成方法歸納為離線式接口集成方法、在線式接口集成方法以及面向功能集成方法。這3種集成方法的特點及應用情況如表1所示。這3種集成方法中，非線性方法因其在工藝規(guī)劃與車間調(diào)度環(huán)節(jié)信息交互方式上比較簡單，應用最為廣泛。大多數(shù)研究者聚焦于建立合適的混合整數(shù)規(guī)劃模型，以期能夠保證工藝規(guī)劃環(huán)節(jié)為車間調(diào)度環(huán)節(jié)提供盡可能多的備選工藝路線集合[8]。

表1 3種集成方法的特點及應用情況Table 1 The characteristics and applications of three integration methods

隨著IPPS基本集成模型研究的日漸成熟，越來越多的學者開始關注特定生產(chǎn)環(huán)境下工藝規(guī)劃與車間調(diào)度進行集成的特殊性。從大批量定制化生產(chǎn)模式的特點出發(fā)，充分考慮到不同類型的制造企業(yè)對于工藝規(guī)劃與車間調(diào)度階段的重視程度有所不同，陳亮[9]采用主從聯(lián)合優(yōu)化思想構建工藝規(guī)劃與車間調(diào)度的集成優(yōu)化模型。Chen等[10]構建了面向產(chǎn)品不確定性的IPPS雙層規(guī)劃模型，采用混合整數(shù)規(guī)劃模型描述上層工藝規(guī)劃模型，采用基于Agent的建模方法處理下層車間調(diào)度問題。Rietz等[11]建立了一種偽多項式網(wǎng)絡流模型，用以對中期工藝規(guī)劃與短期車間調(diào)度進行集成。為了應對實際制造過程中存在的多車間供料及加工的情況，巴黎等[12]提出了綜合考慮裝配及物流環(huán)節(jié)的IPPS模型。針對具有并行單元和資源受限的多產(chǎn)品單級批處理工廠，結合制造服務理念，Aguirre等[13]提出了一種IPPS與機器維護維修集成的模型。上述研究均表明，IPPS建模方法的研究在朝向更貼近實際生產(chǎn)的方向逐步發(fā)展，所建立的集成模型注重工藝規(guī)劃與車間調(diào)度的層次關聯(lián)性，對不同的生產(chǎn)模式更具有針對性，對實際制造環(huán)境描述的更加完備。這將進一步促進IPPS嵌入商業(yè)級工業(yè)軟件，從而更好地發(fā)揮其服務實際生產(chǎn)過程的作用。

1.2 IPPS求解方法的研究概況

當前IPPS問題的求解方法主要集中在使用非線性方法實現(xiàn)工藝規(guī)劃與車間調(diào)度階段的信息交互，并采用智能優(yōu)化算法對問題解空間進行搜索尋優(yōu)。依據(jù)優(yōu)化目標個數(shù)的不同，基于智能優(yōu)化算法的IPPS求解方法又可以進一步分為單目標優(yōu)化方法和多目標優(yōu)化方法。

單目標IPPS問題的求解方法研究相對較為成熟，主要集中在基于蟻群算法的優(yōu)化方法和基于遺傳算法的混合算法設計。研究者在使用蟻群算法求解單目標IPPS問題時，會將螞蟻探尋路徑的過程與IPPS問題中柔性工藝路徑的選擇相結合。Leung等[14]構建了基于Agent系統(tǒng)的蟻群算法求解單目標IPPS問題。Zhang等[15]提出了一種構造式元啟發(fā)規(guī)則與蟻群算法結合求解IPPS問題。王進峰等[16]及黃學文等[17]使用改進的蟻群算法求解單目標IPPS問題。在混合算法設計方面，一般采取的方法是設計有效的鄰域結構嵌入全局搜索能力比較好的算法中進行局部搜索，從而對解空間進行充分探索。混合算法的代表為遺傳算法與變鄰域搜索算法的結合。Li等[18]設計了一種高效遺傳變鄰域混合算法求解單目標IPPS問題。此方法在工藝規(guī)劃階段采用一種三層編碼方法，不僅能夠?qū)に囈?guī)劃階段的工藝柔性、工序柔性及加工柔性進行比較完備的表達，同時也能夠使用相對比較簡單的交叉變異算子。在車間調(diào)度階段考慮的車間類型為作業(yè)車間調(diào)度問題，將變鄰域搜索嵌入遺傳算法中，兼顧多種鄰域結構的優(yōu)點，充分探索問題解空間。工藝規(guī)劃與車間調(diào)度階段協(xié)同進化，在求解IPPS最大完工時間上取得了非常優(yōu)異的計算結果。該方法被用來求解Kim提出的24個IPPS基本測試算例，其中19個解超過或等于當前已取得的最好解，在6個測試算例上發(fā)現(xiàn)了當前最好解。作者還將該算法應用于某非標機械制造廠中實際存在的IPPS問題，計算結果顯示所提出算法能夠有效解決實際工程案例。金亮亮等[19]將遺傳算法與變鄰域搜索有機結合，提出了一種文化基因算法求解單目標IPPS問題。Zhang等[20]提出了一種面向?qū)ο缶幋a的遺傳算法求解單目標IPPS問題。杜軒等[21]綜合運用遺傳算法、差分進化算法以及克隆鄰域搜索算法的特點，設計了一種有效的多群體混合算法求解單目標IPPS問題。Zhang等[22]提出了一種擴展帝國競爭算法求解分布式單目標IPPS問題。Liu等[23]設計了求解單目標IPPS問題的量子啟發(fā)式混合算法。文笑雨等[24]提出了一種兩階段混合算法求解單目標IPPS問題。Barzanji等[25]設計了基于邏輯的Benders分解方法求解單目標IPPS問題。

依據(jù)對多個目標處理方法的不同，多目標IPPS的求解方法可被分為兩類，即非Pareto的方法和基于Pareto的方法。非Pareto的方法屬于先決策后優(yōu)化，即權重的確定代表了決策者的決策結果，權重的設定會對優(yōu)化結果帶來一定的主觀影響因素。早期多目標IPPS問題的研究多采用加權法進行求解，近年來該方法使用較少。僅有Shokouhi[26]使用加權法和遺傳算法求解多目標IPPS問題。近年來，更多的學者采用基于Pareto的方法對IPPS問題進行求解，以期能夠減少主觀決策對問題求解的影響，找尋兼顧多個優(yōu)化目標的Pareto前沿。基于Pareto的方法屬于后驗法，即先優(yōu)化再決策，優(yōu)化的過程只與問題本身特性有關系，較少受到主觀因素的干擾。Jin等[27]設計一種改進的多目標Memetic算法求解多目標IPPS問題。Zhang 等[28]研究了再制造環(huán)境下的IPPS問題，提出了一種基于仿真優(yōu)化的多目標遺傳算法。李言等[29]設計了基于NSGA-II的多目標IPPS求解方法。Mohapatra等[30]設計了一種精英受控的NSGA求解多目標IPPS問題。Luo等[31]提出了一種帶免疫原理和外部存檔策略的多目標遺傳算法求解多目標IPPS問題。Manupati等[32]面向網(wǎng)絡制造環(huán)境提出一種基于移動代理的方法同時優(yōu)化IPPS的最大完工時間以及設備利用率。Milic等[33]提出了一種基于混沌理論的粒子群優(yōu)化算法同時優(yōu)化IPPS問題的最大完工時間、平均流程時間以及機器負載平衡。杜軒等[34]提出一種聚類差分進化算法同時優(yōu)化IPPS問題的3個目標。Zhang等[35]設計出一種參數(shù)調(diào)整的增強蟻群優(yōu)化算法同時優(yōu)化最大完工時間、流程時間以及計算時間。

由于基于Pareto的方法能夠更加客觀反應問題特性，該方法是當前多目標IPPS求解方法的研究焦點。但是，當前大多數(shù)研究僅停留在使用基本的多目標進化算法框架進行多目標IPPS問題的求解，與單目標IPPS優(yōu)化方法相比，多目標IPPS優(yōu)化方法在利用問題領域知識方面略顯不足。另外，在進化算法的研究領域，高維多目標進化算法已經(jīng)在函數(shù)優(yōu)化問題上取得了較為豐碩的理論成果[36]，但是在車間調(diào)度領域的應用還非常少。

2 不確定擾動下的IPPS問題研究現(xiàn)狀

受信息技術的發(fā)展制約，早期的IPPS研究聚焦于靜態(tài)生產(chǎn)環(huán)境，一般在提出模型時先假設不考慮實際制造過程中的不確定擾動因素，相關理論成果在實施應用時具有一定的局限性。隨著近年來新一代信息技術的高速發(fā)展，制造系統(tǒng)實施運行中各環(huán)節(jié)的相關數(shù)據(jù)能夠更容易地被采集以及存儲，不同系統(tǒng)之間的數(shù)據(jù)也更容易進行互聯(lián)互通，因此，越來越多的學者開始關注于不確定擾動下IPPS問題的研究。

Liu 等[37]考慮了新工件到達的不確定事件，設計了基于蟻群優(yōu)化算法的動態(tài)IPPS求解方法。為應對機器故障和新工件到達的不確定性，Xia等[38]將混合算法與滾動窗口技術相結合求解動態(tài) IPPS 問題。Yu等[39]提出了一種混合遺傳粒子群優(yōu)化算法求解動態(tài)IPPS問題，求解過程分為靜態(tài)階段和動態(tài)階段，在動態(tài)階段，針對機器故障這一車間運行動態(tài)事件，通過調(diào)整機器故障時間段內(nèi)待加工工件工藝路線以應對動態(tài)事件。巴黎等[40]將不確定加工時間考慮到工藝規(guī)劃與調(diào)度集成問題中。Jin等[41]提出一種文化基因算法求解帶不確定加工時間的IPPS問題。Jin等[42]考慮最大完工時間，穩(wěn)定性及拖期時間3個準則，提出一種求解動態(tài)IPPS問題的驅(qū)動重調(diào)度策略。Li等[43]采用區(qū)間數(shù)描述不確定加工時間，設計混合遺傳粒子群優(yōu)化算法對不確定IPPS問題進行求解。

表2 不確定擾動下IPPS問題應對策略及新增優(yōu)化目標Table 2 Coping strategies and new optimization objectives of IPPS under uncertain disturbance

3 面向綠色制造的IPPS問題研究現(xiàn)狀

綠色車間調(diào)度是綠色制造的重要環(huán)節(jié)，比傳統(tǒng)調(diào)度問題的求解難度更高，更具學術研究意義和工程應用價值[4]。IPPS問題是一種擴展的車間調(diào)度問題，隨著綠色制造的大力推進，綠色制造模式下IPPS問題的研究開始得到越來越多學者的關注。Li等[44]研究了面向可持續(xù)制造和再制造的IPPS模型。Dai等[45]建立了面向節(jié)能的工藝規(guī)劃與車間調(diào)度集成模型，其中能耗指標包含制造系統(tǒng)中所有工作機器在生產(chǎn)和非生產(chǎn)階段的總能耗。Zhang等[46]提出一種IPPS節(jié)能優(yōu)化模型。劉瓊等[47]提出了一種考慮碳排放量的IPPS模型。李聰波等[48]建立了面向能耗的分批IPPS模型。黃志清等[49]建立了工藝規(guī)劃與車間調(diào)度的能量優(yōu)化模型。李玲玲[50]、張漪[51]構建了IPPS與加工參數(shù)集成優(yōu)化的模型。孟磊磊等[52]使用空閑能耗和空閑時間的不同建模思想構建了面向節(jié)能的IPPS模型。Jin等[53]采用基于網(wǎng)絡圖的混合整數(shù)線性規(guī)劃模型構建了面向節(jié)能的IPPS模型。

在研究綠色制造模式下的IPPS問題時，不僅可以在車間調(diào)度環(huán)節(jié)通過改變工件在機器上的加工順序以實現(xiàn)節(jié)能減排，還可以在工藝規(guī)劃環(huán)節(jié)綜合考慮可選加工工藝、可選加工機器以及工序加工序列等因素對于綠色指標的影響。因此，綠色IPPS問題的研究能夠進一步發(fā)掘制造系統(tǒng)節(jié)能減排的潛力。對綠色IPPS問題進行研究的難點之一是如何構建合適的問題模型。上述面向綠色制造模式的IPPS問題研究大多數(shù)采取在建立模型時增加一個環(huán)境相關的目標函數(shù)，如能耗、碳排放等，建模方法相對比較單一。在已有綠色車間調(diào)度模型研究中，不僅僅采用增加綠色目標函數(shù)這一方法構建綠色車間調(diào)度模型，還有將能耗因素作為約束條件(如峰值能耗)以及將不超過截止完工時間作為約束來優(yōu)化總能耗的方法來構建綠色車間調(diào)度模型。這些研究成果能夠為綠色制造模式下的IPPS問題的研究提供新的思路。另一方面，由于綠色IPPS問題在進行求解時，需要同時兼顧經(jīng)濟指標和綠色指標，問題的解空間更加龐大復雜。綠色指標與經(jīng)濟指標之間呈現(xiàn)復雜的非線性關系，在進行優(yōu)化求解時，對求解算法的設計提出了更高的要求。

4 研究展望

隨著智能制造技術的發(fā)展，IPPS問題的研究迎來了新的機遇與挑戰(zhàn)。未來對該領域的研究可從以下幾個方面繼續(xù)展開：

1)基于工藝規(guī)劃和車間調(diào)度的層次關系構建有效集成模型。

IPPS問題涉及到工藝規(guī)劃部門的決策者與車間調(diào)度部門的決策者以及企業(yè)上層管理部門的決策者。不同決策者因其面向的對象不同，進行決策時的側重點也有所不同。工藝規(guī)劃部門關注工藝編制的合理化與安全規(guī)范、工藝技術的改進以及標準化等工作；車間調(diào)度部門關注車間合理化派工，機器故障的實施監(jiān)控與診斷等工作；企業(yè)上層管理部門直接與客戶對接，更加關注于產(chǎn)品交貨期與客戶滿意度等需求。不同決策者之間通常處于一種非合作的競爭關系，如果不能協(xié)調(diào)好各決策者之間的關系，就有可能出現(xiàn)企業(yè)生產(chǎn)無法順利執(zhí)行的不利局面。IPPS問題是一個典型的多決策者博弈問題。不同企業(yè)的工藝規(guī)劃部門和車間調(diào)度部門職責和能力有所不同，決策者對于工藝規(guī)劃和車間調(diào)度的重視程度也有所不同。但是，在對工藝規(guī)劃和車間調(diào)度集成模型方面，現(xiàn)有研究大多數(shù)是將工藝規(guī)劃和車間調(diào)度放在同一層次。如何從企業(yè)自身制造特點出發(fā)，結合制造系統(tǒng)柔性，評估工藝規(guī)劃與車間調(diào)度在其進行集成優(yōu)化時的主從關系具有非常重要的實際應用價值。比如，當企業(yè)更重于工藝需求，則工藝規(guī)劃在集成優(yōu)化中占據(jù)主導地位。當企業(yè)訂單任務緊急時，車間調(diào)度在集成優(yōu)化中應當占據(jù)主導地位。因此，對工藝規(guī)劃和車間調(diào)度進行集成優(yōu)化時，需要結合具體企業(yè)的實際生產(chǎn)能力和訂單需求，研究能夠揭示工藝規(guī)劃和車間調(diào)度之間層次關系的有效模型。

2)揭示IPPS問題多個優(yōu)化目標的復雜關系。

IPPS問題的優(yōu)化目標往往并不是絕對意義上的矛盾沖突關系，在全局和局部都可能會存在線性或非線性的復雜制約關系，也可能會存在冗余目標。比如，在工藝規(guī)劃階段，工藝成本的降低與客戶對于工藝設計的滿意度之間并不是一種簡單的線性關系，在一定程度上能夠達到雙贏，但是很多時候又是相互沖突的；最大完工時間的減少一般情況下會減少總流程時間，但是有可能會帶來總流程時間的增加，從而影響到面向交貨期的目標。另外，在工藝規(guī)劃階段決定的每個工件的加工時間最短有時能夠帶來車間調(diào)度總完工時間最短，但是當機器之間的負載平衡性沒有有效考慮時，又會增加車間調(diào)度階段的完工時間。綠色制造模式下，經(jīng)濟類的優(yōu)化目標和環(huán)境類的優(yōu)化目標之間也存在復雜的耦合關系。如果能夠揭示IPPS問題多個優(yōu)化目標之間的復雜關系，就可以為多目標優(yōu)化方法的設計提供一定的先驗知識，有助于提高算法性能。

3)基于問題領域知識的高效集成優(yōu)化方法設計。

已有IPPS問題的研究中，大多數(shù)僅考慮同時優(yōu)化3個以內(nèi)的目標。從上述總結中可以看出，IPPS問題包含的優(yōu)化目標非常多，遠不止3個，屬于高維多目標優(yōu)化問題。與同時優(yōu)化3個以內(nèi)的多目標優(yōu)化方法相比，高維多目標優(yōu)化問題中優(yōu)化目標數(shù)量多使得Pareto支配關系失效，優(yōu)化目標之間制約關系復雜使得問題求解更為困難。由于IPPS問題工藝約束少，柔性大，與傳統(tǒng)調(diào)度問題相比，IPPS問題解空間的冗余更大，IPPS高維多目標優(yōu)化方法的研究極具挑戰(zhàn)性。基于Pareto的多目標優(yōu)化方法能夠更加客觀地反應問題本身的特性，因此是當前的主要研究方向。但是，當IPPS問題優(yōu)化目標大大增多時，基于Pareto的多目標優(yōu)化方法在非支配解排序方法，種群收斂性和多樣性維護策略等方面會給算法的設計帶來新的挑戰(zhàn)，傳統(tǒng)多目標優(yōu)化方法無法有效地解決高維多目標IPPS問題，亟需深入挖掘IPPS問題的層次關聯(lián)性、決策空間結構與目標空間特性，指導高效集成優(yōu)化方法的設計。

4)基于數(shù)字孿生技術的IPPS動態(tài)調(diào)控方法研究。

IPPS問題本身因為考慮到制造系統(tǒng)的多種柔性因素，可以較好地應對生產(chǎn)中一些不確定擾動因素。可以考慮結合數(shù)字孿生技術，實時采集工藝規(guī)劃與車間調(diào)度環(huán)節(jié)的產(chǎn)品、資源、物流與生產(chǎn)數(shù)據(jù)，利用搜集的數(shù)據(jù)統(tǒng)計加工時間不確定、交貨期不確定、急件插入、機器故障等不確定擾動事件，歸納不確定擾動事件類型，分析不確定擾動事件對生產(chǎn)效率、碳排放和客戶滿意度的影響，確定不同不確定擾動事件的應對策略，對可選工藝計劃、車間資源，以及在碰到突發(fā)事件時的再規(guī)劃和再調(diào)度問題指標進行統(tǒng)計分析。從模型構建以及運作方法上及時響應突發(fā)事件，發(fā)揮IPPS兼顧多種工藝柔性的特點，探索不確定擾動下的IPPS問題動態(tài)調(diào)控方法，更好地發(fā)揮工藝規(guī)劃與車間調(diào)度集成優(yōu)化帶來的優(yōu)勢。

總而言之，IPPS問題的研究對提高我國智能制造產(chǎn)業(yè)的管理水平、核心競爭力、促進其可持續(xù)發(fā)展具有重要意義，其理論價值與現(xiàn)實意義廣闊。