朱傳軍 馮詩(shī)健 張超勇 金亮亮 王林琳

1.湖北工業(yè)大學(xué)機(jī)械工程學(xué)院,武漢,4300682.華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,武漢,430074 3.紹興文理學(xué)院機(jī)械與電氣工程學(xué)院,紹興,312000

0 引言

開放車間調(diào)度問(wèn)題(open shop scheduling problem,OSSP)是最基本的調(diào)度問(wèn)題之一[1]。相較于流水車間調(diào)度問(wèn)題(flow-shop scheduling problem, FSP)和作業(yè)車間調(diào)度問(wèn)題(jop-shop scheduling problem, JSP),開放車間調(diào)度問(wèn)題具有更大的可行解空間、更高的復(fù)雜度。機(jī)器數(shù)量極大影響開放車間調(diào)度的計(jì)算復(fù)雜度,當(dāng)有三臺(tái)或更多的機(jī)器時(shí),它就是一個(gè)NP-hard問(wèn)題。

目前在開放車間調(diào)度領(lǐng)域研究最多的性能指標(biāo)是最小化最大完工時(shí)間。高亮等[2]以最小化最大完工時(shí)間為性能指標(biāo),采用粒子群優(yōu)化算法求解了傳統(tǒng)開放車間的調(diào)度問(wèn)題,并獲得了滿意的結(jié)果。王軍強(qiáng)等[3]提出一種基于多樣性增強(qiáng)的自適應(yīng)遺傳算法,設(shè)計(jì)了多種進(jìn)化算子,提高了遺傳算法的進(jìn)化效率和進(jìn)化質(zhì)量,求得了Taillard算例庫(kù)60個(gè)算例的最優(yōu)解。

實(shí)際的開放車間調(diào)度中,每個(gè)設(shè)備都可能發(fā)生故障,因此需要對(duì)設(shè)備進(jìn)行維護(hù),防止設(shè)備失效導(dǎo)致的生產(chǎn)中斷。目前主流的設(shè)備預(yù)防性維護(hù)的方式包括傳統(tǒng)的周期性維護(hù)和非周期性維護(hù)。PASURA等[4]采用傳統(tǒng)的周期性維護(hù)方式對(duì)給定儀器設(shè)備進(jìn)行維護(hù)。宋文家等[5]研究柔性作業(yè)車間調(diào)度問(wèn)題時(shí),在模型中加入了對(duì)設(shè)備的非周期預(yù)防性維護(hù)。SHEIKHALISHAHI等[6]研究了帶有非周期預(yù)防性維護(hù)及人工失誤的開放車間調(diào)度問(wèn)題。相較于周期性維護(hù),非周期預(yù)防性維護(hù)更為靈活、更貼合實(shí)際,并能有效避免設(shè)備欠維護(hù)或過(guò)度維護(hù)。目前的研究考慮設(shè)備預(yù)防性維護(hù)的開放車間調(diào)度問(wèn)題較少涉及,相關(guān)研究起步較晚,因此,如何將預(yù)防性維護(hù)集成到開放車間調(diào)度優(yōu)化中是一個(gè)開放的問(wèn)題。

采用非周期預(yù)防性維護(hù)時(shí),不同的生產(chǎn)環(huán)境和設(shè)備的故障率分布函數(shù)通常不同。工業(yè)中,通常采用指數(shù)分布來(lái)描述故障發(fā)生的概率;制造車間中,機(jī)械設(shè)備和電子元件等的故障率一般服從威布爾分布。威布爾分布遵循統(tǒng)計(jì)學(xué)規(guī)律,可以有效反映調(diào)度問(wèn)題中機(jī)器運(yùn)行時(shí)間和狀態(tài)對(duì)設(shè)備役齡的影響[7]。

