王建軍，侯曉文，劉曉盼，繆鴻儒

具有安裝時間的置換流水車間組合干擾管理研究

王建軍，侯曉文，劉曉盼，繆鴻儒

（大連理工大學(xué) 經(jīng)濟管理學(xué)院，遼寧 大連 116023）

針對安裝時間與次序相關(guān)的置換流水車間環(huán)境，研究隨機機器故障、加工時間改變、安裝時間改變、工件優(yōu)先級提高、新工件到達、工件取消加工六類常見干擾事件部分或者全部組合發(fā)生情況下，考慮初始目標最大完工時間和擾動目標次序變動總量的干擾管理問題。經(jīng)分析，該問題為NP難問題。通過改進初始種群構(gòu)建策略以及全局搜索和局部搜索間權(quán)衡策略，提出改進文化基因算法對該問題進行求解。最后設(shè)計隨機干擾算例，分別在初始種群改進前后同經(jīng)典的NSGA-II算法進行對比，結(jié)果驗證了本文所提初始種群構(gòu)建策略和改進文化基因算法在應(yīng)對不同組合干擾事件和不同問題規(guī)模下的有效性。

干擾管理；組合干擾；安裝時間；文化基因算法；有效前沿

0 引言

流水車間調(diào)度問題（Flow shop Scheduling）作為實際生產(chǎn)加工環(huán)境可廣泛抽象化的模型，在冶金、食品加工和手術(shù)排程等制造、服務(wù)領(lǐng)域有著較為普遍的應(yīng)用[1]。絕大多數(shù)情況下屬于NP-難問題，求解較為困難；再加之具有較強的實際應(yīng)用背景而備受學(xué)者們青睞，雖然目前已取得較為豐碩的理論研究成果[2]。但大部分理論成果卻很難運用到生產(chǎn)實踐，其中一個重要的原因是：大部分流水車間調(diào)度研究往往忽略了在實際生產(chǎn)過程中面臨的諸多不確定性因素，如機器故障、訂單變更等干擾事件，這些干擾事件常常造成初始調(diào)度方案執(zhí)行不暢、效率低下、甚至不再可行[3]。近年來，流水車間干擾管理問題已引起學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注度[3-17]。

近幾年來，已有部分研究者考慮在流水車間環(huán)境下進行基于單一干擾事件的研究。如李鐵克等[4]針對生產(chǎn)過程中可能會出現(xiàn)的機器故障干擾事件，通過一致性權(quán)重來量化工件間對時間安排一致性和機器指派一致性要求的差異，并設(shè)計局部性修復(fù)算法求解有效的生產(chǎn)調(diào)度干擾管理方案。Wang等[5]研究了機器故障后的最大完工時間最小化問題，通過將原問題分解為多個簡單集群排序問題來獲得有效解。與前者目標一致，Wang等[6]提出基于模糊邏輯的混合分布估計算法（FL-HEDA）對問題進行求解。針對新工件到達干擾事件，Weng等[7]研究了新到達工件的JIT(Just In Time)生產(chǎn)問題，設(shè)計基于分布計算的路徑選擇策略，并與指派規(guī)則結(jié)合使問題得到了有效的求解。王建軍等[1]則考慮了人的“有限理性”行為，提出基于前景理論的綜合擾動度量，并設(shè)計了具有一般通用性的元啟發(fā)式算法混合策略對問題進行求解。此外部分學(xué)者還對產(chǎn)品返工、緊急訂單等干擾事件進行了研究，但相對較少。Rabiee等[8]針對無等待的兩臺機器流水車間中出現(xiàn)返工時的最小化平均完工時間問題；提出稱為適應(yīng)性帝國競爭算法的元啟發(fā)式算法進行求解。Hu等[9]針對緊急訂單到達后的加權(quán)平均流程時間最小化問題，考慮到緊急訂單的加工優(yōu)先級較高從而賦予更大的權(quán)重，并設(shè)計蟻群算法對問題進行有效求解。

然而現(xiàn)實加工過程中單一干擾事件發(fā)生的情形較少，通常是多種干擾事件組合發(fā)生，該情況的處理相對于單一干擾事件更為復(fù)雜[11]，并且在這種情況下有可能對當前的調(diào)度方案產(chǎn)生更大的影響，因此有研究者提出：如何應(yīng)對組合干擾事件至關(guān)重要[10]。Katragjini等[10]研究了新工件達到、機器故障、加工時間可變?nèi)N干擾事件同時發(fā)生情況下的干擾管理問題，并提出有效的重調(diào)度方法來權(quán)衡調(diào)度的性能和穩(wěn)定性。相較于前者，Li等[12]增加了工件取消加工和工件就緒時間可變干擾事件，并提出了基于教與學(xué)的離散優(yōu)化算法對問題進行了有效求解。與上述文獻中的應(yīng)對方式不同，Rahmani等[13]提出預(yù)測-反應(yīng)式策略來應(yīng)對不確定加工時間和新工件到達組合干擾事件，第一步是利用魯棒優(yōu)化方法獲得對加工時間變動不敏感的魯棒初始調(diào)度方案；第二步則是當新工件到達后選擇合適的反應(yīng)式方法優(yōu)化調(diào)度的最大完工時間、魯棒性度量和穩(wěn)定性度量三個目標，并通過線性加權(quán)將其轉(zhuǎn)化為單目標問題求解。然而相對于不考慮干擾事件或單一干擾事件的研究而言，考慮多種干擾事件組合發(fā)生情況下的調(diào)度研究還較少。

