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

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

(西安交通大學(xué)機(jī)械工程學(xué)院,710049,西安)

?

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

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

(西安交通大學(xué)機(jī)械工程學(xué)院,710049,西安)

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

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

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

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

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

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

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

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

1 必要性分析

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

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

2 機(jī)器故障描述

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

(1)

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

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

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

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

圖2 遺傳算法求解JSP流程

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

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

表1 一個3×3的JSP實(shí)例

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

通過分析車間調(diào)度與預(yù)防性維修之間的內(nèi)在聯(lián)系,以及依據(jù)車間調(diào)度進(jìn)行預(yù)防性維修時單獨(dú)考慮調(diào)整時間的必要性,本文提出了一種考慮調(diào)整時間的作業(yè)車間調(diào)度與預(yù)防性維修集成方案。該方案重點(diǎn)強(qiáng)調(diào)了在預(yù)防性維修與車間調(diào)度集成研究中單獨(dú)考慮調(diào)整時間的重要性。首先利用遺傳算法得到優(yōu)化的初始調(diào)度方案,然后依據(jù)初始調(diào)度方案中各機(jī)器的任務(wù)分配情況以及該機(jī)器的故障概率分布自適應(yīng)地確定各機(jī)器的預(yù)防性維修方案。同時,由于預(yù)防性維修需要占用一定的調(diào)度時間,采用右移策略對初始調(diào)度方案進(jìn)行調(diào)整以保證調(diào)度方案的可行性。最后通過對經(jīng)典調(diào)度實(shí)例的擴(kuò)展構(gòu)造了本文的測試實(shí)例,證明了在預(yù)防性維修與車間調(diào)度集成研究中單獨(dú)考慮調(diào)整時間能夠提高生產(chǎn)效率,并大幅度降低預(yù)防性維修成本,從而驗(yà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)度問題理論與應(yīng)用研究 [D].武漢: 華中科技大學(xué), 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—),男,博士生; 張英杰(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國家科技重大專項(xiàng)資助項(xiàng)目(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