考慮設(shè)備可用性約束的單機(jī)調(diào)度問(wèn)題

王金鳳，陳 璐，楊雯慧

(上海交通大學(xué) 工業(yè)工程與管理系，上海 200240)

傳統(tǒng)調(diào)度方法假設(shè)設(shè)備總是可用的，但在實(shí)際生產(chǎn)過(guò)程中，許多因素會(huì)導(dǎo)致設(shè)備不可用，如更換刀具、設(shè)備檢修、設(shè)備突然故障等情況.當(dāng)這些情況發(fā)生時(shí)，設(shè)備的不可用約束較容易量化，可以通過(guò)定義周期性不可用時(shí)段[1-2]，或通過(guò)定義設(shè)備失效函數(shù)定義不可用約束[3].而當(dāng)設(shè)備中的關(guān)鍵部件發(fā)生可靠性退化而影響工件的加工質(zhì)量、加工速度或加工能耗時(shí)，設(shè)備同樣具有不可用性[4-5].因此，考慮設(shè)備狀態(tài)對(duì)可用性約束的影響對(duì)于生產(chǎn)調(diào)度具有重要的現(xiàn)實(shí)意義.然而，如何量化此類設(shè)備的可用性約束是一個(gè)很大的挑戰(zhàn).在現(xiàn)有文獻(xiàn)中，沒(méi)有統(tǒng)一的方法來(lái)量化設(shè)備狀態(tài)對(duì)可用性的影響，應(yīng)用最廣泛的是利用可靠性來(lái)衡量設(shè)備狀態(tài)，進(jìn)而對(duì)設(shè)備的可用性進(jìn)行量化[6-7].

在現(xiàn)有文獻(xiàn)中，設(shè)備不可用性通常分為單周期不可用、多周期不可用、柔性不可用3類，多數(shù)是以維護(hù)為代表的操作造成的設(shè)備不可用.Lee[8]作為開(kāi)創(chuàng)者，首次在生產(chǎn)調(diào)度問(wèn)題中考慮設(shè)備不可用，考慮單次已知開(kāi)始時(shí)間和持續(xù)時(shí)間的不可用間隔.Kubzin等[9]在考慮設(shè)備單周期不可用時(shí)，假設(shè)其持續(xù)時(shí)間依賴于啟動(dòng)時(shí)間，具有可控長(zhǎng)度.但實(shí)際上，單周期不可用是對(duì)實(shí)際生產(chǎn)情況過(guò)分簡(jiǎn)化的結(jié)果，與現(xiàn)實(shí)情況存在較大差異.Yu等[1]在此類問(wèn)題中引入開(kāi)始時(shí)間和持續(xù)時(shí)間都已知的多周期不可用間隔.蔣凱麗等[2]在模型中考慮具有時(shí)間窗的多周期不可用間隔.但由于影響間隔周期長(zhǎng)短的因素較多，難以準(zhǔn)確計(jì)算.當(dāng)周期過(guò)短時(shí)會(huì)造成資源浪費(fèi)，而周期過(guò)長(zhǎng)又會(huì)導(dǎo)致設(shè)備失效率增加[10].Ahmadi等[11]引入基于狀態(tài)的不可用間隔，并通過(guò)對(duì)比實(shí)驗(yàn)得出采用基于狀態(tài)的不可用間隔更具有現(xiàn)實(shí)應(yīng)用意義的結(jié)論.Yildirim等[12]在研究中提出，當(dāng)可靠性低于臨界閾值時(shí)，需引入單一級(jí)別的不可用間隔.Chen等[13]在此基礎(chǔ)上引入柔性不可用間隔，按照其效果分為3個(gè)級(jí)別：① 將設(shè)備恢復(fù)如新；② 改善部分設(shè)備狀態(tài)；③ 僅將設(shè)備恢復(fù)到失效前的工作狀態(tài).但在上述研究中，設(shè)備失效并沒(méi)有被考慮在模型中.丁珮雯等[14]和Salmasnia等[3]在考慮設(shè)備狀態(tài)的單機(jī)調(diào)度問(wèn)題研究中，也引入了柔性不可用.但以上研究均未考慮由可靠性過(guò)低而引發(fā)的設(shè)備不可用問(wèn)題[15].

