江才林，陸志強(qiáng)，崔維偉

（1.同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海201804；2.上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海200240）

考慮周期預(yù)防性維護(hù)的異速并行機(jī)集成調(diào)度研究

江才林1，陸志強(qiáng)1，崔維偉2

（1.同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院，上海201804；2.上海交通大學(xué)機(jī)械與動(dòng)力工程學(xué)院，上海200240）

針對(duì)異速并行機(jī)系統(tǒng)，考慮機(jī)器具有周期預(yù)防性維護(hù)的不可用約束，建立生產(chǎn)調(diào)度與預(yù)防性維護(hù)集成優(yōu)化的混合整數(shù)規(guī)劃模型。基于改進(jìn)LPT的機(jī)器負(fù)載均衡技術(shù)與基于最小裝箱松弛法的單機(jī)調(diào)度優(yōu)化算法，設(shè)計(jì)了有效的啟發(fā)式算法HCA，與Cplex的數(shù)據(jù)試驗(yàn)比較表明，對(duì)于中小規(guī)模問(wèn)題其解與最優(yōu)解或低界的百分比誤差小于10%。設(shè)計(jì)了結(jié)合裝箱算法的混合遺傳算法HGA，與HCA對(duì)比的數(shù)據(jù)試驗(yàn)表明，對(duì)于大規(guī)模問(wèn)題HGA表現(xiàn)更加優(yōu)異。通過(guò)與獨(dú)立決策比較的數(shù)據(jù)實(shí)驗(yàn)證明了生產(chǎn)調(diào)度與設(shè)備維護(hù)的聯(lián)合決策模型效果更優(yōu)，可有效協(xié)調(diào)車(chē)間生產(chǎn)與維修的總體計(jì)劃。

異速并行機(jī)調(diào)度；預(yù)防性維護(hù)；整數(shù)規(guī)劃；啟發(fā)式算法；混合遺傳算法

生產(chǎn)實(shí)際中隨著設(shè)備老化，機(jī)器需要預(yù)防性維護(hù)以改善機(jī)器性能或者故障后維修以恢復(fù)機(jī)器功能。由于定期執(zhí)行預(yù)防性維護(hù)可降低設(shè)備發(fā)生意外故障的概率以提高系統(tǒng)的穩(wěn)定性，近年來(lái)集成預(yù)防性維護(hù)策略的生產(chǎn)調(diào)度得到了研究者的普遍關(guān)注。根據(jù)計(jì)劃期內(nèi)維護(hù)的次數(shù)不同，研究主要分為2類：一類是在計(jì)劃期內(nèi)設(shè)備僅有一次維護(hù)，另一類是在計(jì)劃期內(nèi)設(shè)備需要進(jìn)行多次周期性維護(hù)。對(duì)于第1類研究，針對(duì)單機(jī)系統(tǒng)，一般假設(shè)工件不可中斷，研究各個(gè)不同調(diào)度目標(biāo)如makespan等，提出各類啟發(fā)式如SPT等并證明其誤差邊界或者設(shè)計(jì)分支定界等精確算法求解［1-3］。對(duì)于并行機(jī)系統(tǒng)，主要有各個(gè)機(jī)器需要同時(shí)進(jìn)行預(yù)防性維護(hù)，或者其中一臺(tái)進(jìn)行預(yù)防性維護(hù)2種假設(shè)，求解方法為提出相應(yīng)啟發(fā)式算法［4-6］。對(duì)于第2類研究，針對(duì)單機(jī)系統(tǒng)，文獻(xiàn)［7］考慮計(jì)劃期內(nèi)具有多個(gè)預(yù)防性維護(hù)，建立了整數(shù)規(guī)劃模型。在此基礎(chǔ)上，文獻(xiàn)［8-12］研究了機(jī)器惰化效應(yīng)，學(xué)習(xí)效應(yīng)、計(jì)件維護(hù)以及柔性時(shí)間窗維護(hù)的拓展問(wèn)題。文獻(xiàn)［13］首先將維修成本、makespan、加權(quán)完成時(shí)間以及加權(quán)總延遲時(shí)間作為優(yōu)化目標(biāo)，采用多目標(biāo)遺傳算法進(jìn)行優(yōu)化。文獻(xiàn)［14］考慮設(shè)備的失效函數(shù)，以總成本最小為目標(biāo)。針對(duì)并行機(jī)系統(tǒng)，有學(xué)者分別研究了2臺(tái)同型機(jī)和m臺(tái)同型并行機(jī)的調(diào)度問(wèn)題，并提出相應(yīng)的改進(jìn)啟發(fā)式規(guī)則［15-16］。文獻(xiàn)［17］則研究了的帶有近似周期預(yù)防性維護(hù)的調(diào)度問(wèn)題，目標(biāo)為最小化最后一個(gè)維護(hù)活動(dòng)的完成時(shí)間，證明其啟發(fā)式算法的界小于2T＇／T。