除了干擾事件的影響之外，理論研究工作無法應(yīng)用到實踐中的另外一個重要原因，則是在加工不同工件的過程中往往需要進行設(shè)備清洗、模具更換、工件運輸?shù)阮~外操作，因此通常在相鄰工件間存在一定的安裝時間[2]。然而，絕大多數(shù)流水車間下的干擾管理研究假設(shè)是沒有安裝時間，或者安裝時間與加工次序無關(guān)從而視為加工時間一部分不予考慮。然而當安裝時間與次序相關(guān)時，就會對調(diào)度結(jié)果產(chǎn)生無法忽視的影響[14]。Gholami等[15]研究了在安裝時間與次序相關(guān)的混合流水車間環(huán)境下，出現(xiàn)隨機機器故障時完工時間期望的優(yōu)化問題；運用遺傳算法來獲取最優(yōu)解，并結(jié)合由事件驅(qū)動策略與右移啟發(fā)式方法所構(gòu)造的模擬器來評價完工時間期望。同樣的研究問題，Zandieh等[16]則通過將模擬仿真與免疫算法相結(jié)合的方式對問題進行了求解。與上述干擾事件不同，Kianfar等[17]研究了柔性流水車間下工件動態(tài)到達時的平均延遲時間最小化問題，提出以協(xié)同調(diào)度為主并結(jié)合柔性流水車間、安裝時間、延遲性能度量三因素的基于搜索的指派規(guī)則，以及基于遺傳算法的混合方法，使問題得到了有效的解決。

由文獻綜述可知，第一，流水車間環(huán)境下的組合干擾事件和安裝時間與次序相關(guān)的干擾管理問題在現(xiàn)實生活中普遍存在，且已引起部分學(xué)者的關(guān)注；雖然已有相關(guān)學(xué)者對單一干擾事件或較少干擾事件發(fā)生的情況展開了研究，但對六類常見干擾事件部分或全部組合發(fā)生的干擾管理研究較少。其次雖已有相關(guān)文獻說明相鄰工件間存在的安裝時間對車間調(diào)度的實際應(yīng)用有著很大的影響，但大部分研究都是未考慮安裝時間的，或者簡單的將安裝時間視為加工時間的一部分，尤其是對結(jié)合多種干擾事件組合發(fā)生和安裝時間與次序相關(guān)的干擾管理問題研究較為匱乏。因其模型構(gòu)建較為復(fù)雜，通常均為NP-難問題，求解較為困難。第二，現(xiàn)有干擾管理研究大部分為單目標問題或者多目標通過線性加權(quán)轉(zhuǎn)化為單目標進行處理，而忽略了干擾管理問題中初始目標與擾動目標之間的權(quán)衡影響。

針對以上兩點研究不足，本研究在置換流水車間環(huán)境下，考慮安裝時間與次序相關(guān)以及六類常見干擾事件部分或全部組合發(fā)生情況下，同時最小化重調(diào)度后初始目標最大完工時間和擾動目標次序變動總量。為了求解此復(fù)雜的多目標干擾管理問題，本文以文化基因算法為框架，基于問題和算法的特性，通過改進初始種群構(gòu)建策略以及全局搜索和局部搜索權(quán)衡策略，提出改進文化基因算法對問題進行有效求解。并且通過數(shù)值實驗驗證本文所提出的改進策略和算法的高效性以及所提初始種群構(gòu)建策略和改進文化基因算法在對不同組合干擾事件和不同問題規(guī)模時的普遍適用性。

1 問題描述

圖1 初始加工時間表

Figure 1 The baseline schedule

然而實際生產(chǎn)加工過程中往往存在眾多干擾事件，基于干擾事件來源的不同可分為外部干擾事件和內(nèi)部干擾事件兩大類。外部干擾事件指由于外部市場需求改變而造成的干擾事件，如工件優(yōu)先級變化、工件取消加工、新工件到達等。內(nèi)部干擾事件則是指因車間內(nèi)部生產(chǎn)設(shè)備老舊或技術(shù)變更而導(dǎo)致的干擾事件，如隨機機器故障、加工時間改變、安裝時間改變等。由于以上干擾事件的存在，初始加工時間表通常無法順利執(zhí)行。這種情況下則需要在干擾事件發(fā)生后，對還未加工的工件進行重調(diào)度來盡可能的減小由于干擾事件對初始排序造成的影響。本文在上述所提到的六種常見干擾事件部分或全部組合發(fā)生的情況下，對各干擾事件的處理方式參考文獻[12]并做出如下假設(shè)：