本文對(duì)單機(jī)調(diào)度問(wèn)題進(jìn)行了研究，同時(shí)考慮設(shè)備失效和設(shè)備可靠性對(duì)可用性的影響，選用不同類型的維護(hù)作業(yè)對(duì)設(shè)備狀態(tài)進(jìn)行恢復(fù)，建立以最小化總拖期時(shí)間為優(yōu)化目標(biāo)的數(shù)學(xué)規(guī)劃模型，并設(shè)計(jì)開(kāi)發(fā)了遺傳算法(GA)對(duì)問(wèn)題進(jìn)行求解，最后利用算例分析對(duì)算法的有效性及效率進(jìn)行驗(yàn)證.

1 設(shè)備可用性的定義

在可靠性、維修性術(shù)語(yǔ)中，將可用性定義為在要求的外部資源得到保證的前提下，設(shè)備在規(guī)定的條件下和規(guī)定的時(shí)間區(qū)間內(nèi)處于可執(zhí)行規(guī)定功能狀態(tài)的能力.利用設(shè)備可靠性對(duì)“可執(zhí)行規(guī)定功能狀態(tài)的能力”進(jìn)行量化.假設(shè)設(shè)備故障函數(shù)服從Weibull分布，可以表示為[16]

ρ(u)=λβuβ-1

(1)

式中：λ和β分別為Weibull分布的比例參數(shù)和形狀參數(shù)；u為設(shè)備役齡.當(dāng)β>1時(shí)，該過(guò)程為非齊次泊松分布過(guò)程(NHPP)，設(shè)備故障率隨時(shí)間的增長(zhǎng)而逐漸增大.在此過(guò)程中，設(shè)備可靠性R可表示為

(2)

本文提出兩種等級(jí)的預(yù)防性維護(hù)策略：不完全維護(hù) (IPM) 和完全維護(hù) (PPM).IPM僅改善部分設(shè)備狀態(tài)，而PPM將設(shè)備狀態(tài)恢復(fù)如新.設(shè)備可靠性隨加工時(shí)間的演化過(guò)程如圖1所示.可靠性閾值δ作為衡量設(shè)備是否可用的標(biāo)準(zhǔn)，假設(shè)當(dāng)設(shè)備可靠性介于[δ,1]時(shí)，設(shè)備可用；而介于[0,δ)時(shí)，設(shè)備不可用.由圖1可知，工件4和工件7的加工將導(dǎo)致設(shè)備可靠性超過(guò)臨界閾值，因此，必須在這兩個(gè)工件開(kāi)始加工之前進(jìn)行維護(hù).此時(shí)，需要在維護(hù)時(shí)間和維護(hù)效果兩者之間進(jìn)行權(quán)衡，確定維護(hù)級(jí)別(IPM或PPM)，即選擇IPM所需維護(hù)時(shí)間較短，但可靠性改善程度有限，而選擇PPM可以使設(shè)備修復(fù)如新，但是所需維護(hù)時(shí)間較長(zhǎng).

圖1 設(shè)備可靠性和可用性的關(guān)系Fig.1 Machine reliability versus availability

2 模型的建立

在考慮設(shè)備狀態(tài)的單機(jī)調(diào)度問(wèn)題中，需要對(duì)工件集合N中的工件進(jìn)行排序，目標(biāo)是最小化總拖期時(shí)間.兩個(gè)相鄰工件中可以插入一次IPM或PPM以改善設(shè)備狀態(tài).模型假設(shè)包括：① 在0時(shí)刻，所有工件均可加工；② 在加工前，設(shè)備役齡為0；③ 設(shè)備在同一位置只能加工一個(gè)工件，且一個(gè)工件只需加工一次；④ 忽略設(shè)備在加工不同工件之間的準(zhǔn)備時(shí)間；⑤ 在加工過(guò)程中，設(shè)備發(fā)生故障修復(fù)后，被中斷的工件可以繼續(xù)加工，不需要額外的加工時(shí)間.

基于可靠性理論中的最優(yōu)維護(hù)間隔(T*)，設(shè)備可靠性的臨界閾值可表示為

(3)

基于NHPP假設(shè)，工位j上的累積故障次數(shù)可表示為

λ[(ufj)β-(ub1)β]

(4)

式中：ub1=0.

模型的決策變量為

由此建立數(shù)學(xué)模型如下：

(5)

s.t.

(6)

(7)

(8)

tPPMzj+tF(Mj-Mj-1)

(9)

?i∈N,?j∈N

