置換流水車間新工件到達干擾管理研究

劉亞凈，　趙奇楠,　王建軍

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連　116023；2.大連理工大學(xué) 公共管理與法學(xué)學(xué)院，遼寧 大連　116023)

?

置換流水車間新工件到達干擾管理研究

劉亞凈1，趙奇楠2,王建軍1

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連116023；2.大連理工大學(xué) 公共管理與法學(xué)學(xué)院，遼寧 大連116023)

摘要：在置換流水加工環(huán)境下，以最小化生產(chǎn)流程時間為目標制定的初始加工方案，由于新工件的到達變得不再最優(yōu)或不可行，為了降低對原始加工方案的影響，在權(quán)衡生產(chǎn)成本和擾動成本的情況下，建立雙目標重調(diào)度干擾管理模型，對初始最優(yōu)方案進行調(diào)整。針對該模型的特點和問題復(fù)雜度，結(jié)合微粒群算法強大的全局搜索能力，以及非支配排序遺傳算法(NSGA-Ⅱ)獲得的Pareto解優(yōu)良的綜合性能，提出了一種混合微粒群算法來對問題求解。通過求解經(jīng)典文獻中置換流水車間雙目標問題和隨機生成的置換流水車間新工件到達問題，結(jié)果表明混合算法要優(yōu)于NSGA-Ⅱ和多目標微粒群算法(MOPSO)，同時驗證了求解置換流水車間干擾管理問題的有效性。

關(guān)鍵詞：干擾管理；重調(diào)度；新工件到達；Pareto有效前沿；混合算法

0引言

置換流水車間調(diào)度(PFSP)作為一種典型的流水車間生產(chǎn)排序問題，在工業(yè)界和學(xué)術(shù)界得到了廣泛的關(guān)注[1]。在實際加工系統(tǒng)中，置換流水車間作業(yè)加工系統(tǒng)時刻面臨著如機器故障、物料短缺、訂單取消、新訂單到達、加工時間變化、訂單優(yōu)先級變化和交貨期變化等[2]干擾事件的發(fā)生，在干擾發(fā)生后，需要及時對初始方案進行調(diào)整，如何以盡量小的擾動和成本，恢復(fù)加工系統(tǒng)的正常運行，是管理科學(xué)研究前沿——干擾管理所致力于解決的問題[3-4]。

目前在置換流水車間加工環(huán)境下，干擾管理相關(guān)研究還比較鮮見?；诟蓴_管理的思想，在此加工環(huán)境下同時考慮原目標和擾動目標，進行新工件到達的反應(yīng)式重調(diào)度問題研究。與本文研究類似的文獻[5]研究了新工件到達使初始方案受到干擾，文中采用兩階段法，為了降低對初始方案的影響，原目標采用經(jīng)典的目標函數(shù)——生產(chǎn)流程時間來度量加工生產(chǎn)成本，擾動目標采用工件加工次序的變動來度量擾動成本，用模擬退火算法對原目標和擾動目標進行線性加權(quán)化為單目標進行求解，每獲得一個有效解需要運行一次程序，通過賦予目標函數(shù)不同的權(quán)值來獲得問題的近似Pareto有效前沿，但求解效率比較低。

在考慮優(yōu)化原目標的前提下，如何使系統(tǒng)的擾動降至最低，是干擾管理的核心問題[6]。一般從對擾動敏感因素的度量角度來考慮干擾事件對初始調(diào)度造成的擾動，而干擾的度量多采用與工件完工時間相關(guān)的擾動，對于調(diào)度的衡量采用的均為時間尺度；采用工件加工位置的擾動[7]是從另外一個角度來進行擾動度量，一方面可以避免原目標和擾動目標的交叉影響，另一方面位置的擾動帶來的最直接的影響是車間工人需重新進行物料的搬運、工件的裝夾等重復(fù)勞動，在一定程度上還可以反應(yīng)干擾事件給車間工人造成的消極情緒。此外，不同于單機環(huán)境，干擾事件對置換流水車間的擾動隨著機器規(guī)模的增大也會變得更為突出。因此，采用位置的擾動度量比較適合置換流水車間加工環(huán)境。

