考慮設(shè)備周期性維護的流水車間生產(chǎn)調(diào)度優(yōu)化算法

張思源，陸志強＋，崔維偉

（1．同濟大學 機械與能源工程學院，上海 201804；2．上海交通大學 工業(yè)工程與物流管理系，上海 200240）

0 引言

流水車間調(diào)度廣泛應用于實際生產(chǎn)制造中，是一類經(jīng)典的組合優(yōu)化問題，自Johnson于1954年提出兩階段流水線車間的最優(yōu)調(diào)度規(guī)則之后，該問題受到學者們的廣泛關(guān)注。傳統(tǒng)的流水線調(diào)度理論假設(shè)機器在調(diào)度期內(nèi)總是可用的，但是隨著機器的老化，發(fā)生故障的概率不斷增大，需要對機器進行定期或不定期的維護，從而造成機器的不可用性。在此實際背景下，考慮生產(chǎn)調(diào)度與設(shè)備維護的相互影響，對兩者進行聯(lián)合建模與優(yōu)化，更加貼近車間的實際情況。

已有流水車間調(diào)度與維護相結(jié)合的文獻中，根據(jù)是否考慮機器的預防性維護，可將其大致分為兩類：①設(shè)備故障率服從指數(shù)分布，調(diào)度期內(nèi)不需要預防性維護；②調(diào)度期內(nèi)設(shè)備進行周期性的預防性維護活動，維護在工件加工之前確定已知。在第①類中，Allahverdi等［1］、Zandieh 等［2］、李 素 粉 等［3］、潘春榮等［4］研究了流水線系統(tǒng)并假設(shè)機器會發(fā)生隨機故障，結(jié)合概率積分或者蒙特卡洛抽樣的方法對問題進行求解。在第②類中，針對兩階段流水線系統(tǒng)的研究較為廣泛，如 Lee［5］、Kubzin等［6］、Hadda［7］分別假設(shè)僅有一次不可用或者多次不可用期，對問題進行了分析研究，但在多階段流水線中此類研究相對較少。周炳海等［8］考慮機器的預防性維護，設(shè)計了基于 NEH（Nawaz－Enscore－Ham）的啟發(fā)式算法；Khelifati等［9］假設(shè)機器需要周期性地在時間窗內(nèi)進行維護，采用多智能體算法求解問題；邵健一等［10］考慮串行生產(chǎn)系統(tǒng)的可靠性，提出基于設(shè)備機會維護的維護策略；Aggoune等［11］假設(shè)機器存在周期性的不可用時間段，且不可用期的數(shù)量已知，設(shè)計了結(jié)合啟發(fā)式規(guī)則的禁忌搜索算法；Choi等［12］研究了機器具有周期性不可用且工件加工時間成比例的流水線系統(tǒng)優(yōu)化問題。上述文獻均僅考慮置換流水車間，但非置換流水車間廣泛存在于現(xiàn)實生產(chǎn)中，且非置換調(diào)度解要優(yōu)于置換調(diào)度解。因此，研究非置換車間在設(shè)備可用性約束下的調(diào)度優(yōu)化，并將其與置換車間的優(yōu)化結(jié)果進行對比，更有利于提高車間的實際效益。

本文旨在研究多階段的置換流水車間與非置換流水車間的生產(chǎn)特點，考慮機器具有周期性的預防性維護約束，且周期性維護的次數(shù)依賴于所有工件的加工時間總和，以最小化Makespan為優(yōu)化目標，分別建立了兩種車間的生產(chǎn)調(diào)度與設(shè)備周期性維護的聯(lián)合優(yōu)化模型，并設(shè)計有效算法對模型進行優(yōu)化求解。

1 問題描述

針對m臺機器的流水線系統(tǒng)，每個階段僅有一臺機器，調(diào)度期內(nèi)共有n個工件需要加工，各工件的工藝路線固定，每個工件均包含m道工序，每道工序依次經(jīng)過各個機器進行加工。目標為決策各機器上的工件加工順序，使Makespan最小，即minCmax，決策各機器上的工件加工順序。如果每臺機器上加工的各工件的順序必須一致，則該問題稱為置換流水車間調(diào)度；如果允許每臺機器上加工的各工件的順序不一致，則稱為非置換流水車間調(diào)度。

本問題基本假設(shè)如下：

