帶有拒絕工件的公共窗口指派單機排序問題

徐景孝，呂丹陽，王吉波

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

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

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

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

1 問題描述

(1)

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

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

(2)

2 主要結(jié)果

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

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

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

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

(1)情況一

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

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

(2)情況二

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

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

(3)情況三

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

(3)

其中

(4)

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

(5)

其中

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

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

(6)

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

(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計算k、l的值；

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

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

步驟 4：通過求解指派問題得出F(h)。

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

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

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

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

解

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

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

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

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

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

3 結(jié)論

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