喻明讓,張英杰,陳琨,高瑞,張定

(西安交通大學機械工程學院,710049,西安)

?

考慮調(diào)整時間的作業(yè)車間調(diào)度與預防性維修集成方法

喻明讓,張英杰,陳琨,高瑞,張定

(西安交通大學機械工程學院,710049,西安)

為了解決作業(yè)車間調(diào)度理論研究中兩種常見但卻不符合生產(chǎn)實際的理想假設所帶來的問題,提出了一種考慮調(diào)整時間的作業(yè)車間調(diào)度與預防性維修集成方法。首先利用遺傳算法得到單獨考慮調(diào)整時間時的最優(yōu)初始調(diào)度方案,然后依據(jù)初始調(diào)度方案中各機器的任務分配情況以及該機器的故障概率分布自適應確定其預防性維修方案,同時依據(jù)插入的預防性維修時間間隔采用右移策略對初始調(diào)度方案進行調(diào)整,最終得到優(yōu)化的作業(yè)車間調(diào)度與預防性維修集成方案。通過對經(jīng)典調(diào)度基準實例進行擴展來構造測試實例,進而驗證所提方法的有效性。實驗結果表明:單獨考慮調(diào)整時間不僅能夠提高車間調(diào)度性能,還能夠使得依據(jù)機器的運行時間和故障概率分布得到的預防性維修方案更加合理,從而達到提高生產(chǎn)效率并降低預防性維修成本的目的,對于實際生產(chǎn)具有一定的指導意義。

作業(yè)車間調(diào)度;調(diào)整時間;預防性維修;故障概率分布

車間調(diào)度問題是組合優(yōu)化問題理論研究與生產(chǎn)實際相結合的典范,對車間調(diào)度問題的研究不僅能夠在理論上推進優(yōu)化理論的發(fā)展,而且能夠提高實際生產(chǎn)的效率,其中作業(yè)車間調(diào)度問題(JSP)由于具有典型性而受到研究者們的廣泛關注。JSP定義如下[1]:n個工件在m臺機器上加工,每個工件包含多個具有先后順序的工序,各工件的工藝路線不盡相同,各工序采用的機器及其在該機器上的加工時間已知。要求在滿足各工件工序順序約束的前提下,確定各工件在每臺機器上的加工順序及加工開始時間,以使某些性能指標最優(yōu)。

JSP問題早已被證明是非確定性多項式難題[2],為了便于求解,研究者在建立JSP模型時往往通過一些理想假設來對問題進行簡化,其中最常見的兩種理想假設[3-4]:①機器在任何時刻都是可用的;②工序的調(diào)整時間是可以忽略的,或者將調(diào)整時間合并為工序的加工時間。

毫無疑問,以上假設使JSP求解過程得到簡化,并因此產(chǎn)生了豐富的理論研究成果[5-7]。然而,這些假設往往并不符合車間生產(chǎn)實際。例如,生產(chǎn)過程中的機器故障使得機器在調(diào)度區(qū)間內(nèi)會出現(xiàn)不可用時段,從而導致已有調(diào)度方案不在最優(yōu)甚至是不可行的;另一方面,在許多實際生產(chǎn)中,調(diào)整時間相對于加工時間來說是不可以忽略的,而將調(diào)整時間合并為工序的加工時間則會導致調(diào)度性能惡化。因此,車間調(diào)度理論研究中這兩種常見但不符合生產(chǎn)實際的理想假設,使得車間調(diào)度的理論研究成果難以很好地應用于實際生產(chǎn)[8]。