從以上文獻(xiàn)綜述可以看到，考慮機(jī)器具有周期預(yù)防性維護(hù)的可用度約束，單機(jī)調(diào)度文獻(xiàn)較多而并行機(jī)調(diào)度文獻(xiàn)有限，且系統(tǒng)為同速并行機(jī)。實(shí)際車(chē)間中由于機(jī)器屬性不同或機(jī)器新舊差異，導(dǎo)致其工件加工速率、預(yù)防性維護(hù)的周期以及維護(hù)所需時(shí)間均不同。本文旨在考慮異速并行機(jī)系統(tǒng)內(nèi)各機(jī)器具有不同周期的周期性不可用約束，以最小化工件最大完工時(shí)間為目標(biāo)，建立生產(chǎn)調(diào)度與設(shè)備維護(hù)的聯(lián)合優(yōu)化數(shù)學(xué)規(guī)劃模型，并設(shè)計(jì)有效啟發(fā)式算法對(duì)問(wèn)題進(jìn)行優(yōu)化求解。

1 問(wèn)題描述

將含有n個(gè)工件的工件集J＝｛J1，J2，…，Jn｝分配到m臺(tái)機(jī)器M＝｛M1，M2，…，Mm｝上加工，目標(biāo)為最小化工件的最大完工時(shí)間。所有工件在零時(shí)刻到達(dá)，工件基本加工時(shí)間為（i＝1，2，…，n），工件在加工過(guò)程中不允許中斷；機(jī)器Mj加工速率為sj（i＝1，2，…，m），工件Ji的實(shí)際加工時(shí)間為＝／sj；機(jī)器需要周期性預(yù)防性維護(hù)，2次維護(hù)的間隔時(shí)間為T(mén)j（i＝1，2，…，m），維護(hù)時(shí)間長(zhǎng)度為tj（i＝1，2，…，m）。按照調(diào)度三元組表示法，問(wèn)題可記為Qm／pm－nr／Cmax。圖1為示例問(wèn)題甘特圖。

由于各個(gè)機(jī)器需要進(jìn)行周期預(yù)防性維護(hù)，一個(gè)完整調(diào)度方案應(yīng)包含工件的加工順序和維護(hù)位置2個(gè)部分。若將2個(gè)預(yù)防性維護(hù)之間的工件集合稱為一個(gè)批次，用Bjk表示機(jī)器j的第k加工批次的所有工件集合，則對(duì)應(yīng)于這個(gè)批次的工件有其相應(yīng)的開(kāi)始時(shí)間以及完工時(shí)間。因此一個(gè)調(diào)度方案π是由m個(gè)子集πj（i＝1，2，…，m）構(gòu)成，每個(gè)子集為工件批次集合和維護(hù)的組合πj＝（Bj1，PMj，Bj2，PMj…Bjkj），其中PMj代表機(jī)器j的維護(hù)時(shí)段，kj表示機(jī)器j的加工批次序號(hào)。用Pjk表示機(jī)器j的第k加工批次內(nèi)所有工件的加工時(shí)間總和，用Gjk表示機(jī)器j的第k加工批次內(nèi)的松弛時(shí)間，則有Gjk＝Tj－Pjk。

