帶有遞送時間的工期窗口指派排序問題研究

崔 博，王吉波

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

在排序模型中，帶有遞送時間的排序問題受到了廣泛關(guān)注。Koulamas等[1]引入了依賴過去序列的遞送時間這一概念，假設(shè)工件的遞送時間與等待時間有一定的比例關(guān)系，提出帶有遞送時間的排序問題并應(yīng)用于電子制造業(yè)中，并對單機帶有遞送時間的極小化工件加工時間表長、最大延遲和最大延誤問題給出多項式時間算法。Liu等[2]研究了工件具有準(zhǔn)備時間的遞送時間單機排序問題，目標(biāo)是極小化總完工時間。在工件可中斷條件下，他們證明了此問題是多項式時間可解的，在不可中斷情況下，他們證明了此問題是NP難的，并提出了近似算法求解此問題。Liu等[3]研究了工件具有遞送時間單機排序問題，對一些正則和非正則目標(biāo)函數(shù)，他們給出了一些結(jié)論。Yang等[4]和Shen等[5]研究了工件加工時間具有學(xué)習(xí)效應(yīng)的單機排序問題。Liu[6]研究了帶有遞送時間和學(xué)習(xí)效應(yīng)的平行機排序問題。Yang[7]與 Zhao[8]研究了帶有遞送時間的單機排序問題，其中工件加工時間是位置的函數(shù)。他們證明了一些正則和非正則目標(biāo)函數(shù)問題都是多項式時間可解的。Yang等[9]研究了帶有遞送時間且具有惡化和學(xué)習(xí)效應(yīng)的排序問題。Wu[10]研究了帶有遞送時間和截斷學(xué)習(xí)效應(yīng)的單機排序問題，他們證明了極小化時間表長、加權(quán)總完工時間和最大延誤極小化問題均是多項式時間可解的。

另一方面，在準(zhǔn)時制生產(chǎn)過程中，在工期窗口前完工的工件要受到提前懲罰(比如提前完成，顧客還不需要，從而產(chǎn)生存儲和人工等費用)，在工期窗口后完工的工件也要受到延誤懲罰(比如顧客不滿意產(chǎn)生的費用)(Janiak等[11])。Wang等[12]研究了共同窗口指派模型，其中工件的加工時間具有學(xué)習(xí)與惡化效應(yīng)。對一個非正則目標(biāo)函數(shù)，他們給出了多項式時間最優(yōu)算法。劉春來等[13]研究了具有退化工件的共同工期窗口指派問題，在單機和兩臺機器的流水作業(yè)環(huán)境下，對一個非正則目標(biāo)函數(shù)分別給出了多項式時間算法。Wang等[14]研究了具有位置權(quán)重的窗口指派問題，對共同窗口指派和松弛窗口指派，他們分別對所提出的問題給出了多項式時間算法。

本文考慮工件同時帶有遞送時間和窗口指派的單機排序問題，且考慮了共同窗口和松弛窗口兩種情況。目標(biāo)是確定工件的排列順序、窗口的開始時間和結(jié)束時間，使得提前時間、延誤時間、窗口開始時間和窗口長度的加權(quán)和達到最小，其中權(quán)重為位置權(quán)重。對提出的問題最優(yōu)解進行分析，并給出多項式時間算法。

1 問題描述

假設(shè)零時刻到達n個工件J={J1,…,Jn}，他們要在一臺機器上加工，機器不可中斷且工件加工過程中也不允許中斷。設(shè)工件Ji的加工時間為pi，等待時間為wi，遞送時間為qi，S(i)代表排序中第i個位置，假設(shè)工件Ji的遞送時間與等待時間成比例，即

(1)

(2)

2 主要結(jié)論

2.1 位置權(quán)重的共同工期窗口問題

本節(jié)研究位置權(quán)重的共同工期窗口問題，且工件帶有遞送時間。所有的工件有共同的工期窗口[d1,d2]，其中d1≥0表示工期窗口的開始時間，d2(d2≥d1)表示工期窗口的結(jié)束時間，窗口大小為D=d2-d1，目標(biāo)是確定一個工件的加工序列和窗口位置，目標(biāo)函數(shù)為