（1）機器失效函數(shù)服從威布爾分布，對于機器j，λ（t）j為設(shè)備故障率函數(shù)；βj為威布爾分布的形狀參數(shù)；θj為威布爾分布的尺寸參數(shù)；tj為設(shè)備平均預防性維護作業(yè)本身所需時間；ωj為設(shè)備維護的成本因子；經(jīng)過預防性維護設(shè)備的狀態(tài)“恢復如新”，此時最優(yōu)預防性維護周期由Tj＝θj｛ωj（βj－1）｝1/βj求得。

（2）當?shù)竭_周期Tj時，機器需要進行預防性維護，即設(shè)備存在周期性的不可用期［ljTj＋（lj－1）tj，lj（Tj＋tj）］，其中l(wèi)j為機器j的第lj個預防性維護。預防性維護周期內(nèi)設(shè)備故障采用小修，小修僅恢復設(shè)備的功能，不改變設(shè)備的故障率狀態(tài)?？紤]小修時間長度小于1個單位時間，相對于設(shè)備運行時間來說很短，忽略不計。

（3）工件集J＝｛J1，J2，…，Jn｝，所有工件零時刻到達，工件i在機器j上的加工時間為pij（i＝1，2，3，…，n，j＝1，2，3，…，m）；假設(shè)工件加工被打斷后不可恢復，即遇到預防性維護時間段時，必須等到機器修復完成后才能重新開始加工工件。

（4）機器集 M＝｛M1，M2，…，Mm｝，各機器之間存儲空間無限，系統(tǒng)不會發(fā)生阻塞。

2 數(shù)學模型

由于周期性不可用期的時間段固定已知，需要將其引入調(diào)度約束之中，本模型與傳統(tǒng)的流水車間調(diào)度模型不同。雖然周期Tj固定，但其數(shù)量未知，因為工件數(shù)量不同時，調(diào)度期內(nèi)預防性維護周期的數(shù)量也不同。假設(shè)pij≤Tj?i，j，否則問題無解。而在pij＝Tj?i，j的場景下，最后一臺機器調(diào)度期內(nèi)最多有n＋m個預防性維護周期，因此在建模時設(shè)機器Mj的不可用時間段上界為Lj＝n＋m。

2．1 置換車間調(diào)度模型

在置換流水車間中，機器按照先到先服務的規(guī)則加工工件，有其廣泛的實際應用背景，大量文獻研究了此類傳統(tǒng)流水線調(diào)度問題。因此，針對置換調(diào)度，引入機器周期性預防維護，建立聯(lián)合優(yōu)化模型model－1如下，其中Z為無窮大正數(shù)：

決策變量：xik為0/1變量，表示對任意一臺機器j，工件i是否在k個位置，若是則為1，反之為0。

輔助決策變量：O［k］j為機器j的第k個位置的工序；p［k］j為工序O［k］j的加工時間；S［k］j為工序O［k］j的 開 始 加 工 時 間；C［k］j為 工 序 O［k］j的 完 成 時 間 ；a［k］jlj為0/1變量，表示工序O［k］j的開始加工時間是否在第lj（lj≤Lj）個預防性維護結(jié)束之后，若是則為1；b［k］jlj為0/1變量，表示工序O［k］j的完成時間是否在第lj個預防性維護開始之前，若是則為1。其中：式（1）為最小化 Makespan；約束（2）和（3）為工序的加工時間和完成時間；約束（4）和（5）為工序間順序約束，某工序O［k］j的開始時間必須晚于該工件上各工序的完成時間且必須晚于該機器的前一工件的完成時間；約束（6）～約束（8）表示工序O［k］j在第lj個預防性維護之后開始；約束（9）～約束（11）表示工序O［k］j在第lj個預防性維護之前已經(jīng)結(jié)束；約束（12）保證工序不會與任何不可用期沖突；約束（13）和（14）表示工件和加工位置的一一對應關(guān)系；約束（15）表示布爾類型變量。

2．2 非置換車間調(diào)度模型

對于考慮預防性維護的F｜｜Cmax問題，因為機器不可用期的存在，置換調(diào)度解并不一定是最優(yōu)解，即可能存在一個最優(yōu)調(diào)度，在這個調(diào)度中，工件在所有機器上的加工順序不完全一致，所以下文假設(shè)每臺機器的工件序列不必完全相同。對model－1作如下改進，得到考慮機器預防性維護的非置換調(diào)度聯(lián)合優(yōu)化模型model－2：