圖1 考慮周期預(yù)防性維護(hù)的異速并行機(jī)調(diào)度示例Fig.1 An example of uniform machine scheduling with periodic maintenance

模型決策變量：xijk為0／1變量，如果工件i在第j機(jī)器第k加工批次加工，則取1，否則取0；yjk為0／1變量，如果機(jī)器j的第k加工批次有加工的工件，則取1，否則取0；zjk為0／1變量，如果機(jī)器j的第k加工批次為最后一個(gè)有加工工件實(shí)批次，則取1，否則取0。M為無(wú)窮大的正整數(shù)。約束（1）表示并行機(jī)系統(tǒng)的最大完工時(shí)間為所有機(jī)器完工時(shí)間的最大值；約束（2）表示每個(gè)工件僅由一臺(tái)確定的機(jī)器加工一次；約束（3）表示若此批次有加工工件為“實(shí)批次”，則此批次的工件數(shù)量為1～n；約束（4）保證了當(dāng)?shù)趈機(jī)器的第k加工批次為實(shí)批次，則之前的k－1加工批次也必為實(shí)批次；約束（5）、（6）表示分配到機(jī)器各個(gè)批次工件加工時(shí)間總和小于維護(hù)周期T；約束（7）、（8）表示當(dāng)?shù)趈機(jī)器的第k加工批次為其最后一個(gè)實(shí)批次，則后續(xù)所有批次均為沒(méi)有加工工件的“虛批次”；約束（9）表示每臺(tái)機(jī)器至少存在一個(gè)實(shí)批次；約束（10）表示各個(gè)機(jī)器的最大完工時(shí)間由最后一個(gè)實(shí)批次的加工時(shí)間總和及其加工批次數(shù)量決定。

上述數(shù)學(xué)模型具有較好的擴(kuò)展性，對(duì)于不同維護(hù)策略下的并行機(jī)調(diào)度問(wèn)題，可通過(guò)相關(guān)變量的調(diào)整獲得。例如，對(duì)于同速型的具有周期預(yù)防性維護(hù)的并行機(jī)調(diào)度問(wèn)題Pm／pm－nr／Cmax只需要把約束（5）中的sj設(shè)置為1即可。

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

由于此問(wèn)題的強(qiáng)NP難性質(zhì)，無(wú)法獲得多項(xiàng)式時(shí)間的精確算法，雖可用Cplex等商用軟件進(jìn)行求解，但僅能求解小規(guī)模問(wèn)題，無(wú)法在有效時(shí)間內(nèi)解決大規(guī)模問(wèn)題。本文提出基于改進(jìn)LPT規(guī)則與最小裝箱松弛法的構(gòu)造型啟發(fā)式算法HCA以及結(jié)合裝箱算法的混合遺傳算法HGA，可快速有效的解決此組合優(yōu)化問(wèn)題。

2.1 啟發(fā)式算法HCA

