桂 林，張春江，李新宇

(華中科技大學 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢430074)

制造業(yè)是國民經(jīng)濟的重要支柱，而優(yōu)化調(diào)度是整個制造系統(tǒng)的核心環(huán)節(jié)。調(diào)度的目的是在滿足一系列約束的前提下，通過對資源的合理分配，使得某些指標達到最優(yōu)[1]。學術(shù)界對于生產(chǎn)調(diào)度問題的研究，通常是在一系列假設的基礎上，如工藝流程簡單、加工路徑固定、工藝約束確定等。但實際的生產(chǎn)加工過程往往具有復雜且可變的工藝路線和工藝約束，加工機器也往往具有不同的功能，因此具有柔性的調(diào)度往往更加符合實際的生產(chǎn)特點?；?、建筑、電子、紡織等行業(yè)的加工、裝配和運輸環(huán)節(jié)都可視為柔性調(diào)度問題[2]。因此，對柔性車間調(diào)度問題的研究具有理論意義和實際應用價值。

柔性車間調(diào)度問題的柔性主要分為3個方面[3]：工藝路線柔性、機器選擇柔性和工序順序柔性。工藝路線柔性是指工件在加工的過程中，有某一個或若干個加工工藝可以替換為其他不同的加工工藝；機器選擇柔性是指在車間中有多臺加工機器可以滿足相同工藝的加工要求；工序順序柔性是指工件的若干加工工藝在滿足工藝約束的前提下仍可以具有不同的加工順序。本文主要對現(xiàn)有研究中3種具有工序順序柔性的車間調(diào)度問題(混合車間調(diào)度問題、分組車間調(diào)度問題和部分車間調(diào)度問題)的發(fā)展現(xiàn)狀、存在的問題及未來的發(fā)展方向進行綜述。

1定義和分類

在以往的研究中，研究人員通常將具有工序順序柔性的車間調(diào)度問題描述為作業(yè)車間調(diào)度問題(job shop scheduling problem,JSP)和開放車間調(diào)度問題(open shop scheduling problem,OSP)2種問題的融合。實質(zhì)上，這幾種問題的不同是由于需要調(diào)度的工件具有不同的先后加工約束的工藝性質(zhì)，因此有必要對不同性質(zhì)的工件進行定義和分類。具體定義如下，工件類型如圖1所示。

圖1工件類型表示Figure 1 Workpiece type representation

1)工藝順序完全確定性工件是指該工件任意2個加工工藝之間都有先后加工約束關(guān)系的工件，如圖1(a)所示。這種工件用JCD表示。2)工藝順序完全柔性工件是指該工件任意2個加工工藝之間都沒有先后加工約束關(guān)系，加工工序順序是任意的，如圖1(b)所示。這種工件用JCF表示。3)工藝順序非完全確定性工件是指該工件的所有工藝可以分為若干個組，在同一組內(nèi)，所有工藝之間不具有先后加工的工藝約束，但不同組之間具有先后加工的工藝約束，如圖1(c)所示。這種工件用JNCD表示。JNCD常見于加工、檢測一體化車間中，如PCB生產(chǎn)車間。4)工序順序非完全柔性工件是指該工件的所有工藝可以分為若干個組，在同一組內(nèi)，所有工藝之間具有先后加工的工藝約束，但不同組之間不具有先后加工的工藝約束，如圖1(d)所示。這種工件用JNCF表示。JNCF常見于模塊化生產(chǎn)的生產(chǎn)車間中，如裝配車間。5) 工序順序部分柔性工件指的是在工件的所有工藝中，其中一個或若干個工藝與其他一些工藝存在先后加工的工藝約束關(guān)系，而與另一些工藝之間不存在先后加工的工藝約束的工件，如圖1(e)所示。這種工件用JPF表示。具有工序順序部分柔性的工件常見于物品回收再利用工業(yè)中，如對回收物品的拆卸過程。

當有一組待加工工件分別為JCD、JCF、JNCD和JPF時，則對這一組工件進行加工調(diào)度的問題分別為JSP、OSP、GSP (group shop scheduling problem，分組車間調(diào)度問題)和PSP (partial shop scheduling problem，部分車間調(diào)度問題)。當有一組待加工工件都是由JCD和JCF混合組成時，則對這一組工件進行加工調(diào)度的問題為MSP(mixed shop scheduling problem，混合車間調(diào)度問題)。在現(xiàn)有研究中，暫時沒有關(guān)于工件由JNCF組成的車間調(diào)度問題的研究，本文暫時將這一類問題歸于GSP中，稱為GSP(II)。由上文對各種不同類型工件的描述不難發(fā)現(xiàn)，JCD和JCF分別是JNCD和JNCF的特殊情況，而JNCD和JNCF同時又是JPF的特殊情況。由此易知，JSP和OSP是MSP的特殊情況，MSP是GSP的特殊情況，GSP和GSP(II)是PSP的特殊情況，具體關(guān)系如圖2所示。

