帶有機(jī)器維修和工件派送的單機(jī)排序問題

蔡 偉,楊 梅

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

0 引言

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

1 問題描述及符號(hào)說明

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

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

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

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

2 近似算法

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

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

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

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

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

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

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

3 最壞情況界分析

成立，于是對(duì)每個(gè)客戶i都可得

那么

那么

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

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

(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相同.

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

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

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

4 特殊情況

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

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

定理4 對(duì)于所給特殊問題(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序的批次不會(huì)空閑，所以當(dāng)車輛在派送LPT序的批次時(shí)有空閑，那么

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

(2)維修打斷SPT序.

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

b.車輛在派送LPT序批次時(shí)無(wú)空閑且車輛在派送SPT序的批次也無(wú)空閑,

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

ⅰ.當(dāng)K=K*時(shí),

ⅱ.當(dāng)K>K*時(shí),

(3)維修打斷LPT序.

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

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

b.車輛在派送LPT序批次時(shí)無(wú)空閑,

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

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