機器故障是導致調(diào)度資源環(huán)境發(fā)生變化的主要原因之一,并且機器故障可能造成重大的生產(chǎn)損失。為了減少可能發(fā)生的機器故障,需要定期對機器進行停機檢修,即預防性維修(PM)。對機器進行預防性維修時會造成生產(chǎn)的停滯,占用一定的生產(chǎn)時間。在進行生產(chǎn)調(diào)度時若不考慮機器的預防性維修,則有可能因為機器發(fā)生故障造成不必要的損失。因此,車間生產(chǎn)調(diào)度與預防性維修之間存在密切的聯(lián)系,有必要對二者進行集成研究。另外,由于機器運行過程中,只有加工時間才會造成機器的退化,進而引起機器故障[9]。在大多數(shù)車間調(diào)度的研究中經(jīng)常假設調(diào)整時間是可以忽略的或者將調(diào)整時間合并為工序的加工時間,因此導致依據(jù)機器故障概率分布確定的預防性維修計劃不夠合理。

調(diào)整時間主要指的是更換夾具、模具以及清理工作臺、切屑、廢液等消耗的時間。文獻[10]對考慮調(diào)整時間的車間調(diào)度問題進行了綜述,認為調(diào)整時間可以分為與順序無關的調(diào)整時間和與順序相關的調(diào)整時間。前者指的是工序的調(diào)整時間只與該工序所屬的工件以及所選擇的機器有關;后者指的是工序的調(diào)整時間與該工序所屬的工件以及該機器上一個加工任務所屬的工件有關。文獻[11]進一步將調(diào)整時間劃分為可提前發(fā)生的調(diào)整時間和不可提前發(fā)生的調(diào)整時間,若調(diào)整工作可以在工件到達該機器前進行則稱該調(diào)整是可提前發(fā)生的,否則為不可提前發(fā)生的。本文主要考慮可提前發(fā)生且順序無關的調(diào)整時間對作業(yè)車間調(diào)度與預防性維修集成研究的影響。

