江才林，陸志強，崔維偉

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

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

江才林1，陸志強1，崔維偉2

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

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

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

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

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

1 問題描述

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

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

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

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

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

2 算法設(shè)計

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

2.1 啟發(fā)式算法HCA

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

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

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

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

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

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

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

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

③令i＝1。

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

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

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

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

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

2.2 混合遺傳算法HGA

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

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

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

2.2.2 解的改進(jìn)

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

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

2.2.3 遺傳算子

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

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

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

3 仿真實驗

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

3.1 算法驗證

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

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

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

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

表3 不同維護時間長度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 模型驗證

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

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

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

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

4 結(jié)論

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

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

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

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

［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］蔣志高，董明.考慮維護且加工時間可變的單機調(diào)度問題研究［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ù)防性維修計劃和生產(chǎn)調(diào)度的多目標(biāo)優(yōu)化［J］.哈爾濱工程大學(xué)學(xué)報，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］崔維偉，陸志強.單機系統(tǒng)的生產(chǎn)調(diào)度與預(yù)防性維護的集成優(yōu)化［J］.上海交通大學(xué)學(xué)報，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］程貞敏，李洪興.最小化時間表長的平行機調(diào)度近似算法研究［J］.北京師范大學(xué)學(xué)報，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ò)出版時間：2014-09-25.

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

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

陸志強，E-mail：zhiqianglu＠#edu.cn.