ubj=uf(j-1)(1-θyj-zj),?j∈N

(10)

ufj≥ubj+xijpi,?j∈N

(11)

e-λ[(ufj)β-(ubj)β]≥δ,j∈N

(12)

yj+zj≤1,?j∈N

(13)

(14)

?i∈N,?j∈N

3 算法設(shè)計(jì)

考慮設(shè)備狀態(tài)的單機(jī)調(diào)度問(wèn)題已被學(xué)者證明是NP難問(wèn)題[17]，引入計(jì)算可靠性的非線性約束(約束12)，增加了求解難度.Lingo等商業(yè)求解器只能對(duì)有限規(guī)模的問(wèn)題進(jìn)行計(jì)算.因此，研究采用更為高效的遺傳算法進(jìn)行求解，并通過(guò)C++語(yǔ)言實(shí)現(xiàn).

3.1 編碼與解碼

染色體對(duì)工件加工序列進(jìn)行編碼，圖1中算例的編碼染色體如圖2所示.

圖2 染色體編碼方式Fig.2 Chromosome coding

通過(guò)對(duì)染色體進(jìn)行解碼，確定維護(hù)位置和維護(hù)方式，獲得一個(gè)完整的調(diào)度策略，其解碼算法如算法1所示.

算法1解碼

1.已知各工位j上的待加工工件的序號(hào)、加工時(shí)間以及δ.

2.根據(jù)式(2)，計(jì)算工位j在完成工件加工后的設(shè)備可靠性R.

3.若R≥δ，則yj=zj=0，即表示不需要任何類型的維護(hù).

4.否則，令yj=1,即假設(shè)在工位j上進(jìn)行IPM，并計(jì)算該工位在完成工件加工后的設(shè)備可靠性R′.

5.若R′≥δ，則yj=1,zj=0，即在工位j上進(jìn)行IPM.

6.否則，yj=0,zj=1，即在工位j上進(jìn)行PPM.

7.j++，若j≤|N|，則返回步驟2；否則，繼續(xù)步驟8.

8.將各工位上的維護(hù)操作和工件序列結(jié)合，獲得完整的調(diào)度方案.

利用上述算法對(duì)圖2中的染色體編碼進(jìn)行解碼，獲得一個(gè)完整調(diào)度方案，如圖3所示.

圖3 完整調(diào)度方案Fig.3 A complete schedule for sample problem

3.2 種群初始化

種群規(guī)模的大小會(huì)影響算法的性能及效率，所提算法中，種群規(guī)模Npop=50.首先，采用完全隨機(jī)的方式生成45個(gè)不同的個(gè)體作為初始解，繼而利用最早交貨期啟發(fā)式(EDD)規(guī)則生成5個(gè)較好的初始解，這樣既保證了初始種群的多樣性，同時(shí)能提高算法的收斂速度.

3.3 評(píng)價(jià)與選擇

3.4 交叉與變異

考慮到染色體代表個(gè)體的可行性，故對(duì)實(shí)數(shù)編碼的工序染色體采用兩點(diǎn)式交叉方法.交叉概率范圍一般為0.4～0.9.同樣，為保證染色體的可行性，對(duì)工序染色體采用換位變異方式.在變異過(guò)程中，引入Emmons規(guī)則[18]確定工件的優(yōu)先關(guān)系，縮小搜索空間[19].

設(shè)Bi和Ai分別為在工件i加工前和加工后的工件集合，記為Bi→i和i→Ai.j

變異的發(fā)生需滿足上述優(yōu)先規(guī)則，定義pm為變異概率.算法2詳細(xì)描述了變異過(guò)程.

算法2變異

1.已知各工位j上待加工工件的序號(hào)i、加工時(shí)間pi和交貨期di；

2.對(duì)于任意染色體，隨機(jī)生成(0，1)之間的數(shù)a；

3.若a>pm，則該染色體不進(jìn)行變異，i++,返回2；

4.否則，隨機(jī)生成兩個(gè)滿足條件j

3.5 算法流程

完整算法流程可見(jiàn)算法3.

算法3遺傳算法

1.已知算法參數(shù)Npop，Gmax，pc和pm.

2.初始化第1代種群，解碼后計(jì)算適應(yīng)度值，得到最優(yōu)個(gè)體π*和最差個(gè)體ω，并將π*的染色體序列復(fù)制給ω.