（1）對于任何機器故障事件，其故障發(fā)生時刻和持續(xù)時間都是事先未知的；因機器故障而被迫中斷加工的工件待機器恢復(fù)后，接著之前未完成的操作繼續(xù)加工，即執(zhí)行“中斷-繼續(xù)”操作。

（2）受加工時間改變、安裝時間改變、優(yōu)先級提高、取消加工四類干擾事件影響的加工工件在未加工工件集中隨機產(chǎn)生。

（4）當工件優(yōu)先級提高后，將其安排在已加工工件集后進行及時加工；當新工件到達生產(chǎn)加工系統(tǒng)時，將其安排到初始加工次序最后進行加工；當工件取消加工任務(wù)時，將其從初始加工次序中刪除。

（5）所有受干擾事件影響的工件，按照假設(shè)（1）~（4）進行處理后，其它工件依次順延，加工時間表也進行相應(yīng)調(diào)整。

2 求解算法

安裝時間與次序相關(guān)的單機最大完工時間max最小化調(diào)度問題可視為旅行商問題的特例，屬于典型的NP-難問題。本文在此基礎(chǔ)上將問題擴展到更為復(fù)雜的置換流水車間環(huán)境，因此求解更為困難，同樣也意味著難以通過精確型算法進行有效求解[18]。而智能優(yōu)化算法則是從若干初始解開始，通過進化搜索能夠在有效時間內(nèi)獲得較好的解集，也是目前解決置換流水車間調(diào)度問題最為廣泛的方法[1]。

隨著現(xiàn)實問題的日趨復(fù)雜及求解難度的不斷加大，單一智能優(yōu)化算法已無法取得滿意的結(jié)果，進行算法混合實現(xiàn)優(yōu)勢互補已成為目前的研究趨勢和熱點[19]。其中全局搜索與局部搜索相結(jié)合的算法混合思路在解決復(fù)雜組合優(yōu)化問題中表現(xiàn)出較好的性能，而文化基因算法(Memetic)正與此相契合。因此本文在求解算法方面借助于文化基因算法的思想框架，針對所提出的雙目標干擾管理問題，通過改進多目標初始種群構(gòu)建策略和全局搜索與局部搜索的權(quán)衡策略，在全局搜索和局部搜索的關(guān)鍵環(huán)節(jié)中選擇合適的處理方式，最終提出改進文化基因算法對問題進行求解。

2.1 初始種群構(gòu)建策略

2.2 改進文化基因算法

如前文所述，本文提出的多目標干擾管理問題是一個復(fù)雜的組合優(yōu)化問題，而文化基因算法中的全局搜索與局部搜索相結(jié)合的算法混合思路在解決復(fù)雜組合優(yōu)化問題中表現(xiàn)出較好的性能，能夠有效提高算法的收斂速度；同時也增加了每代消耗時間，從而減少了搜索代數(shù)[21]。其中全局搜索是對解空間全局性探索的過程，直接影響著算法的收斂性和多樣性。而局部搜索則是對遺傳操作后的個體進一步改進的過程，影響著最終解的質(zhì)量好壞。為了滿足在合理時間能得到質(zhì)量較好的近似解的要求，除了在2.1節(jié)對初始種群的生成策略進行改進外，還需要根據(jù)問題和算法的特性對全局搜索和局部搜索中關(guān)鍵的步驟進行設(shè)計和改進處理。

2.2.1 全局搜索策略

2.2.2 局部搜索策略

（2）在鄰域結(jié)構(gòu)確定上，本文為了能夠繼承父代的優(yōu)良基因且具備多樣性，借鑒已在相關(guān)置換流水車間調(diào)度研究[21,23]中獲得較好結(jié)果的方法：選擇為連續(xù)多基因位插入操作，連續(xù)基因的個數(shù)控制在三個以內(nèi)，如圖2所示。

圖2 鄰域結(jié)構(gòu)示意圖

Figure 2 Neighborhood structure

（3）在新個體的接收準則上，常見的做法是若新個體相較于目標個體更優(yōu)，則用新個體來替換目標個體[21]，然而這樣容易錯失一些整體較優(yōu)的目標個體。本文最終想要給出質(zhì)量較好的帕累托最優(yōu)解，為了避免丟棄一些支配其它個體的帕累托最優(yōu)解。算法采取只要新個體不被目標個體所支配則接收該個體為新解，并保留目標個體的做法。并在種群更新時進行整體排序，擇優(yōu)進入下一代。

圖3 改進文化基因算法流程圖

Figure 3 The framework of improved memetic algorithm

在更新種群時為了能夠改善每代種群的整體質(zhì)量，采用的種群更新機制為擇優(yōu)進入下代。首先將上代種群與本代產(chǎn)生的新解合并去重，然后對其進行非支配排序，最后選擇排序靠前的滿足種群數(shù)量的個體構(gòu)成下代種群參與后續(xù)操作。而算法的終止條件同文獻[21]采用函數(shù)評價10萬次。