開放車間調(diào)度問(wèn)題和作業(yè)車間調(diào)度問(wèn)題的求解具有很大的相似性。張超勇等[8]提出一種進(jìn)化禁忌混合算法,并設(shè)計(jì)了IPOX交叉算子和禁忌搜索的新鄰域結(jié)構(gòu),取得了車間調(diào)度問(wèn)題的高質(zhì)量解。CAMINO等[9]針對(duì)具有模糊作業(yè)時(shí)間和柔性交貨期的作業(yè)車間調(diào)度問(wèn)題,采用進(jìn)化禁忌搜索算法取得了調(diào)度問(wèn)題的滿意解。具有良好全局搜索能力的遺傳算法和具有優(yōu)秀局部搜索能力的禁忌搜索算法相結(jié)合可產(chǎn)生更均衡的搜索算法,因此本文借鑒求解作業(yè)車間調(diào)度問(wèn)題的優(yōu)秀算法,選擇混合遺傳禁忌搜索算法來(lái)求解考慮設(shè)備預(yù)防性維護(hù)的開放車間調(diào)度問(wèn)題。

1 設(shè)備預(yù)防性維護(hù)

1.1 服從威布爾分布的概率密度函數(shù)

采用二參數(shù)威布爾分布描述一般設(shè)備的故障規(guī)律,判斷其是否達(dá)到給定的故障率閾值,進(jìn)行預(yù)防性維護(hù),二參威布爾分布的率密度函數(shù)為

(1)

式中,β、θ分別為形狀參數(shù)和尺度參數(shù),β>0,θ>0;t為機(jī)器役齡。

β決定曲線形狀,θ決定曲線橫軸和縱軸的尺度。服從二參威布爾分布的積故障函數(shù)為

(2)

可靠度函數(shù)為

(3)

則設(shè)備達(dá)到可靠度閾值時(shí)的役齡為

t=θ(-lnR(t))i/β

(4)

使用過(guò)程中,設(shè)備狀態(tài)不斷變化,役齡也會(huì)縮短,既使進(jìn)行了維護(hù),設(shè)備還是不能回到最初的狀態(tài),因此采用役齡退回因子pm來(lái)描述這一過(guò)程的變化,經(jīng)過(guò)預(yù)防性維護(hù)后設(shè)備的實(shí)際役齡變?yōu)?1-pm)t。

1.2 極大似然估計(jì)法

采用極大似然估計(jì)法求解二參威布爾分布中的β和θ[10-11]。服從二參威布爾分布的似然函數(shù)為

(5)

通過(guò)兩邊取對(duì)數(shù),可得對(duì)數(shù)似然函數(shù):

(6)

繼而分別對(duì)β和θ求偏導(dǎo),得如下公式:

(7)

(8)

式中,n為歷史故障數(shù)據(jù)的數(shù)量;ti為第i個(gè)歷史故障的實(shí)際役齡。

將歷史故障數(shù)據(jù)代入式(7)、式(8),利用牛頓迭代算法對(duì)其進(jìn)行求解,即可求出參數(shù)β和θ。

1.3 設(shè)備的預(yù)防性維護(hù)

在生產(chǎn)調(diào)度和機(jī)器維護(hù)的集成問(wèn)題上,設(shè)備維護(hù)與工件調(diào)度不能發(fā)生沖突,即設(shè)備維護(hù)只能安排在工件加工前后。為解決這一問(wèn)題,本文采用動(dòng)態(tài)安排設(shè)備維護(hù)的方法[5],具體過(guò)程如下:

(1)首先按照單純的開放車間調(diào)度進(jìn)行決策,決定每個(gè)工序的加工順序以及每個(gè)機(jī)器上工件的加工順序。

(2)安排每道工序前,先計(jì)算出每臺(tái)加工機(jī)器的當(dāng)前役齡。如果完成該道工序后的機(jī)器故障率超過(guò)所給故障率閾值(役齡退回因子)pm,則在該工序前安排一次預(yù)防性維護(hù);否則,安排下一道工序。