從以上研究發(fā)現(xiàn)，流水車間的干擾管理研究主要集中在魯棒調(diào)度的初始方案的制定以及機器中斷情況下的部分修復(fù)或者重調(diào)度，目前針對新工件到達的干擾事件對加工系統(tǒng)的擾動研究明顯不足。另外，擾動度量方法大多是從單機直接推廣到平行機、流水車間或者更為復(fù)雜的加工系統(tǒng)，而在實際調(diào)度中，同一干擾事件對不同加工系統(tǒng)造成的擾動往往是不同的。由此，就置換流水車間下的新訂單到達的干擾事件，提出了一種更適合置換流水車間的擾動度量方法——加工資源位置的擾動，建立同時考慮生產(chǎn)成本目標和擾動目標的重調(diào)度模型，并提出一種結(jié)合微粒群算法和非支配排序遺傳算法(Non-dominated Sorting Genetic AlgorithmⅡ,NSGA-Ⅱ)優(yōu)勢的有效的混合啟發(fā)式算法來對問題進行有效求解。

1問題描述

置換流水車間調(diào)度是一類經(jīng)典的流水車間作業(yè)問題。在此加工環(huán)境下，新工件到達是最為常見的干擾事件之一[2]。問題具體描述如下：n0個工件組成的待加工工件集，以最小化生產(chǎn)流程時間為目標制定初始加工方案π0={J1,J2,…,Jn0}。n0個工件按照初始最優(yōu)方案π0在m臺機器上順次加工，每一個工件需要進行m個操作工序，分別在m臺機器上進行。在加工過程中不允許搶占，每一個工件的每種操作只能在一臺機器上進行；每臺機器只能進行一種操作的加工；同一時間、同一臺機器上至多加工一個工件，機器和工件在時刻0準備就緒。在按初始加工方案加工之前，新到達一批加工工件，致使初始最優(yōu)加工方案不可行。采用重調(diào)度的策略對原有工件和新工件進行調(diào)整，對新到達的nN個工件進行重新編碼{Jn0+1,…,Jn0+nN}，此時，工件集為{J1,J2,…,Jn}，其中n=n0+nN。制造商以工件的生產(chǎn)流程時間為目標來衡量加工成本，并依此制定初始加工方案，用新工件對原加工系統(tǒng)中加工資源位置的擾動來度量干擾事件的影響。

相關(guān)參數(shù)定義如下：π0為初始最優(yōu)的加工計劃；π為加工系統(tǒng)在受到干擾之后，制定的新的加工計劃；Cij(π)為在機器j上，第i個位置上工件的完工時間，采用Cij簡化表示；Di(π,π0)=|yi-xi|表示1臺機器上，重調(diào)度前后與工件Ji相關(guān)的加工資源位置的偏差，xi和yi分別為工件Ji在初始調(diào)度π0和重調(diào)度π中的加工位置。

工件在機器上的完工時間與它在前一臺機器上的完工時間和當前機器上前一工件的完工時間有關(guān)。初始調(diào)度受到干擾事件的影響不再最優(yōu)或者變得不可行。在重調(diào)度過程中，采用原目標——生產(chǎn)流程時間來度量加工成本

(1)

新到達的工件對加工系統(tǒng)造成的擾動最直接的體現(xiàn)在與加工工序相關(guān)的加工資源位置的改變。由此，在每臺機器上工人需要根據(jù)加工工序的改變，重新進行加工前的準備如物料的搬運、工件的裝夾等，從而產(chǎn)生擾動成本，尤其當訂單規(guī)模很大時，這種頻繁地重復(fù)的無用功勞動會給車間工人心理上帶來負面影響，嚴重的甚至?xí)?dǎo)致工人消極怠工或者罷工等[8]。對于干擾的度量，相對于單機環(huán)境，干擾對置換流水車間的擾動與流水線的機器臺數(shù)m是成正比的，即在置換流水車間環(huán)境下，干擾對工件位置的擾動具有放大效應(yīng)。擾動目標函數(shù)為與初始工件相關(guān)的加工資源位置擾動之和

