高 亮，劉齊浩，李新宇，李全俊

(1.華中科技大學 機械科學與工程學院，湖北 武漢 430074；2.中國兵器裝備集團自動化研究所有限公司 智能制造事業(yè)部，四川 綿陽 621000)

“中國制造2025”是我國制造強國戰(zhàn)略的第一個十年行動綱領，其核心是智能制造。實現(xiàn)智能制造的關鍵一步是實現(xiàn)制造系統(tǒng)的智能化。制造系統(tǒng)的高效運行能提高企業(yè)的競爭能力與對市場的快速響應能力，對于企業(yè)乃至國家制造戰(zhàn)略層面的發(fā)展至關重要[1]。但我國制造系統(tǒng)的效率明顯低于國外先進水平，其運行優(yōu)化技術(shù)是主要瓶頸之一。制造系統(tǒng)的運行優(yōu)化一直是機械制造學科的研究熱點。資料表明，制造系統(tǒng)中非切削過程的時間占比較大[2]。車間調(diào)度是指在企業(yè)車間有限資源的約束下，確定工件在相關設備上的加工順序和開始加工時間，以保證所選定的生產(chǎn)目標最優(yōu)。調(diào)度是制造系統(tǒng)的基礎，是提高制造系統(tǒng)效率的關鍵技術(shù)之一。因此，制造系統(tǒng)運行優(yōu)化中的調(diào)度技術(shù)直接影響著制造的效率與成本，與其相關的研究具有重要的實際工程意義。

隨著車間信息化能力的增強，各制造子系統(tǒng)之間的關聯(lián)程度也相應提升，為工藝規(guī)劃與車間調(diào)度的集成提供技術(shù)保障[3]。傳統(tǒng)的工藝規(guī)劃與車間調(diào)度在制造系統(tǒng)中通常獨立運行，相互之間不存在優(yōu)化配合。將兩個制造子系統(tǒng)進行集成，能有效地提高生產(chǎn)效率和提升產(chǎn)品質(zhì)量。集成式工藝規(guī)劃與車間調(diào)度(integrated process planning and scheduling，IPPS)的集成優(yōu)化技術(shù)能夠在工藝規(guī)劃執(zhí)行的同時，考慮制造車間的機器狀態(tài)、制造資源和訂單交貨期等約束條件，生成更符合調(diào)度環(huán)境的工藝路線，能夠進一步推進制造系統(tǒng)的智能化。

IPPS作為一類典型的NP (non-deterministic polynomial) 難問題，廣泛存在于化工、冶金、航空、航天等制造領域中，具有重要的研究意義和工程價值[4]。本文在2011年本團隊所發(fā)表IPPS綜述研究的基礎之上[5]，主要對近十多年來的相關研究工作進行系統(tǒng)綜述與回顧。

1 集成式工藝規(guī)劃與車間調(diào)度問題概述

1.1 工藝規(guī)劃問題概述

工藝規(guī)劃是產(chǎn)品設計與制造的橋梁，能將產(chǎn)品設計數(shù)據(jù)轉(zhuǎn)化成制造信息。通過合理優(yōu)化工件的工藝路線，能有效提升生產(chǎn)效率、降低生產(chǎn)成本、節(jié)省生產(chǎn)資源，在有限的資源及加工能力范圍內(nèi)，滿足設計規(guī)格和需求。一個成熟的工藝規(guī)劃系統(tǒng)一般應具有但不限于如下功能，包括檢索標準工藝文件、選擇加工方式、規(guī)劃加工路線、選擇和分配加工資源(機床、刀具、量具和夾具等)、優(yōu)化工藝參數(shù)、計算加工時間和加工成本、確定工序尺寸和公差及選擇毛坯、生成工序圖或工序卡等[6]。其中，選擇加工方式、規(guī)劃工藝路線、分配加工資源等功能，可以看作是廣義的工藝規(guī)劃內(nèi)容，是工藝規(guī)劃系統(tǒng)的核心功能。