(3)

使其最小，其中ωi>0(i=0,1,2,…,n,n+1)為第i個位置的權(quán)重(即位置權(quán)重)，LS(i)代表工件JS(i)提前(延誤)懲罰，且滿足

(4)

用三參數(shù)表示法，此問題可以表示為

顯然，存在一個最優(yōu)工件加工序列，從第一個工件在零時刻開始加工到最后一個工件加工結(jié)束，機器加工無空閑時間。令LS(0)=d1，LS(n+1)=D,則目標(biāo)函數(shù)整理為

(5)

引理1對于任意給定的工件加工序列S,存在一個最優(yōu)解，滿足工期窗口的開始時間和結(jié)束時間分別等于某個工件的完工時間，即

證明：與Wang等[14]的證明方法類似，分別考慮①CS(k)

證明：與Wang等[14]的證明方法類似。

(6)

其中

(7)

證明：基于引理1和引理2，假設(shè)給定最優(yōu)序列S且d1=CS(k)，d2=CS(l)，可知

其中λi由式(7) 給出。

算法1步驟如下：

步驟1：根據(jù)引理2計算出k和l的值;

步驟2：根據(jù) (7) 式計算λi的值;

步驟3： 根據(jù)HLP規(guī)則， 即最小的λi對應(yīng)最大的pS(i)， 第二小的λi對應(yīng)第二大的pS(i)，依次這樣，得到工件的最優(yōu)排序S*(i)(i=1,2,…,n)；

步驟4：計算共同工期窗口開始時間d1(d1=CS(k))和共同工期窗口結(jié)束時間d2(d2=CS(l))。

證明由引理1、2及其上面的敘述可以保證算法1的正確性。步驟1、2和4的時間復(fù)雜度是線性的，步驟3的時間復(fù)雜度是O(nlogn)，因此算法1的總時間復(fù)雜度為O(nlogn)。

2.2 位置權(quán)重的松弛工期窗口問題

(8)

使其取得最小值，其中

(9)

用三參數(shù)表示法，此問題可以表示為

其中slkw表示松弛工期窗口指派。不妨假設(shè)q1=LS(0)，D=LS(n+1)，則

(10)

類似于2.1節(jié)，我們有

引理3對于任意給定的工件加工序列S,存在一個最優(yōu)解，其中決策變量q1、q2分別等于某個工件的完工時間時，即

(11)

其中

λi=

(12)

算法2步驟如下：

步驟1:根據(jù)引理4計算出k和l的值;

步驟2:根據(jù)式(12)計算λi的值;

步驟3:根據(jù)HLP規(guī)則， 即最小的λi對應(yīng)最大的pS(i)， 第二小的λi對應(yīng)第二大的pS(i)，依次這樣，得到工件的最優(yōu)排序S*(i)(i=1,…,n);

3 數(shù)值算例

為了詳細(xì)說明算法的計算過程，舉出如下的例子。

例1：本例僅考慮共同工期窗口的情況(松弛工期窗口情況相似)。n=7，b=0.05，位置權(quán)重分別是ω0=2,ω1=7,ω2=4,ω3=5,ω4=8，ω5=2,ω6=6,ω7=1，ω8=10，p1=14,p2=16,p3=18,p4=19,p5=10,p6=15,p7=17。

4 結(jié)論

本文研究了帶有遞送時間和工期窗口指派的單機排序問題，目的是分別在共同和松弛兩種工期窗口下確定工件的排列順序和窗口位置，使得工件的提前時間、延誤時間和工期窗口的開始時間和工期窗口長度的加權(quán)和最小，其中權(quán)重為位置權(quán)重。證明了此問題是多項式時間可解的，并給出了求解算法。在以后的研究中，可以考慮工件的加工時間有可能存在的其他的影響(比如學(xué)習(xí)效應(yīng)或惡化效應(yīng),王吉波等[16-17])，或者可以考慮具有遞送時間和工期窗口指派的平行機或流水作業(yè)排序問題(王吉波等[18])。