決策變量：xijk為0/1變量，表示對于機器j，工件i是否在k個位置，若是則為1，反之為0。

輔助決策變量：Cij為工件i的工序j的完成時間；Cijk表示若工件i在機器j的第k個位置時Cijk＝Cij，否則為0；其余變量的定義均與model－1中的相同。

將model－1中的約束（2）改為約束（16）；約束（5）改為約束（17），并增加約束（18）～ 約束（21）以確保約束的完整性；約束（13）和（14）分別改為約束（22）和（23）；其余約束均與model－1相同。

3 混合遺傳算法設(shè)計

雖然上述兩個線性數(shù)學模型可用ILOG CPLEX等商用規(guī)劃軟件求解，但是求解規(guī)模非常有限，而且由于問題的強NP難性質(zhì)，除非NP＝P，否則不可能找到多項式時間的精確算法。而遺傳算法在組合優(yōu)化問題中被廣泛認為是非常有效的算法，因此本文設(shè)計一種結(jié)合增量式進化策略、局域搜索機制、種群密度管理的混合遺傳算法（Hybrid Genetic Algorithm，HGA）求解模型。

在標準種群迭代遺傳算法中，種群規(guī)模不變，子群體以某一覆蓋比率直接替代父群體，而本文基于文獻［13］設(shè)計的增量式進化策略，種群規(guī)模由小逐漸增大，可使子個體有機會盡早進入交配池，在提高種群進化速度的同時保證種群的穩(wěn)定性，同時更方便地將有利于種群多樣性的操作嵌入算法框架中。增量式策略的具體描述如下：種群初始規(guī)模即最小規(guī)模為μ，每次僅生成一個子個體并將其插入種群中，因此種群中個體的數(shù)量popt為變動值，直到種群規(guī)模到達μ＋λ；此時，采用競爭生存策略，從種群中選出μ個個體，形成下一代種群。

混合遺傳算法框架如下：

步驟1 采用種群初始化子算法生成初始種群，popt＝μ。

步驟2 令I(lǐng)ter＝1，BestIter＝1，DivIter＝1。

步驟3 一代種群演化步驟。當種群個體數(shù)量小于μ＋λ時，則：

（1）從種群中隨機選取兩個個體，并采用兩規(guī)模聯(lián)賽法保留較好的個體作為父個體P1；繼而采用同樣方法得到父個體P2。

（2）將P1與P2交叉得到新個體P′。

（3）以Pm的概率對P′進行變異。

（4）以Pls的概率對P′進行局域搜索操作。

（5）將P′插入種群之中，popt＝popt＋1。

步驟4 采用競爭生存策略，從中挑出μ個個體，構(gòu)成下一代種群。

步驟5 Iter＝Iter＋1；若最好解沒有改進，則BestIter＝BestIter＋1，DivIter＝DivIter＋1；否則，BestIter＝1，DivIter＝1。

步驟6 如果DivIter＝MaxDivIter，則啟動種群重生機制，DivIter＝1。

步驟7 如果BestIter＝MaxBestIter或者Iter＝MaxIter，則算法結(jié)束，輸出最好解；否則轉(zhuǎn)步驟3。

其中：MaxIter為最大迭代代數(shù)，MaxBestIter為最好解持續(xù)沒有改進的最大迭代代數(shù)，MaxDivIter為啟動重生機制的迭代代數(shù)。

3．1 染色體的編碼及解碼

本文采用工件優(yōu)先列表的形式對個體進行編碼。染色體編碼如圖1所示，表示工件優(yōu)先序列為π＝ （1，3，4，7，6，5，8，9，2，10）。對于model－1，由于每臺機器的工件加工順序一致，可直接將該序列作為各機器上的工件加工順序，考慮機器的不可用期，可得到此染色體的目標值；對于model－2，由于每臺機器的工件加工順序不必一致，該優(yōu)先序列并不直接表示工件在所有機器上的加工順序，而是各機器加工工件的Input Sequence，染色體解碼時，首先按照Schedule Generator機制得到各機器工件加工順序，繼而求其目標函數(shù)值。Schedule Generator的基本思想為：以置換調(diào)度解為優(yōu)先序列，依次調(diào)整各機器上的工件順序，分別計算和比較所得調(diào)度的Cmax，最終得到非置換調(diào)度解。