通常情況下，工藝規(guī)劃問題可以被描述為一個待加工工件的加工過程包含一定數(shù)量的加工特征，特征之間存在特定的優(yōu)先關系約束；不同特征可由不同的工序或工序集合完成加工，一個工序的加工存在多臺加工機器可選；工藝規(guī)劃的任務是在遵循特定的優(yōu)先關系約束的前提下，合理安排工序的加工順序及分配對應的加工機器，規(guī)劃出一條滿足特定加工需求的最優(yōu)工藝路線[7]。

工藝規(guī)劃需要決策的子問題一般包括加工工藝選擇、加工資源選擇和工序加工序列確定。與3類子問題相對應的是3種加工柔性：不同的加工特征通過不同的加工工序或工序集合實現(xiàn)，可稱為工藝柔性；在滿足特定先后約束的前提下，加工工序相互之間的順序可調(diào)，稱為工序次序柔性；同一工序的加工有多臺機器可選，即機器選擇柔性。

1.2 車間調(diào)度問題概述

車間調(diào)度問題可以描述為將n個工件安排在m臺機器上加工，每個工件的加工由若干個工序?qū)崿F(xiàn)，工件在若干臺機器上加工；在遵循一定的工藝約束情況下，將各工件合理地安排到各機器，并決策工件的加工次序和加工開始時間，滿足特定的生產(chǎn)目標或需求。一個調(diào)度問題可以由三元組α|β|γ描述，α為機器環(huán)境，β為加工特征及約束，γ為優(yōu)化目標。根據(jù)α的類型，可以將車間調(diào)度問題分為如下類別[8]。

1) 單機調(diào)度問題 (single machine scheduling problem，SMP)：單機調(diào)度問題是所有調(diào)度問題中最基礎和最簡單的，是其他復雜調(diào)度問題的特例。其特征為所有工件只有一道加工工序，生產(chǎn)系統(tǒng)中只有一臺加工機器，所有工件都在該機器上加工。

2) 并行機調(diào)度問題 (parallel machine scheduling problem，PMP)：加工系統(tǒng)中有若干臺加工功能相同的機器，所有待加工工件只有一道工序，工件可選任一機器執(zhí)行加工。并行機調(diào)度問題可根據(jù)機器加工速度的不同，分為并行同速機調(diào)度和并行異速機調(diào)度。

3) 流水車間調(diào)度問題 (flow shop scheduling problem，F(xiàn)SP)：n個工藝路線相同的工件，在m臺機器上串行加工，需要決策各機器上工件的加工次序[9]。若存在至少某一階段有多臺加工機器可選，則該問題被稱為混合流水車間調(diào)度問題 (hybrid flow shop scheduling problem，HFSP) 或柔性流水車間調(diào)度問題 (flexible flow shop scheduling problem，F(xiàn)FSP)。

4) 作業(yè)車間調(diào)度問題 (job shop scheduling problem，JSP)：n個工藝路線不同的工件，在m臺加工功能各異的機器上加工，需要決策各工件的開始加工時間和各機器上工件的加工次序。若存在至少某一工件的工序有多臺加工機器可選，則該問題被稱為柔性作業(yè)車間調(diào)度問題 (flexible job shop scheduling problem，F(xiàn)JSP)。

5) 開放車間調(diào)度問題 (open shop scheduling problem，OSP)：n個待加工工件的加工工序給定，但工序間的加工次序未定，在m臺機器上多次加工，需要決策各機器上的工序次序與工序的開始加工時間[10]。

加工特征及約束β主要包括順序相關的準備時間、加工中斷、優(yōu)先約束、機器故障、機器適用限制、阻塞、零等待等。而優(yōu)化目標 γ通常包括最大完工時間Cmax、最大流經(jīng)時間Fmax、最大推遲完成時間Lmax、最大拖后時間Tmax等。