綜上所述，通過對初始種群構(gòu)建的改進，對全局搜索和局部搜索中關(guān)鍵步驟的設(shè)計，以及提出局部搜索效率的設(shè)定對局部搜索的強度進行改進，從而使得算法滿足本文問題的實際求解要求，平衡計算資源在全局搜索和局部搜索之間的分配，并且極大程度的提高了算法的性能。本文提出的改進文化基因算法流程圖如圖3所示。

3 數(shù)值實驗

針對本文提出的具有安裝時間的置換流水車間組合干擾管理問題，為了驗證所提初始種群構(gòu)建策略和改進文化基因算法在求解六種干擾事件部分或者全部組合情況下的有效性，我們分別在運用初始種群構(gòu)建策略前后與目前最為流行的多目標算法NSGA-II進行對比。為了比較的公平性，其中NSGA-II算法遺傳操作與文化基因算法保持一致。本部分首先對實驗算例參數(shù)和算法參數(shù)進行設(shè)計說明，給出對比實驗中的五個有效前沿比較指標；最后通過對比實驗結(jié)果并對其進行分析。

3.1 數(shù)值實驗設(shè)計

（4）新到達工件：新工件的加工時間和安裝時間的設(shè)置與初始調(diào)度問題設(shè)置一致。

為了驗證對于不同干擾事件組合的普適性，每個算例分別考慮常見的三種干擾事件組合情況。第一種由于外部需求而發(fā)生的組合干擾事件，包括新工件到達、工件優(yōu)先級變化、取消工件加工任務(wù)；第二種則是由于加工車間內(nèi)部設(shè)備老舊或者技術(shù)改變而發(fā)生的組合干擾事件，包括隨機機器故障、加工時間改變、安裝時間改變。第三種則是上述外部干擾事件和內(nèi)部干擾事件同時發(fā)生的全部組合干擾事件。

為了更有效地比較本文提出的改進策略和改進算法的有效性，借鑒文獻[24-27]中的五個性能指標，分別從非支配解集的臨近性、多樣性、綜合性三個方面對有效前沿進行評價。五個比較指標如下所示（比較指標的具體定義和計算公式，可查閱對應(yīng)文獻）：

本文算法采用MATLAB語言進行編程，運行環(huán)境為MATLAB7.10.0，；計算機CPU為Intel(R) Core(TM)2 Duo CPU，內(nèi)存為2G，主頻為3.00GHz。在對比實驗的算法參數(shù)設(shè)置上，通過預(yù)先在100個工件10臺機器規(guī)模下六種干擾事件組合發(fā)生情況下的進行隨機數(shù)值實驗，從而對NSGA-II算法和改進文化基因算法中的參數(shù)進行調(diào)整和確定。首先對NSGA-II算法進行調(diào)參，該算法共涉及種群規(guī)模、交叉概率、變異概率三個參數(shù)，分別取100、150、200； 0.7、0.8、0.9；0.05、0.10、0.15，共27種組合，取五次實驗結(jié)果中平均超體積最小的參數(shù)組合。然后對改進文化基因算法的參數(shù)進行調(diào)整和確定，涉及到與NSGA-II共有的參數(shù)取值與其保持一致；而復(fù)制淘汰比例、局部搜索周期、局部搜索步長三個參數(shù)，分別取0.1、0.2、0.3；3、4、5；1、2、3，確定過程與前面三個參數(shù)相同。最后算法所涉及的參數(shù)值如表1所示。

表1 算法參數(shù)設(shè)置

3.2 實驗結(jié)果與分析

3.2.1 不同組合干擾事件時有效性分析

為了驗證本文提出的初始種群構(gòu)建策略與改進文化基因算法，在應(yīng)對不同組合干擾事件時的普遍適用性；因此在5臺機器50個工件的問題規(guī)模下針對外部組合干擾事件、內(nèi)部組合干擾事件、全部組合干擾事件3種不同組合分別進行了10組隨機數(shù)值實驗。

將改進文化基因算法和NSGA-II算法，同隨機初始種群策略和所提構(gòu)建初始種群策略進行相互組合，可以得到4種策略，并對就其有效前沿進行對比，如圖4所示。可以看到不同組合干擾事件時，在初始種群生成策略相同的情況下，改進文化基因算法所得有效前沿完全支配NSGA-II算法所獲得的有效前沿解；而在算法相同的情況下，運用所提構(gòu)建初始種群策略得到的有效前沿解要完全支配隨機初始種群產(chǎn)生的解。因此，從有效前沿對比圖中可以較為直觀得驗證所提初始種群構(gòu)建策略與改進文化基因算法的有效性。

由圖4可見，相比外部組合干擾事件，內(nèi)容組合干擾事件對企業(yè)的生產(chǎn)管理造成的影響更大，所以生產(chǎn)管理者應(yīng)更加關(guān)注內(nèi)部干擾事件組合發(fā)生的情況。內(nèi)外干擾事件組合發(fā)生時，對企業(yè)初始目標和擾動目標都會造成較大的影響，但擾動目標變化更加敏感。因此，生產(chǎn)管理者應(yīng)盡量避免內(nèi)外干擾事件組合發(fā)生情況的出現(xiàn)；如果內(nèi)外干擾事件組合發(fā)生，建議生產(chǎn)管理者采取首先確定擾動目標范圍，然后獲取初始目標的策略，這樣有望獲得更佳的管理效果。

