黃 雪，駱思雯，王吉波

(沈陽航空航天大學(xué) 理學(xué)院,沈陽 110136)

傳統(tǒng)的排序問題通常假設(shè)任務(wù)的加工時間是常數(shù)。但在現(xiàn)實中，很多任務(wù)的加工時間往往隨著開始時間的變化而變化[1]。如果任務(wù)的開始時間晚，那么它的加工時間就可能變長，這就是常說的惡化效應(yīng)。比如火災(zāi)救援中，消防人員到達火災(zāi)現(xiàn)場的時間越晚，搶救火災(zāi)的時間就會越長。鋼鐵生產(chǎn)中，如果鋼件處理有延誤就會導(dǎo)致加工時間變長。目前已經(jīng)有很多文獻研究帶有惡化效應(yīng)的排序問題，如Gupta等[2]、Huang等[3],Wang 等[4]，Li等[5],Sun等[6]。

近年來，準時制(JIT)已經(jīng)廣泛應(yīng)用于現(xiàn)代制造業(yè)和供應(yīng)鏈中。而在準時制策略中，企業(yè)向客戶交付產(chǎn)品或服務(wù)時，通常企業(yè)被允許有一個時間間隔，這個時間間隔被稱為工期窗口。一般用窗口的位置和長度來確定工期窗口。工期窗口過大，顧客不能接受，可能會導(dǎo)致顧客的流失；工期窗口過小，缺少生產(chǎn)彈性，企業(yè)不能接受。所以為了權(quán)衡雙方的利益，非常有必要確定每個任務(wù)合理的工期窗口。在工期窗口前完工的工件要受到提前懲罰，在工期窗口后完工的工件也要受到延誤懲罰，這就是工期窗口分配問題[7]。工期窗口一般可分為共同工期窗口、松弛工期窗口和不同工期窗口。Kramer等[8]研究了共同工期窗口排序問題。Liu等[9]研究了具有簡單惡化的共同工期窗口問題；Huang等[10]研究了具有一般惡化效應(yīng)的共同工期窗口問題；Wang等[11]研究了既有學(xué)習(xí)效應(yīng)又有惡化效應(yīng)的松弛工期窗口和不同工期窗口問題；Yue等[12]研究了簡單線性惡化的松弛工期窗口和不同工期窗口問題；Wang等[13]研究了與位置有關(guān)的加權(quán)窗口問題；Zhang等[14]研究了簡單線性惡化下兩個目標函數(shù)的共同工期窗口和松弛工期的窗口問題。

本文將工件加工時間具有一般線性惡化效應(yīng)的共同工期窗口指派問題[10]推廣到松弛工期窗口上。目標是確定工件的排列順序、窗口的開始時間和結(jié)束時間，使得兩種目標函數(shù)達到最優(yōu)。一個目標函數(shù)為提前時間、延誤時間、窗口開始時間和窗口長度的加權(quán)和；另一個目標函數(shù)為提前任務(wù)數(shù)、誤工任務(wù)數(shù)、窗口開始時間以及窗口長度的加權(quán)和。同時對所提出的問題給出多項式時間算法。

1 問題的描述

(1)

(2)

其中系數(shù)α≥0,β≥0,γ≥0,δ≥0，利用三元組記號法，以上兩個問題可以表示成

其中SLKDW(Slack Due Date Window)表示松弛工期窗口。

研究分兩部分解決上述兩個目標函數(shù)問題。

2.1 基本結(jié)論

易知，此問題一定存在著一個所有工件被連續(xù)加工而沒有空閑時間的最優(yōu)順序。

由文獻[16]可知，下面兩個引理成立。

引理2 對于任何指定的工件順序φ，一定存在最優(yōu)的q1,q2值，即q1=C[l*-1]，q2=C[k*-1]，其中l(wèi)*=min{max{0,|(n(δ-γ))/α|},n}，k*=min{max{0,「(n(β-δ))/β?},n}，[l]代表工件被排在第l個位置，這里C[0]=0(此處，由q1≤q2可知l*≤k*)。

由引理1可知,{J[1],…J[l*-1]}∈E，J[k*]∈O,{J[k*+1],…J[n]}∈T,{J[l*+1],…J[k*-1]}∈W。若l*=0，則無提前工件；如果l*=k*，則窗口里無工件；如果k*=n，則無延誤工件。

而Tj=0,(j=1,2,…,k*-1)，那么有

由此可整理出

2.2 最優(yōu)的工件加工順序

引理3 最優(yōu)順序中必滿足：

(1)各個集合內(nèi)部順序為：

①集合E里的工件按照LDR順序排列；

②集合O∪T中工件按SDR排列；

③集合F∪W中工件按任意順序排列。

(2)集合之間的順序為：

①集合F∪W中工件的惡化率要小于集合E和集合O∪T中工件的惡化率；