根據(jù)實際生產(chǎn)需求和制造環(huán)境，車間調(diào)度還具有多目標、不確定、動態(tài)等特性，給問題帶來了更大的求解難度。車間調(diào)度已經(jīng)被證明是NP-Complete組合優(yōu)化問題，問題可行解的數(shù)量隨著問題規(guī)模的增大呈指數(shù)級增長[8]。問題較高的求解難度吸引了大量的研究者尋求快速高效的求解方法。從20世紀50年代開始，國內(nèi)外的學者們嘗試了各種類型的方法對調(diào)度問題進行求解。早期這些方法主要是以運籌學為基礎的精確算法，包括割平面法 (cutting plane method)、分支定界法 (branch & bound) 等[8]。但是精確算法受限于問題規(guī)模，無法在較大規(guī)模的調(diào)度問題中展現(xiàn)出優(yōu)勢，反而是近似求解方法在20世紀80年代以后成為了當前調(diào)度問題求解方法的主流。包括元啟發(fā)式算法，如遺傳算法 (genetic algorithm，GA) 等，以及優(yōu)先調(diào)度規(guī)則等方法，在調(diào)度問題的求解上展現(xiàn)了足夠的優(yōu)勢，逐漸成為當前研究者們求解調(diào)度問題的主要手段。到目前為止，新的啟發(fā)式或元啟發(fā)式算法的提出和改進，仍然是當前車間調(diào)度領域的主要研究方向。

1.3 IPPS問題概述

傳統(tǒng)的工藝規(guī)劃和車間調(diào)度是分步進行的。在既定的工藝上進行調(diào)度，意味著工藝部分不能給調(diào)度提供柔性支持。這會導致某些生產(chǎn)問題，如機器載荷分布不均、瓶頸資源的分配不當、矛盾目標之間優(yōu)化沖突等。為了解決上述問題，近年來，越來越多的學者提出將工藝規(guī)劃和車間調(diào)度進行集成優(yōu)化，來尋求更好更高效的制造方案。工藝規(guī)劃與車間調(diào)度的集成逐漸成為當下研究的熱點與趨勢。

IPPS問題由工藝規(guī)劃和車間調(diào)度兩部分組成。與各子問題相比，IPPS問題具有更大的求解難度。其包含的3類柔性分別為工藝柔性、次序柔性及機器柔性。在以上3種柔性確定的前提條件下，車間調(diào)度部分可看作是傳統(tǒng)的JSP，需要做的決策為對不同工件的工序進行調(diào)度。IPPS問題作為工藝規(guī)劃與車間調(diào)度的集成，需要同時決策4類子問題，包括不同工件的工序排序、相同工件工序排序、加工機器選擇、工藝選擇。這一點不同于任一基礎的車間調(diào)度類型——FSP、JSP、FJSP。IPPS問題以及各類型調(diào)度問題包含的柔性如圖1所示。從圖1中可以看出，IPPS包含的柔性最多，需要做的決策最多，是最復雜和最難以求解的基礎調(diào)度類型。

圖1 IPPS問題與其他基礎車間調(diào)度問題的關系Figure 1 The relationship between IPPS problem and other basic shop scheduling problems

根據(jù)前文對工藝規(guī)劃和車間調(diào)度的問題概述，可將IPPS的問題描述如下。n個工藝待定的工件，需要在m臺具有加工柔性的機器上完成加工；IPPS的任務是在滿足特定的約束和優(yōu)化目標的前提下，為這些工件制定合理的加工工藝路線和車間調(diào)度方案。相比于車間調(diào)度問題，IPPS問題需要在調(diào)度之外為每個工件制定工藝路線。待定工藝的工件需要從網(wǎng)絡圖中規(guī)劃生成工藝路線。以圖2為例，網(wǎng)絡圖由5種類型的節(jié)點組成：起始節(jié)點，表示零件生產(chǎn)過程的開始；終止節(jié)點，表示零件生產(chǎn)的終止；工序節(jié)點，表示加工工序；OR節(jié)點與JOIN節(jié)點的組合，代表工件的工藝柔性。工序節(jié)點包含3種類型的信息：實心圈中的工序號，{}中的可選機器號，以及[]中對應的加工時間。網(wǎng)絡圖中的節(jié)點由箭頭連接，表示工序之間的優(yōu)先關系約束。需要注意的是，生成工藝路線時，只能選擇包含在一對OR節(jié)點和對應的JOIN節(jié)點間的其中一條工序支路。所選支路所包含的工序和其他工序構(gòu)成了該工件的可行加工工序組合。此外，每道工序只能選擇一臺機器作為平臺進行相應的加工。以圖2為例，其中一條完整可行的工藝路線為1(3)→2(5)→3(2)→6(7)→5(8)→7(13)→9(11)→10(13)。括號外的數(shù)字表示工序號，括號內(nèi)的數(shù)字表示機器號。不同的工件具有不同的工藝網(wǎng)絡圖，一個待加工工件會衍生出相當數(shù)量的工藝路線。