2混合車間調(diào)度

圖2工件之間的關(guān)系和問題之間的關(guān)系Figure 2 Relationship between artifacts and problems

1985年，Masuda等[4]首次提出了MSP的概念。當假設車間中只有2臺加工機器時，作者給出了一種精確算法。1987年，Ishii等[5]在上文工作的基礎上添加了當機器工作速度可控時的假設條件，并給出了多項式時間內(nèi)求解的算法。1999年，Shakhlevich等[6]考慮了具有m個加工機器和n個加工工件的MSP，證明了當m=3，n=3時，在工件的操作允許搶占的情況下，該問題為NP-hard 問題。2000 年，Shakhlevich等[7]對MSP的復雜度進行了總結(jié)。1998年Cheng等[8]對成批的MSP提出精確算法。2002年，Kis[9]探討了2個工件分別為JCD和JCF，且工件的操作為非搶占時的MSP 的復雜度。2009 年，Liu等[10]對考慮準備時間和拆卸時間的雙機MSP進行研究，并提出了一種近似算法。2010年，Cetinkaya等[11]探討了批量的雙機MSP，并提出了最優(yōu)求解方法。2015年，Koulamas等[12]研究了當加工機器為3時的MSP，并提出近似算法。2015年，Dugarzhapov等[13]對可搶占的雙機MSP提出一種新的多項式時間內(nèi)求解的精確算法。2018和2020年，Liu等[14-15]對加工機器數(shù)為3時的MSP進行了研究，當同一工件在不同機器上的加工時間相同時，提出了4/3的近似算法。對于MSP，學者們大多從問題本身出發(fā)，對加工機器數(shù)較少或加工工件數(shù)為定值的問題進行研究，探索了MSP可用多項式進行求解的問題邊界。

由于問題本身實際意義的限制，現(xiàn)有研究中很少有對大規(guī)模的MSP進行求解。1994年，Shakhlevich等[16]考慮了2個工件在m臺機器上加工的車間調(diào)度問題，2個工件分別為JCD和JCF。研究結(jié)果表明，當目標函數(shù)為最小化最大完工時間或平均流經(jīng)時間，且不允許工件操作之間的搶占時，該問題為NPhard問題，并提出元啟發(fā)式求解方法。2000年Ferrell等[17]將一些常見的啟發(fā)式規(guī)則應用于MSP，如先進先出、最短加工時間、非遞減松弛和修正松弛法等。2012年，Liu等[18]針對MSP提出一種鄰域結(jié)構(gòu)，并使用3種元啟發(fā)式法對問題進行求解。2016年，Nguyen等[19]使用元啟發(fā)式法求解了MSP。2018年，F(xiàn)an等[20]對不同的混合車間類型進行了分類。

對MSP的總結(jié)如表1所示。其中，m為加工機器數(shù)，n(j)為工序順序完全確定性工件數(shù)，n(o)為工序順序完全柔性工件數(shù)，m1、n1、n2分別為任意的加工機器數(shù)和工件數(shù)，k和L為一個確定的數(shù)值，r為所有工件中最大的加工工藝數(shù)。

3分組車間調(diào)度

GSP是在1997年的一個數(shù)學競賽中被提出來的。當時的名稱為FOPSS(first order parallel shop scheduling)[21]。

1998年之后，Blum等[22-24]對目標函數(shù)為最小化最大完工時間的GSP進行求解，定義了關(guān)鍵路徑上的領(lǐng)域結(jié)構(gòu)，并使用蟻群優(yōu)化算法求解GSP。2002年，Sampels等[25]使用多種元啟發(fā)式算法如蟻群算法、模擬退火算法、禁忌搜索算法等求解GSP。2005年，Liu等[26]對GSP定義了2種鄰域結(jié)構(gòu)，用禁忌搜索算法解決了GSP問題，最后又在算法中嵌入模擬退火算法以避免陷入局部最優(yōu)。此后，Ahmadizar等[27-31]分別在2008年、2010年、2013年、2014年和2017年發(fā)表了與GSP相關(guān)的研究文章。其中，文獻[27-29]研究了工件釋放時間和工件加工時間不確定的隨機GSP問題；文獻[30]研究了帶有序列相關(guān)準備時間和運輸時間的GSP問題；文獻[31]研究了帶有隨機工件釋放時間、隨機工件加工時間和模糊交貨期的GSP問題。2018年，Kemmoe-Tchomte等[32]研究了目標函數(shù)為最小化最大完工時間的GSP，并用多次重啟多級進化局部搜索算法求解。

