蔡 偉,楊 梅

(1.南京審計大學金審學院，江蘇南京 210046；2.中國石油大學(北京)克拉瑪依校區(qū)，新疆克拉瑪依 834000)

0 引言

機器加工及派送協(xié)同和帶維修區(qū)間的排序問題是兩類重要的排序問題，由于這兩類排序問題在制造生產(chǎn)與供應鏈管理中應用前景廣闊，所以近年來得到了廣泛研究.而機器帶維修區(qū)間的加工與工件派送相結(jié)合的排序問題，同樣具有重要的應用價值，得到了一定的關注和研究.

1 問題描述及符號說明

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

n工件的個數(shù)ni第i個客戶的工件數(shù)目m客戶的個數(shù)Jj第j個工件Y={J1,J2,…,Jn}總工件集合Y=J1∪J2∪…∪Jm總工件集合Ji={Ji1,Ji2,…,Jini}第i個客戶的工件集合P(B)集合B中工件的總加工時間ti工件派送到第i個客戶所需時間s維修開始的時間t維修結(jié)束的時間△維修時長δ維修前空閑時間Ba維修后加工的第一批次BqSPT序列中最后一個批次Bw決定批次P所有工件加工時間和

定理1 問題(1，h(1)→D，k=m|v=1，c=1，ti|Cmax)是NP-難的.

證明由現(xiàn)有結(jié)論知：問題(1，h(1)→D，k=1|v=1，c=1，ti|Cmax)是NP-難的，本文研究的問題是派送到多客戶情況，把派送到每個客戶的時間都看成相同就是現(xiàn)有結(jié)論中單客戶情形，所以問題[1，h(1)→D，k=m|v=1，c=1，ti|Cmax]也是NP-難的.或者可以把工件的加工時間都看成0，此時與機器加工無關，只需將工件分批派送，即簡化為一個裝箱問題，由于裝箱問題是NP-難的，那么本章節(jié)研究的問題也是NP-難的.

2 近似算法

第1步 依據(jù)每批體積不超過車輛總體積的原則，利用FFD算法對每個客戶的工件進行分批.

(3)將派送到客戶的時間按不減排序，最小記為t1,最大記為tm.

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

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

(1)按照π中的批次順序加工、交付批次；

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

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

3 最壞情況界分析

成立，于是對每個客戶i都可得

那么

那么

證明已知Cmax的取值是前面批次的完工時間與后面運送時間和，我們稱決定完工時間的批次w為決定批次.根據(jù)批次的加工時間與派送時間，批次分成SPT與LPT階段，按照維修的位置及決定批次的位置分以下情況證明.

由于情況(1)(3)(6)本質(zhì)上都是決定批次在SPT序內(nèi)部，并且維修在計算完工時間時不起作用，證明方式完全相同，本文只證明情況(1)即可.情況(2)(5)(7)(8)本質(zhì)上都是決定批次在LPT序內(nèi)部，證明過程相同者只證明其中一種.情況(4)本質(zhì)上是決定批次在SPT序內(nèi)部，但是放縮有所不同，需單獨證明.

(1)維修在SPT與LPT之間，即維修不打斷SPT和LPT序列.

a.決定批次在維修之前,

b.決定批次在維修之后,

(2)維修在SPT之間，即維修打斷SPT序列.

c.決定批次在維修之前，證明與(1)的a相同.

d.決定批次在維修之后,

ⅰ.決定批次在SPT內(nèi),

ⅱ.決定批次在LPT內(nèi)，證明與(1)的b相同.

(3)維修在LPT之間，即維修打斷LPT序列.

a.決定批次在維修之前,

ⅰ.決定批次在SPT內(nèi)，證明與(1)的a相同.

ⅱ.決定批次在LPT內(nèi),

b.決定批次在維修之后，證明與(1)的b相同.

對于問題(1，h(1)→D，k=m|v=1，c=1，ti|Cmax),本章節(jié)提出的FFD-Johnson算法得到的界不是緊界，這就需要我們提出更好的算法，或者是在最差性能比分析的過程中給出更細致與嚴格的放縮.

定理3 FFD-Jonhson算法的時間復雜度為O(nlogn)，n是工件個數(shù).

證明首先FFD裝箱算法所需時間是O(nlogn)，所分批次數(shù)目最多為n；其次比較批次的加工時間與派送時間，所需時間為最多為O(n)；最后對加工時間小于派送時間的批次按SPT序排，加工時間大于派送時間的批次按LPT序排，所需時間也是O(nlogn)；因此FFD-Jonhson算法的時間復雜度為O(nlogn).

4 特殊情況

接下來考慮只有一個客戶的特殊情況，即：工件在帶有一個不可用維修區(qū)間的機器上加工且由單車輛派送到單顧客的情形，問題表示為(1，h(1)→D，k=1|v=1，c=1，T|Cmax).

引理4 對于該特殊情況，最優(yōu)排序π*得到的最優(yōu)時間表長C*max滿足

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

證明若K*≥2，按維修區(qū)間的位置分以下幾種情形證明：

(1)維修不打斷SPT和LPT序.

a.由于車輛在派送SPT序的批次不會空閑，所以當車輛在派送LPT序的批次時有空閑，那么

b.若車輛在派送LPT序的批次時不空閑,

(2)維修打斷SPT序.

a.車輛在派送LPT序批次時有空閑,

b.車輛在派送LPT序批次時無空閑且車輛在派送SPT序的批次也無空閑,

c.車輛在派送LPT序批次時無空閑且在派送SPT序的批次時有空閑，此時空閑只會發(fā)生在維修后第一個批次加工完成之前，否則與派送SPT序的批次時有空閑矛盾，因此

ⅰ.當K=K*時,

ⅱ.當K>K*時,

(3)維修打斷LPT序.

a.車輛在派送LPT序批次時有空閑,

Cmax=P+△+δ+T≤2C*max.

b.車輛在派送LPT序批次時無空閑,

Cmax=P(B1)+KT≤2C*max.

緊界實例：設有兩個工件，加工時間與體積分別為J1=(1，∈)和J2=(∈，1),派送時間T=2∈，機器維修區(qū)間為[1，1+∈]，車輛容積為1，其中∈是趨于0的正常數(shù).利用FFD裝箱算法將工件分為兩個批次B1={J1}和B2={J2}.最優(yōu)算法是先加工B1再加工B2，所用時間為1+4∈,利用FFD-Johnson算法是先加工B2再加工B1，所用時間為2+3∈，于是當∈→0時,