Schedule Generator具體步驟如下：

步驟1 現(xiàn)有一個優(yōu)先列表（J1，J2，…，Jn），稱該置換為Input Sequence，維護時間將整個時間軸劃分為Ij1，Ij2，…，Iju等各個時間段；令j＝1，i＝1。

步驟2 設(shè)工件Ji加工時間pij和各時段間隙的大小為L，按照時段的先后順序，若pij≤L，則將Ji插入該時段，并更新L的值。

步驟3 令i＝i＋1，若i＞n，則輸出此時Mj的序列πj，稱該置換為Mj的Output Sequence；否則返回步驟2。

步驟4 令j＝j＋1，若j＞m則終止算法，計算此時的Cmax；否則令i＝1，返回步驟2。

下面以（J1，J2，J3）為Input Sequence，作為例子，具體說明利用Schedule Generator生成各機器工件加工順序的過程（如圖2）：

步驟1 由于P1j＜Lj1，工件J1的第O1j個作業(yè)可以插入間隙Ij1中。

步驟2 由于P2j＋P1j＞Lj1，且不允許工件中斷，只能將O2j插入間隙Ij2中。

步驟3 由步驟1和步驟2，間隙I′j1＝Lj1－P1j，P3j＋P1j＜Lj1，因此O3j插入間隙I′j1中。

顯然，對于給定的Input（J1，J2，J3），得到的最終置換為Output（J1，J3，J2）；在機器 Mj＋1中，同樣考慮（J1，J2，J3），由于之前的Output（J1，J3，J2）會對后續(xù)排序產(chǎn)生影響，重復上述步驟1～步驟3，易得到機器 Mj＋1的 Output Sequence 為（J3，J1，J2）；顯然，對于同樣的Input Sequence，得到的各機器上的工件實際加工順序并非完全一致。

3．2 解的評價與選擇

由于輪盤賭的選擇壓力過大，本算法采用兩規(guī)模聯(lián)賽制進行個體選擇。在解的評價中，為避免由于僅考慮目標函數(shù)導致的種群早熟現(xiàn)象，本算法將聯(lián)合考慮個體的目標函數(shù)值與個體擁擠度。個體P的適應度值f＝1/［r1＋（1－e/popt）r2］。其中：popt為此刻種群個體數(shù)量，e為在競爭生存步驟中將要保留到下一代種群的精英個體（僅考慮目標函數(shù)值）的數(shù)量，r1為根據(jù)目標函數(shù)值個體P在種群中的排序，r2為根據(jù)擁擠距離個體P在種群中的排序。顯然，當一個新子個體加入種群后，需要更新個體P在種群中的排序位置，重新計算各個體的適應度值。

3．3 遺傳算法基本操作

（1）交叉與變異為保證交叉后染色體的可行性以及較小的交叉壓力，本算法采用十字交叉法，交叉概率為1。通過分析，染色體的鄰域結(jié)構(gòu)為增大變異因子，跳出局部解的能力，采用逆轉(zhuǎn)變異法，變異概率為pm。

（2）局域搜索機制由于交叉變異無法保證解的局部最優(yōu)性，采取基于相鄰工件對交換的鄰域搜索機制。個體P的工件優(yōu)先列表為π0，以概率pls對個體進行局域搜索，具體步驟如下：

1）令i＝1。

2）交換Ji、Ji＋1，得到排序πi，按照前述解碼方式計算，若

（3）i＝i＋1，若i＞n，則得到新個體P′；否則返回（2）。

3．4 種群密度管理

如何避免早熟是遺傳算法的最大挑戰(zhàn)，特別是本算法中加入了局域搜索機制，因此必須設(shè)計合理的種群密度管理策略，才能保證算法有效性。首先，前述染色體的評價方法貫穿整個算法，有利于控制種群密度。然后，在種群進化過程中采取如下三個基本機制。

（1）種群初始化子算法隨機生成μ＋λ個個體，并采用競爭生存策略從中選出μ個個體。

（2）競爭生存策略當種群規(guī)模達到μ＋λ時，啟動此機制。首先，刪除種群中的重復個體。然后，依次刪除種群中的最差個體（適應度值最小的個體），直到種群規(guī)模降為μ；顯然，在該策略中選擇保留到下一代的個體時，考慮到了個體的目標函數(shù)值與擁擠度。與此同時，適應度值的獨特公式保證了在該生存策略下，僅考慮目標函數(shù)值時的e個精英個體不會被刪除，從而有利于種群收斂。