(3)安排預(yù)防性維護(hù)后,重新計(jì)算機(jī)器完成當(dāng)前工序后的運(yùn)行時(shí)間。

(4)重復(fù)步驟(2)和(3),直到安排完所有的工序。

2 考慮預(yù)防性維護(hù)的開放車間調(diào)度數(shù)學(xué)模型

優(yōu)化目標(biāo)為

minCmax

(9)

約束條件如下:

Yii′k+Yi′ik=1 ?i≠i′∈N,?k∈M

(10)

Xijj′+Xij′j=1 ?i∈N,?j≠j′∈M

(11)

Si′j-Sij≥tij+dkZij-L(1-Yii′k)

(12)

?k,j∈M,?i≠i′∈N

Sij′-Sij>tij-L(1-Xijj′)

(13)

?i∈N,?j≠j′∈M

Cmax≥Sij+tij+Zijdk

(14)

?i∈N,?j,k∈M

其中,Cmax為最大完工時(shí)間;i、i′為工件編號(hào);j、j′、k為機(jī)器編號(hào);N為工件集合,N={1,2,…,n};n為工件總數(shù);M為機(jī)器集合,M={1,2,…,m};m為機(jī)器總數(shù);Yii′k表示機(jī)器k上的零件i′和零件i的加工順序,零件i′在零件i之前加工時(shí),Yii′k=0,否則Yii′k=1;Xijj′表示零件i上的第j道工序和第j′道工序的加工順序,第j道工序在第j′道工序之前加工時(shí),Xijj′=1,否則Xijj′=0;Sij為零件i的第j道工序的開始加工時(shí)間;tij為工件i的第j道工序的加工時(shí)間;dk為機(jī)器k一次預(yù)防性維護(hù)所需時(shí)間;Zij表示工件i的第j道工序后面是否安排預(yù)防性維護(hù),如果安排,則Zij=1,否則Zij=0;L為一個(gè)很大的正整數(shù)。傳統(tǒng)的開放車間調(diào)度問(wèn)題中,一個(gè)工件的工序數(shù)量與設(shè)備數(shù)量一致,同一工件的各工序在不同的設(shè)備上完成。

3 遺傳禁忌搜索算法

3.1 遺傳算法

3.1.1編碼

編碼是設(shè)計(jì)遺傳算法的關(guān)鍵。編碼須考慮合法性、可行性、有效性,以及對(duì)問(wèn)題解空間表征的完全性。本文采用基于工序的編碼,以確保解碼總能得到可行調(diào)度,并涵蓋所有的問(wèn)題解空間。表1所示為染色體(4, 8, 0, 5, 1, 3, 7, 2, 6)中的元素對(duì)應(yīng)的工件編號(hào)和加工機(jī)器編號(hào)。

表1 染色體解析表

3.1.2解碼

本文采用插入式貪婪解碼算法[12]對(duì)染色體進(jìn)行解碼,該算法可以確保染色體解碼后產(chǎn)生主動(dòng)調(diào)度。插入式貪婪解碼算法操作方法如下:遍歷染色體上的基因,找到與該基因?qū)?yīng)工序的加工機(jī)器,然后在該機(jī)器上搜索該工序最早的加工時(shí)間,并將該工序安排在此時(shí)間開始。

3.1.3交叉算子

自適應(yīng)交叉算子是一種改進(jìn)的交叉算子,它根據(jù)種群中個(gè)體的適應(yīng)度動(dòng)態(tài)調(diào)整交叉概率和交叉方式,以提高算法的性能和收斂速度。種群中的個(gè)體適應(yīng)度較大時(shí),交叉概率減小,避免該個(gè)體的優(yōu)良基因被破壞,算法早熟收斂到局部最優(yōu);個(gè)體適應(yīng)度較小時(shí),交叉概率增大,以促進(jìn)探索更大的搜索空間。交叉概率的計(jì)算公式為