由于機(jī)器具有可用度約束，本問(wèn)題可以分解為2個(gè)子問(wèn)題：1）工件分配即機(jī)器選擇問(wèn)題，應(yīng)使得機(jī)器的負(fù)載均衡化。對(duì)于這類問(wèn)題，當(dāng)不考慮機(jī)器可用度時(shí)，LPT［1］規(guī)則為較好的啟發(fā)式規(guī)則，其是指在零時(shí)刻將m個(gè)最長(zhǎng)的工件分配到m臺(tái)機(jī)器。此后，任一臺(tái)機(jī)器空閑，剩下的工件中加工時(shí)間最長(zhǎng)的將分配給這臺(tái)空閑機(jī)器；2）當(dāng)工件分配到機(jī)器后的單機(jī)工件排序問(wèn)題。由約束（10）可知，機(jī)器Mj上，當(dāng)機(jī)器具有最少加工批次以及最后加工實(shí)批次的工件加工時(shí)間最少時(shí)獲得問(wèn)題的最優(yōu)解。由此，問(wèn)題轉(zhuǎn)化為變型的一維裝箱問(wèn)題。對(duì)于這類問(wèn)題，由Gupta等提出的最小裝箱松弛法（minimum bin slack，MBS）［18］采用遞歸方法在迭代的過(guò)程中不斷減少非最后一個(gè)箱子的松弛量，使箱子的總數(shù)量減少的同時(shí)也降低最后一個(gè)箱子的容量。HCA首先通過(guò)改進(jìn)LPT規(guī)則將工件均衡分配到各個(gè)機(jī)器上；繼而將分配到機(jī)器的工件按照MBS規(guī)則重新排列使單機(jī)松弛時(shí)間最小，實(shí)現(xiàn)單臺(tái)機(jī)器的局部?jī)?yōu)化；隨后將每臺(tái)機(jī)器的最后一批工件與其他機(jī)器的非最后一批工件進(jìn)行交換，通過(guò)局域搜索實(shí)現(xiàn)各臺(tái)機(jī)器間的平衡優(yōu)化；最后將所有機(jī)器的最后一個(gè)加工批次的所有工件作為新工件集J＇，轉(zhuǎn)化為沒(méi)有可用度約束的小規(guī)模并行機(jī)調(diào)度問(wèn)題并采用CPLEX求解，進(jìn)一步均衡各臺(tái)機(jī)器以提升解的質(zhì)量。具體步驟如下：

1）生成初始調(diào)度方案。

①將工件集J按照加工時(shí)間長(zhǎng)度降序排列，形成優(yōu)先列表集合L＝｛J1，J2，…，Jn｝。

②將Ji按照列表L順序逐一安排到能將其最先完工的機(jī)器上。即針對(duì)每臺(tái)機(jī)器Mj，搜索工件Ji的最早允許加工時(shí)間為，并計(jì)算其完工時(shí)間，將工件分配到可以最早完工的機(jī)器上，生成一個(gè)初始調(diào)度方案π0＝｛，，…，｝。

2）對(duì)初始調(diào)度方案π0＝｛，，…，的每一個(gè)子集進(jìn)行MBS重新排列得到一個(gè)新的調(diào)度方案π1＝｛，…，｝。

3）對(duì)新調(diào)度方案進(jìn)行鄰域交換以進(jìn)一步改善。

①根據(jù)調(diào)度π1，機(jī)器Mj共包含kj個(gè)加工批次，集合記為Bj，Gjk為Mj的第k個(gè)批次的松弛時(shí)間。求得各機(jī)器的完工時(shí)間Cmjax，并記完工時(shí)間最長(zhǎng)的機(jī)器為Ml。

②Ml的最后一個(gè)批次的工件數(shù)量為nl，并將工件按照加工時(shí)間降序排列，記J［i］為該批次的第i個(gè)工件。

③令i＝1。

④在機(jī)器集合｛M／Ml｝中，按照機(jī)器編號(hào)依次搜索機(jī)器Mj，在Mj中按照批次編號(hào)依次搜索各批次的最短加工時(shí)間工件J*，若交換J［i］、J*后不會(huì)違反Gjk約束，則交換兩工件并轉(zhuǎn)入⑤；若遍歷結(jié)束之后沒(méi)有交換成功，轉(zhuǎn)入⑥。

⑤工件交換后，得到新調(diào)度π*，π*→π1，轉(zhuǎn)入①。

⑥令i＝i＋1，若i≤nl，則轉(zhuǎn)入④；否則轉(zhuǎn)入步驟4）。

4）根據(jù)調(diào)度π1，將各臺(tái)機(jī)器的最后一批工件取出，作為一個(gè)新的工件集J＇，將每臺(tái)機(jī)器的前kj－1加工批次的結(jié)束時(shí)間作為機(jī)器的釋放時(shí)間，此時(shí)轉(zhuǎn)化為不帶可用度約束的小規(guī)模純調(diào)度問(wèn)題，建立模型并導(dǎo)入Cplex求得最終解，算法結(jié)束。