在現(xiàn)有文獻中，階段車間調(diào)度問題(stage shop scheduling problem,SSP)與GSP具有相同的約束，因此這是同一問題的2個名稱。1997年，Strusevich[33]研究了工件之間帶有約束的SSP。2002年，Strusevich等[34]研究了加工機器數(shù)為3的SSP，并給出近似多項式算法。2003年，Kis[35]研究了工藝路線可變的SSP。2005年，Su等[36]研究了一種特殊的SSP，將工件的所有加工工藝分為2個部分，前一部分的加工工藝都具有先后加工的工藝約束，后一部分的加工工藝都不具有先后加工的工藝約束。2011年，Nasiri等[37]對目標函數(shù)為最小化最大完工時間的SSP建立了混合整數(shù)規(guī)劃模型，并用禁忌搜索算法和遺傳算法對問題進行求解。2013年，Dong等[38]對工件的前2個加工工藝沒有先后加工約束，其他加工工藝具有先后加工約束的問題進行研究，并證明該問題為NP-hard問題。2015年，Nasiri等[39]使用蟻群算法對目標函數(shù)為完工時間的SSP進行求解。2019年，Mayer等[40]根據(jù)生產(chǎn)實例提出了帶有并行機的SSP，并使用遺傳算法對問題進行求解。

表1 MSP總結(jié)Table 1 Summary of MSP

對GSP的總結(jié)如表2所示。

4部分車間調(diào)度

在已有研究中，對于部分車間調(diào)度問題的研究可以歸納為2種類型。一種是從工藝規(guī)劃角度對單一工件的工序順序排序；另一種是從工藝規(guī)劃與調(diào)度集成的角度對多個待加工工件的工序順序排序。本文主要對后一種問題進行討論和研究。

對于PSP的研究，大多數(shù)文獻基于一個具體的生產(chǎn)實際展開。2002年，Gan等[41]對模具制造車間的工序順序安排問題進行研究。2000年，Beach等[42]對具有柔性的車間調(diào)度進行綜述，其中提及工序順序柔性是柔性車間調(diào)度的一種重要形式。2005年，Ding等[43]提出了一種將遺傳算法、神經(jīng)網(wǎng)絡和層次分析法相結(jié)合的混合算法，以求解具有多目標的PSP。2008年，Adenso-Díaz等[44]對具有雙目標的拆卸車間的PSP進行研究。2011年，Nasiri等[45]對PSP建立了混合整數(shù)規(guī)劃模型，并采用離散搜索和禁忌搜索相結(jié)合的方法求解該問題。2012年，Go等[46]提出了一種基于遺傳算法解決汽車零部件拆卸序列優(yōu)化模型；Zhu等[47]討論了基于產(chǎn)品多樣性所引起的復雜混合裝配線最優(yōu)序列的選擇問題。2013年，黃學文等[48]總結(jié)了該問題中柔性工序順序的類型和特點。2014年，Bentaha等[49]對工件拆卸時間為已知概率分布的隨機變量的PSP進行研究；Quibell等[50]對加工機器數(shù)為3的PSP進行了研究，并提出了2種近似算法。2016年，黃學文等[51]提出一種工序順序柔性描述方法和工件工序順序的生成方法。2018年，Zubaran等[52]提出很多符合PSP的應用實例。

表2 GSP總結(jié)Table 2 Summary of GSP

最后為加深對PSP了解，這里例舉文獻[48]中某型號軸承的加工實例。該型號軸承的加工需要11道工序，其工序約束如圖3所示，工序名稱及約束情況如表3所示。箭頭始端要先于箭頭終端進行加工，如工序1要先于工序2加工，工序3要先于工序5和工序6加工，工序4要先于工序5和工序6加工。而工序3和工序4之間沒有工序約束，可以先加工工序3，也可以先加工工序4。

5總結(jié)和展望