圖2 工件工藝網(wǎng)絡圖Figure 2 The process network graph

2 集成式工藝規(guī)劃與車間調(diào)度問題的研究現(xiàn)狀

2.1 工藝規(guī)劃問題的研究現(xiàn)狀

工藝規(guī)劃的研究方法主要分為精確方法和近似方法兩類。其中，精確方法包括數(shù)學規(guī)劃法和分支定界法；近似方法主要包括以GA、蟻群算法 (ant colony optimization，ACO) 在內(nèi)的諸多智能算法。精確方法能夠有效求解小規(guī)模問題的最優(yōu)解，但是隨著問題規(guī)模的增大，組合爆炸導致的計算效率低下，使得精確方法在求解大規(guī)模工藝規(guī)劃問題中未能展示出足夠的優(yōu)勢。相比于精確算法，近似算法更貼合生產(chǎn)實際：實際生產(chǎn)中需要在可接受計算時間內(nèi)得到近優(yōu)解，對于問題的最優(yōu)解則不給予過多關注。

1) 精確求解方法與數(shù)學規(guī)劃模型。

從問題的數(shù)學規(guī)劃模型出發(fā)對問題展開研究，有助于加深研究者對問題特征的理解。當前，大多數(shù)文獻都是基于工藝特征的方式對工藝規(guī)劃問題進行建模。這種方式會對工件的工藝信息進行整合處理，且在某種程度上使得工件原始的加工工藝信息發(fā)生改變[11]。此外，一些文獻中的其他建模方式需要對模型進行繁雜的預處理，如將所有可選的工序進行組合，以消除OR節(jié)點[12]。這種組合的方式雖然能完整表達工序間的優(yōu)先關系，且不添加任何額外約束，但是其預處理操作較為繁雜。當OR節(jié)點較多或者OR節(jié)點間相互包容、拓撲結(jié)構(gòu)復雜時，這種預處理操作會對研究者造成較大的工作負擔。Floudas等[13]根據(jù)時間表示方式的不同，詳細分析了幾種工藝規(guī)劃混合整數(shù)規(guī)劃模型，并提出幾類優(yōu)化方法以提升模型的計算效率。考慮工藝規(guī)劃與調(diào)度的互補性，Li等[14]建立了集成工藝規(guī)劃與車間調(diào)度的數(shù)學模型。Xia等[15]為可重構(gòu)工藝規(guī)劃問題提出基于特征的零件種類表示模型。同樣是基于特征，Jin等[16]建立考慮運輸時間的工藝規(guī)劃問題的混合整數(shù)規(guī)劃模型。

由于精確方法求解工藝規(guī)劃問題的效率較低，所以當前相關研究較少。早期研究中，Kusiak等[6]用整數(shù)規(guī)劃法嘗試求解了工藝規(guī)劃問題，但是僅局限于較小規(guī)模的問題實例。在注塑模具的實際工藝規(guī)劃中，Gan等[17]提出的一種分支定界方法成功優(yōu)化并求解動態(tài)的工藝規(guī)劃問題。對于具有柔性工藝規(guī)劃路線的生產(chǎn)調(diào)度問題，Jiang等[18]應用數(shù)學規(guī)劃法，求解以最小化生產(chǎn)到期日絕對偏差和完工時間為優(yōu)化目標的調(diào)度問題。

2) 近似求解方法與啟發(fā)式。

