朱傳軍 馮詩健 張超勇 金亮亮 王林琳

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

0 引言

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

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

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

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

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

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

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

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

(1)

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

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

(2)

可靠度函數(shù)為

(3)

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

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

(4)

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

1.2 極大似然估計法

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

(5)

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

(6)

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

(7)

(8)

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

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

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

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

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

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

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

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

3 遺傳禁忌搜索算法

3.1 遺傳算法

3.1.1編碼

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

表1 染色體解析表

3.1.2解碼

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

3.1.3交叉算子

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

Pc(i,j)=

(15)

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

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

3.1.4變異操作

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

3.1.5增強種群多樣性算子

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

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

3.1.6選擇算子

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

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

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

(16)

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

(17)

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

(5)若R

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

3.2 禁忌搜索算法

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

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

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

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

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

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

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

圖1 同一機器上交換弧

圖2 同一工件上的交換弧

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

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

3.2.2禁忌表和禁忌長度

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

3.2.3精華解機制

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

3.2.4移動選擇

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

3.2.5終止準(zhǔn)則

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

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

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

圖3 遺傳禁忌算法框架圖

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

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

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

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

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

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

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

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

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

表2 算例結(jié)果

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

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

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

圖5 威布爾分布擬合圖

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

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

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

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

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

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

6 結(jié)論

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