桂 林,張春江,李新宇
(華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,湖北 武漢430074)
制造業(yè)是國(guó)民經(jīng)濟(jì)的重要支柱,而優(yōu)化調(diào)度是整個(gè)制造系統(tǒng)的核心環(huán)節(jié)。調(diào)度的目的是在滿足一系列約束的前提下,通過(guò)對(duì)資源的合理分配,使得某些指標(biāo)達(dá)到最優(yōu)[1]。學(xué)術(shù)界對(duì)于生產(chǎn)調(diào)度問(wèn)題的研究,通常是在一系列假設(shè)的基礎(chǔ)上,如工藝流程簡(jiǎn)單、加工路徑固定、工藝約束確定等。但實(shí)際的生產(chǎn)加工過(guò)程往往具有復(fù)雜且可變的工藝路線和工藝約束,加工機(jī)器也往往具有不同的功能,因此具有柔性的調(diào)度往往更加符合實(shí)際的生產(chǎn)特點(diǎn)?;?、建筑、電子、紡織等行業(yè)的加工、裝配和運(yùn)輸環(huán)節(jié)都可視為柔性調(diào)度問(wèn)題[2]。因此,對(duì)柔性車間調(diào)度問(wèn)題的研究具有理論意義和實(shí)際應(yīng)用價(jià)值。
柔性車間調(diào)度問(wèn)題的柔性主要分為3個(gè)方面[3]:工藝路線柔性、機(jī)器選擇柔性和工序順序柔性。工藝路線柔性是指工件在加工的過(guò)程中,有某一個(gè)或若干個(gè)加工工藝可以替換為其他不同的加工工藝;機(jī)器選擇柔性是指在車間中有多臺(tái)加工機(jī)器可以滿足相同工藝的加工要求;工序順序柔性是指工件的若干加工工藝在滿足工藝約束的前提下仍可以具有不同的加工順序。本文主要對(duì)現(xiàn)有研究中3種具有工序順序柔性的車間調(diào)度問(wèn)題(混合車間調(diào)度問(wèn)題、分組車間調(diào)度問(wèn)題和部分車間調(diào)度問(wèn)題)的發(fā)展現(xiàn)狀、存在的問(wèn)題及未來(lái)的發(fā)展方向進(jìn)行綜述。
在以往的研究中,研究人員通常將具有工序順序柔性的車間調(diào)度問(wèn)題描述為作業(yè)車間調(diào)度問(wèn)題(job shop scheduling problem,JSP)和開放車間調(diào)度問(wèn)題(open shop scheduling problem,OSP)2種問(wèn)題的融合。實(shí)質(zhì)上,這幾種問(wèn)題的不同是由于需要調(diào)度的工件具有不同的先后加工約束的工藝性質(zhì),因此有必要對(duì)不同性質(zhì)的工件進(jìn)行定義和分類。具體定義如下,工件類型如圖1所示。
圖1工件類型表示Figure 1 Workpiece type representation
1)工藝順序完全確定性工件是指該工件任意2個(gè)加工工藝之間都有先后加工約束關(guān)系的工件,如圖1(a)所示。這種工件用JCD表示。2)工藝順序完全柔性工件是指該工件任意2個(gè)加工工藝之間都沒有先后加工約束關(guān)系,加工工序順序是任意的,如圖1(b)所示。這種工件用JCF表示。3)工藝順序非完全確定性工件是指該工件的所有工藝可以分為若干個(gè)組,在同一組內(nèi),所有工藝之間不具有先后加工的工藝約束,但不同組之間具有先后加工的工藝約束,如圖1(c)所示。這種工件用JNCD表示。JNCD常見于加工、檢測(cè)一體化車間中,如PCB生產(chǎn)車間。4)工序順序非完全柔性工件是指該工件的所有工藝可以分為若干個(gè)組,在同一組內(nèi),所有工藝之間具有先后加工的工藝約束,但不同組之間不具有先后加工的工藝約束,如圖1(d)所示。這種工件用JNCF表示。JNCF常見于模塊化生產(chǎn)的生產(chǎn)車間中,如裝配車間。5) 工序順序部分柔性工件指的是在工件的所有工藝中,其中一個(gè)或若干個(gè)工藝與其他一些工藝存在先后加工的工藝約束關(guān)系,而與另一些工藝之間不存在先后加工的工藝約束的工件,如圖1(e)所示。這種工件用JPF表示。具有工序順序部分柔性的工件常見于物品回收再利用工業(yè)中,如對(duì)回收物品的拆卸過(guò)程。
當(dāng)有一組待加工工件分別為JCD、JCF、JNCD和JPF時(shí),則對(duì)這一組工件進(jìn)行加工調(diào)度的問(wèn)題分別為JSP、OSP、GSP (group shop scheduling problem,分組車間調(diào)度問(wèn)題)和PSP (partial shop scheduling problem,部分車間調(diào)度問(wèn)題)。當(dāng)有一組待加工工件都是由JCD和JCF混合組成時(shí),則對(duì)這一組工件進(jìn)行加工調(diào)度的問(wèn)題為MSP(mixed shop scheduling problem,混合車間調(diào)度問(wèn)題)。在現(xiàn)有研究中,暫時(shí)沒有關(guān)于工件由JNCF組成的車間調(diào)度問(wèn)題的研究,本文暫時(shí)將這一類問(wèn)題歸于GSP中,稱為GSP(II)。由上文對(duì)各種不同類型工件的描述不難發(fā)現(xiàn),JCD和JCF分別是JNCD和JNCF的特殊情況,而JNCD和JNCF同時(shí)又是JPF的特殊情況。由此易知,JSP和OSP是MSP的特殊情況,MSP是GSP的特殊情況,GSP和GSP(II)是PSP的特殊情況,具體關(guān)系如圖2所示。
圖2工件之間的關(guān)系和問(wèn)題之間的關(guān)系Figure 2 Relationship between artifacts and problems
1985年,Masuda等[4]首次提出了MSP的概念。當(dāng)假設(shè)車間中只有2臺(tái)加工機(jī)器時(shí),作者給出了一種精確算法。1987年,Ishii等[5]在上文工作的基礎(chǔ)上添加了當(dāng)機(jī)器工作速度可控時(shí)的假設(shè)條件,并給出了多項(xiàng)式時(shí)間內(nèi)求解的算法。1999年,Shakhlevich等[6]考慮了具有m個(gè)加工機(jī)器和n個(gè)加工工件的MSP,證明了當(dāng)m=3,n=3時(shí),在工件的操作允許搶占的情況下,該問(wèn)題為NP-hard 問(wèn)題。2000 年,Shakhlevich等[7]對(duì)MSP的復(fù)雜度進(jìn)行了總結(jié)。1998年Cheng等[8]對(duì)成批的MSP提出精確算法。2002年,Kis[9]探討了2個(gè)工件分別為JCD和JCF,且工件的操作為非搶占時(shí)的MSP 的復(fù)雜度。2009 年,Liu等[10]對(duì)考慮準(zhǔn)備時(shí)間和拆卸時(shí)間的雙機(jī)MSP進(jìn)行研究,并提出了一種近似算法。2010年,Cetinkaya等[11]探討了批量的雙機(jī)MSP,并提出了最優(yōu)求解方法。2015年,Koulamas等[12]研究了當(dāng)加工機(jī)器為3時(shí)的MSP,并提出近似算法。2015年,Dugarzhapov等[13]對(duì)可搶占的雙機(jī)MSP提出一種新的多項(xiàng)式時(shí)間內(nèi)求解的精確算法。2018和2020年,Liu等[14-15]對(duì)加工機(jī)器數(shù)為3時(shí)的MSP進(jìn)行了研究,當(dāng)同一工件在不同機(jī)器上的加工時(shí)間相同時(shí),提出了4/3的近似算法。對(duì)于MSP,學(xué)者們大多從問(wèn)題本身出發(fā),對(duì)加工機(jī)器數(shù)較少或加工工件數(shù)為定值的問(wèn)題進(jìn)行研究,探索了MSP可用多項(xiàng)式進(jìn)行求解的問(wèn)題邊界。
由于問(wèn)題本身實(shí)際意義的限制,現(xiàn)有研究中很少有對(duì)大規(guī)模的MSP進(jìn)行求解。1994年,Shakhlevich等[16]考慮了2個(gè)工件在m臺(tái)機(jī)器上加工的車間調(diào)度問(wèn)題,2個(gè)工件分別為JCD和JCF。研究結(jié)果表明,當(dāng)目標(biāo)函數(shù)為最小化最大完工時(shí)間或平均流經(jīng)時(shí)間,且不允許工件操作之間的搶占時(shí),該問(wèn)題為NPhard問(wèn)題,并提出元啟發(fā)式求解方法。2000年Ferrell等[17]將一些常見的啟發(fā)式規(guī)則應(yīng)用于MSP,如先進(jìn)先出、最短加工時(shí)間、非遞減松弛和修正松弛法等。2012年,Liu等[18]針對(duì)MSP提出一種鄰域結(jié)構(gòu),并使用3種元啟發(fā)式法對(duì)問(wèn)題進(jìn)行求解。2016年,Nguyen等[19]使用元啟發(fā)式法求解了MSP。2018年,F(xiàn)an等[20]對(duì)不同的混合車間類型進(jìn)行了分類。
對(duì)MSP的總結(jié)如表1所示。其中,m為加工機(jī)器數(shù),n(j)為工序順序完全確定性工件數(shù),n(o)為工序順序完全柔性工件數(shù),m1、n1、n2分別為任意的加工機(jī)器數(shù)和工件數(shù),k和L為一個(gè)確定的數(shù)值,r為所有工件中最大的加工工藝數(shù)。
GSP是在1997年的一個(gè)數(shù)學(xué)競(jìng)賽中被提出來(lái)的。當(dāng)時(shí)的名稱為FOPSS(first order parallel shop scheduling)[21]。
1998年之后,Blum等[22-24]對(duì)目標(biāo)函數(shù)為最小化最大完工時(shí)間的GSP進(jìn)行求解,定義了關(guān)鍵路徑上的領(lǐng)域結(jié)構(gòu),并使用蟻群優(yōu)化算法求解GSP。2002年,Sampels等[25]使用多種元啟發(fā)式算法如蟻群算法、模擬退火算法、禁忌搜索算法等求解GSP。2005年,Liu等[26]對(duì)GSP定義了2種鄰域結(jié)構(gòu),用禁忌搜索算法解決了GSP問(wèn)題,最后又在算法中嵌入模擬退火算法以避免陷入局部最優(yōu)。此后,Ahmadizar等[27-31]分別在2008年、2010年、2013年、2014年和2017年發(fā)表了與GSP相關(guān)的研究文章。其中,文獻(xiàn)[27-29]研究了工件釋放時(shí)間和工件加工時(shí)間不確定的隨機(jī)GSP問(wèn)題;文獻(xiàn)[30]研究了帶有序列相關(guān)準(zhǔn)備時(shí)間和運(yùn)輸時(shí)間的GSP問(wèn)題;文獻(xiàn)[31]研究了帶有隨機(jī)工件釋放時(shí)間、隨機(jī)工件加工時(shí)間和模糊交貨期的GSP問(wèn)題。2018年,Kemmoe-Tchomte等[32]研究了目標(biāo)函數(shù)為最小化最大完工時(shí)間的GSP,并用多次重啟多級(jí)進(jìn)化局部搜索算法求解。
在現(xiàn)有文獻(xiàn)中,階段車間調(diào)度問(wèn)題(stage shop scheduling problem,SSP)與GSP具有相同的約束,因此這是同一問(wèn)題的2個(gè)名稱。1997年,Strusevich[33]研究了工件之間帶有約束的SSP。2002年,Strusevich等[34]研究了加工機(jī)器數(shù)為3的SSP,并給出近似多項(xiàng)式算法。2003年,Kis[35]研究了工藝路線可變的SSP。2005年,Su等[36]研究了一種特殊的SSP,將工件的所有加工工藝分為2個(gè)部分,前一部分的加工工藝都具有先后加工的工藝約束,后一部分的加工工藝都不具有先后加工的工藝約束。2011年,Nasiri等[37]對(duì)目標(biāo)函數(shù)為最小化最大完工時(shí)間的SSP建立了混合整數(shù)規(guī)劃模型,并用禁忌搜索算法和遺傳算法對(duì)問(wèn)題進(jìn)行求解。2013年,Dong等[38]對(duì)工件的前2個(gè)加工工藝沒有先后加工約束,其他加工工藝具有先后加工約束的問(wèn)題進(jìn)行研究,并證明該問(wèn)題為NP-hard問(wèn)題。2015年,Nasiri等[39]使用蟻群算法對(duì)目標(biāo)函數(shù)為完工時(shí)間的SSP進(jìn)行求解。2019年,Mayer等[40]根據(jù)生產(chǎn)實(shí)例提出了帶有并行機(jī)的SSP,并使用遺傳算法對(duì)問(wèn)題進(jìn)行求解。
表1 MSP總結(jié)Table 1 Summary of MSP
對(duì)GSP的總結(jié)如表2所示。
在已有研究中,對(duì)于部分車間調(diào)度問(wèn)題的研究可以歸納為2種類型。一種是從工藝規(guī)劃角度對(duì)單一工件的工序順序排序;另一種是從工藝規(guī)劃與調(diào)度集成的角度對(duì)多個(gè)待加工工件的工序順序排序。本文主要對(duì)后一種問(wèn)題進(jìn)行討論和研究。
對(duì)于PSP的研究,大多數(shù)文獻(xiàn)基于一個(gè)具體的生產(chǎn)實(shí)際展開。2002年,Gan等[41]對(duì)模具制造車間的工序順序安排問(wèn)題進(jìn)行研究。2000年,Beach等[42]對(duì)具有柔性的車間調(diào)度進(jìn)行綜述,其中提及工序順序柔性是柔性車間調(diào)度的一種重要形式。2005年,Ding等[43]提出了一種將遺傳算法、神經(jīng)網(wǎng)絡(luò)和層次分析法相結(jié)合的混合算法,以求解具有多目標(biāo)的PSP。2008年,Adenso-Díaz等[44]對(duì)具有雙目標(biāo)的拆卸車間的PSP進(jìn)行研究。2011年,Nasiri等[45]對(duì)PSP建立了混合整數(shù)規(guī)劃模型,并采用離散搜索和禁忌搜索相結(jié)合的方法求解該問(wèn)題。2012年,Go等[46]提出了一種基于遺傳算法解決汽車零部件拆卸序列優(yōu)化模型;Zhu等[47]討論了基于產(chǎn)品多樣性所引起的復(fù)雜混合裝配線最優(yōu)序列的選擇問(wèn)題。2013年,黃學(xué)文等[48]總結(jié)了該問(wèn)題中柔性工序順序的類型和特點(diǎn)。2014年,Bentaha等[49]對(duì)工件拆卸時(shí)間為已知概率分布的隨機(jī)變量的PSP進(jìn)行研究;Quibell等[50]對(duì)加工機(jī)器數(shù)為3的PSP進(jìn)行了研究,并提出了2種近似算法。2016年,黃學(xué)文等[51]提出一種工序順序柔性描述方法和工件工序順序的生成方法。2018年,Zubaran等[52]提出很多符合PSP的應(yīng)用實(shí)例。
表2 GSP總結(jié)Table 2 Summary of GSP
最后為加深對(duì)PSP了解,這里例舉文獻(xiàn)[48]中某型號(hào)軸承的加工實(shí)例。該型號(hào)軸承的加工需要11道工序,其工序約束如圖3所示,工序名稱及約束情況如表3所示。箭頭始端要先于箭頭終端進(jìn)行加工,如工序1要先于工序2加工,工序3要先于工序5和工序6加工,工序4要先于工序5和工序6加工。而工序3和工序4之間沒有工序約束,可以先加工工序3,也可以先加工工序4。
本文主要討論了具有工序順序柔性的車間調(diào)度問(wèn)題。通過(guò)對(duì)工件類型的分類,本文更加清楚地描述了各種不同的車間類型。之后對(duì)研究具有工序順序柔性的車間調(diào)度問(wèn)題的現(xiàn)有文獻(xiàn)進(jìn)行分類和整理。由文獻(xiàn)分析可知,對(duì)具有工序順序柔性的車間調(diào)度問(wèn)題的研究從20世紀(jì)80年代開始,研究大體上可以分為3種不同的問(wèn)題:MSP、GSP和PSP。
圖3某型號(hào)軸承加工工序約束圖Figure 3 A certain type of bearing processing technology constraint diagram
表3某型號(hào)軸承加工工序約束表Table 3 A certain type of bearing processing technology constraint table
對(duì)于MSP的研究大多關(guān)注問(wèn)題本身。學(xué)者們對(duì)具有不同加工數(shù)量的機(jī)器、工件和不同約束條件的問(wèn)題的復(fù)雜度進(jìn)行了詳細(xì)研究,并探索了可用多項(xiàng)式求出最優(yōu)解的問(wèn)題邊界:當(dāng)加工機(jī)器數(shù)為2,或當(dāng)加工機(jī)器數(shù)和加工工件數(shù)為定值,且工件在加工時(shí)可搶占,可重入時(shí),該問(wèn)題可用多項(xiàng)式算法求解;在其他情況下,只能用近似算法對(duì)問(wèn)題進(jìn)行求解。
相比于MSP,很少有研究人員對(duì)于GSP本身進(jìn)行研究,大多數(shù)研究集中于使用不同的啟發(fā)式算法對(duì)具有不同約束條件、不同目標(biāo)函數(shù)的問(wèn)題進(jìn)行求解。由于GSP與JSP在一定程度上的相似性,用于求解GSP的元啟發(fā)式算法大都由解決JSP的元啟發(fā)式算法改進(jìn)而來(lái)。但GSP中含有“組”的特性,因此,在編碼設(shè)計(jì)時(shí)大多用兩階段編碼。
對(duì)于PSP的研究,本文主要從工藝規(guī)劃與調(diào)度集成的角度對(duì)該問(wèn)題進(jìn)行分析?,F(xiàn)有的研究大多基于一個(gè)實(shí)際的生產(chǎn)案例進(jìn)行研究,提出了適用于該具體案例的解決方法。但很少有研究人員對(duì)實(shí)際問(wèn)題進(jìn)行抽象,因此PSP缺少對(duì)問(wèn)題本身的研究和適用于通用問(wèn)題的算法。
為了以后能夠更好地開展具有工序順序柔性的車間調(diào)度問(wèn)題的研究,以下從4個(gè)層面提出現(xiàn)有研究中存在的不足和今后研究的發(fā)展方向。
1)問(wèn)題層面。雖然現(xiàn)有的研究對(duì)于MSP和GSP都具有明確的定義,但從生產(chǎn)實(shí)際出發(fā),現(xiàn)有的研究對(duì)問(wèn)題挖掘不夠充分。在現(xiàn)有研究中,MSP只包含JCD和JCF這2類工件。但在生產(chǎn)實(shí)際中,很少存在只具有這2 種類型的工件的加工車間。因此在MSP的研究中,需要在前2種類型工件的基礎(chǔ)上,添加其他類型的工件,如JNCD、JNCF等,使問(wèn)題更加貼合生產(chǎn)實(shí)際。對(duì)于GSP而言,需要根據(jù)問(wèn)題獨(dú)有的特性,挖掘出更多的有利于問(wèn)題求解的知識(shí),如基于問(wèn)題特性的鄰域等。此外,盡管GSP(II)類型的加工車間具有很大的實(shí)際應(yīng)用價(jià)值,但到目前幾乎沒有對(duì)該問(wèn)題的研究,因此在后面的研究中可以加大對(duì)該問(wèn)題的投入。
2)模型層面。相對(duì)于其他類型的車間調(diào)度問(wèn)題,具有工序順序柔性的車間調(diào)度的研究較少。其主要原因是到現(xiàn)在為止,沒有出現(xiàn)能夠有利于問(wèn)題求解的模型,使得將問(wèn)題輸入到計(jì)算機(jī)求解時(shí)不具有完備性或簡(jiǎn)潔性。雖然對(duì)各類問(wèn)題,都有精確表達(dá)的混合整數(shù)規(guī)劃模型,但該模型在問(wèn)題求解上并不具有優(yōu)勢(shì)。因此需要建立具有問(wèn)題特性并利于問(wèn)題求解的模型。
3)約束層面。在以后的研究中,需要在其基礎(chǔ)上添加其他的約束條件使得問(wèn)題進(jìn)一步貼近生產(chǎn)實(shí)際。比如考慮工件運(yùn)輸時(shí)間、準(zhǔn)備時(shí)間、動(dòng)態(tài)生產(chǎn)和多目標(biāo)等。在添加一系列的約束后,不能僅改變問(wèn)題求解的目標(biāo)函數(shù),而需要考慮添加的約束對(duì)于問(wèn)題本身的影響,并在此基礎(chǔ)上開發(fā)針對(duì)該問(wèn)題和約束的有效搜索機(jī)制。
4)算法層面。大多數(shù)研究人員使用解決其他車間問(wèn)題的策略和元啟發(fā)式算法對(duì)具有工序順序柔性的車間調(diào)度問(wèn)題進(jìn)行求解,使用的編碼方式大多是兩階段編碼等,這使得在問(wèn)題求解時(shí)會(huì)出現(xiàn)結(jié)果質(zhì)量不高,求解速度較慢等缺陷。因此在今后的研究中,需要在對(duì)問(wèn)題進(jìn)行深入分析的基礎(chǔ)上,設(shè)計(jì)基于問(wèn)題特性的編解碼方式、鄰域結(jié)構(gòu)、求解策略等。