同時就不同算法與初始種群生成策略相互組合得到的4種策略，針對不同組合干擾事件分別計算10個隨機算例下的有效前沿指標均值，并對其進行了歸一化處理。在圖5中我們針對每個有效前沿指標，按照越向外越優(yōu)的方向進行繪制，圖形面積可直觀地反應(yīng)出策略整體性能。因此可得出“文化基因算法+構(gòu)建初始種群”表現(xiàn)最佳，隨后為“NSGA-II算法+構(gòu)建初始種群”、“文化基因算法+隨機初始種群”，表現(xiàn)最差的則是“NSGA-II算法+隨機初始種群”。并且可以發(fā)現(xiàn)相對于外部組合干擾事件和內(nèi)部組合干擾事件，當全部組合干擾事件發(fā)生時，有效前沿變得非常陡峭，表明此時目標函數(shù)對決策的權(quán)衡取舍非常敏感，同時也說明在這種情況下為不同決策者提供有效前沿是十分必要的。

圖4 不同組合干擾事件時的有效前沿對比

Figure 4 Pareto front comparison of different combinational events

圖4（續(xù)） 不同組合干擾事件時的有效前沿對比

Figure 4(continue) Pareto front comparison of different combinational events

除此之外，對4種策略的不同指標進行分析。綜合性指標超體積HV，以及臨近性指標世代距離GD和非支配距離NDS_DIS三個指標上策略的優(yōu)劣順序與整體性分析所得一致。在多樣性指標有效前沿解數(shù)量ONVG上，文化基因算法與NSGA-II算法不相上下，而所提構(gòu)建初始種群策略相較于隨機初始種群策略依然具有較強的優(yōu)勢；同時在另一多樣性指標非支配解數(shù)量NDS_NUM上，文化基因算法與所提構(gòu)建初始種群策略都表現(xiàn)出較強的優(yōu)勢，反應(yīng)了有效前沿解較好的質(zhì)量。

圖5 不同組合干擾事件時的有效前沿指標分析

Figure 5 Index analysis of different combinational events

注：按照越向外越優(yōu)的方向進行繪制，圖形面積越大反應(yīng)出策略整體性能越好

3.2.2 不同問題規(guī)模情況下有效性分析

為了驗證所提初始種群構(gòu)建策略與改進文化基因算法，在不同問題規(guī)模情況下的普遍適用性；因此分別考慮工件個數(shù)=25、50、100，機器臺數(shù)=3、5、10的情況，同一問題規(guī)模下針對外部組合干擾事件、內(nèi)部組合干擾事件、全部組合干擾事件3種不同組合分別隨機進行10組數(shù)值實驗。

針對不同算法與初始種群生成策略相互組合得到的4種策略，分別計算在9種不同規(guī)模下綜合性指標超體積HV的誤差棒圖，如圖6所示。在同一問題規(guī)模下，4種策略的表現(xiàn)優(yōu)劣順序依然為“文化基因算法+構(gòu)建初始種群”表現(xiàn)最佳，隨后為“NSGA-II算法+構(gòu)建初始種群”、“文化基因算法+隨機初始種群”，表現(xiàn)最差的則是“NSGA-II算法+隨機初始種群”。

表2 數(shù)值實驗結(jié)果指標對比分析

在機器數(shù)量相同，工件數(shù)量規(guī)模不斷增大過程中，改進文化基因算法相較于經(jīng)典NSGA-II算法，所提構(gòu)建初始種群策略相較于隨機初始種群的優(yōu)勢開始體現(xiàn)的越明顯。原因可以歸結(jié)為兩點：第一，隨著工件數(shù)量的增加，解空間也在增加；此時改進文化基因算法能夠利用局部搜索將有限計算資源集中運用到較優(yōu)解的搜索方向，避免了資源的浪費。第二，所提構(gòu)建初始種群能夠一定程度上給后期搜索工作指明方向，避免了盲目的搜索。而工件數(shù)量相同，機器數(shù)量規(guī)模不斷增加的過程中相應(yīng)HV的增加，僅僅是由于相應(yīng)的最大完工時間增加的原因，因此不做過多分析。

同時就不同算法與初始種群生成策略相互組合得到的4種策略，針對不同規(guī)模下不同組合干擾事件分別計算10個隨機算例下的有效前沿指標均值，并對其進行了歸一化處理。如表2所示。就綜合性指標而言，全部數(shù)據(jù)所呈現(xiàn)的超體積HV大小關(guān)系，顯示4種策略優(yōu)劣順序與之前分析一致，再次表明改進文化基因算法和所提初始種群構(gòu)建策略的有效性。下面分別對有效前沿的臨近性和多樣性分別進行分析。