Pc(i,j)=

(15)

式中,Pc(i,j)為個(gè)體i和個(gè)體j的交叉概率;hmax、havg分別為當(dāng)前種群的最大適應(yīng)度和平均適應(yīng)度;h(i,j)為與最優(yōu)個(gè)體相交叉的個(gè)體的適應(yīng)度;K1、K2為交叉概率修正系數(shù)(常數(shù)),K1,K2∈(0,1)且K1≠K2。

本文對(duì)交叉策略進(jìn)行適當(dāng)改進(jìn),具體操作方法如下:首先規(guī)定2個(gè)交叉?zhèn)€體P1和P2,定義大小與P1和P2相同的空白個(gè)體S1和S2,將當(dāng)前種群中的最優(yōu)個(gè)體作為P1,在剩下的個(gè)體中選出一個(gè)作為P2。交叉操作時(shí),如果交叉對(duì)象的交叉概率較大,則將P2染色體上少部分的基因映射至容器S2對(duì)應(yīng)的基因序號(hào)上,并將P1中的基因(不包含S2上已有的)依次插入到S2的空白位置。種群中的最優(yōu)個(gè)體P1則進(jìn)行與P2相反的操作,即將P1染色體上大部分的基因映射到容器S1對(duì)應(yīng)的基因位,將P2中的基因(不包含S1上已有的)依次插入到S1的空白位置。對(duì)S1和S2進(jìn)行解碼并比較S1和S2的適應(yīng)度,將其中更優(yōu)良的個(gè)體放入新的種群。經(jīng)數(shù)據(jù)檢驗(yàn),該交叉方式提高了遺傳算法的穩(wěn)定性。

3.1.4變異操作

變異操作通過(guò)引入一些新的個(gè)體來(lái)增強(qiáng)種群的多樣性。盡管變異操作在一定程度上具有局部搜索的作用,但作用有限。本文采用的變異策略是隨機(jī)選擇染色體中的2個(gè)基因并交換它們的位置。

3.1.5增強(qiáng)種群多樣性算子

算法迭代進(jìn)化的過(guò)程中,調(diào)度的解會(huì)逐漸向最優(yōu)解或近似最優(yōu)解靠攏,因此個(gè)體差異逐漸減小,種群多樣性不斷降低,可能導(dǎo)致算法陷入局部最優(yōu)。增強(qiáng)種群的多樣性可以增大算法的搜索空間,避免算法過(guò)早陷入局部最優(yōu)。文獻(xiàn)[3]基于隨機(jī)二分法原理設(shè)計(jì)的主動(dòng)式種群多樣性判定算子降低了對(duì)鄰域局部解集的搜索能力,但增強(qiáng)了種群的多樣性。在增強(qiáng)種群多樣性的同時(shí),本文采用局部搜索能力更好的禁忌搜索算法。

實(shí)現(xiàn)種群多樣性增強(qiáng)算子時(shí),需要引入多樣性判定閾值w,將初始種群、交叉種群和變異種群合并,并判斷合并后的種群的多樣性是否達(dá)到多樣性指標(biāo)判定閾值。如果種群的多樣性達(dá)到多樣性指標(biāo)判定閾值,則不進(jìn)行任何操作;否則,對(duì)種群中的冗雜個(gè)體進(jìn)行隨機(jī)二分洗牌操作,以增強(qiáng)種群的多樣性。

3.1.6選擇算子

本文采用輪盤賭的方式從多樣性判定后的合并種群中選擇出子代種群。假設(shè)初始種群數(shù)量為P,則合并種群數(shù)量W=3P。輪盤具體操作如下:

(1)計(jì)算合并種群Wp中個(gè)體i的適應(yīng)度h(i),i=1,2,…,W。

(2)計(jì)算種群中個(gè)體i被選中進(jìn)入下一代群體中的概率pi:

(16)