②集合E和集合O∪T中工件需要進一步按照引理4進行判斷。

證明：運用反證法和相鄰交換法易證，具體可參見文獻[12]。

引理4 假定工件Ju和Jv分別排在x和y的位置(1≤x≤l*-1,k*+1≤y≤n),

(1)如果Txy≥0,那么Ju和Jv的惡化率滿足bu

(2)如果Txy<0,那么Ju和Jv的惡化率滿足bu≥bv,

其中

證明：設(shè)最優(yōu)順序φ中Ju和Jv分別排在x和y的位置(1≤x≤l*-1,k*+1≤y≤n),將工件Ju和Jv交換位置而不改變其他工件的位置得到新加工順序記為φ′。對于順序φ和φ′，總目標函數(shù)值的不同之處僅在于Ju和Jv之間的目標函數(shù)值。不妨設(shè)φ中工件Ju的開始時間為t，G1(φ)和G1(φ′)分別為順序φ和φ′下Ju和Jv之間工件的目標函數(shù)值，那么

(1+bbt),pj(φ′)=bj(a+bt)(1+bbv)

因此可計算出

G2(φ′)-G2(φ)=(bv-bu)(a+bt)Txy

那么當Txy≥0,必有bu

2.3 最優(yōu)求解算法

最優(yōu)算法：

步驟1 將所有工件按照惡化率不減的順序重新標號：b[1]≤b[2]≤…≤b[n]。

步驟2 計算l*,k*的值，將J[1],…,J[k*-l*]排在集合F∪W中，并確定E有l(wèi)*-1個工件，O∪T有n-k*個工件。

步驟3 按照引理4計算Txy，并根據(jù)Txy的值來具體確定哪些工件排在集合E中哪些工件O∪T在中。

步驟4 對于集合E里的工件按照LDR順序排列；集合O∪T中工件按SDR排列；

并計算q1和q2，以及D=q2-q1和最優(yōu)目標函數(shù)值。

顯然算法1對所有工件進行排序，所以它的時間復(fù)雜度為O(nlogn)。

3.1 基本結(jié)論

引理5 對于任何指定的工件順序，一定存在最優(yōu)的松弛窗口滿足q1=C[l*-1]，q2=C[k*-1]其中1≤l*≤k*≤n，[l]代表工件被排在第l個位置。

證明：利用反證法易證，可以參見文獻[12]。

根據(jù)以上分析，方程(2)可以整理為式(3)

(3)

3.2 最優(yōu)的工件加工順序

根據(jù)文獻[10]中引理3～5，得到下面幾個結(jié)論。

引理6 在最優(yōu)排序中，集合E、F∪W和O∪T中的工件可以任意排序。

引理7 在最優(yōu)排序中，集合E和F∪W中的工件的惡化率需要滿足以下條件：

(1)如果γ≥δ,那么集合E中工件的惡化率都要小于集合F∪W中工件的惡化率；

(2)如果γ<δ,那么集合E中工件的惡化率都要大于集合F∪W中工件的惡化率。

引理8 在最優(yōu)排序中，集合F∪W中的工件的惡化率要小于集合O∪T中工件的惡化率；集合E中工件的惡化率要小于集合O∪T中工件的惡化率。

推論1：在最優(yōu)排序中，集合E、F∪W和O∪T中工件的惡化率滿足：

(1)如果γ≥δ,集合間惡化率順序為E→F∪W→O∪T；

(2)如果γ<δ,集合間惡化率順序為F∪W→E→O∪T。

3.3 最優(yōu)求解算法

最優(yōu)算法：

步驟1 按照惡化率的大小重新對工件進行標號b[1]≤b[2]≤…≤b[n]，令開始時間為t0=0。

步驟2 先令E、F∪W、O∪T為空集。再令l*從1到n進行取值，k*從l*到n進行取值，對于每一個組合(l*,k*)，如果γ≥δ,將轉(zhuǎn)到步驟3，如果γ<δ,將轉(zhuǎn)到步驟4。

步驟3 將J[1],…,J[l*-1]排入E中，將J[l*],…,J[k*-1]排入F∪W中，將剩余的工件加入O∪T，再按照公式(3)計算出目標函數(shù)值。

步驟4 將J[1],…,J[k*-l*]加入F∪W中，將J[k*-l*+1]…J[k*-1]加入E中，再將剩余的工件加入O∪T，最后按照公式(3)計算出目標函數(shù)值。

步驟5 選擇目標函數(shù)值最小的組合(l*,k*)即可，并計算q1、q2和D值。

由于考慮(l*,k*)的所有可能組合，顯然算法2的時間復(fù)雜度為O(n3)。

4 結(jié)論

本文研究單機更一般線性惡化的松弛窗口排序問題，給出解決問題的多項式時間算法。可以將本文的結(jié)果進一步拓展到不同工期窗口排序問題，并可以考慮將單機問題推廣到平行機問題中。