工藝規(guī)劃屬于NP-Complete問題[19]，僅僅利用傳統(tǒng)的梯度下降法、圖論法和仿真方法很難得到令人滿意的優(yōu)化結(jié)果[20]。因此，國內(nèi)外眾多研究學者選擇通過智能算法來求解工藝規(guī)劃問題，其方法主要包括多代理系統(tǒng) (multi-agent system，MAS)[21]、GA[22]、禁忌搜索 (tabu search，TS)[23]、模擬退火 (simulated annealing，SA)[24]、粒子群優(yōu)化 (particle swarm optimization，PSO)[25-26]、ACO[27]等。上述智能算法及其混合算法在工藝規(guī)劃問題的求解中展現(xiàn)了一定的優(yōu)越性，并在實際案例的應用中取得一定成效。

工藝規(guī)劃問題可被看作為受約束的旅行商問題(traveling salesman problem，TSP)[28]。為了解決較為復雜的柱狀零件的工藝規(guī)劃問題，Li等[29]提出了一種GA和SA的混合算法。根據(jù)可選工藝路線之間的漢明距離 (hamming distance) 來搜索和選擇解，混合的SA算法加強了混合算法的鄰域搜索能力。Hua等[30]提出了一種基于GA的綜合算法，求解工藝規(guī)劃問題中機器方案選擇和工序序列的全局或近全局最優(yōu)解。Li等[31]提出一種基因編程 (genetic programming，GP) 算法，對工藝信息網(wǎng)狀圖中的OR節(jié)點分支進行遺傳操作。與傳統(tǒng)的GA相比，GP算法展現(xiàn)了一定的優(yōu)越性，但是其將網(wǎng)狀圖轉(zhuǎn)換成樹狀圖的預處理操作難度會隨網(wǎng)狀圖拓撲結(jié)構(gòu)復雜化而增大。Shin等[32]考慮刀具選擇和進刀方向等制造資源，提出共生進化算法 (symbiotic evolutionary algorithm，SEA)，同時對機器負載平衡、最小化零件轉(zhuǎn)移和最小化刀具更換3個目標進行優(yōu)化。通過將PSO算法離散化，Wang等[25]提出一種混合了兩類局部搜索策略的PSO算法來求解工藝規(guī)劃問題。隨后Li等[33]也提出一種改進的PSO算法，對考慮準備時間的工藝規(guī)劃問題進行求解，雖未考慮刀具選擇和進刀方向，但其算法的效率與其他算法相比仍展現(xiàn)了一定的優(yōu)勢。在文獻[34]中，ACO算法結(jié)合問題的約束矩陣和狀態(tài)矩陣，在兩個柱狀零件的工藝規(guī)劃問題中得到應用，對比于傳統(tǒng)的TS算法、SA算法和GA，該算法的求解效果更好。

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

早期的研究者們將工藝和調(diào)度分開進行討論，會在實際生產(chǎn)中導致嚴重的瓶頸問題，如載荷分布不均、優(yōu)化目標沖突等。Nasr等[35]和Kim等[36]較早開始嘗試將工藝規(guī)劃與作業(yè)車間調(diào)度集成。從此，集成式工藝規(guī)劃與車間調(diào)度走進了研究者的視野。工藝規(guī)劃與車間調(diào)度的集成相關研究最早開始于20世紀80年代中期。早期的集成僅是通過增加可選工藝路線數(shù)量，以提升制造系統(tǒng)的柔性。而后隨著動態(tài)反饋思想的引入，使得兩系統(tǒng)的集成進一步提升。發(fā)展至今，IPPS問題可以根據(jù)集成形式大致分成兩類：第1類是每個工件具有多條預先生成的工藝路線，調(diào)度集成工藝的任務是從這些工藝路線中選擇一條進行調(diào)度[37]；第2種則是每個工件的工藝信息以特征表 (feature table) 或網(wǎng)絡圖 (network graph) 的形式表示，IPPS需要從圖或表中規(guī)劃得出工藝路線再進行調(diào)度。