(3)計(jì)算個(gè)體i的累積概率qi。計(jì)算第i個(gè)個(gè)體的累積概率時(shí),需要將第1個(gè)個(gè)體到第i個(gè)個(gè)體的所有概率累加:

(17)

(4)生成的隨機(jī)數(shù)R在[0, 1]區(qū)間內(nèi)服從均勻分布。

(5)若R

(6)判斷下一代種群中的個(gè)體數(shù)量是否小于P,如果小于,則重復(fù)步驟(4)、步驟(5),反之,則結(jié)束輪盤賭操作。

3.2 禁忌搜索算法

3.2.1鄰域結(jié)構(gòu)設(shè)計(jì)

在解決開放車間調(diào)度問(wèn)題時(shí),禁忌搜索是一種非常有效的局部搜索算法。鄰域結(jié)構(gòu)的設(shè)計(jì)是禁忌搜索中非常關(guān)鍵的一個(gè)步驟,它決定了搜索空間的大小和搜索質(zhì)量。本文采用的鄰域結(jié)構(gòu)的設(shè)計(jì)思路如下:

首先找出當(dāng)前調(diào)度的關(guān)鍵路徑,其次將關(guān)鍵路徑劃分為關(guān)鍵塊,最后對(duì)關(guān)鍵塊內(nèi)的工序進(jìn)行調(diào)整,產(chǎn)生鄰域解,本文采用NOWICKI等[13]提出的N5鄰域結(jié)構(gòu)。以保證所有移動(dòng)產(chǎn)生的解不會(huì)變差。該鄰域結(jié)構(gòu)的具體操作如下:

(1)如果第一個(gè)關(guān)鍵塊包含2個(gè)以上的工序,則只交換塊尾的2個(gè)工序;如果最后一個(gè)關(guān)鍵塊包含2個(gè)以上的工序,則只交換塊首相連的2個(gè)工序;如果該關(guān)鍵塊只包含2個(gè)工序,則只交換這2個(gè)工序。

(2)首尾關(guān)鍵塊以外的關(guān)鍵塊如果有3個(gè)或3個(gè)以上的工序,則交換塊首和塊尾的2個(gè)工序。

(3)如果關(guān)鍵塊只包含1個(gè)工序,則不進(jìn)行任何操作。

開放車間調(diào)度問(wèn)題中,對(duì)同一工件的不同工序或同一機(jī)器的不同工序均沒(méi)有固定的先后要求,因此在調(diào)整關(guān)鍵塊時(shí),需要考慮的兩種情況,如圖1、圖2所示,其中,PJ(n)、SJ(n)分別為某個(gè)工件的工序n(n=i,j)的緊前工序和緊后工序,PM(n)、SM(n)分別為某臺(tái)機(jī)器完成的工序n的緊前工序和緊后工序。

圖1 同一機(jī)器上交換弧

圖2 同一工件上的交換弧

如圖1所示,對(duì)于由同一個(gè)機(jī)器完成的工序i和j,鄰域結(jié)構(gòu)的交換方式可分為4種:①交換弧(i,j);②同時(shí)交換弧(i,j)和(PJ(i),j);③同時(shí)交換弧(i,j)和(i,SJ(i));④同時(shí)交換弧(i,j)、(i,SJ(i))、(PJ(i),j)。

如圖2所示,對(duì)于屬于同一個(gè)工件的工序i和j,鄰域交換方式可分為4種:①交換弧(i,j);②同時(shí)交換弧(i,j)和(PM(j),j);③同時(shí)交換弧(i,j)和(i,SM(i));④同時(shí)交換弧(i,j)、(i,SM(i))、(PM(j),j)。

3.2.2禁忌表和禁忌長(zhǎng)度