圖6 不同問題規(guī)模情況下超體積HV的誤差棒圖

Figure 6 The error bBar chart of hyper-volume in different scale

在臨近性方面，世代距離GD指標和非支配距離NDS_DIS指標，絕大多數(shù)是在初始種群生成策略相同的情況下，改進文化基因算法比NSGA-II算法的指標值??；在算法相同的情況下，運用所提構(gòu)建初始種群策略要比隨機初始種群得到的指標值小。因此，可以驗證改進文化基因算法和所提初始種群構(gòu)建策略在有效前沿臨近性具有優(yōu)越性。

在多樣性方面，從有效前沿解的數(shù)量ONVG指標上可以看出，在初始種群生成策略相同的情況下，改進文化基因算法與NSGA-II算法的表現(xiàn)不相上下；而在算法相同的情況下，所有運用構(gòu)建初始種群策略的要比隨機初始種群的有效前沿數(shù)量多。構(gòu)建初始種群策略在ONVG指標上的優(yōu)勢，主要原因是初始種群中所加入的兩個單目標較優(yōu)種群具有一定的相似性，這樣有利于廣度搜索更加有效，增加了非支配排序中相同層級的解。從非支配解的數(shù)量NDS_DIS指標上，可以得出與之前4種策略優(yōu)劣順序一致的結(jié)果。之所以此時改進文化基因算法能夠具有明顯的優(yōu)勢，主要原因是通過適度有效的局部搜索，有利于解的深度搜索更加有效，提升了非支配排序中解的層級。

4 結(jié)論

在安裝時間與次序相關(guān)的置換流水車間環(huán)境下，研究機器故障、加工時間改變、安裝時間改變、新工件到達、工件優(yōu)先級提高、工件取消加工六類常見干擾事件部分或者全部組合發(fā)生情況下的干擾管理問題。組合干擾事件發(fā)生后為了保持良好的調(diào)度性能(最大完工時間)而進行重調(diào)度，同時考慮給生產(chǎn)車間帶來的擾動目標次序變化，因此為多目標重調(diào)度問題。為了獲得較好的有效前沿，提出各單目標較優(yōu)種群與隨機生成種群相結(jié)合的初始種群構(gòu)建策略，以及通過權(quán)衡全局搜索和局部搜索關(guān)系的改進文化基因算法來對問題進行求解。

通過數(shù)值實驗表明：（1）通過單目標較優(yōu)種群與隨機生成種群相結(jié)合的初始種群構(gòu)建策略能夠有效改善帕累托有效前沿的質(zhì)量。（2）通過調(diào)整局部搜索強度來平衡全局搜索和局部搜索的改進文化基因算法比單純的NSGA-II算法獲得的有效前沿性能更優(yōu)。（3）所提初始種群構(gòu)建策略和改進文化基因算法對不同組合干擾事件和不同問題規(guī)模具有普遍適用性。

本研究在理論上進一步完善和豐富了考慮安裝時間和次序相關(guān)的置換流水車間環(huán)境下的干擾管理研究，而在實踐上有助于為生產(chǎn)加工企業(yè)在面臨較為復(fù)雜的組合干擾事件時，提供有效且多樣化的重調(diào)度方案，指導(dǎo)生產(chǎn)實踐。未來進一步的研究方向可聚焦于以下兩方面，在問題方面，所構(gòu)建的組合干擾管理模型應(yīng)能夠涵蓋更多干擾事件；尤其是加工時間不確定此類在初始調(diào)度制定過程中就需要考慮的干擾事件。在求解算法方面，可以嘗試在文化基因算法全局搜索部分應(yīng)用其它多目標算法；也可以提出新的多目標智能優(yōu)化算法進行求解，并嘗試從算法實踐中提煉挖掘?qū)芾碚哂幸娴臐撛诠芾韱⑹尽?/p>

[1] 王建軍,劉亞凈,劉鋒,等.考慮行為主體的置換流水車間干擾管理研究[J].系統(tǒng)工程理論與實踐,2015,35(12):3092-3106.

Wang J J, Liu Y J, Liu F,. Disruption management considering real-word behavioral participators in permutation flowshop [J]. Systems Engineering-Theory & Practice, 2015,35(12):3092-3106.

[2] 徐建有,董乃群,顧樹生.帶有順序相關(guān)調(diào)整時間的多目標流水車間調(diào)度問題[J].計算機集成制造系統(tǒng),2013,19(12):3170-3176.

Xu J Y, Dong N Q, Gu S S. Multi-objective permutation flowshop scheduling with sequence-dependent setup times[J]. Computer Integrated Manufacturing Systems, 2013, 19(12):3170-3176

[3] 劉樂, 周泓. 一種常見干擾條件下的開放式車間重調(diào)度研究[J].管理科學(xué)學(xué)報, 2014,17(6): 28-48.

Liu L, Zhou H. Open shop rescheduling under a common disruptive condition[J]. Journal of Management Sciences in China, 2014, 17(6): 28-48.