(2)

綜上所述，使用經(jīng)典的三元組α|β|γ將問題表述為

原問題Fm|prmu|Cmax(m>2)為NP-難問題[9]。當新工件到達干擾發(fā)生后，在此基礎(chǔ)上，需要權(quán)衡原目標和干擾目標的情況下進行重調(diào)度。因此，重調(diào)度模型Fm|prmu|f1,f2在求解復(fù)雜度上是沒有多項式算法的。

2問題求解

針對上述雙目標重調(diào)度模型的復(fù)雜性分析可見，經(jīng)典的精確算法求解此類問題，尤其是當問題規(guī)模較大且問題結(jié)構(gòu)比較復(fù)雜時，需要花費很大的代價，得不到問題的(近似)最優(yōu)解。相比而言，啟發(fā)式算法更適合求解多目標優(yōu)化問題，一方面啟發(fā)式算法強大的并行計算能力，運行一次，能輸出多個解，求解效率高；另外其對Pareto有效前沿的形狀和連續(xù)性不敏感，能很好得逼近最優(yōu)有效前沿[10]。因此，本文設(shè)計了一種混合啟發(fā)式算法來對上述問題進行求解。

近幾年，微粒群算法(ParticleSwarmOptimization,PSO)由于其原理簡單、易于實現(xiàn)等特點，備受學(xué)者們的關(guān)注。PSO算法具有很強的全局優(yōu)化能力，但局部搜索能力相對較差，而遺傳算法在生產(chǎn)調(diào)度領(lǐng)域的應(yīng)用也相當廣泛[11]，但在求解高維問題時全局搜索能力不足[12]。鑒于以上兩種算法的優(yōu)勢與不足，并針對本文問題特點，提出了一種混合啟發(fā)式算法——混合粒子群算法(HybridParticleSwarmOptimization,HPSO)。該混合算法首先利用PSO算法進行初步搜索，在其基礎(chǔ)上用NSGA-Ⅱ進行深入的局部搜索，增強其局部搜索能力。另外，微粒群粒子位置編碼可以直接作為NSGA-Ⅱ個體的實數(shù)編碼，速度保持不變，NSGA-Ⅱ編碼也易于轉(zhuǎn)化為微粒群編碼，由此利于種群的進化和優(yōu)勢個體的保留。根據(jù)以上幾點，HPSO算法能夠更好地平衡全局搜索與局部搜索，以獲得質(zhì)量更高的Pareto有效前沿。HPSO算法設(shè)計的流程圖如圖1所示。

圖1　HPSO算法流程圖

3數(shù)值試驗

在前文已經(jīng)提到經(jīng)典的置換流水車間調(diào)度本身是結(jié)構(gòu)簡單但求解復(fù)雜的一類問題，在此類加工系統(tǒng)發(fā)生干擾之后，本文采用反應(yīng)式策略進行干擾應(yīng)對，而反應(yīng)式調(diào)度是在既定的初始加工方案的基礎(chǔ)上，進行干擾應(yīng)對。本文初始方案的產(chǎn)生是由HPSO算法獲得，所以有必要在干擾測試之前進行算法性能的測試。為了驗證本文所提混合算法求解問題的有效性，數(shù)值試驗分為兩部分，第一部分是經(jīng)典問題測試試驗，這部分算例是來自現(xiàn)有文獻中的算例，通過與文獻中的結(jié)果對比，來驗證算法的性能；另外一部分是進行隨機干擾試驗，針對不同的問題規(guī)模隨機產(chǎn)生數(shù)值算例進行干擾測試，通過從解的多樣性和臨近性兩方面來衡量輸出有效解的質(zhì)量。算法采用C語言編程實現(xiàn)；計算機CPU為Intel(R) Core(TM)2 Duo CPU，內(nèi)存為2 GB，主頻為3.00 GHz。