本文主要討論了具有工序順序柔性的車間調(diào)度問題。通過對工件類型的分類，本文更加清楚地描述了各種不同的車間類型。之后對研究具有工序順序柔性的車間調(diào)度問題的現(xiàn)有文獻進行分類和整理。由文獻分析可知，對具有工序順序柔性的車間調(diào)度問題的研究從20世紀80年代開始，研究大體上可以分為3種不同的問題：MSP、GSP和PSP。

圖3某型號軸承加工工序約束圖Figure 3 A certain type of bearing processing technology constraint diagram

表3某型號軸承加工工序約束表Table 3 A certain type of bearing processing technology constraint table

對于MSP的研究大多關(guān)注問題本身。學者們對具有不同加工數(shù)量的機器、工件和不同約束條件的問題的復雜度進行了詳細研究，并探索了可用多項式求出最優(yōu)解的問題邊界：當加工機器數(shù)為2，或當加工機器數(shù)和加工工件數(shù)為定值，且工件在加工時可搶占，可重入時，該問題可用多項式算法求解；在其他情況下，只能用近似算法對問題進行求解。

相比于MSP，很少有研究人員對于GSP本身進行研究，大多數(shù)研究集中于使用不同的啟發(fā)式算法對具有不同約束條件、不同目標函數(shù)的問題進行求解。由于GSP與JSP在一定程度上的相似性，用于求解GSP的元啟發(fā)式算法大都由解決JSP的元啟發(fā)式算法改進而來。但GSP中含有“組”的特性，因此，在編碼設計時大多用兩階段編碼。

對于PSP的研究，本文主要從工藝規(guī)劃與調(diào)度集成的角度對該問題進行分析。現(xiàn)有的研究大多基于一個實際的生產(chǎn)案例進行研究，提出了適用于該具體案例的解決方法。但很少有研究人員對實際問題進行抽象，因此PSP缺少對問題本身的研究和適用于通用問題的算法。

為了以后能夠更好地開展具有工序順序柔性的車間調(diào)度問題的研究，以下從4個層面提出現(xiàn)有研究中存在的不足和今后研究的發(fā)展方向。

1)問題層面。雖然現(xiàn)有的研究對于MSP和GSP都具有明確的定義，但從生產(chǎn)實際出發(fā)，現(xiàn)有的研究對問題挖掘不夠充分。在現(xiàn)有研究中，MSP只包含JCD和JCF這2類工件。但在生產(chǎn)實際中，很少存在只具有這2 種類型的工件的加工車間。因此在MSP的研究中，需要在前2種類型工件的基礎上，添加其他類型的工件，如JNCD、JNCF等，使問題更加貼合生產(chǎn)實際。對于GSP而言，需要根據(jù)問題獨有的特性，挖掘出更多的有利于問題求解的知識，如基于問題特性的鄰域等。此外，盡管GSP(II)類型的加工車間具有很大的實際應用價值，但到目前幾乎沒有對該問題的研究，因此在后面的研究中可以加大對該問題的投入。

2)模型層面。相對于其他類型的車間調(diào)度問題，具有工序順序柔性的車間調(diào)度的研究較少。其主要原因是到現(xiàn)在為止，沒有出現(xiàn)能夠有利于問題求解的模型，使得將問題輸入到計算機求解時不具有完備性或簡潔性。雖然對各類問題，都有精確表達的混合整數(shù)規(guī)劃模型，但該模型在問題求解上并不具有優(yōu)勢。因此需要建立具有問題特性并利于問題求解的模型。

3)約束層面。在以后的研究中，需要在其基礎上添加其他的約束條件使得問題進一步貼近生產(chǎn)實際。比如考慮工件運輸時間、準備時間、動態(tài)生產(chǎn)和多目標等。在添加一系列的約束后，不能僅改變問題求解的目標函數(shù)，而需要考慮添加的約束對于問題本身的影響，并在此基礎上開發(fā)針對該問題和約束的有效搜索機制。

4)算法層面。大多數(shù)研究人員使用解決其他車間問題的策略和元啟發(fā)式算法對具有工序順序柔性的車間調(diào)度問題進行求解，使用的編碼方式大多是兩階段編碼等，這使得在問題求解時會出現(xiàn)結(jié)果質(zhì)量不高，求解速度較慢等缺陷。因此在今后的研究中，需要在對問題進行深入分析的基礎上，設計基于問題特性的編解碼方式、鄰域結(jié)構(gòu)、求解策略等。