[4] 李鐵克,肖擁軍,王柏琳. 基于局部性修復(fù)的HFS機器故障重調(diào)度[J]. 管理工程學(xué)報,2010,24(3):45-49.

Li T K, Xiao Y J, Wang B L. HFS rescheduling under machine failures based on local repair[J]. Journal of Management in Engineering, 2010, 24(3):45-49.

[5] Wang K, Choi S H. A decomposition-based approach to flexible flow shop scheduling under machine breakdown[J]. International Journal of Production Research, 2012, 50(1): 215-234.

[6] Wang K, Huang Y, Qin H. A fuzzy logic-based hybrid estimation of distribution algorithm for distributed permutation flowshop scheduling problems under machine breakdown[J]. Journal of the Operational Research Society, 2016, 67(1): 68-82.

[7] Weng W, Wei X, Fujimura S. Dynamic routing strategies for JIT production in hybrid flow shops[J]. Computers & Operations Research, 2012, 39(12):3316-3324.

[8] Rabiee M, Zandieh M, Jafarian A. Scheduling of a no-wait two-machine flow shop with sequence-dependent setup times and probable rework using robust meta-heuristics[J]. International Journal of Production Research, 2012, 50(24): 7428-7446.

[9] Hu Yanhai, Yan Junqi, Ye Feifan,. Flow shop rescheduling problem under rush orders[J]. Journal of Zhejiang University Science A, 2005, 6(10): 1040-1046.

[10] Katragjini K, Vallada E, Ruiz R. Flow shop rescheduling under different types of disruption [J]. International Journal of Production Research, 2013, 51(3):780-797.

[11] 王旭坪, 阮俊虎, 張凱,等. 有模糊時間窗的車輛調(diào)度組合干擾管理研究[J].管理科學(xué)學(xué)報, 2011, 14(6):2-15.

Wang X P, Ruan J H, Zhang K,. Study on combinational disruption management for vehicle routing problem with fuzzy time windows [J]. Journal of Management Sciences in China, 2011, 14(6):2-15.

[12] Li J, Pan Q, Mao K. A discrete teaching-learning-based optimisation algorithm for realistic flowshop rescheduling problems [J]. Engineering Applications of Artificial Intelligence, 2015, 37:279-292.

[13] Rahmani D, Heydari M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times [J]. Journal of Manufacturing Systems, 2014, 33(1):84-92.

[14] 劉鋒,王建軍,饒衛(wèi)振,等.安裝時間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究[J].中國管理科學(xué),2014, 22(1):45-54.

Liu F, Wang J J, Rao W Z,. Machine scheduling disruption management with sequence dependent setup times [J].Chinese Journal of Management Science, 2014, 22(1):45-54.

[15] Gholami M, Zandieh M, Alem-Tabriz A. Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns[J]. The International Journal of Advanced Manufacturing Technology, 2009, 42(1-2): 189-201.

[16] Zandieh M, Gholami M. An immune algorithm for scheduling a hybrid flow shop with sequence-dependent setup times and machines with random breakdowns[J]. International Journal of Production Research, 2009, 47(24): 6999-7027.

[17] Kianfar K, Fatemi Ghomi S M T, Oroojlooy Jadid A. Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA[J]. Engineering Applications of Artificial Intelligence, 2012, 25(3): 494-506.

[18] Mirabi M. A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2014, 71(1-4): 429-437.

[19] Pan Q K, Wang L, Li J Q,. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J]. Omega, 2014, 45:42-56.

[20] 王凌, 吳昊, 唐芳, 等. 混合量子遺傳算法及其性能分析[J]. 控制與決策, 2005, 20(2): 156-160.

Wang L, Wu H, Tang F,. Hybrid quantum genetic algorithms and performance analysis[J]. Control and Decision, 2005, 20(2):156-160.