3.1混合算法的測試

利用本文提出的混合啟發(fā)式算法HPSO對現(xiàn)有4篇文獻中出現(xiàn)的經(jīng)典的測試算例進行求解，并與原文獻中的原算法的結(jié)果進行對比(見表1)，從輸出解的質(zhì)量上來比較算法優(yōu)劣。

由表1可以看出，本文的算法可以獲得與原文獻中相同或者比原文更好的解。驗證了本文提出的HPSO算法是一種有效的求解多目標優(yōu)化問題的方法。

表1　現(xiàn)有文獻中的算例與本文算法結(jié)果對比

3.2干擾測試

多目標優(yōu)化算法的求解質(zhì)量一般從有效前沿的多樣性和對理想點的臨近性兩方面來衡量[13]。為了進一步檢驗算法的求解質(zhì)量，從以下6個指標[13]來衡量HPSO和NSGA-Ⅱ的求解質(zhì)量。

(1)ONVG表示非支配解集E中，不同非支配解的數(shù)量，該指標越大說明解越具有多樣性。

(2)CM表示2個算法獲得的有效前沿的相互支配關(guān)系。如果算法的該指標值越小，說明對應(yīng)的算法越不被其他算法獲得的解所支配。

(3)Dave表示最優(yōu)有效前沿到算法獲得的有效前沿中解的最短距離的平均值。該指標越小說明算法獲得的有效前沿臨近性越好，算法的收斂性越好。

(4)Dmax表示最優(yōu)有效前沿到算法獲得的有效前沿中解的最短距離的最大值。評價方法與Dave類似。

(5)TS表示算法有效前沿的分布情況，該指標值越小說明有效前沿中解分布越均勻。

(6)AQ衡量有效前沿在多樣性和臨近性兩方面的平均性能。指標值越小，說明有效前沿的平均性能越好。

為了更好地比較NSGA-Ⅱ和HPSO獲得的解的質(zhì)量，在同一問題規(guī)模下，隨機生成30個加工時間服從均勻分布U[1, 99]的算例。每個算例運行1次。統(tǒng)計30次運算中每個有效前沿指標的平均值(ave)、最大值(max)和最小值(min)，從統(tǒng)計意義上反映了該指標在30次實驗中的平均情況和分布情況。問題規(guī)模設(shè)計原始工件n0=20，40，60和80，和新工件nN=5，10的組合實驗。

表2　數(shù)值運算結(jié)果對比分析

注：表中H表示HPSO； N表示NSGA-Ⅱ。

表2為算法HPSO和NSGA-Ⅱ在解的6個指標衡量下的數(shù)值結(jié)果。從ONVS指標來看，HPSO算法獲得的非支配有效前沿的數(shù)量或多于NSGA-Ⅱ算法，或少于NSGA-Ⅱ算法，且數(shù)量差別不大，二者解的多樣性相當；其次HPSO算法的CM指標總是等于0或者接近0，而NSGA-Ⅱ的該指標值接近于1，說明HPSO獲得的解能絕大多數(shù)地支配由NSGA-Ⅱ獲得的解；從解的臨近性指標Dave和Dmax的ave，max和min 3個角度來看，HPSO獲得的有效前沿比NSGA-Ⅱ更能逼近最優(yōu)有效前沿。HPSO的TS指標值分布在NSGA-Ⅱ的TS值的上下，說明在有些情況下，HPSO獲得的有效前沿解的分布情況較NSGA-Ⅱ算法是比較均勻的。單從多目標優(yōu)化問題解的分布情況TS指標來評價算法，二者是相當?shù)摹６鴱姆从辰獾亩鄻有院团R近性的綜合情況的AQ指標來看，HPSO的綜合性能明顯優(yōu)于NSGA-Ⅱ。綜合以上圖表分析，HPSO雖然在解的多樣性上有時會稍遜色于NSGA-Ⅱ，但HPSO算法能夠獲得更臨近于理想點的Pareto有效前沿，而且在綜合性能上表現(xiàn)較為突出，從而證明了算法求解問題的有效性。

