徐景孝，呂丹陽(yáng)，王吉波

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

在以往的排序問(wèn)題中，一般假設(shè)所有的工件(也叫任務(wù)或作業(yè))都需要被加工。然而，為了降低制造成本，獲得更大利潤(rùn)，工件加工商往往選擇拒絕加工一些制造時(shí)間(成本)長(zhǎng)、利潤(rùn)小的工件，這就是具有拒絕工件的排序問(wèn)題。Bartal等[1]研究了工件可拒絕的平行機(jī)排序問(wèn)題。Chen等[2]證明了帶有拒絕工件的流水作業(yè)問(wèn)題中的最大完工時(shí)間問(wèn)題是NP難的。對(duì)于此問(wèn)題，他們給出了3種近似算法，并對(duì)復(fù)雜性進(jìn)行了分析。Koulamas等[3]研究了在公共工期條件下帶有拒絕工件的單機(jī)排序問(wèn)題，他們對(duì)總延誤和總加權(quán)延誤問(wèn)題分別給出了2個(gè)問(wèn)題的NP-難證明，并給出了一種改進(jìn)的近似算法和啟發(fā)式算法。王曉丹等[4]提出了帶有惡化和拒絕工件的工期指派的單機(jī)排序問(wèn)題的多項(xiàng)式時(shí)間算法。慕迪等[5]研究了帶有拒絕和到達(dá)時(shí)間的單機(jī)排序問(wèn)題，目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與所有被拒絕工件的拒絕費(fèi)用之和，他們給出了一個(gè)分支定界算法，并做了數(shù)值模擬。張玉忠[6]對(duì)各類拒絕工件的排序問(wèn)題進(jìn)行了綜述。

另一方面，拒絕工件是有限度的，不能無(wú)限制拒絕加工。如果經(jīng)常拒絕加工工件，不僅會(huì)使企業(yè)效益降低，也會(huì)使制造商的信譽(yù)下降。因此，為了避免這種情況，制造商希望在被拒絕的工件總拒絕懲罰不能超過(guò)給定上限的約束條件下，最小化給定的標(biāo)準(zhǔn)。這時(shí)就需要一個(gè)上限進(jìn)行約束，使得拒絕工件總費(fèi)用不得超過(guò)這個(gè)上限。劉曉霞等[7]研究了工件有到達(dá)時(shí)間且拒絕工件總個(gè)數(shù)受限的單機(jī)平行分批排序問(wèn)題，給出了所有工件到達(dá)時(shí)間都相同時(shí)的近似算法。Zhang等[8]證明了帶有拒絕上限的排序問(wèn)題中的最大延誤、總完工時(shí)間以及總提前延誤都是強(qiáng)NP-難的，并給出了在拒絕上限有限制下的最大延誤和最大完工時(shí)間問(wèn)題的擬多項(xiàng)式時(shí)間算法。Mor等[9]研究了在共同工期和拒絕上限條件限制下的總提前延誤和總加權(quán)提前延誤的單機(jī)排序問(wèn)題。Gerstl等[10]討論了一般工期下帶有拒絕的單機(jī)排序問(wèn)題中的最大延誤問(wèn)題，并給出了基于二劃分問(wèn)題的NP-難證明。國(guó)峰等[11]研究了具有拒絕工件和學(xué)習(xí)效應(yīng)的資源分配單機(jī)排序問(wèn)題，在線性資源和凸資源約束下，證明了一類正則目標(biāo)函數(shù)是多項(xiàng)式時(shí)間可解的。

本文考慮具有位置權(quán)重和可拒絕的公共窗口指派單機(jī)排序問(wèn)題，目標(biāo)函數(shù)包括工件的提前/延誤量、窗口開始時(shí)間、窗口大小的線性加權(quán)和以及拒絕費(fèi)用，其中權(quán)重只與工件被排在序列中的位置有關(guān)，即位置權(quán)重。本文給出了最優(yōu)解滿足的一些性質(zhì)，在拒絕工件個(gè)數(shù)為給定的情況下，證明了最優(yōu)排序問(wèn)題可以轉(zhuǎn)化成指派問(wèn)題進(jìn)行求解，從而證明這個(gè)問(wèn)題是多項(xiàng)式時(shí)間可解的，并做了算法復(fù)雜性分析。

1 問(wèn)題描述

(1)

最小，其中α是窗口開始時(shí)間的權(quán)重，β是窗口大小的權(quán)重。

用三參數(shù)表示法，本文所研究的問(wèn)題可以記為

(2)

2 主要結(jié)果

性質(zhì)1存在一個(gè)最優(yōu)排序，加工的工件集合A中，第一個(gè)工件從0時(shí)刻開始加工，且工件間無(wú)空閑時(shí)間。

證明性質(zhì)1顯然成立。

性質(zhì)2 存在一個(gè)最優(yōu)排序，公共窗口的開始時(shí)間d1和公共窗口的結(jié)束時(shí)間d2分別為某個(gè)工件的完工時(shí)間，即d1=C[k]，d2=C[l]，其中k和l為最優(yōu)排序中工件的某個(gè)位置，且k≤l。

證明：證明分為以下3種情況。