禁忌表用于記錄鄰域解產(chǎn)生過(guò)程中已交換過(guò)的弧,避免禁忌搜索的重復(fù)搜索。實(shí)際運(yùn)用中,禁忌表的長(zhǎng)度可以不固定,但禁忌表太短可能導(dǎo)致可行解得不到充分搜索,陷入局部解,太長(zhǎng)則會(huì)影響到算法的效率。因此,本文采用在給定區(qū)間內(nèi)隨機(jī)取值的方法確定禁忌表的長(zhǎng)度。

3.2.3精華解機(jī)制

本文采用的精華解機(jī)制[8]操作如下:在禁忌搜索的過(guò)程中,如果發(fā)現(xiàn)比當(dāng)前解更好的解,則將其加入精華解集。算法運(yùn)行給定的最大未改進(jìn)代數(shù)后,若未出現(xiàn)更優(yōu)解,則從精華解集中取出解,將其作為當(dāng)前解,并清空禁忌表,重新進(jìn)行禁忌搜索。

3.2.4移動(dòng)選擇

如果某次移動(dòng)產(chǎn)生的解優(yōu)于當(dāng)前解,但該次移動(dòng)處于禁忌狀態(tài)時(shí),則對(duì)其進(jìn)行豁免并解禁。如果所有的移動(dòng)都處于禁忌狀態(tài),則從所有被禁忌的移動(dòng)中隨機(jī)選擇一個(gè),并將其解禁。

3.2.5終止準(zhǔn)則

算法運(yùn)行給定代數(shù)或找到最優(yōu)解時(shí)終止。

3.3 混合遺傳算法和禁忌搜索算法

遺傳算法和禁忌搜索算法融合的關(guān)鍵在于編碼的相互轉(zhuǎn)化。本文中的遺傳算法采用基于工序的編碼方式,該種編碼方式可以保證父輩優(yōu)良的基因在遺傳進(jìn)化的過(guò)程中被子代繼承,禁忌搜索則采用的是基于析取圖的編碼方式。目前,基于析取圖的編碼與基于工序的編碼的相互轉(zhuǎn)換已在作業(yè)車間調(diào)度中得到應(yīng)用[8]。在開放車間調(diào)度中,基于工序的編碼和主動(dòng)調(diào)度的析取圖編碼之間也可以進(jìn)行相護(hù)轉(zhuǎn)換。為了更清晰地表述遺傳算法和禁忌搜索算法的混合,給出了遺傳禁忌搜索算法的簡(jiǎn)化框架,如圖3所示。

圖3 遺傳禁忌算法框架圖

4 算法的時(shí)間復(fù)雜度分析

遺傳禁忌搜索算法由遺傳算法和禁忌搜索算法組合而成,每個(gè)算法部分又由多種算子組成。因此整體的時(shí)間復(fù)雜度分析依靠對(duì)各個(gè)算子的分析,并將這些組成部分中的時(shí)間復(fù)雜度最大值作為算法的時(shí)間復(fù)雜度。

遺傳算法的復(fù)雜度與初始種群數(shù)量P、工件數(shù)量N、機(jī)器數(shù)量M相關(guān)。在遺傳算法中,初始種群生成算子的時(shí)間復(fù)雜度為O(NPM),主動(dòng)調(diào)度解碼的時(shí)間復(fù)雜度為O(N2PM),自適應(yīng)交叉的時(shí)間復(fù)雜度為O(NPM),變異算子的時(shí)間復(fù)雜度為O(P)。

種群多樣性增強(qiáng)的算子中,多樣性判斷算子的時(shí)間復(fù)雜度為O(W2NM)。選擇算子與工件數(shù)量和機(jī)器數(shù)量無(wú)關(guān),其時(shí)間復(fù)雜度為O(WP)。