4結(jié)論

針對干擾事件影響下置換流水車間重調(diào)度問題，構(gòu)建了一個同時考慮生產(chǎn)成本和擾動成本的雙目標重調(diào)度模型。鑒于求解初始方案以及重調(diào)度模型的復(fù)雜性，在PSO算法的基礎(chǔ)上引入NSGA-Ⅱ，設(shè)計了一種混合元啟發(fā)式算法——HPSO來求解上述問題。以經(jīng)典目標函數(shù)——生產(chǎn)流程時間為目標制定初始加工方案，一批待加工新工件到達使得初始方案不再最優(yōu)或不可行，對新舊工件進行重調(diào)度，并根據(jù)置換流水車間加工系統(tǒng)的特點，提出了一種新的擾動度量方法——加工資源的位置擾動來進行擾動度量，并將干擾度量引入方案的評價體系中來，同時優(yōu)化原目標和擾動目標，利用雙目標的HPSO算法求得問題的Pareto有效前沿。通過數(shù)值試驗，驗證了HPSO算法是求解多目標優(yōu)化問題的一種有效方法，并且與MOPSO和NSGA-Ⅱ進行比較，從衡量解的多樣性和臨近性的6個指標進行比較分析，驗證了算法求解置換流水車間新工件到達干擾問題的有效性。

在實踐中，因需求的不確定性，企業(yè)經(jīng)常面臨緊急插單的情況，如何提高企業(yè)的盈利能力和保持生產(chǎn)平穩(wěn)的進行是現(xiàn)代生產(chǎn)企業(yè)面臨的實際問題，本文在置換流水車間環(huán)境下，提出了一種針對新工件達到干擾事件的應(yīng)對方法，該方法可以為決策者提供更多高質(zhì)量的決策方案，決策者可以根據(jù)加工系統(tǒng)特點和自身偏好，選擇最優(yōu)的加工方案，提高企業(yè)生產(chǎn)管理的效能；另外，在混合啟發(fā)式算法設(shè)計上，為算法之間的融合提供了一種新的思路，為推動混合算法的發(fā)展進行了初步探索。

國內(nèi)外在生產(chǎn)調(diào)度干擾管理中的應(yīng)用研究還有待進一步加強，特別是加工車間等領(lǐng)域。本文就置換流水車間環(huán)境下新工件到達的情況進行了初步研究，未來進一步的研究方向可集中在：(1)新的擾動度量方式的研究；(2)考慮更為復(fù)雜的干擾事件對置換流水車間的干擾管理問題，如同時發(fā)生的機器故障與新工件到達的組合干擾事件等；(3)構(gòu)建新模型和新算法求解此類干擾模型等都是一些值得研究的方向。

參考文獻

[1]YENISEY M M, YAGMAHAN B. Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends[J]. Omega, 2014, 45: 119-135.

[2]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.

[3]HALL NG, POTTS CN. Rescheduling for job unavailability[J]. Operations Research, 2010, 58(3): 746-755.

[4]王杜娟, 王建軍, 劉春來,等.具有惡化效應(yīng)的新工件到達生產(chǎn)調(diào)度干擾管理[J]. 系統(tǒng)工程理論與實踐, 2015, 35(2): 368-380.

[5]BEN ITAYEF A, LOUKIL T, TEGHEM J. Rescheduling a permutation flowshop problems under the arrival a new set of jobs[C]//39th International Conference on Computers and Industrial Engineering.France: Troyes CEDEX, 2009: 188-192.