為了進(jìn)一步改善大規(guī)模下解的質(zhì)量，本文設(shè)計(jì)了混合遺傳算法HGA如2.2節(jié)所示。

2.2 混合遺傳算法HGA

2.2.1 染色體編碼與初始種群生成

選用實(shí)數(shù)編碼，染色體的長(zhǎng)度為n＋m－1，用－1～（－m＋1）作為劃分不同機(jī)器的標(biāo)識(shí)。圖2為將9個(gè)工件分配到3臺(tái)機(jī)器上加工的一條染色體示例。種群規(guī)模設(shè)為100，為保證種群多樣性，采用隨機(jī)生成的方法產(chǎn)生初始種群。

圖2 編碼示例Fig.2 An example of coding

2.2.2 解的改進(jìn)

如圖2所示，任一條染色體均包括m臺(tái)機(jī)器的工件加工序列。對(duì)于機(jī)器Mj，預(yù)防性維護(hù)時(shí)間段已知，將各工件依次插入其最早允許加工的時(shí)間間隙內(nèi)，可求得對(duì)應(yīng)機(jī)器的最大完工時(shí)間。由2.1節(jié)子問(wèn)題2可知，在工件分配到機(jī)器后該問(wèn)題轉(zhuǎn)化為變型的一維裝箱問(wèn)題，而MBS和降序首次適應(yīng)算法（first fit decreasing，F(xiàn)FD）［15］均是較好的求解裝箱問(wèn)題算法，其中FFD是指將物品按照體積大小進(jìn)行降序排列，然后按照順序?qū)⑽锲贩诺降谝粋€(gè)能裝下它的箱子去。因此在GA的種群進(jìn)化過(guò)程中，對(duì)每個(gè)新個(gè)體均執(zhí)行如下Education操作，對(duì)個(gè)體進(jìn)行改進(jìn)。

Education：針對(duì)染色體中各個(gè)機(jī)器Mj（i＝1，2，…，m）的工件序列，將其所有工件分別按照FFD、MBS規(guī)則重新排列得到、，計(jì)算3個(gè)序列的Cmjax并取最小值的工件排序?yàn)樽罱K序列πj，繼而將所有機(jī)器的πj組合為新染色體。

2.2.3 遺傳算子

由于本文采取實(shí)數(shù)編碼方式，選擇順序交叉法對(duì)2個(gè)染色體進(jìn)行交叉操作，選取互換變異進(jìn)行變異操作。遺傳算法中交叉概率一般取0.4～0.99，變異概率一般取為0.000 1～0.1。通過(guò)預(yù)實(shí)驗(yàn)調(diào)整，本算法選取交叉概率Pc＝0.8，變異概率Pm＝0.1。

2.2.4 適應(yīng)度函數(shù)與種群進(jìn)化機(jī)制

本文選取f（x）＝1／z作為適應(yīng)度函數(shù)并進(jìn)行指數(shù)尺度轉(zhuǎn)換f＇（x）＝exp［（n＋m）f（x）］；通過(guò)輪盤(pán)賭方式進(jìn)行選擇操作，假設(shè)f（xi）為第i染色體的適應(yīng)度值，染色體數(shù)量為N，則個(gè)體被選中的概率為；采用精英策略，使每一代最優(yōu)個(gè)體能不參與交配直接保留下一代中。

3 仿真實(shí)驗(yàn)

本文運(yùn)用優(yōu)化軟件ILOG CPLEX 12.1對(duì)線性整數(shù)規(guī)劃模型進(jìn)行求解，使用Visual C＃平臺(tái)實(shí)現(xiàn)兩類啟發(fā)式算法，仿真環(huán)境為內(nèi)存2.0 GB、主頻2.1 GHz的便攜式計(jì)算機(jī)。

3.1 算法驗(yàn)證