第1種形式的IPPS問題相對第2種類型更簡單，因為通常情況下工件的候選工藝路線數(shù)是有限的。Jain等[38]嘗試求解車間生產(chǎn)中有多重工藝路線可選的車間調(diào)度問題。Chan等[39]提出帶支配基因的GA(GA with dominant genes，GADG) 來解決柔性制造系統(tǒng) (flexible manufacturing system，F(xiàn)MS) 中具有可選工藝路線的調(diào)度問題。Li等[14]建立第1種類型IPPS問題的數(shù)學模型，并提出相應的進化算法進行求解。Shen等[40]研究分布式制造系統(tǒng)中的IPPS問題，提出基于代理智能體 (Agent) 的求解思路，啟發(fā)了后續(xù)的相關研究。隨后，Li等[21]又提出基于代理智能體的方法來集成工藝規(guī)劃和調(diào)度，并通過實驗證明代理智能體之間的交互和溝通在解決IPPS問題中的有效性。?zgüven等[41]在FJSP的基礎上，建立第1種類型IPPS問題的混合整數(shù)線性規(guī)劃 (mixed-integer linear programming，MILP) 模型。在供應鏈的IPPS問題中，Moon等[42]同樣建立了一個MILP模型來描述問題中的集成，并提出一種基于拓撲排序的進化算法來求解該類IPPS問題。

由于第1種形式的IPPS問題中，每個工件的待選工藝路線有限，本質(zhì)上還是屬于FJSP。因此，近十年IPPS研究的焦點逐漸轉(zhuǎn)移到了第2種類型上。第2種類型IPPS問題的工件工藝信息，通常有兩種表達方式：特征表和網(wǎng)絡圖，兩種表現(xiàn)形式可以互相轉(zhuǎn)換。Li等[20]提出一種SA算法來求解該類IPPS問題，并通過最大完工時間、機器利用率、工件總拖期和制造成本這4個目標來評價所提算法的優(yōu)越性。Leung等[43]將ACO算法應用于多Agent系統(tǒng)來求解IPPS問題。針對第2種類型的IPPS問題，Jin等[44]對多個MILP模型進行了分析討論，并在線性求解器上對這些模型進行了求解。第2種類型最著名的數(shù)據(jù)集為Kim數(shù)據(jù)集[45]，許多研究都是基于該數(shù)據(jù)集開展的。Li等[46]提出一種新的混合算法對Kim數(shù)據(jù)集進行了求解，與Kim等[45]的算法相比，刷新了大部分結(jié)果。Zhang等[47]提出一個加強的ACO算法，對Kim數(shù)據(jù)集進行求解，并刷新了24個問題中的17個。Li等[48]隨后提出一種變鄰域搜索遺傳算法(genetic algorithm and variable neighborhood search，GAVNS)，再次刷新了該數(shù)據(jù)集中的9個解，其中3個解達到了下界。Lian等[49]提出的殖民競爭算法進一步刷新Kim數(shù)據(jù)集，取得了更好的結(jié)果，成功找到全部下界。

現(xiàn)在有關于IPPS的精確方法和數(shù)學模型的研究較少?；谶壿嫷腂enders分解 (logic-based benders decomposition，LBBD) 算法，Barzanji等[50]開發(fā)了幾種分解方式，作為解決IPPS問題的精確求解方法。Li等[14]建立基于工件工藝路線的IPPS數(shù)學模型，并提出一種進化算法對問題進行求解。關于IPPS問題模型最系統(tǒng)的研究是Jin等[44]于2016年開展的，在研究中分析了幾類MILP模型，并且在線性求解器CPLEX中進行求解，以比對它們的求解效率。但是，對于當前大部分的大規(guī)模IPPS問題實例，現(xiàn)有的IPPS模型都無法進行求解。受限于問題規(guī)模，現(xiàn)有主流的線性求解器求解模型時，獲得可行解的求解時間過長，甚至在較長時間內(nèi)都無法得到一個可行解。

從問題類型角度出發(fā)，第2種類型的IPPS問題更符合先進制造系統(tǒng)的現(xiàn)狀，因為特征表和網(wǎng)絡圖的工藝表現(xiàn)形式能夠給予調(diào)度系統(tǒng)更多的支持。從問題的求解方法出發(fā)，當前無論是第1種類型的IPPS問題還是第2種類型，主流求解算法都屬于近似求解方法，如啟發(fā)式規(guī)則、GA、SA算法、TS算法、PSO算法、ABC算法等。由此，可以推斷出未來短期內(nèi)IPPS問題的主流研究方向，仍然是改進各類型求解算法以獲取第2種類型IPPS問題更好的求解效果。

