集成式工藝規(guī)劃與車間調(diào)度的研究綜述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 IPPS問(wèn)題概述

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

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

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

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

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

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

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

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

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

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

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

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

工藝規(guī)劃屬于NP-Complete問(wèn)題[19]，僅僅利用傳統(tǒng)的梯度下降法、圖論法和仿真方法很難得到令人滿意的優(yōu)化結(jié)果[20]。因此，國(guó)內(nèi)外眾多研究學(xué)者選擇通過(guò)智能算法來(lái)求解工藝規(guī)劃問(wèn)題，其方法主要包括多代理系統(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ī)劃問(wèn)題的求解中展現(xiàn)了一定的優(yōu)越性，并在實(shí)際案例的應(yīng)用中取得一定成效。

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

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

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

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

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

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

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

3 多目標(biāo)IPPS問(wèn)題的研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

針對(duì)上述現(xiàn)狀，IPPS未來(lái)工作可聚焦在以下幾點(diǎn)。

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

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

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

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