3.基于輪盤(pán)賭選擇法在種群中選取兩條染色體作為父代.

4.對(duì)父代進(jìn)行交叉操作，得到子代.

5.對(duì)子代進(jìn)行突變操作，得到新的子代.

6.對(duì)新的子代染色體解碼后，計(jì)算其適應(yīng)度值，得到當(dāng)前代最優(yōu)個(gè)體π，最差個(gè)體ω，將 π的染色體序列復(fù)制給ω，并更新全局最優(yōu)個(gè)體π*.

7.g++，若g≤Gmax，則返回3；否則，繼續(xù)8.

8.返回最優(yōu)個(gè)體π*.

其中：g為當(dāng)前代數(shù)；Gmax為最大迭代次數(shù)；pc為交叉概率；π*為最優(yōu)個(gè)體；π為當(dāng)前代最優(yōu)個(gè)體；ω為當(dāng)前代最差個(gè)體.

4 算例驗(yàn)證與分析

4.1 小規(guī)模算例驗(yàn)證

為證明遺傳算法的有效性，將遺傳算法所求的解與商業(yè)求解器Lingo所求的最優(yōu)解進(jìn)行比較.考慮8種不同規(guī)模的問(wèn)題，分別在每種規(guī)模下生成10個(gè)算例.設(shè)置Lingo求解時(shí)限為 5 400 s.兩種解的比較如表1所示.其中，OLin和OGA分別為L(zhǎng)ingo求解器和GA所求解的目標(biāo)值；tCPU為運(yùn)算時(shí)間.

由表1可知，在小于8個(gè)工件的算例中，GA不僅得到了最優(yōu)解，而且在求解時(shí)間上明顯優(yōu)于Lingo.當(dāng)工件數(shù)量增加時(shí)，Lingo求解器無(wú)法在限定的時(shí)間內(nèi)得到最優(yōu)解，此時(shí)GA得到的最優(yōu)解優(yōu)于Lingo在規(guī)定時(shí)間內(nèi)得到的最優(yōu)解.因此，遺傳算法的有效性得以驗(yàn)證.

表1 小規(guī)模算例實(shí)驗(yàn)結(jié)果Tab.1 Results of small-scale instants

4.2 中、大規(guī)模算例驗(yàn)證

為了評(píng)估不同類型的維護(hù)作業(yè)對(duì)調(diào)度策略的影響，首先對(duì)GA進(jìn)行修改，得到以下兩種算法：

(1) GA-IPM：對(duì)任意一個(gè)工位j，令zj=0，此時(shí)算法只考慮IPM.

(2) GA-PPM：對(duì)任意一個(gè)工位j，令yj=0，此時(shí)算法只考慮PPM.

將第3節(jié)中提出的GA所求的解作為基準(zhǔn)解，分別計(jì)算GA-IPM和GA-PPM所求解的偏差：

(15)

(16)

式中：OTPM，OIPM和OPPM分別為GA、GA-IPM和GA-PPM所求解的目標(biāo)值，其結(jié)果如表2所示.

表2 不同GA在中、大規(guī)模算例中的表現(xiàn)Tab.2 Performance of different GAs on medium and large scales

由表2可知，同時(shí)考慮兩種維護(hù)作業(yè)對(duì)減少總拖期時(shí)間具有一定的優(yōu)越性，這種優(yōu)越性隨問(wèn)題規(guī)模的增大而減小，最終趨于穩(wěn)定，相比于GA-IPM和GA-PPM的改善分別維持在25%和5%左右.另外，與GA-IPM相比，GA-PPM表現(xiàn)更優(yōu).由此可見(jiàn)，雖然PPM耗時(shí)長(zhǎng)，但能更顯著降低設(shè)備的失效風(fēng)險(xiǎn)，從而達(dá)到縮短總拖期時(shí)間的效果.

4.3 敏感性分析

下文將分別針對(duì)可靠性閾值和設(shè)備狀態(tài)改善因子進(jìn)行敏感性分析.

4.3.1可靠性閾值對(duì)調(diào)度決策的影響 考慮3個(gè)級(jí)別的可靠性閾值，分別為δ=0.5，δ=0.6，δ=0.78.其中，δ=0.78是通過(guò)式(3)計(jì)算出來(lái)的臨界閾值.在其他參數(shù)設(shè)置保持不變的情況下，對(duì)比不同可靠性閾值對(duì)調(diào)度決策的影響，如圖4和5所示.其中：tW為總拖期時(shí)間；L為維護(hù)次數(shù).