3 多目標IPPS問題的研究現(xiàn)狀

為解決實際生產(chǎn)中的多目標問題，并為生產(chǎn)管理決策者提供高質(zhì)量的替代方案，實際的IPPS問題同樣可以作為多目標優(yōu)化問題存在。常見的優(yōu)化目標包括最小化最大完工時間、最小化總機器負荷和最小化最大機器負荷等。多目標IPPS問題的常用處理方法有基于權(quán)重的方法和基于Pareto的方法。由于目標間權(quán)重系數(shù)難以平衡，基于Pareto的方法是當前多目標優(yōu)化研究的主流。

Li等[51]提出一種基于博弈論的方法來研究多目標IPPS問題，并利用基于博弈論方法中的納什均衡來解決多目標問題。Mohammadi等[52]充分利用勘探搜索和快速收斂的能力，提出一種多目標混合模擬退火算法 (multiobjective simulated annealing algorithm，MOHSA)。Mohapatra等[53]將IPPS視為可重構(gòu)制造環(huán)境下的多目標優(yōu)化問題，采用非支配排序GA二代(non-dominated sorting GA-II，NSGA-II) 處理問題的計算復雜性。Li等[54]用多層結(jié)構(gòu)改進了解的表示，并應用NSGA-II來解決多目標IPPS問題。Jin等[55]提出一種多目標Memetic算法來解決多目標IPPS問題。Shokouhi等[56]將最小化最大完工時間、最小化關鍵機器負荷和最小化機器總負荷作為目標函數(shù)，嘗試以加權(quán)的形式應用GA求解多目標IPPS問題。Zhao等[57]提出一種基于兩代Pareto的ACO算法，求解具有可選工藝路線和不相關并行機器的多目標JSP。Zhang等[58]以節(jié)能減排為目標，利用工藝規(guī)劃與調(diào)度的集成，采用基于非支配排序的層級式多策略GA實現(xiàn)節(jié)能優(yōu)化。

4 分布式IPPS問題的研究現(xiàn)狀

在經(jīng)濟全球化的背景下，訂單個性化的需求增加，導致了產(chǎn)品多樣化的生產(chǎn)需求，制造企業(yè)正朝著大規(guī)模定制的方向發(fā)展。傳統(tǒng)的制造和管理模式越來越難以滿足現(xiàn)代企業(yè)的發(fā)展要求。因此，制造模式開始從傳統(tǒng)的單一車間向分布式多車間演變。分布式制造已逐漸成為一種重要的趨勢，并已在許多重要行業(yè)有了成功的應用，如航空、航天、電子制造等。2021年的Science最新發(fā)文也指出了分布式制造的重要性[59]。

分布式車間調(diào)度的研究專注于分布式制造系統(tǒng)，在企業(yè)、工廠和車間之間分配工作計劃，為各企業(yè)、工廠或車間生成生產(chǎn)計劃，以優(yōu)化生產(chǎn)指標。根據(jù)不同工廠的具體情況制定生產(chǎn)方案至關重要。通過合理分配工廠間的生產(chǎn)任務，管理者可以更好地處理單一生產(chǎn)的風險，降低相應的生產(chǎn)成本和產(chǎn)品交付周期。

分布式制造模式已經(jīng)成為工業(yè)中的一個典型現(xiàn)象。目前關于分布式制造的研究主要集中在分布式流水車間或分布式作業(yè)車間問題上，其中工廠的結(jié)構(gòu)大多被看作是同構(gòu)的。但實際上，不同工廠的生產(chǎn)能力不同，對于相同的零件，各工廠可以提供完全不同的可選工藝方案。將每個工廠視為一個簡單的同構(gòu)作業(yè)車間環(huán)境，是對柔性制造能力的忽視和浪費。因此，考慮分布式制造中的異構(gòu)工藝柔性，即分布式IPPS (distributed IPPS，DIPPS) 問題，更適合于實際生產(chǎn)環(huán)境。與分布式JSP (distributed JSP，DJSP) 或分布式FJSP (distributed FJSP，DFJSP) 相比，DIPPS問題更貼近實際生產(chǎn)需求，同時更有研究價值。