本文中，將2類算法結(jié)果Ch與最優(yōu)解Co的百分比誤差e＝（Ch－Co）·100／Co以及算法的運(yùn)行時(shí)間作為指標(biāo)來(lái)評(píng)估算法性能，并首先測(cè)試構(gòu)造型啟發(fā)式算法HCA的性能。考慮到不同問(wèn)題規(guī)模以及參數(shù)設(shè)置可能對(duì)算法結(jié)果產(chǎn)生影響，參照文獻(xiàn)［7］中的調(diào)度問(wèn)題算例生成方法并進(jìn)行適當(dāng)調(diào)整，生成如下測(cè)試算例：工件規(guī)模n∈［20，30，50，100，200，500，1 000］；機(jī)器規(guī)模m∈［2，3，5，10，20，30，50］；工件的加工時(shí)間pi服從［10，30］的均勻分布；每種問(wèn)題規(guī)模隨機(jī)生成10組不同算例。在參數(shù)設(shè)置時(shí)，對(duì)于機(jī)器的加工速率參數(shù)分別設(shè)置sj∈［1.0，2.0］、sj∈［1.0，1.5］；預(yù)防性維護(hù)周期參數(shù)選取Tj設(shè)置；預(yù)防性維護(hù)時(shí)間長(zhǎng)度參數(shù)也有tj＝Tj、tj＝Tj／5、tj＝Tj／10這3種設(shè)置，則共有18種參數(shù)設(shè)置。采用控制因子法，即在測(cè)試機(jī)器加工速率sj對(duì)算法影響時(shí)，對(duì)于每個(gè)sj將9種參數(shù)設(shè)置下共90個(gè)隨機(jī)算例的平均值作為輸出結(jié)果。同理，對(duì)于每個(gè)參數(shù)Tj、tj試驗(yàn)時(shí)分別將6種參數(shù)設(shè)置下的60組隨機(jī)算例的平均值作為輸出結(jié)果。數(shù)據(jù)測(cè)試結(jié)果如表1～3所示。

由表1～3可知，不同參數(shù)設(shè)置對(duì)啟發(fā)式算法HCA結(jié)果影響甚微，算法百分比誤差表現(xiàn)主要取決于問(wèn)題規(guī)模的大小。在規(guī)模小于時(shí)50×5時(shí)該算法可以在運(yùn)行時(shí)間小于2 s獲得與最優(yōu)解百分比誤差在5%以內(nèi)，當(dāng)問(wèn)題的規(guī)模達(dá)到200×10時(shí)，算法與CPLEX獲得的低界的百分比誤差接近10%。針對(duì)這一特點(diǎn)，本文提出了結(jié)合裝箱算法的混合遺傳算法對(duì)大規(guī)模問(wèn)題下的解進(jìn)一步改善。

表1 不同機(jī)器速率sj設(shè)置下HCA算法性能表現(xiàn)Table 1 The performance of HCA algorithm under different sjsetting

表2 不同預(yù)防性維護(hù)周期Tj參數(shù)設(shè)置下算法HCA性能表現(xiàn)Table 2 The performance of HCA algorithm under different Tjsetting

表3 不同維護(hù)時(shí)間長(zhǎng)度tj參數(shù)設(shè)置下算法HCA性能表Table 3 The performance of HCA algorithm under different tjsetting

表4 啟發(fā)式算法HCA與混合遺傳算法HGA比較Table 4 The comparison between heuristic HCA and improved genetic algorithm HGA

3.2 模型驗(yàn)證

生產(chǎn)實(shí)際中，生產(chǎn)計(jì)劃與維護(hù)計(jì)劃往往單獨(dú)決策，首先采用傳統(tǒng)的啟發(fā)式規(guī)則如MULTIFIT［19］得到一個(gè)生產(chǎn)部分的工件加工順序，繼而依據(jù)預(yù)防性維護(hù)周期T，得到完整的調(diào)度方案。

表5 聯(lián)合決策和單獨(dú)決策的算法結(jié)果比較Table 5 The comparison between joint decision-making and independent decision-making