[6]劉鋒,王征,王建軍,等. 加工能力受擾的可控排序干擾管理[J]. 系統(tǒng)管理學(xué)報, 2013, 22(4): 505-512.

[7]ZHAO Q, YUAN J. Pareto optimization of rescheduling with release dates to minimize makespan and total sequence disruption[J]. Journal of Scheduling, 2013, 16(3): 253-260.

[8]姜洋, 孫偉, 丁秋雷,等. 考慮行為主體的單機調(diào)度干擾管理模型[J]. 機械工程學(xué)報, 2013, 49(14): 191-198.

[9]WANG S, WANG L, LIU M, et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J]. International Journal of Production Economics, 2013, 145(1): 387-396.

[10]雷德明, 嚴新平. 多目標智能優(yōu)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社,2009.

[11] ZAKARIA Z, PETROVIC S. Genetic algorithms for match-up rescheduling of the flexible manufacturing systems[J]. Computers & Industrial Engineering, 2012, 62(2): 670-686.

[12]王林, 陳璨. 一種基于DE算法和NSGA-Ⅱ 的多目標混合進化算法[J]. 運籌與管理, 2010, 19(6): 58-64.

[13]LI BB, 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.

[14]SELEN WJ, HOTT DD. A mixed-integer goal-programming formulation of the standard flow-shop scheduling problem[J]. Journal of the Operational Research Society, 1986,12(37), 1121-1128.

[15]HO JC, CHANG Y. A new heuristic for the n-job, m-machine flow-shop problem[J]. European Journal of Operational Research, 1991, 52(2): 194-202.

[16]RAJENDRAN C. Heuristics for scheduling in flowshop with multiple objectives[J]. European Journal of Operational Research, 1995, 82(3): 540-555.

[17]LIAO C, YU W, JOE C. Bicriterion scheduling in the two-machine flowshop[J]. Journal of the Operational Research Society, 1997, 48(9): 929-935.

Disruption Management for Permutation Flowshop Problem with New Orders Arrival

Liu Yajing1,Zhao Qinan2,Wang Jianjun1

(1.Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China;2.School of Public Management & Law, Dalian University of Technology, Dalian 116023, China)

Abstract:In Permutation flowshop scheduling, the initial schedule is obtained via minimizing the makespan. A set of new arrival jobs make the initial schedule not optimal or feasible. Initial scheduling should be revised to trade off the original objective and deviation cost, and a bi-objective disruption management model is built up. Given the characteristics of the model and the complication of the problem, with concern of the Particle Swarm Algorithm with strong global search ability and the Pareto solutions with excellent comprehensive properties obtained by the Non-dominated Sorting Genetic Algorithm II(NSGA-Ⅱ), we propose the Hybrid Particle Swarm Optimization algorithm (HPSO) to obtain the (approximate) optimal solutions. By solving bi-objective flow shop problems in classic literatures and randomly generated flowshop problems with new arrival orders, the proposed HPSO outperforms NSGA-II and MOPSO is verified as an effective approach to coping with disruptions.

Key words:disruption management; rescheduling; new orders arrival; Pareto fronts; hybrid algorithm

中圖分類號：TP301.6;TB497

文獻標志碼：A

文章編號：2095-0373(2016)01-0086-07

作者簡介：劉亞凈(1989-),女，碩士研究生，主要從事生產(chǎn)調(diào)度方面的研究。E-mail:lyj20088802@126.com通訊作者：王建軍，教授，博士生導(dǎo)師，主要從事干擾管理、服務(wù)管理方面的研究。E-mail:drwangjj@dlut.edu.cn

基金項目:國家自然科學(xué)基金(71271039)

收稿日期：2015-11-05責任編輯:劉憲福

DOI:10.13319/j.cnki.sjztddxxbzrb.2016.01.16

劉亞凈，趙奇楠,王建軍.置換流水車間新工件到達干擾管理研究[J].石家莊鐵道大學(xué)學(xué)報:自然科學(xué)版,2016,29(1):86-92.