崔 博，王吉波

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

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

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

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

1 問(wèn)題描述

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

(1)

(2)

2 主要結(jié)論

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

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

(3)

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

(4)

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

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

(5)

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

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

證明：與Wang等[14]的證明方法類(lèi)似。

(6)

其中

(7)

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

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

算法1步驟如下：

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

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

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

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

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

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

(8)

使其取得最小值，其中

(9)

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

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

(10)

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

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

(11)

其中

λi=

(12)

算法2步驟如下：

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

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

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

3 數(shù)值算例

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

例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é)論

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