張思源，陸志強(qiáng)＋，崔維偉

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

0 引言

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

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

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

1 問題描述

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

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

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

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

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

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

2 數(shù)學(xué)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

混合遺傳算法框架如下：

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

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

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

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

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

（3）以Pm的概率對P′進(jìn)行變異。

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

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

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

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

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

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

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

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

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

Schedule Generator具體步驟如下：

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

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

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

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

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

步驟1 由于P1j＜Lj1，工件J1的第O1j個(gè)作業(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）；在機(jī)器 Mj＋1中，同樣考慮（J1，J2，J3），由于之前的Output（J1，J3，J2）會對后續(xù)排序產(chǎn)生影響，重復(fù)上述步驟1～步驟3，易得到機(jī)器 Mj＋1的 Output Sequence 為（J3，J1，J2）；顯然，對于同樣的Input Sequence，得到的各機(jī)器上的工件實(shí)際加工順序并非完全一致。

3．2 解的評價(jià)與選擇

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

3．3 遺傳算法基本操作

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

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

1）令i＝1。

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

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

3．4 種群密度管理

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

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

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

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

4 啟發(fā)式算法

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

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

步驟1 生成初始解。

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

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

（3）i＝3～n，依次取出第i個(gè)工件，插入前面所產(chǎn)生的置換的任意可能位置，同樣計(jì)算Cmax，取最小的Cmax時(shí)工件的位置。得到最終排序?yàn)棣?，其目標(biāo)值為C0max，C0max→Cbestmax。

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

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

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

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

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

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

（2）令i＝1。

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

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

5 實(shí)驗(yàn)與分析

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

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

為驗(yàn)證HGA的有效性，現(xiàn)將在置換車間與非置換車間下HGA的解分別與CPLEX精確解在內(nèi)存4G、主頻2．40GHz的Intel Core i5的 Win7系統(tǒng)中通過C＃平臺進(jìn)行比較。參考一般的遺傳算法參數(shù)設(shè)置并通過預(yù)實(shí)驗(yàn)調(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ī)模下隨機(jī)生成10個(gè)算例。每個(gè)算例利用HGA獨(dú)立運(yùn)行10次，并記錄各算例下的最好值、最差值和標(biāo)準(zhǔn)差，10個(gè)算例的統(tǒng)計(jì)平均結(jié)果如表1和表2所示。從表1和表2可以看出，各算例下HGA的平均標(biāo)準(zhǔn)差均小于2%，說明HGA收斂結(jié)果的穩(wěn)定性較好。而且HGA的解與精確解的GAP（GAP＝［z（HGA）－z（CPLEX）］/z（CPLEX））均小于1%，從而驗(yàn)證了HGA算法的有效性。

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

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

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

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

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

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

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

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

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

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

表5 工件在相應(yīng)機(jī)器上的加工時(shí)間

6 結(jié)束語

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

［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）．［李素粉，朱云龍，尹朝萬．具有隨機(jī)加工時(shí)間和機(jī)器故障的流水車間調(diào)度［J］．計(jì)算機(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è)備故障響應(yīng)策略［J］．計(jì)算機(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)與預(yù)防性維護(hù)的流水車間調(diào)度算法［J］．大連海事大學(xué)學(xué)報(bào)，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ī)會維護(hù)建模方法［J］．計(jì)算機(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．