Wu等[60]首次將分布式虛擬制造 (distributed virtual manufacturing，DVM) 環(huán)境中的工藝規(guī)劃問題和車間調(diào)度問題同時考慮，還基于Java的多代理系統(tǒng)(multi-agent system，MAS) 實現(xiàn)了DVM中的集成框架。最后，通過在仿真環(huán)境中建立虛擬制造模型，并與實際生產(chǎn)中的順序制造方法進行對比，驗證該方法的有效性。在綜述文章中，Shen等[40]分別討論了分布式制造系統(tǒng)中工藝規(guī)劃問題和車間調(diào)度問題的研究現(xiàn)狀，并介紹了基于Agent方法在解決分布式工藝規(guī)劃和調(diào)度問題方面幾個潛在的優(yōu)勢，為后繼研究者們在DMS (distributed manufacturing system)中同時考慮這兩個問題，提供了開創(chuàng)性的想法。Wang等[61]對DMS中工藝規(guī)劃和車間調(diào)度的研究進行了系統(tǒng)的綜述，討論了當前的生產(chǎn)模式以及現(xiàn)有優(yōu)化方法的局限性。Zhang等[62]研究了DMS中的工藝規(guī)劃與調(diào)度問題，提出一種多目標GA來解決該問題。上述研究雖然在同一個DMS中同時考慮了工藝規(guī)劃和調(diào)度，但對于二者集成性的討論還有待深入。隨著對IPPS問題研究的深入，Zhang等[63]試圖利用兩類GA來解決DMS中的IPPS問題，即DIPPS問題。隨后，研究對另一種擴展型的GA進行改進，用來解決模糊工藝規(guī)劃與調(diào)度問題的分布式集成問題，該問題可視為DIPPS問題的變體類型[63]。Lin等[64]同樣是基于GA框架，通過生成負載均衡解來更有效地搜索DIPPS問題解空間，并比較3種類型染色體表示的優(yōu)劣。

5 研究現(xiàn)狀總結(jié)與問題分析

雖然IPPS的研究已經(jīng)取得較好進展，但依然不完善，還有很大的探索空間。

1) 當前工藝規(guī)劃問題以及IPPS問題的模型在求解大規(guī)模案例時，求解效率低下，無法在短時間內(nèi)獲得最優(yōu)解。

2) 工藝規(guī)劃和車間調(diào)度的集成方式一直是IPPS問題的研究重點?，F(xiàn)有IPPS研究中的集成方式還有待改進，子系統(tǒng)間的結(jié)合還不夠緊密，無法充分發(fā)揮工藝規(guī)劃與車間調(diào)度的互補屬性。

3) 現(xiàn)有多目標求解方法較少考慮子系統(tǒng)的耦合關系，決策者常常難以把握各優(yōu)化目標間的權(quán)重，對多目標決策造成困擾。

4) 在分布式制造系統(tǒng)中，求解IPPS問題時考慮分布式制造的特征還不充足，無法充分發(fā)揮分布式制造的優(yōu)勢。

針對上述現(xiàn)狀，IPPS未來工作可聚焦在以下幾點。

1) 對問題模型進行線性化研究，建立可高效求解的MILP模型。此外，研究更為通用化的建模技術(shù)，為實際生產(chǎn)中的約束與優(yōu)化目標處理提供技術(shù)基礎。

2) 進一步研究更有效的集成方式，充分釋放二者的柔性，拓展制造系統(tǒng)整體的優(yōu)化空間。其主要方向可以為研究求解算法的個體編碼表達，以及數(shù)學模型層次間的耦合關系構(gòu)建。

3) 多目標優(yōu)化可存在于IPPS問題研究中的不同層面，協(xié)調(diào)工藝規(guī)劃子系統(tǒng)與車間調(diào)度子系統(tǒng)不同目標間的優(yōu)化，以達到制造系統(tǒng)多目標的整體優(yōu)化，是未來重要研究方向之一。

4) 考慮各分布式工廠的異構(gòu)工藝及生產(chǎn)條件，探索更符合分布式系統(tǒng)的特征的DIPPS求解方法，是促進未來分布式制造系統(tǒng)發(fā)展的重要手段。