考慮機器預防性維修的車間調(diào)度即在調(diào)度方案中插入一定的空閑時間間隔(PM時間)以進行機器的預防性維修。盡管已有的研究中對考慮預防性維修的車間調(diào)度進行了較多的研究,但是大多數(shù)此類研究中都忽略調(diào)整時間或?qū)⒄{(diào)整時間作為加工時間的一部分來進行考慮[12-14]。如前所述,這將導致依據(jù)機器故障概率分布確定的預防性維修周期與實際不相符,因此本文對考慮調(diào)整時間的作業(yè)車間調(diào)度與預防性維修集成問題進行研究,從而使車間調(diào)度的理論研究更加符合實際生產(chǎn),同時達到提高生產(chǎn)效率并降低預防性維修成本的目的。

1 必要性分析

圖1 作業(yè)車間調(diào)度與預防性維修集成中考慮調(diào)整時間與否的對比結果

在預防性維修的研究中,依據(jù)機器的故障概率分布確定預防性周期是最常采用的方法。假設圖1a與圖1b分別是將調(diào)整時間合并為加工時間以及將調(diào)整時間單獨考慮的調(diào)度甘特圖(僅以機器M1上的任務為例)。假設依據(jù)機器M1的故障概率分布計算得到每隔20個單位時間M1的故障概率就會大于所設定的閾值,即需要進行預防性維修(一般假設故障概率大于設定的閾值時機器很可能發(fā)生故障,需要進行預防性維修[14]),且一次預防性維修需要持續(xù)5個單位時間,則將調(diào)整時間合并為工序加工時間以及單獨考慮調(diào)整時間的預防性維修與調(diào)度集成方案,如圖1c和圖1d所示。由圖1對比結果可知,當單獨考慮調(diào)整時間時,插入預防性維修時間間隔的數(shù)量和位置更加精確,能夠有效地提高生產(chǎn)效率(最大完工時間),同時降低了預防性維修成本(預防性維修次數(shù))。因此,有必要在進行作業(yè)車間調(diào)度與預防性維修集成研究時單獨考慮調(diào)整時間。

2 機器故障描述

對機器故障的研究一般將機器故障分為故障信息完全未知、故障信息完全已知以及故障信息部分已知3類。對于故障信息完全未知的機器故障主要采用經(jīng)驗估計的方法進行固定的周期性預防性維修;對于故障信息完全已知的機器故障則可直接在已知的故障發(fā)生時刻前進行預防性維修。實際上大多數(shù)生產(chǎn)中所面臨的機器故障屬于故障信息部分已知的情況,即可以依據(jù)機器的歷史數(shù)據(jù)得到機器故障的概率分布。本文研究是針對已知機器故障概率分布的情況來進行的,選擇以指數(shù)分布為例來描述機器故障的概率分布。假設各機器故障概率獨立且同分布,各機器進行一次預防性維修所需要的時間相同(在實際應用中需要依據(jù)各機器歷史運行數(shù)據(jù)進行確定)。同時,假設進行預防性維修后機器故障概率重置為0,則機器故障的指數(shù)分布描述如下

(1)

3 作業(yè)車間調(diào)度與預防性維修集成方法

本文將作業(yè)車間調(diào)度與預防性維修集成分為兩個階段。首先單獨考慮調(diào)整時間生成優(yōu)化的初始調(diào)度方案,然后依據(jù)初始調(diào)度方案中各機器的任務安排情況以及機器的故障概率分布自適應確定各機器的預防性維修計劃。同時,由于插入預防性維修時間間隔,初始調(diào)度方案也需要進行適當?shù)恼{(diào)整。本文采用右移策略對受影響的工序進行調(diào)整以保證調(diào)度方案總是可行的。

3.1 初始調(diào)度方案生成方法

如前所述,JSP屬于典型的NP-hard問題,因此采用近似算法在可接受的時間內(nèi)尋求問題的近似最優(yōu)解成為主要的研究方法[2]。如遺傳算法、粒子群優(yōu)化、蟻群算法、模擬退化算法以及禁忌搜索算法等都在一定程度上解決了某一類型的車間調(diào)度問題,其中GA算法由于良好的搜索能力而受到廣泛關注。本文選擇遺傳算法來求解JSP,從而得到優(yōu)化的初始調(diào)度方案。遺傳算法求解JSP的研究較為成熟,不同的是本文在進行作業(yè)車間調(diào)度時對調(diào)整時間進行單獨考慮,因此其解碼方法需要進行調(diào)整。圖2給出了采用遺傳算法求解JSP的流程,接下來對其關鍵步驟進行簡要介紹。

圖2 遺傳算法求解JSP流程

(1)編碼。本文采用基于工序的編碼,基于工序的編碼具有任意交換編碼位置仍然能夠得到可行調(diào)度的特點。表1給出了一個3×3的JSP實例(時間為無量綱單位時間),則其一個可能的染色體編碼為[2 1 2 3 3 1 3 2 1],其中基因位的數(shù)字表示其對應的工件編號,該數(shù)字在染色體中第幾次出現(xiàn)表示該工件的第幾個工序,如第1個3表示J3的第1道工序,第2個1表示J1的第2道工序等。

(2)解碼。間隙擠壓法能夠保證解碼得到活動調(diào)度,此處對其進行改進使其能夠應用于考慮調(diào)整時間的JSP優(yōu)化求解。由于本文考慮的調(diào)整時間與順序無關,直接將工序的開始時間加上其相應的調(diào)整時間以及加工時間即可得到該工序的完工時間。

表1 一個3×3的JSP實例

間隙擠壓解碼算法的其他操作可參考文獻[15]。

針對JSP的適應度函數(shù)為最大完成時間,則適應度值越小的個體越適合生存,采用輪盤賭的方式進行選擇操作,交叉方法采用文獻[15]提出的基于工序編碼的交叉算子,變異采用互換變異。采用遺傳算法求解JSP問題的研究較為成熟,此處不做過多描述,詳細操作可以參考文獻[15]。

3.2 作業(yè)車間調(diào)度與預防性維修集成

在得到作業(yè)車間調(diào)度的初始方案之后,進行車間調(diào)度集成與預防性維修的流程如下。

Step 2: 由式(1)以及機器Mk的故障概率閾值Ptk得到機器的累積加工時間閾值

(2)

Step 3: 依據(jù)初始調(diào)度方案S中機器Mk上的任務分配情況及其累積加工時間閾值tak結合預防性維修策略,自適應確定機器Mk的預防性維修計劃,即在機器Mk的調(diào)度區(qū)間內(nèi)自適應插入一定數(shù)量的預防性維修時間間隔。同時,由于預防性維修間隔時間的插入,調(diào)度方案S也需要及時地進行調(diào)整。即將機器Mk上直接受影響的工序以及其他機器上間接受影響的工序都采用右移策略進行調(diào)整,并以調(diào)整后的調(diào)度方案S′代替初始調(diào)度方案S,同時令k=k+1。

Step 4: 判斷k≤m是否成立,其中m表示調(diào)度系統(tǒng)中機器的數(shù)量,若成立,轉到Step 2;否則,退出循環(huán),輸出最終的調(diào)度方案(集成了預防性維修方案的調(diào)度方案)。

在上述流程Step 3里提到采用預防性維修策略自適應確定機器Mk的預防性維修計劃,就是當預防性維修與車間調(diào)度集成時,進行預防性維修必須考慮車間調(diào)度任務的執(zhí)行情況,同時車間調(diào)度方案也需要根據(jù)預防性維修計劃進行相應的調(diào)整。為了盡可能降低預防性維修活動對調(diào)度執(zhí)行的干擾,預防性維修活動應盡可能被安排在該機器某一工序完成之后或者另一工序開始之前進行。

假設在調(diào)度開始時各機器的累積加工時間及故障概率均為0,令Oki和Ok(i+1)分別表示機器Mk上相鄰的兩個工序,且工序Ok(i+1)在Oki之后進行加工。令taki和tak(i+1)分別表示工序Oki和Ok(i+1)加工完成時機器Mk的累積加工時間,tak表示機器Mk的累積加工時間閾值,則當taki≤tak且tak(i+1)>tak時,在工序Oki后插入一次預防性維修活動。此時,若工序Oki和Ok(i+1)之間不存在足夠的空閑時間來進行預防性維修,則需要將機器Mk上的工序Ok(i+1)及其以后的工序進行右移,同時將其他機器上受影響的工序也進行相應的右移。

針對表1所示調(diào)度實例,其最優(yōu)調(diào)度方案如圖3所示(其中時間為無量綱單位時間,下同)。假設各機器的tMTBF都為5個單位時間,且進行一次預防性維修需要1個單位時間。設定的機器故障概率閾值為0.7。由式(2)得到tak≤6.019 9,向下取整得到tak=6,即各機器累積加工時間達到6個單位時間時需要進行預防性維修。依據(jù)上述方法得到考慮預防性維修的作業(yè)車間調(diào)度甘特圖如圖4所示,其中M1和M2在累積加工時間為6個單位時間時進行了預防性維修,而M3在累積加工時間為5個單位時間時進行了預防性維修。由于預防性維修活動的插入,最大完工時間增加了1個單位時間。

圖3 表1實例的最優(yōu)調(diào)度甘特圖

4 實驗結果與分析

本節(jié)通過對經(jīng)典調(diào)度基準實例進行擴展來構造測試實例,進而驗證本文所提方法的有效性。選擇Fisher等提出的FT06[16]作為基礎實例,FT06加工數(shù)據(jù)如表2所示。首先構造各工序的調(diào)整時間,假設調(diào)整時間是順序無關的,且取值范圍為[1,3],隨機生成一個6×6的二維矩陣,矩陣的元素為1到3之間的整數(shù),得到的擴展FT06加工數(shù)據(jù)如表3所示。

表2 FT06初始加工數(shù)據(jù)

表3 擴展后的FT06加工數(shù)據(jù)

依據(jù)表3中的數(shù)據(jù),首先采用前述遺傳算法分別生成不考慮調(diào)整時間和考慮調(diào)整時間的調(diào)度方案,其中不考慮調(diào)整時間指的是將調(diào)整時間合并為工序的加工時間來進行調(diào)度優(yōu)化。兩種方法得到的最優(yōu)調(diào)度甘特圖分別如圖5和圖6所示,其中考慮調(diào)整時間比不考慮調(diào)整時間得到的最優(yōu)調(diào)度方案的最大完工時間縮短了7個單位時間(約9.46%)。

圖5 合并調(diào)整時間的調(diào)度甘特圖

圖6 考慮調(diào)整時間的調(diào)度甘特圖

由于本文方法重點強調(diào)在預防性維修與車間調(diào)度集成研究中單獨考慮調(diào)整時間的重要性,而機器故障的概率分布模型等不是本文研究的重點。此處假設各機器故障獨立且服從相同的指數(shù)分布,各機器平均無故障時間間隔tMTBF都為33個單位時間。對各機器進行一次預防性維修的時間為2個單位時間,一次預防性維修的成本為200元,各機器故障概率閾值設定為0.6。那么,由式(2)計算得到各機器的累積加工時間閾值為30.24個單位時間,為安全起見,向下取整得到ta=30。采用第3節(jié)所述方法,分別以圖5和圖6的調(diào)度方案作為初始調(diào)度方案進行預防性維修計劃的制定,同時對初始調(diào)度方案進行適當?shù)恼{(diào)整。最終得到的車間調(diào)度與預防性維修集成方案分別如圖7和圖8所示,詳細的對比結果如表4所示。

圖7 不考慮調(diào)整時間的車間調(diào)度及預防性維修方案

圖8 考慮調(diào)整時間的車間調(diào)度及預防性維修方案

從表4結果可以發(fā)現(xiàn),當單獨考慮調(diào)整時間時,車間調(diào)度方案的最大完工時間有一定程度的降低,意味著生產(chǎn)效率得到提高,同時預防性維修成本也得到大幅度的降低。證明了在作業(yè)車間調(diào)度與預防性維修集成研究中單獨考慮調(diào)整時間的重要性,也說明本文所提方法是有效的,其對實際生產(chǎn)具有一定的指導意義。

表4 兩種方案的預防性維修與車間調(diào)度集成對比結果

5 結 論

通過分析車間調(diào)度與預防性維修之間的內(nèi)在聯(lián)系,以及依據(jù)車間調(diào)度進行預防性維修時單獨考慮調(diào)整時間的必要性,本文提出了一種考慮調(diào)整時間的作業(yè)車間調(diào)度與預防性維修集成方案。該方案重點強調(diào)了在預防性維修與車間調(diào)度集成研究中單獨考慮調(diào)整時間的重要性。首先利用遺傳算法得到優(yōu)化的初始調(diào)度方案,然后依據(jù)初始調(diào)度方案中各機器的任務分配情況以及該機器的故障概率分布自適應地確定各機器的預防性維修方案。同時,由于預防性維修需要占用一定的調(diào)度時間,采用右移策略對初始調(diào)度方案進行調(diào)整以保證調(diào)度方案的可行性。最后通過對經(jīng)典調(diào)度實例的擴展構造了本文的測試實例,證明了在預防性維修與車間調(diào)度集成研究中單獨考慮調(diào)整時間能夠提高生產(chǎn)效率,并大幅度降低預防性維修成本,從而驗證了本文所提方法的有效性。

[1]PENG Yunfang.Job shop scheduling with sequence-dependent setup times based on constraint programming approach [C]∥Proceedings of 2012 3rd International Asia Conference on Industrial Engineering and Management Innovation.Berlin, Germany: Springer, 2013: 835-841.

[2]GEN M, LIN L.Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey [J].Journal of Intelligent Manufacturing, 2014, 25(5): 849-866.

[3]SHA D Y, HSU C Y.A hybrid particle swarm optimization for job shop scheduling problem [J].Computers & Industrial Engineering, 2006, 51(4): 791-808.

[4]LEI Deming, WU Zhiming.Crowding measure based multiobjective evolutionary algorithm for job shop scheduling [J].The International Journal of Advanced Manufacturing Technology, 2006, 30(1/2): 112-117.

[5]ZHANG Chaoyong, LI Peigen, RAO Yunqing, et al.A new hybrid GA/SA algorithm for the job shop scheduling problem [M]∥Evolutionary Computation in Combinatorial Optimization.Berlin, Germany: Springer, 2005: 246-259.

[6]NOWICKI E, SMUTNICKI C.An advanced tabu search algorithm for the job shop problem [J].Journal of Scheduling, 2005, 8(2): 145-159.

[7]VELA C, VARELA R, GONZALEZ M.Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times [J].Journal of Heuristics, 2010, 16(2): 139-165.

[8]SHEN Liji.A tabu search algorithm for the job shop problem with sequence dependent setup times [J].Computers & Industrial Engineering, 2014, 78: 95-106.

[9]ZHANG Yingjie, GE Liling.Reliability analysis of machining systems by considering system cost [EB/OL].[2014-10-24].http:∥www.tandfonline.com/doi/abs/10.1080 /0951192X.2014.914630.

[10]ALLAHVERDI A, GUPTA J N D, ALDOWAISAN T.A review of scheduling research involving setup considerations [J].Omega, 1999, 27(2): 219-239.

[11]ALLAHVERDI A, NG C T, CHENG T C E, et al.A survey of scheduling problems with setup times or costs [J].European Journal of Operational Research, 2008, 187(3): 985-1032.

[12]LU C C, LIN S W, YING K C.Robust scheduling on a single machine to minimize total flow time [J].Computers & Operations Research, 2012, 39(7): 1682-1691.

[13]TANG Lixin, ZHANG Yanyan.Parallel machine scheduling under the disruption of machine breakdown [J].Industrial & Engineering Chemistry Research, 2009, 48(14): 6660-6667.

[14]HE Wei, SUN Dihua.Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies [J].The International Journal of Advanced Manufacturing Technology, 2013, 66(1/2/3/4): 501-514.

[15]張超勇.基于自然啟發(fā)式算法的作業(yè)車間調(diào)度問題理論與應用研究 [D].武漢: 華中科技大學, 2007.

[16]FISHER H, THOMPSON G L.Probabilistic learning combinations of local job-shop scheduling rules [J].Industrial Scheduling, 1963, 3(2): 225-251.

(編輯 杜秀杰)

Job-Shop Scheduling and Preventive Maintenance Considering Setup Time

YU Mingrang, ZHANG Yingjie, CHEN Kun, GAO Rui, ZHANG Ding

(School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

To close the gap between scheduling theory and practice from unrealistic assumptions, a method for integrating job-shop scheduling (JSP) and preventive maintenance (PM) is proposed.The original scheduling plan is generated by genetic algorithm, where the setup time is taken into account.Then the preventive maintenance plan for each machine according to the assigned tasks of the machine and its failure probability distribution is adaptively determined.The original schedule meanwhile should be slightly modified by right-shifting strategy according to inserted time intervals for PM activities, thus the optimal integrated plan of JSP and PM is obtained.A classical benchmark instance is extended and used to verify the effectiveness of the proposed method.The comparative results show that the explicit consideration of the setup time improves the scheduling performances and makes the PM plan generated according to the machining time and failure probability distribution much more reasonable.

job-shop scheduling problem; setup time; preventive maintenance; distribution of failure probability

2014-11-24。 作者簡介:喻明讓(1986—),男,博士生; 張英杰(通信作者),男,教授,博士生導師。 基金項目:國家科技重大專項資助項目(2012ZX04010-071)。

時間:2015-03-18

http:∥www.cnki.net/kcms/detail/61.1069.T.20150318.0940.003.html

10.7652/xjtuxb201506003

TH166

A

0253-987X(2015)06-0016-06