（3）種群重生機制當DivIter＝MaxDivIter時，啟動該機制。首先保留0．25μ的最優(yōu)個體（僅考慮目標函數(shù)值），繼而如種群初始化子算法般挑選出0．75μ的個體，使種群規(guī)?；謴蜑棣?。

4 啟發(fā)式算法

雖然各種不同規(guī)模下的數(shù)據(jù)實驗顯示該混合遺傳算法的收斂性和穩(wěn)定性很好（如5．1節(jié)所述），但在大規(guī)模問題下的運算時間較長。因此，本文設(shè)計了相應的快速啟發(fā)式算法，可在保證解的質(zhì)量較優(yōu)的同時加快問題的求解速度。該算法與HGA相互補充，當決策者追求較短的算法運行時間時可采取此算法。

本文的啟發(fā)式算法基本思想可分為三部分：①通過結(jié)合預防性維護的NEH啟發(fā)式算法，得到初始解；②采用上述HGA中的局域搜索機制對解進行改進；③基于解序列的破壞，以改進NEH算法作為解序列重組的廣度搜索機制，保證解的全局較優(yōu)性。令為算法當前最優(yōu)解的目標值，若經(jīng)過連續(xù)Maxiterate次破壞、重組、鄰域搜索后最優(yōu)解沒有改進，則搜索停止。算法具體步驟如下：

步驟1 生成初始解。

（1）對所有工件的加工總時間做非增排序，得到工件優(yōu)先列表π。

（2）取π中的前兩個工件，按照上述HGA中的解碼方式，考慮定周期維護的時間節(jié)點，分別計算這兩個工件順序不同時的Cmax，取較小Cmax時的工件順序。

（3）i＝3～n，依次取出第i個工件，插入前面所產(chǎn)生的置換的任意可能位置，同樣計算Cmax，取最小的Cmax時工件的位置。得到最終排序為π0，其目標值為C0max，C0max→Cbestmax。

步驟2 基于相鄰工件對交換的鄰域搜索。步驟同3．3節(jié)的局域搜索機制。

步驟3 停止規(guī)則。

（1）若C0max＜Cbestmax，則iterate＝0，C0max→Cbestmax；否則，iterate＝iterate＋1。

（2）若iterate＞Maxiterate，則算法結(jié)束；否則，轉(zhuǎn)步驟4。

步驟4 基于破壞和重組的廣度搜索。

（1）隨機從π0中選取連續(xù)的r個工件，將這r個工件組成的排序πr0從π0中刪去，假設(shè)πD0為（J1，J2，…，Jn－r），πr0為（J1′，J2′，…，Jr′）；πD0為π0刪除了r個工件后得到的排序。

（2）令i＝1。

（3）將Ji′插入πD0中的所有可能位置，同樣按照解碼方法計算各種置換的Cmax，選擇Cmax最小的位置，得 到 新 的 排 序 πD0（J1，J2，…，Jn－r＋i），i ＝i＋1。

（4）若i＜r，則轉(zhuǎn)入（3）；否則轉(zhuǎn)步驟2。

5 實驗與分析

文獻［14］研究了單機的生產(chǎn)與維護集成調(diào)度問題，由于該文獻的模型與算例的完整性，被后續(xù)研究者廣泛引用。本文根據(jù)問題的特點，適當調(diào)整算例參數(shù)，設(shè)置如下：工件的加工時間為在區(qū)間［10，100］的離散平均隨機變量；機器的故障函數(shù)服從威布爾分布，預防性維護的成本因子ωj＝3，集合Ω＝（θ，β，t），其中θ＝150，180，200，β＝2，3，t＝5，10，15。

5．1 遺傳算法數(shù)值驗證