圖3 聯(lián)合決策方法相對(duì)于單獨(dú)決策方法提升百分比GFig.3 The improvement of joint decision-making compared with independent decision-making

表5顯示了各類問(wèn)題規(guī)模下聯(lián)合決策優(yōu)化模型優(yōu)化方法相對(duì)于單獨(dú)決策模型優(yōu)化方法的數(shù)據(jù)實(shí)驗(yàn)比較，可以看出聯(lián)合決策模型的方法在犧牲少量運(yùn)算時(shí)間的情況下可得到更優(yōu)的解。圖3顯示了聯(lián)合決策的優(yōu)化方法HCA和HGA相對(duì)于單獨(dú)決策的優(yōu)化方法MULTIFIT的目標(biāo)值提升百分比，可以看出隨著問(wèn)題規(guī)模的增大，聯(lián)合決策的優(yōu)化方法優(yōu)勢(shì)愈加明顯，特別是HGA在問(wèn)題規(guī)模為1 000×50時(shí)較單獨(dú)決策的目標(biāo)值提升超過(guò)22%。

4 結(jié)論

本文針對(duì)具有周期預(yù)防性維護(hù)的異速并行機(jī)集成調(diào)度問(wèn)題進(jìn)行研究，建立了相應(yīng)的整數(shù)規(guī)劃模型，得到結(jié)論如下：

1）Cplex軟件能在可接受的時(shí)間內(nèi)（2 h）對(duì)問(wèn)題模型進(jìn)行求解，獲取工件與機(jī)器規(guī)模為50×5問(wèn)題的最優(yōu)解。

2）通過(guò)與求得的精確解或低界比較，表明本文提出的構(gòu)造型啟發(fā)式算法HCA能快速的求得中小規(guī)模問(wèn)題的滿意解，其GAP小于10%。而混合遺傳算法HGA在求解大規(guī)模問(wèn)題時(shí)效果更優(yōu)，其解得到明顯的改善。

3）與單獨(dú)決策的調(diào)度模型相比較，集成預(yù)防性維護(hù)的聯(lián)合決策方法較單獨(dú)決策方法的優(yōu)勢(shì)明顯，更有利于車(chē)間總體決策。

［1］LEE C Y.Machine scheduling with an availability constraint［J］.Journal of Global Optimization，1996，9（3）：395-416.

［2］MOSHEIOV G，SARIG A.Scheduling a maintenance activity to minimize total weighted completion time［J］.Computers and Mathematics with Applications，2009，57（4）：619-623.

［3］YANG S J.Minimizing total completion time on a single machine with a flexible maintenance activity［J］.Computers＆Operations Research，2011，38（4）：755-757.

［4］LIAO L W.Parallel machine scheduling with machine availability and eligibility constraints［J］.European Journal of Operational Research，2008，184（2）：458-467.

［5］RACEM M.Identical parallel machine scheduling under availability constraints to minimize the sum of completion times［J］.European Journal of Operational Research，2009，197（3）：1150-1165.

［6］TAN Z Y，CHEN Y.On the exact bounds of SPT for scheduling on parallel machines with availability constraints［J］.International Journal of Production Economics，2013，146（1）：293-299.

［7］CHOU J H，LOW C Y.A single-machine scheduling problem with maintenance activities to minimize makespan［J］.Applied Mathematics and Computation，2010，215（11）：3929-3935.

［8］XUEP F.Single machine scheduling with piece-rate maintenance and interval constrained position-dependent processing times［J］.Applied Mathematics and Computation 2014，226：415-417.

［9］LEE J Y.Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance［J］.Computers＆Operations Research，2012，39（9）：2196-2205.

［10］YANG S J.Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration［J］.Computers＆Industrial Engineering，2012，62（1）：271-275.