禁忌搜索算法的時(shí)間復(fù)雜度是不斷變化的,它與關(guān)鍵路徑長(zhǎng)度Kp、關(guān)鍵模塊個(gè)數(shù)Kn、關(guān)鍵模塊長(zhǎng)度Kl、禁忌表長(zhǎng)度Tl、禁忌搜索代數(shù)Gt、初始種群數(shù)量P、工件數(shù)量N以及機(jī)器數(shù)量M有關(guān),因此需要根據(jù)實(shí)際問(wèn)題的特性來(lái)確定。本文中,禁忌搜索算法的時(shí)間復(fù)雜度取其在變化過(guò)程的最大值O(NPMGt)。

從整體算法的角度來(lái)看,需要綜合考慮各個(gè)參數(shù)對(duì)遺傳禁忌搜索算法時(shí)間復(fù)雜度的影響。但從實(shí)際問(wèn)題的特性來(lái)看,本文所提遺傳禁忌搜索算法的時(shí)間復(fù)雜度主要由遺傳算法的解碼復(fù)雜度、多樣性增強(qiáng)復(fù)雜度和禁忌搜索算法的復(fù)雜度決定。

5 計(jì)算結(jié)果與分析

本文算法使用C++語(yǔ)言編程,計(jì)算機(jī)為Intel I5-6300HQ多核的個(gè)人計(jì)算機(jī),算法參數(shù)設(shè)置如下:初始種群規(guī)模P= 30;交叉概率修正系數(shù)K1=0.75,K2=0.99;變異概率Pr=0.05;多樣性判定閾值w=0.95;禁忌表長(zhǎng)Tl在區(qū)間[8,12]之間隨機(jī)取值;禁忌代數(shù)Gt=200;最大未改進(jìn)代數(shù)Tn=10。

為驗(yàn)證本文所提算法有效性,實(shí)驗(yàn)案列采用Taillard[14]系列OSP標(biāo)準(zhǔn)測(cè)試實(shí)例的40個(gè)實(shí)例(4×4、5×5、7×7、10×10的實(shí)例各10個(gè)),將本文提出的遺傳禁忌搜索(GATS)算法、貓群優(yōu)化[15](CSO)算法、蝙蝠群優(yōu)化(BA_OS)算法[16]相比較,運(yùn)算結(jié)果見表2,其中,t為GATS算法求得最優(yōu)解的運(yùn)行時(shí)間。

表2 算例結(jié)果

由表2可以看出GATS算法和BA_OS算法在求解單純的調(diào)度問(wèn)題時(shí)均能求得所有算例的最優(yōu)解,CSO算法能求出大部分算例的最優(yōu)解,這驗(yàn)證了所提算法的有效性和穩(wěn)定性,能用來(lái)求解該類復(fù)雜的調(diào)度問(wèn)題。圖4是實(shí)例10×10的算例1的最優(yōu)調(diào)度甘特圖。

圖4 實(shí)例10×10 的算例1的最優(yōu)調(diào)度甘特圖

本文選取實(shí)例7×7的算例1,并在該算例中加入了預(yù)防性維護(hù)這一過(guò)程。將每臺(tái)設(shè)備的歷史故障數(shù)據(jù)代入最大似然估計(jì)法的函數(shù),在MATLAB上利用牛頓迭代算法仿真獲得威布爾分布函數(shù)的形狀參數(shù)θ和尺度參數(shù)β。如圖5所示,歷史故障數(shù)據(jù)沿一條直線均勻分布,表明收集的故障數(shù)據(jù)符合威布爾分布,因此可以使用服從威布爾分布的故障率函數(shù)模型對(duì)設(shè)備的故障時(shí)間進(jìn)行預(yù)測(cè)。表3所示為OSP模型7×7的算例1求解得到的設(shè)備維護(hù)相關(guān)數(shù)據(jù),設(shè)備的可靠度閾值為0.85。

圖5 威布爾分布擬合圖

表3 實(shí)例7×7的算例1的設(shè)備維護(hù)相關(guān)參數(shù)

