帶有機器維修和兩車輛派送的單機排序問題

蔡 偉, 楊 梅

(1.南京審計大學(xué)金審學(xué)院 基礎(chǔ)教學(xué)部，江蘇 南京 210046; 2.中國石油大學(xué)(北京)克拉瑪依校區(qū)文理學(xué)院，新疆克拉瑪依 834000)

0 引言

件加工及派送和機器帶維修區(qū)間的排序問題是兩類重要的排序問題，由于這兩類排序問題在工業(yè)生產(chǎn)與物流管理中應(yīng)用前景廣闊，所以近年來得到了廣泛關(guān)注，而將兩者相結(jié)合的排序問題，與實際的生產(chǎn)生活結(jié)合更加緊密，具有更為重要的應(yīng)用價值。

對于加工及派送的排序問題已有大量學(xué)者進行了研究，如：Maggu等[1]首次考慮了工件需要運輸?shù)膯栴}，研究了兩機器流水作業(yè)問題，工件在第一臺機器上加工完成后由有限數(shù)量的運輸工運送到下一臺機器上繼續(xù)加工，每個工件的運輸時間由該工件決定，并利用Johnson算法解決了該問題。Chang等[2]考慮了目標函數(shù)是極小化最大工件完工時間的三類機器加工及運輸問題，首先對于單機加工后由單車輛派送給單客戶情形，他們證明了該問題是強NP-難的，給出界為5/3的近似算法，并證明了該界是緊界；其次對于兩臺平行機加工后由單車輛派送給單客戶情形，他們證明該問題是強NP-難的，并提出界是2的啟發(fā)式算法，并證明是緊界；最后對于單機器加工后由單車輛派送給兩個客戶情形，他們證明了該問題也是強NP-難的，并給出界為2的啟發(fā)式算法。Li等[3]研究了工件運輸?shù)蕉鄠€顧客的情形，給出了客戶數(shù)固定的情況下，目標函數(shù)是極小化最大工件完工時間的多項式時間算法，對于單客戶的特殊情形提出了時間復(fù)雜度較低的改進算法。Zhong等[4]對文獻[3]所研究的單機單客戶問題給出了界為3/2+ε的改進算法；對于平行機單客戶問題提出了界是5/3的改進算法。Lu等[5]對文獻[2]所研究的單機單客戶問題提出了界為3/2的啟發(fā)式算法；對于多客戶情形，批次派送時間定義為該批次內(nèi)工件最大派送時間的排序問題，提出了界為2的啟發(fā)式算法，并證明了界為緊界。Dong等[6]研究了單機加工并由單車輛派送到多客戶的排序問題，提出了界為2的啟發(fā)式算法，并對客戶數(shù)目為兩個的特殊情況提出了界為5/3的啟發(fā)式算法，并說明該算法是漸進緊的。Jiang等[7]研究了單機器分批加工并由兩臺同類車派送到單顧客的排序問題，提出了界為2的近似算法，并證明了該界是緊界。

現(xiàn)有文獻表明目前國內(nèi)外研究僅考慮了機器維修和工件派送兩者之一，很少將二者相結(jié)合；其次是只考慮到單車輛派送和工件體積相同等特殊的情況。這些較為特殊的情況都與實際生產(chǎn)生活中的企業(yè)、工廠的產(chǎn)業(yè)鏈及供應(yīng)鏈有所區(qū)別。本文綜合考慮機器維修和工件派送兩類排序問題，對單機器加工后由兩車輛派送到單客戶的情形給出了近似算法，為企業(yè)的生產(chǎn)與供應(yīng)鏈管理提供了理論依據(jù)。

1 問題描述及說明

本文研究的帶有機器維修和兩車輛派送到單顧客的排序問題，具體描述如下：給定工件集J={J1，J2,…,Jn}，工件的Ji體積為si(0

h(1)機器具有一個維修區(qū)間D工件加工完成后需要派送

k顧客的數(shù)量,v同類車的數(shù)量

c同類車的容積,T工件派送所需時間

Δ維修時長,δ維修前空閑時間

P所有工件加工時間和

SPT序按加工時間不減排序,LPT序按加工時間不增排序

定理1問題1,h(1)→D,k=1|v=2,c=1,T|Cmax是NP-難的。

證明把工件的加工時間都看成0，此時與機器加工無關(guān)，只需將工件分批派送，即轉(zhuǎn)化為一個裝箱問題，由于裝箱問題是NP-難的，則本文研究的問題也是NP-難的。

2 近似算法

本文需要綜合考慮工件加工與派送，那么算法整體可以構(gòu)造為兩階段流水作業(yè)模型，然后利用已知算法求解；其次，用于派送車輛的車輛容積固定，加工之前可以按照車輛容積對工件分批再按照批次加工，加工完成的批次可以直接派送；最后，由于機器含有一個維修區(qū)間，只需要維修不打斷批次，工件加工就不會中斷。按照以上對問題的分析，構(gòu)造的具體算法如下：

第1步依據(jù)每批體積不超過車輛總體積的原則，利用FFD算法對所有工件進行分批，記總批數(shù)為b，工件批次集記為B={B1,B2,…,Bb}。

第2步計算每個批次Bk加工所需時間Pk，其中k=1,2,…,b。

第3步按照如下規(guī)則構(gòu)造流水作業(yè)排序問題實例I(F2‖Cmax)。

任意批次Bk∈B在加工中心的加工時間為Pk，派送時間為T。

第4步利用Johnson算法最優(yōu)的求解所構(gòu)造的流水作業(yè)排序問題實例I，得到的排序記為π=。

按照π中的批次順序加工、交付批次，第一輛車派送奇數(shù)批次，第二輛車派送偶數(shù)批次；

同一批次加工不被維修打斷，即若維修前不能加工完該批次，則該批次放在維修后加工；

每一個批次內(nèi)工件加工順序任意，若車輛可用時有多個批次可派送，則先加工完的先派送。

3 最壞情況界分析

引理3由FFD-Johnson算法得到的Cmax，有以下結(jié)論：

證明若b=2，則Cmax=P+Δ+δ+T，顯然成立；若b>2，按如下情況進行分類討論：

(1)維修在SPT與LPT之間

(2)維修在SPT中

(3)維修在LPT中

(1)Cmax=P+Δ+δ+T;

(1)Cmax=P+Δ+δ+T;

定理2對于問題1,h(1)→D,k=1|v=2,c=1,T|Cmax，F(xiàn)FD-Johnson算法的界為2，且是緊界。

證明由引理4和引理5知定理第一部分成立。

眾所周知，下列二劃分問題是NP-難的。

4 結(jié)論

本文研究了帶有機器維修和工件派送的單機排序問題，不同體積的工件需要在帶有維修區(qū)間的機器上加工，且加工不可中斷，然后由固定容量的兩輛同類車分批派送給單客戶，目標函數(shù)是最小化最大完工時間。首先，根據(jù)裝箱問題的NP-難性證明了該問題也是NP-難的；其次，提出解決該問題的近似算法；最后分析了算法的最壞情況界，并證明了該界是緊界。