［11］蔣志高，董明.考慮維護(hù)且加工時(shí)間可變的單機(jī)調(diào)度問(wèn)題研究［J］.工業(yè)工程與管理，2011，16（3）：68-74.JIANG Zhigao，DONG Ming.Study on single machine problem with maintenance and variable processing time［J］.Industrial Engineering and Management，2011，16（3）：68-74.

［12］CHEN J S.Scheduling of non-resumable jobs and flexible maintenance activities on a single machine to minimize makespan［J］.European Journal of Operational Research，2008，190：90-120.

［13］金玉蘭，蔣祖華.預(yù)防性維修計(jì)劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2011，32（9）：1205-1209.JIN Yulan，JIANG Zuhua.Multi-objective optimization research on preventive maintenance and production scheduling［J］.Journal of Harbin Engineering University，2011，32（9）：1205-1209.

［14］崔維偉，陸志強(qiáng).單機(jī)系統(tǒng)的生產(chǎn)調(diào)度與預(yù)防性維護(hù)的集成優(yōu)化［J］.上海交通大學(xué)學(xué)報(bào)，2012，46（12）：2009-2013. CUI Weiwei，LU Zhiqiang.Integrating production scheduling and preventive maintenance planning for a single machine［J］.Journal of Shanghai Jiaotong University，2012，46（12）：2009-2013.

［15］SUN K B.Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines［J］.International Journal of Production Economics，2010，124（1）：151-158.

［16］程貞敏，李洪興.最小化時(shí)間表長(zhǎng)的平行機(jī)調(diào)度近似算法研究［J］.北京師范大學(xué)學(xué)報(bào)，2012，48（1）：11-15.CHENG Zhenmin，LI Hongxin.Approximated algorithm for identical machine scheduling with minimized makespan［J］.Journal of Beijing Normal University，2012，48（1）：11-15.

［17］XU D H.Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan［J］.Computers＆Operations Research，2008，35（4）：1344-1349.

［18］GUPTA J N D.A new heuristic algorithm for the one-dimensional bin-packing problem［J］.Production Planning＆Control，1999，10（6）：598-603.

［19］BURKARD R E.A note on MULTIFIT scheduling for uniform machines［J］.Computing，1998，61（1）：277-283.

Integrated uniform machine scheduling with periodic preventive maintenance

JIANG Cailin1，LU Zhiqiang1，CUI Weiwei2
（1.School of Mechanical and Energy Engineering，Tongji University，Shanghai 201804，China；2.School of Mechanical and Power Engineering，Shanghai Jiaotong University，Shanghai 200240，China）

A mixed integer programming model integrating the production scheduling and preventive maintenances is proposed to solve the unavailability constraints of uniform machine scheduling system problem.Specifically，a constructive heuristic algorithm（HCA）has been developed based on load balancing technology of improved longest processing time（LPT）rule and single machine optimization method of minimum bin slack heuristic.The numerical experiment compared with Cplex showed that the gap between the solution of HCA and optimal solution（low bound）is less than 10%for the small and medium scale problems.Furthermore，a hybrid genetic algorithm（HGA）combining bin-packing algorithm is proposed.The numerical experiment compared with HCA showed that the performance of HGA is better than HCA for large scale problems.Finally，the data experiments indicated that the joint decision-making model integrating production scheduling and machine maintenance appears to perform better than the independent decision-making model，as well as coordinate the overall plan of the production and maintenance effectively.

uniform machine scheduling；preventive maintenance；integer programming；heuristic algorithm；hybrid genetic algorithm

10.3969／j.issn.1006-7043.201307059

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006-7043.201307059.html

F224

A

1006-7043（2014）11-1409-06

2013-07-22.網(wǎng)絡(luò)出版時(shí)間：2014-09-25.

國(guó)家自然科學(xué)基金資助項(xiàng)目（71171130）；上海市自然科學(xué)基金資助項(xiàng)目（12ZR1414400）.

江才林（1989-），男，碩士研究生；陸志強(qiáng)（1968-），男，教授，博士生導(dǎo)師.

陸志強(qiáng)，E-mail：zhiqianglu＠#edu.cn.