[21] Ishibuchi H, Yoshida T, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling [J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 204-223.

[22] Pan Q, Wang L, Sang H,. A high performing memetic algorithm for the flowshop scheduling problem with blocking [J]. IEEE Transactions on Automation Science and Engineering, 2013, 10(3): 741-756.

[23] Anand S, Maria B, Chris N. An iterated local search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times[J]. International Journal of Production Research, 2014, 52(9): 2729-2742.

[24] Robi? T, Filipi? B. DEMO: Differential evolution for multiobjective optimization[C]. Evolutionary multi-criterion optimization. Springer Berlin Heidelberg, 2005: 520-533.

[25] Qian B, Wang L, Huang D,. Scheduling multi-objective job shops using a memetic algorithm based on differential evolution[J]. The International Journal of Advanced Manufacturing Technology, 2008, 35(9-10): 1014-1027.

[26] Li B, Wang L. A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling[J].IEEE Transactions on Systems, Man and Cybernetics, Part B: (Cybernetics), 2007, 37(3): 576-591.

[27] Bhuvana J, Aravindan C. Memetic algorithm with preferential local search using adaptive weights for multi-objective optimization problems[J]. Soft Computing, 2016, 20(4): 1365-1388.

Combinational disruption management in permutation flow shops with sequence-dependent setup times

WANG Jianjun, HOU Xiaowen, LIU Xiaopan, MIAO Hongru

(School of Economics and Management, Dalian University of Technology, Dalian 116023, China)

The flow shop scheduling problem, as one that can be widely abstracted in the actual production and processing environment, is common in manufacturing and service areas such as metallurgy, food processing, and surgical scheduling. Although relatively rich theoretical research results have been achieved, most of these developed solutions are difficult to apply to production practices. A key issue is that most flow shop scheduling research to date ignores the impact of various disruption events in the actual production process. As such, the problem of flow shop disruption management has gradually attracted widespread attention. In recent years, some researchers have begun to consider approaching their analysis from the point of a single disruption event in a flow shop environment. However, in most practical situations, multiple disruption events occur in combination. The processing of such situations is more complicated than for those involving a single disruption event, and in this case, may have a greater impact on the current scheduling scheme. Some researchers have put forward combinational disruption management as a very important research focus and have started to carry out corresponding analysis. However, relative to the number of studies that do not take disruption events into consideration, the body of scheduling research with a focus on combinational disruption events is inadequate. In addition, most of the existing research on disruption management in permutation flow shops assumes that setup time is negligible, or otherwise factored into the processing time. Where the setup time is relatable to the setup sequence, it will have an impact on the scheduling results that cannot be ignored. Finally, most of the existing body of disruption management research tackles single-objective problems, or converts multi-objective problems to single-objective ones through a linear weighted method, while neglecting the impact of the trade-off between the initial objective and the disruption objective in the disruption management problem.

In light of the various deficiencies within the existing body of research, this paper studies six types of common disruption events: random machine failure, processing time variation, setup time variation, job priority update, new job arrival, and job cancellation, in a permutation flow shop environment where setup time and sequence are relevant factors. Disruption management problems are framed as a consequence of either partially or fully combinational events. In order to meet the preferences of different decision makers, in reference to the existing literature on the treatment of various disruption events, we are committed to simultaneously minimizing the initial objective (make span) and the disruption objective (sequence deviation) to better performance and obtain a Pareto optimal solution.

After analysis, this problem appeared to be difficult to solve. However, we proposed an improved memetic algorithm to solve it. Based on our memetic algorithm, we implemented an initial population construction strategy. First, the optimal population under two single objectives is obtained by minimizing the initial objective and the disruption objective by sorting using a non-dominant sorting method, and then selecting the individuals who reign superior after the non-dominant ones are selected out. Second, the remaining initial population is supplemented with randomly generated individuals to construct a final initial population. For some key elements of local search (such as the selection of objective individuals or the criteria for receiving new individuals), the characteristics of the problem and the algorithm are further analyzed to determine the appropriate processing method that will allow the algorithm to better meet the problem-solving requirements. Finally, the concept of "local search efficiency", defined as the ratio of the number of receiving individuals to the number of searching individuals, is introduced and used to balance the allocation of computing resources between global search and local search. By adjusting the search period and search probability of the local search at different stages through local search efficiency, the diversity and practical effectiveness of the Pareto solution can be significantly improved.

We referenced the existing five effectiveness comparison indicators, and designed numerical experiments for different combinational disruption events, to test the effectiveness of the proposed initial population construction strategy and improved memetic algorithm. To facilitate a more effective comparison, this paper improved the memetic and NSGA-II algorithms, and combined them with the random initial population and initial population construction strategies to obtain four hybrid conditions: “memetic algorithm + initial population construction", "NSGA-II algorithm + initial population construction", "memetic algorithm + random initial population", " NSGA-II algorithm + random initial population". Through numerical experiments, we found that, given the same initial population, the improved memetic algorithm proposed in this paper provided a better Pareto frontier; and, given the same algorithm, the initial population construction strategy proposed in this paper significantly improved the performance of the algorithm, thus demonstrating its advantages. This study further improves and theoretically enriches the body of research on combinational disruption management in a permutation flow shop environment where setup time and sequence are relevant factors, and in practice, can help facilitate effective production and the implementation of rescheduling programs to guide production practices, at times when enterprises may face combinational disruption events.

Disruption management; Combinational disruption; Setup times; Memetic algorithm; Pareto front

2018-01-25

2018-05-08

Supported by the National Natural Science Foundation of China (71672019, 71271039, 71421001) and the Program for New Century Excellent Talents in University（NCET-13-0082）

C939

A

1004-6062(2020)04-0144-010

10.13587/j.cnki.jieem.2020.04.016

2018-01-25

2018-05-08

國家自然科學(xué)基金資助項目（71672019、71271039、71421001）；教育部新世紀優(yōu)秀人才支持計劃資助項目（NCET-13-0082）

王建軍（1977—），男，河北保定市人，大連理工大學(xué)經(jīng)濟管理學(xué)院教授，博士生導(dǎo)師，研究方向：服務(wù)管理、運作管理等。

中文編輯：杜 ?。挥⑽木庉嫞築oping Yan