具有安裝時(shí)間的置換流水車(chē)間組合干擾管理研究

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

具有安裝時(shí)間的置換流水車(chē)間組合干擾管理研究

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

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

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

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

0 引言

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

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

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

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

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

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

1 問(wèn)題描述

圖1 初始加工時(shí)間表

Figure 1 The baseline schedule

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

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

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

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

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

2 求解算法

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

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

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

2.2 改進(jìn)文化基因算法

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

2.2.1 全局搜索策略

2.2.2 局部搜索策略

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

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

Figure 2 Neighborhood structure

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

圖3 改進(jìn)文化基因算法流程圖

Figure 3 The framework of improved memetic algorithm

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

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

3 數(shù)值實(shí)驗(yàn)

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

3.1 數(shù)值實(shí)驗(yàn)設(shè)計(jì)

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 不同組合干擾事件時(shí)有效性分析

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

將改進(jìn)文化基因算法和NSGA-II算法，同隨機(jī)初始種群策略和所提構(gòu)建初始種群策略進(jìn)行相互組合，可以得到4種策略，并對(duì)就其有效前沿進(jìn)行對(duì)比，如圖4所示?？梢钥吹讲煌M合干擾事件時(shí)，在初始種群生成策略相同的情況下，改進(jìn)文化基因算法所得有效前沿完全支配N(xiāo)SGA-II算法所獲得的有效前沿解；而在算法相同的情況下，運(yùn)用所提構(gòu)建初始種群策略得到的有效前沿解要完全支配隨機(jī)初始種群產(chǎn)生的解。因此，從有效前沿對(duì)比圖中可以較為直觀得驗(yàn)證所提初始種群構(gòu)建策略與改進(jìn)文化基因算法的有效性。

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

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

圖4 不同組合干擾事件時(shí)的有效前沿對(duì)比

Figure 4 Pareto front comparison of different combinational events

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

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

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

圖5 不同組合干擾事件時(shí)的有效前沿指標(biāo)分析

Figure 5 Index analysis of different combinational events

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

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

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

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

表2 數(shù)值實(shí)驗(yàn)結(jié)果指標(biāo)對(duì)比分析

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

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

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

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

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

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

4 結(jié)論

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

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

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

[1] 王建軍,劉亞凈,劉鋒,等.考慮行為主體的置換流水車(chē)間干擾管理研究[J].系統(tǒng)工程理論與實(shí)踐,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] 徐建有,董乃群,顧樹(shù)生.帶有順序相關(guān)調(diào)整時(shí)間的多目標(biāo)流水車(chē)間調(diào)度問(wèn)題[J].計(jì)算機(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] 劉樂(lè), 周泓. 一種常見(jiàn)干擾條件下的開(kāi)放式車(chē)間重調(diào)度研究[J].管理科學(xué)學(xué)報(bào), 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機(jī)器故障重調(diào)度[J]. 管理工程學(xué)報(bào),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] 王旭坪, 阮俊虎, 張凱,等. 有模糊時(shí)間窗的車(chē)輛調(diào)度組合干擾管理研究[J].管理科學(xué)學(xué)報(bào), 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)振,等.安裝時(shí)間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究[J].中國(guó)管理科學(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

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

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

中文編輯：杜 健；英文編輯：Boping Yan