趙玉芳, 何欣怡, 陳狀狀

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

0 引 言

工件有截止日期的約束問題在實際問題中普遍存在[1-3],并且在傳統(tǒng)的排序問題中,都假設(shè)每一個工件必須被加工。然而,在現(xiàn)實中決策者為了節(jié)省加工成本以獲得更大的利益,會選擇拒絕加工一部分工件而支付一定的費用。張玉忠[4]對工件可拒絕的排序問題進(jìn)行了綜述。Blazewicz[5]首先提出了誤工量問題,稱其為“信息丟失”,并介紹了極小化總加權(quán)誤工量的排序模型。Sterna[6]對早期的誤工量問題進(jìn)行了綜述。Potts和van Wassenhove[7]證明了單機總誤工量排序問題和單機總加權(quán)誤工量排序問題是一般意義NP-難的,并給出了擬多項式動態(tài)規(guī)劃算法。同年，Potts和van Wassenhove[8]對單機總誤工量排序問題又提出了2個FPTAS(fully polynomial time approximation scheme)算法。Wu等[9]研究了帶有學(xué)習(xí)效應(yīng)的總誤工量問題,構(gòu)造出一個分支定界算法并用遺傳算法得到了近似最優(yōu)解。對于極小化單機總加權(quán)誤工量的排序問題,Kovalyov等[10]對單機總加權(quán)誤工量排序問題提出了一個動態(tài)規(guī)劃算法,并設(shè)計了一個FPTAS。Hariri等[11]在上述動態(tài)規(guī)劃算法的基礎(chǔ)上對這個問題提出了一個算法復(fù)雜度為O(n2∑pj)的擬多項式動態(tài)規(guī)劃算法,對于工件的工期都相同的問題可以在O(n)時間內(nèi)求解,當(dāng)工件的加工時間相同時構(gòu)造了一個算法復(fù)雜度為O(n3)的最優(yōu)算法。Chen等[12]研究了工件具有加工位置上限的總加權(quán)誤工量問題,證明了當(dāng)工件具有相同工期時,問題是一般意義NP-難的,且構(gòu)造了一個擬多項式動態(tài)規(guī)劃算法,證明了當(dāng)工件具有單位權(quán)重的時候,問題是強NP-難的。Chen等[1]首次研究了工件有截止日期的問題,證明了帶有截止日期約束且工件工期相同時,總加權(quán)誤工量單機排序問題是一般意義NP-難的,并構(gòu)造了一個擬多項式動態(tài)規(guī)劃算法和一個FPTAS。

拒絕的概念首先由Bartal等[13]提出,此后得到了學(xué)者們的廣泛關(guān)注。Engels等[14]研究了帶有拒絕的單機排序問題,目標(biāo)函數(shù)為接受工件的總加權(quán)完工時間與拒絕工件的總拒絕懲罰之和,證明了其是NP-難的,并給出了動態(tài)規(guī)劃算法和FPTAS。Cheng和Sun[15]考慮了帶有退化和拒絕的單機排序問題,目標(biāo)函數(shù)為接受工件的最大完工時間與拒絕工件的總拒絕懲罰之和,證明了該問題是一般意義NP-難的,并給出了擬多項式時間動態(tài)規(guī)劃算法。國峰和王吉波[16]研究了帶有拒絕工件和學(xué)習(xí)效應(yīng)的資源約束排序問題,對線性和凸資源分配函數(shù)的2種模型給出了最優(yōu)求解算法,時間復(fù)雜度分別為O(n4)和O(n3)。

本文研究在截止日期的限制下,工件是可拒絕且工期都相同的總加權(quán)誤工量與拒絕懲罰之和的單機排序問題。

1 問題描述

2 可行性檢驗

3 主要結(jié)論

下面構(gòu)造一個擬多項式算法來求解這個NP-難問題。與文獻(xiàn)[7]和[17]中提出的方法類似,可以通過依次選取關(guān)鍵工件或者依次列舉關(guān)鍵工件的完工時間,再從所有的可行解中選擇最優(yōu)解。

對于問題P(J(c))的可行排序如圖1所示。

圖1 可行排序Fig.1 Feasible schedules

性質(zhì)1 問題P(J(c))存在一個最優(yōu)排序,排在J(c)之前的工件從0時刻開始以任意順序連續(xù)加工且無空閑時間。

性質(zhì)2 對于問題P(J(c)),存在一個最優(yōu)排序σ,排在J(c)之后的工件按截止日期不減的順序排列,即按照它們的下標(biāo)順序排列。

注意到工件Jj共有3種排序情況:

動態(tài)規(guī)劃算法DP1:

Step 1 對于j∈{1,2,…,n-1}和τ∈{0,1,…,d},有

定理2 動態(tài)規(guī)劃算法DP1的時間復(fù)雜性為O(n2d)。

證明 因為j∈{1,2,…,n-1},τ∈{0,1,…,d},Step 1的運行時間為O(nd),Step 2計算函數(shù)δ時j最多可以取遍{1,2,…,n-1},運行時間為O(n),因此動態(tài)規(guī)劃算法DP1在O(n2d)時間內(nèi)運行。

引理1 問題P(J(c))的最優(yōu)解為

(1)

Step 1 將工件按照截止日期的不減順序重新標(biāo)號。指定J1∈J作為關(guān)鍵工件,記為問題P(J(1)),k=1。

定理3 動態(tài)規(guī)劃算法DP2的時間復(fù)雜性為O(n3d)。

4 數(shù)值例子

求得WY(c)=9 ,工件排序為{J4,J2,J3,J(c)}或者{J4,J3,J(c)}。

2) 依次選取J2,J3,J4作為關(guān)鍵工件的情況同上。

5 結(jié) 論

本文研究了帶有截止日期和工件可拒絕的極小化總加權(quán)誤工量與拒絕懲罰之和的單機排序問題,該問題是NP-難的,用依次選取關(guān)鍵工件的方法構(gòu)造了一個擬多項式時間動態(tài)規(guī)劃算法,并證明了該算法的時間復(fù)雜度是O(n3d)。對于此問題的后續(xù)研究,如考慮不同機器環(huán)境下的平行機、恒速機等同一目標(biāo)函數(shù)的其他問題,或者考慮當(dāng)工件有單位權(quán)重時總加權(quán)誤工量與拒絕懲罰之和的問題,或研究允許中斷的情況等問題,都值得進(jìn)一步探討。