趙玉芳, 何欣怡, 陳狀狀

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

0 引 言

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

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

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

1 問(wèn)題描述

2 可行性檢驗(yàn)

3 主要結(jié)論

下面構(gòu)造一個(gè)擬多項(xiàng)式算法來(lái)求解這個(gè)NP-難問(wèn)題。與文獻(xiàn)[7]和[17]中提出的方法類(lèi)似,可以通過(guò)依次選取關(guān)鍵工件或者依次列舉關(guān)鍵工件的完工時(shí)間,再?gòu)乃械目尚薪庵羞x擇最優(yōu)解。

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

圖1 可行排序Fig.1 Feasible schedules

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

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

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

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

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

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

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

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

(1)

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

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

4 數(shù)值例子

求得WY(c)=9 ,工件排序?yàn)閧J4,J2,J3,J(c)}或者{J4,J3,J(c)}。

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

5 結(jié) 論

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