利用遺傳禁忌搜索算法對(duì)該帶預(yù)防性維護(hù)的調(diào)度模型進(jìn)行求解,非周期預(yù)防性維護(hù)的結(jié)果如下:機(jī)器M1、M2、M5、M6的維護(hù)次數(shù)為2,機(jī)器M3的維護(hù)次數(shù)為3,機(jī)器M4、M7的維護(hù)次數(shù)為1;總維護(hù)次數(shù)ψ為13;每臺(tái)機(jī)器的平均維護(hù)次數(shù)ν為1.85;加工某個(gè)工序時(shí),機(jī)器超過(guò)可靠度閾值進(jìn)行加工的次數(shù)即維護(hù)不及時(shí)次數(shù)δ為0;最大完工時(shí)間T為468 s。

非周期預(yù)防性維護(hù)與周期性維護(hù)的最大區(qū)別是:非周期性維護(hù)通過(guò)擬合分析機(jī)器故障歷史數(shù)據(jù)來(lái)判斷下次維護(hù)的時(shí)間,保證機(jī)器一直在可靠度范圍內(nèi)正常運(yùn)轉(zhuǎn);周期性維護(hù)按照固定周期進(jìn)行維護(hù),由于沒(méi)有故障歷史數(shù)據(jù)的支持,因此容易出現(xiàn)機(jī)器的過(guò)度維護(hù)或欠維護(hù)。過(guò)度維護(hù)會(huì)導(dǎo)致資源的浪費(fèi),而欠維護(hù)會(huì)導(dǎo)致機(jī)器可能發(fā)生故障停工,引起不必要的損失。

表4所示為不同周期維護(hù)下的結(jié)果,為保證結(jié)果的一般性,分別選取閾值附近、閾值以下和閾值以上的5組數(shù)據(jù)進(jìn)行對(duì)比分析。由表4可以看出,周期性維護(hù)的周期過(guò)短時(shí),設(shè)備的維護(hù)次數(shù)顯著增大,調(diào)度時(shí)間延長(zhǎng)。周期性維護(hù)的周期過(guò)長(zhǎng)時(shí),雖然工件完工時(shí)間變短,但設(shè)備處于欠維護(hù)狀態(tài)的次數(shù)明顯增多。圖6所示為在設(shè)備預(yù)防性維護(hù)下,該算例所得到的滿意調(diào)度方案。

圖6 實(shí)例7×7的算例1 的維護(hù)調(diào)度甘特圖

表4 周期性維護(hù)結(jié)果

6 結(jié)論

本文根據(jù)實(shí)際生產(chǎn)車間的運(yùn)行場(chǎng)景,介紹了一種考慮設(shè)備預(yù)防性維護(hù)的開放車間調(diào)度模型,并提出一種混合遺傳禁忌搜索算法求解該問(wèn)題。對(duì)所提遺傳禁忌搜索算法的遺傳編碼和解碼、改進(jìn)交叉和變異操作,以及禁忌搜索算法的鄰域結(jié)構(gòu)進(jìn)行了設(shè)計(jì),得到了一種搜索能力更均衡的混合算法。以最小化最大完工時(shí)間為目標(biāo),將所提算法用于求解開放車間調(diào)度問(wèn)題的基準(zhǔn)問(wèn)題和帶設(shè)備預(yù)防性維護(hù)的開放車間調(diào)度問(wèn)題,獲得了開放車間調(diào)度問(wèn)題基準(zhǔn)實(shí)例問(wèn)題的最優(yōu)解和帶設(shè)備預(yù)防性維護(hù)開放車間調(diào)度問(wèn)題的滿意解。預(yù)防性維護(hù)下,調(diào)度車間的維護(hù)更加靈活有效且符合實(shí)際。實(shí)際生產(chǎn)車間中存在許多不確定的問(wèn)題,并且可能涉及多個(gè)性能指標(biāo)的求解,未來(lái)工作將開展考慮設(shè)備預(yù)防性維護(hù)的不確定性和多目標(biāo)開放車間調(diào)度問(wèn)題。