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

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

?

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

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

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

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

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

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

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

毫無疑問,以上假設(shè)使JSP求解過程得到簡(jiǎn)化,并因此產(chǎn)生了豐富的理論研究成果[5-7]。然而,這些假設(shè)往往并不符合車間生產(chǎn)實(shí)際。例如,生產(chǎn)過程中的機(jī)器故障使得機(jī)器在調(diào)度區(qū)間內(nèi)會(huì)出現(xiàn)不可用時(shí)段,從而導(dǎo)致已有調(diào)度方案不在最優(yōu)甚至是不可行的;另一方面,在許多實(shí)際生產(chǎn)中,調(diào)整時(shí)間相對(duì)于加工時(shí)間來說是不可以忽略的,而將調(diào)整時(shí)間合并為工序的加工時(shí)間則會(huì)導(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ī)器故障,需要定期對(duì)機(jī)器進(jìn)行停機(jī)檢修,即預(yù)防性維修(PM)。對(duì)機(jī)器進(jìn)行預(yù)防性維修時(shí)會(huì)造成生產(chǎn)的停滯,占用一定的生產(chǎn)時(shí)間。在進(jìn)行生產(chǎn)調(diào)度時(shí)若不考慮機(jī)器的預(yù)防性維修,則有可能因?yàn)闄C(jī)器發(fā)生故障造成不必要的損失。因此,車間生產(chǎn)調(diào)度與預(yù)防性維修之間存在密切的聯(lián)系,有必要對(duì)二者進(jìn)行集成研究。另外,由于機(jī)器運(yùn)行過程中,只有加工時(shí)間才會(huì)造成機(jī)器的退化,進(jìn)而引起機(jī)器故障[9]。在大多數(shù)車間調(diào)度的研究中經(jīng)常假設(shè)調(diào)整時(shí)間是可以忽略的或者將調(diào)整時(shí)間合并為工序的加工時(shí)間,因此導(dǎo)致依據(jù)機(jī)器故障概率分布確定的預(yù)防性維修計(jì)劃不夠合理。

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

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

1 必要性分析

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

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

2 機(jī)器故障描述

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

(1)

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

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

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

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

圖2 遺傳算法求解JSP流程

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

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

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

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

針對(duì)JSP的適應(yīng)度函數(shù)為最大完成時(shí)間,則適應(yīng)度值越小的個(gè)體越適合生存,采用輪盤賭的方式進(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ī)器的累積加工時(shí)間閾值

(2)

Step 3: 依據(jù)初始調(diào)度方案S中機(jī)器Mk上的任務(wù)分配情況及其累積加工時(shí)間閾值tak結(jié)合預(yù)防性維修策略,自適應(yīng)確定機(jī)器Mk的預(yù)防性維修計(jì)劃,即在機(jī)器Mk的調(diào)度區(qū)間內(nèi)自適應(yīng)插入一定數(shù)量的預(yù)防性維修時(shí)間間隔。同時(shí),由于預(yù)防性維修間隔時(shí)間的插入,調(diào)度方案S也需要及時(shí)地進(jìn)行調(diào)整。即將機(jī)器Mk上直接受影響的工序以及其他機(jī)器上間接受影響的工序都采用右移策略進(jìn)行調(diào)整,并以調(diào)整后的調(diào)度方案S′代替初始調(diào)度方案S,同時(shí)令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)度集成時(shí),進(jìn)行預(yù)防性維修必須考慮車間調(diào)度任務(wù)的執(zhí)行情況,同時(shí)車間調(diào)度方案也需要根據(jù)預(yù)防性維修計(jì)劃進(jìn)行相應(yīng)的調(diào)整。為了盡可能降低預(yù)防性維修活動(dòng)對(duì)調(diào)度執(zhí)行的干擾,預(yù)防性維修活動(dòng)應(yīng)盡可能被安排在該機(jī)器某一工序完成之后或者另一工序開始之前進(jìn)行。

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

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

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

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

本節(jié)通過對(duì)經(jīng)典調(diào)度基準(zhǔn)實(shí)例進(jìn)行擴(kuò)展來構(gòu)造測(cè)試實(shí)例,進(jìn)而驗(yàn)證本文所提方法的有效性。選擇Fisher等提出的FT06[16]作為基礎(chǔ)實(shí)例,FT06加工數(shù)據(jù)如表2所示。首先構(gòu)造各工序的調(diào)整時(shí)間,假設(shè)調(diào)整時(shí)間是順序無關(guān)的,且取值范圍為[1,3],隨機(jī)生成一個(gè)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)整時(shí)間和考慮調(diào)整時(shí)間的調(diào)度方案,其中不考慮調(diào)整時(shí)間指的是將調(diào)整時(shí)間合并為工序的加工時(shí)間來進(jìn)行調(diào)度優(yōu)化。兩種方法得到的最優(yōu)調(diào)度甘特圖分別如圖5和圖6所示,其中考慮調(diào)整時(shí)間比不考慮調(diào)整時(shí)間得到的最優(yōu)調(diào)度方案的最大完工時(shí)間縮短了7個(gè)單位時(shí)間(約9.46%)。

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

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

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

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

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

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

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

5 結(jié) 論

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

時(shí)間: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