為驗證HGA的有效性，現(xiàn)將在置換車間與非置換車間下HGA的解分別與CPLEX精確解在內(nèi)存4G、主頻2．40GHz的Intel Core i5的 Win7系統(tǒng)中通過C＃平臺進行比較。參考一般的遺傳算法參數(shù)設(shè)置并通過預實驗調(diào)整各參數(shù)值，HGA各參數(shù)設(shè)置如下：μ＝30，λ＝70，Maxiter＝300，MaxDivIter＝30，MaxBestIter＝70，c＝0．2μ，e＝0．4μ，pls＝1，pm＝0．01；在每種參數(shù)組合的每種問題規(guī)模下隨機生成10個算例。每個算例利用HGA獨立運行10次，并記錄各算例下的最好值、最差值和標準差，10個算例的統(tǒng)計平均結(jié)果如表1和表2所示。從表1和表2可以看出，各算例下HGA的平均標準差均小于2%，說明HGA收斂結(jié)果的穩(wěn)定性較好。而且HGA的解與精確解的GAP（GAP＝［z（HGA）－z（CPLEX）］/z（CPLEX））均小于1%，從而驗證了HGA算法的有效性。

表1 置換車間下CPLEX與HGA的結(jié)果比較

5．2 啟發(fā)式算法數(shù)值驗證

為證明提出的啟發(fā)式算法的有效性，現(xiàn)將其與HGA進行比較。在C＃平臺下進行12組數(shù)據(jù)試驗，每組參數(shù)組合下針對三種問題規(guī)模，每組隨機生成10個算例。該啟發(fā)式算法只需運行一次，Maxiterate＝3，機器數(shù)量m＝5，而HGA對每個算例獨立運行10次取平均值，置換車間下兩者的對比如表3所示，非置換車間下兩者的對比如表4所示，其中Heu表示啟發(fā)式算法。從表中可以看出，雖然啟發(fā)式算法的解比遺傳算法差，但兩者的GAP（GAP＝［z（Heu）－z（HGA］/z（Heu））小于2%，在可接受的范圍內(nèi)，而且該算法的求解時間非常短。顯然，由于Heu屬于構(gòu)造式啟發(fā)式算法而非基于群體的元啟發(fā)式算法，運行速度會非常快；同時，由于在Heu中增加了有限制的全局搜索機制，使得該算法仍有比較好的全局最優(yōu)性。

表2 非置換車間下CPLEX與HGA的比較

表3 置換車間不同參數(shù)下HGA與啟發(fā)式的比較

5．3 置換車間與非置換車間比較

統(tǒng)計不同算例參數(shù)設(shè)置下置換車間的解與非置換車間的解，并進行比較。從表3和表4的對比可以看出，在相同的工件數(shù)量和預防性維護周期時間下，非置換調(diào)度所獲得的解明顯優(yōu)于置換調(diào)度的解，兩者解的GAP平均為10%，由于在非置換調(diào)度下所獲得的解更具柔性，可以根據(jù)預防性維護的時間調(diào)整工件的加工順序。為了清晰地展示隨著工件數(shù)量和θ的變化，兩種車間的解的GAP的變化趨勢，繪制其變化曲線如圖3所示。由圖3可知：①同一Ω參數(shù)下，工件數(shù)量越大，GAP越大，即非置換調(diào)度所獲得的解優(yōu)勢越明顯；②在同一工件數(shù)量下，θ越小，GAP越大，因為θ越小，預防性維護的頻率越大，此時非置換的解更有優(yōu)勢。

表4 非置換車間不同參數(shù)下HGA與啟發(fā)式的比較

為清晰地描述非置換車間解的優(yōu)越性及其原因，本文隨機選取上述比較算例中的某一具體案例，其工件對應的加工時間如表5所示，各機器的預防性維護時間tj＝10，形狀參數(shù)均為β＝2，尺度參數(shù)均為θ＝150。利用上文提出的HGA，可得如圖4所示的置換解與非置換解。

從圖4中可以看出，由于機器無法在預防性維護的時間內(nèi)加工工件，而工件2的加工時間較長，導致J2在M2上的加工延遲到第5個維護周期，從而延長了Makespan（Makespan＝267）。相反，由于在非置換車間中，各機器上的工件加工順序不必完全一致，將J4在J2之前在M2上加工，可大大縮短Makespan（Makespan＝230）。當問題規(guī)模增大時，機器不可用時間段增多，在不可用期的附近出現(xiàn)工件順序調(diào)換的情況相應增加，因此非置換調(diào)度的這種柔性在大規(guī)模問題下表現(xiàn)出的優(yōu)越性更為顯著。

表5 工件在相應機器上的加工時間

6 結(jié)束語