由圖4可知，隨著可靠性閾值的增加，總拖期時(shí)間增大.問(wèn)題規(guī)模越大，這種變化趨勢(shì)變得更加明顯.造成這種現(xiàn)象的原因?yàn)椋S著可靠性閾值的增加，設(shè)備需要更頻繁的維護(hù)作業(yè)，使得設(shè)備可靠性能夠保持在閾值之上.而當(dāng)維護(hù)作業(yè)時(shí)間增加時(shí)，總拖期時(shí)間也增加.然而，當(dāng)設(shè)備可靠性閾值降低時(shí)，設(shè)備在加工時(shí)的狀態(tài)較差，將會(huì)導(dǎo)致加工工件的質(zhì)量降低.

圖4 不同可靠性閾值下的總拖期時(shí)間Fig.4 Total tardiness at different reliability thresholds

由圖5可知，當(dāng)可靠性閾值增加時(shí)，采用IPM的次數(shù)增加，采用PPM的次數(shù)減少.原因是IPM能夠以較短的耗時(shí)將設(shè)備可靠性恢復(fù)到閾值之上，而PPM則在恢復(fù)效率(改善效果與維護(hù)時(shí)長(zhǎng)的比值)上稍顯劣勢(shì).由此可見(jiàn)，在可靠性閾值增加時(shí)，調(diào)度決策更加側(cè)重維護(hù)的效率.

圖5 不同可靠性閾值下的維護(hù)次數(shù)Fig.5 Times of maintenance at different reliability thresholds

4.3.2狀態(tài)改善因子對(duì)調(diào)度決策的影響 考慮3種不同程度的狀態(tài)改善因子，分別是θ=0.3，θ=0.4，和θ=0.5.在其他參數(shù)設(shè)置保持不變的情況下，對(duì)比不同狀態(tài)改善因子對(duì)調(diào)度決策的影響，如圖6和7所示.

由圖6可知，當(dāng)改善因子增加時(shí)，總拖期時(shí)間相應(yīng)降低，這種變化趨勢(shì)隨著問(wèn)題規(guī)模的增大而變得更加明顯.這是由于在IPM耗時(shí)不變的前提下，隨著改善因子的增加，IPM的效率提高，節(jié)省了維護(hù)時(shí)間，從而減少了總拖期時(shí)間.

圖6 不同改善因子下總拖期時(shí)間的變化曲線Fig.6 Total tardiness with different improvement factors

由圖7可知，當(dāng)改善因子增加時(shí)，采用IPM的次數(shù)增加，PPM的次數(shù)減少至0.

圖7 不同改善因子下的維護(hù)次數(shù)Fig.7 Times of maintenance with different improvement factors

以上結(jié)果表明，在實(shí)際生產(chǎn)調(diào)度決策時(shí)，可以通過(guò)提高維護(hù)效率，提高可靠性改善效果來(lái)降低生產(chǎn)交付的壓力.

5 結(jié)語(yǔ)

本文研究了某轉(zhuǎn)子車間內(nèi)單臺(tái)設(shè)備的生產(chǎn)調(diào)度問(wèn)題，考慮設(shè)備可用性約束，以及不同級(jí)別的維護(hù)作業(yè)，優(yōu)化目標(biāo)為最小化總拖期時(shí)間.優(yōu)化模型中通過(guò)可靠性來(lái)表征設(shè)備的可用性約束，減少當(dāng)設(shè)備可靠性下降時(shí)對(duì)加工質(zhì)量的影響.設(shè)計(jì)開(kāi)發(fā)了遺傳算法對(duì)模型進(jìn)行優(yōu)化求解.實(shí)驗(yàn)結(jié)果表明，所提方法能夠有效量化設(shè)備可用性對(duì)生產(chǎn)調(diào)度的影響，并能夠合理地選擇不同類型的維護(hù)作業(yè)，以減少總拖期時(shí)間.靈敏度分析為車間內(nèi)實(shí)際生產(chǎn)調(diào)度提供決策支持，具有實(shí)際應(yīng)用價(jià)值.后續(xù)研究將把該方法應(yīng)用于更復(fù)雜的生產(chǎn)環(huán)境中，如并行機(jī)、流水線生產(chǎn)等.