(1)情況一

存在一個(gè)最優(yōu)排序σ=[J1,J2,…,Jh]，d1不是序列中某個(gè)工件的完工時(shí)間，而d2是某個(gè)工件的完工時(shí)間，即C[k]

這就說(shuō)明窗口開始時(shí)間為某個(gè)工件的完工時(shí)間時(shí)，最優(yōu)排序存在。

(2)情況二

存在一個(gè)最優(yōu)排序σ=[J1,J2,……，Jh]，d2不是序列中某個(gè)工件的完工時(shí)間，而d1是某個(gè)工件的完工時(shí)間，即C[l]

這就說(shuō)明窗口結(jié)束時(shí)間為某個(gè)工件的完工時(shí)間時(shí)，最優(yōu)排序存在。

(3)情況三

存在一個(gè)最優(yōu)排序σ=[J1,J2,……，Jh]，d1、d2都不是序列中某個(gè)工件的完工時(shí)間，即C[k]

(3)

其中

(4)

證明對(duì)于任意排序σ=[J1,J2,……，Jh]，由性質(zhì)1和性質(zhì)2可知機(jī)器沒有空閑且d1=C[k]，d2=C[l]，則目標(biāo)函數(shù)可以化簡(jiǎn)為

(5)

其中

由引理1可知，一旦接受工件集A中的工件數(shù)目確定，則提前和延誤工件已知，這時(shí)候λi就與工件的加工順序無(wú)關(guān)，故有以下結(jié)論。

證明若接受工件集A中的工件數(shù)為h，即|A|=h，由引理2可知k、l的值，從而提前工件和延誤工件隨之確定。將提前工件排在前k個(gè)位置，延誤工件排在中間(h-l)個(gè)位置，其余工件放最后，由引理2，定義

(6)

為工件Jj,(j=1,2,…,n)排在第r個(gè)位置上的費(fèi)用。假設(shè)一個(gè)變量Xjr，如果工件Jj排在第r個(gè)位置上，則Xjr=1，否則Xjr=0。則問(wèn)題可歸結(jié)為如下的指派問(wèn)題。

(7)

(8)

(9)

Xjr∈{0,1},j=1,2,…n,r=1,2,…,n

(10)

算法1

步驟 1：給定h的值(h=0,1,2,…,n)，根據(jù)引理1計(jì)算k、l的值；

步驟 2：由引理2求λi的值；

步驟 3：根據(jù)定理1求得Wjr的值；

步驟 4：通過(guò)求解指派問(wèn)題得出F(h)。

步驟 5：最優(yōu)的目標(biāo)函數(shù)值為min{F(h)|h=0,1,2,…,n}。

證明在算法1中，對(duì)于每一個(gè)給定的h，步驟1、2、3都可以在O(n)時(shí)間得到，步驟4(指派問(wèn)題)的復(fù)雜性為O(n3)。h的范圍為h=0,1,2,…,n，所以算法1總的時(shí)間復(fù)雜性為O(n4)。

例1考慮6個(gè)工件的集合J={J1,J2,J3,J4,J5,J6}，窗口開始時(shí)間權(quán)重α為10，窗口大小權(quán)重β為30，其他參數(shù)見表1。

表1 例1的數(shù)據(jù)

解

①當(dāng)h=0時(shí)，此時(shí)接受工件集中的工件數(shù)為0，即所有工件均被拒絕，產(chǎn)生的費(fèi)用為所有拒絕費(fèi)用和，F(xiàn)(0)=1 116。

②當(dāng)h=1時(shí)，由步驟1可得k=1,l=0，由步驟2可得λi=[10,0,0,0,0,0]，步驟3得指派問(wèn)題的系數(shù)矩陣，通過(guò)求解指派問(wèn)題得最優(yōu)排序?yàn)閇J1]，拒絕工件為J2,J3,J4,J5,J6，目標(biāo)函數(shù)最優(yōu)值為1 096，詳見表2，黑體為最優(yōu)值解。

表2 指派問(wèn)題系數(shù)矩陣

表3 接受工件數(shù)h=2,…,6的結(jié)果

由以上實(shí)驗(yàn)結(jié)果可得，當(dāng)h=1時(shí)，目標(biāo)函數(shù)最優(yōu)。

3 結(jié)論

本文研究了具有公共交貨期窗口和工件可拒絕的單機(jī)排序問(wèn)題。所有工件被分成2個(gè)工件集，即接受工件集和拒絕工件集。在接受的工件中共享一個(gè)公共交貨期窗口，在窗口內(nèi)完工的工件不會(huì)產(chǎn)生任何額外費(fèi)用，否則都將會(huì)產(chǎn)生提前或延誤懲罰。拒絕工件集里的工件會(huì)產(chǎn)生拒絕費(fèi)用。證明了此問(wèn)題存在最優(yōu)的多項(xiàng)式時(shí)間算法。以后的研究可以考慮學(xué)習(xí)效應(yīng)[12]、惡化效應(yīng)[13]和拒絕工件結(jié)合在一起的情況，目標(biāo)函數(shù)是具有位置權(quán)重的窗口排序問(wèn)題Wang等[14]和Sun等[15])。