本文研究了帶有周期性預防性維護的流水車間調(diào)度問題，分別在置換流水車間和非置換流水車間兩種不同情形下建立了數(shù)學優(yōu)化模型。繼而提出了結(jié)合增量式進化策略、局域搜索機制、種群密度管理的混合遺傳算法和將鄰域搜索與廣度搜索相結(jié)合的啟發(fā)式算法。通過在不同問題規(guī)模下的數(shù)據(jù)實驗表明，遺傳算法解可有效求解此類問題，而提出的啟發(fā)式算法可在保證解較優(yōu)性的基礎(chǔ)上快速尋找到滿意解。此外，隨著問題規(guī)模和維護頻率的增加，非置換車間獲得的解相對置換車間更加優(yōu)異。各種不同的維護策略、混合流水線生產(chǎn)系統(tǒng)、維護成本與Makespan的聯(lián)合優(yōu)化等均可以本文算法思想為基礎(chǔ)，作為進一步的研究方向。

［1］ ALI A，JOHN M．Scheduling on a two－machine flowshop subject to random breakdown with a makespan objective function［J］．European Journal of Operational Research，1995，81（2）：376－387．

［2］ ZANDIEH M，GHOLAMI M．An immune algorithm for scheduling a hybrid flow shop with sequence dependent setup times and machines with random breakdowns［J］．International Journal of Production Research，2009，47（24）：6999－7027．

［3］ LI Sufen，ZHU Yunlong，YIN Chaowan．Flow shop scheduling with stochastic processing times and machine breakdowns［J］．Computer Integrated Manufacturing Systems，2005，10（2）：1425－1429（in Chinese）．［李素粉，朱云龍，尹朝萬．具有隨機加工時間和機器故障的流水車間調(diào)度［J］．計算機集成制造系統(tǒng)，2005，10（2）：1425－1429．］

［4］ PAN Chunrong，WU Naiqi．Failure response policy for cluster tools with parallel processing module［J］．Computer Integrated Manufacturing Systems，2010，16（4）：888－895（in Chinese）．［潘春榮，伍乃騏．具有并行加工模塊的組合設(shè)備故障響應策略［J］．計算機集成制造系統(tǒng)，2010，16（4）：888－895．］

［5］ LEE C Y．Minimizing the makespan in the two－machine flowshop scheduling problem with a availability constraint［J］．Operational Research Letters，1997，20（3）：129－139．

［6］ KUBZIN M A，POTTS C N，et al．Approximation results for flowshop scheduling problems with a machine availability constrains［J］．Computers ＆Operational Research，2009，36（2）：379－390．

［7］ HADDA H．A polynomial－time approximation scheme for the two machine flow shop problem with several availability constrains［J］．Optimization Letters，2012，6（3）：559－569．

［8］ ZHOU Binghai，JIANG Shuyu．Integrated production and preventive maintenance scheduling algorithm for flowshops［J］．Journal of Dalian Maritime University，2007，33（3）：32－35（in Chinese）．［周炳海，蔣舒宇．集成生產(chǎn)與預防性維護的流水車間調(diào)度算法［J］．大連海事大學學報，2007，33（3）：32－35．］

［9］ KHELIFATI S L，BENBOUZID S F．A multi－Agent scheduling approach for the joint scheduling of jobs and maintenance operations in the flowShop sequencing problem［J］．Lecture Notes in Computer Science，2011，6923：60－69．

［10］ SHAO Jianyi，ZHOU Binghai．Opportunistic maintenance modeling method for series production system based on capacity constraint resource［J］．Computer Integrated Manufacturing Systems，2013，19（5）：1051－1057（in Chinese）．［邵健一，周炳海．基于CCR的串行生產(chǎn)系統(tǒng)機會維護建模方法［J］．計算機集成制造系統(tǒng)，2013，19（5）：1051－1057．］

［11］ AGGOUNE R，PORMANN M C．Flow shop scheduling problem with a limited machine availability：a heuristic approach［J］．International Journal of Production Economics，2006，99（1/2）：4－15．

［12］ CHOI B C，LEE K，et al．Flow shops with machine maintenance：Ordered and proportionate cases ［J］．International Journal of Production Research，2010，207（1）：97－104．

［13］ GENDREAU M，POTVIN J Y，et al．Handbook of metaheuristics［M］//International Series in Operations Research＆ Management Science．Berlin，Germany：Springer－Verlag，2010：146．

［14］ CASSADY C R，KUTANO E．Integrating preventive maintenance planning and production scheduling for a single machine［J］．IEEE Transactions on Reliability，2005，54（2）：304－309．