到達(dá)時間與工期同序并帶有不可用區(qū)間的串行批處理機(jī)問題

趙玉芳, 陳狀狀, 何欣怡

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

0 引 言

在大規(guī)模的生產(chǎn)流水線,如電子產(chǎn)品制造系統(tǒng)、鋼鐵制造業(yè)、計算機(jī)集成制造系統(tǒng)、加工制造業(yè)等,常常有一臺或多臺機(jī)器可以成批地加工工件。同一批工件有相同的加工時間和完工時間,并且批的加工時間為批內(nèi)工件加工完的時間之和,只有批內(nèi)的工件都加工完成后才可以加工下一批,批的完工時間等于批中最后一個工件加工完的時間。由于機(jī)器的損壞、保養(yǎng)等現(xiàn)實因素,在一段時間之內(nèi)不能使用,這段時間為機(jī)器的不可用區(qū)間。在實際生產(chǎn)過程中,工件都有一個交貨期,其重要程度由權(quán)來決定。 本文研究的是帶有2個不同的到達(dá)時間和不可用區(qū)間,目標(biāo)是使得未按時完工工件的總加權(quán)誤工數(shù)最小的問題。

對于分批排序問題,興起于20世紀(jì)90年代初,是實際應(yīng)用背景極強(qiáng)的一類優(yōu)化問題,Ikura和Gimple[1]首次提出分批排序,在工件加工時間相等且到達(dá)時間與交付期同序的情況下,給出了時間復(fù)雜性為O(n2)的算法,來求解具有極小化最大完工時間的可行排序。Webster和Baker[2]對于批處理機(jī)排序問題進(jìn)行了綜述,依據(jù)加工特點將批處理機(jī)排序問題分為并行批(p-batch)模型、串行批(s-batch)模型和半連續(xù)批(c-batch)模型。

對于串行批處理機(jī)問題,批的加工時間等于批內(nèi)所有工件加工完成的時間之和。Yuan等[3]對于有到達(dá)時間、目標(biāo)函數(shù)為最大延誤問題的單機(jī)串行批處理機(jī)問題,給出了時間復(fù)雜性為O(n14logn)的多項式時間算法。Hochbaum和Landy[4]研究了目標(biāo)函數(shù)為極小化加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)問題,給出了擬多項式動態(tài)規(guī)劃算法。Brucker和Kovalyov[5]改進(jìn)了上述擬多項式動態(tài)規(guī)劃算法,并給出了復(fù)雜性為O(n2B)的完全多項式時間近似策略(fully polynomial time approximation scheme,FPTAS)。Cheng和Kovalyov[6]對于加工時間和工期有不同的固定的數(shù)、目標(biāo)函數(shù)為加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)問題,分別給出了擬多項式動態(tài)規(guī)劃算法。Baptiste[7]對于單機(jī)串行批處理機(jī),研究了工件帶有到達(dá)時間且所有工件的加工時間相同的加權(quán)誤工工件數(shù)問題,給出了多項式動態(tài)規(guī)劃算法。岳雅娟等[8]研究了到達(dá)時間與工期同序的加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)問題,并給出了擬多項式動態(tài)規(guī)劃算法。胡金昌等[9]研究了目標(biāo)函數(shù)為極小化加權(quán)總誤工并具有學(xué)習(xí)效應(yīng)的單機(jī)串行批處理機(jī)問題,給出了動態(tài)規(guī)劃算法和模擬退火算法。李豆豆[10]研究了具有2個競爭代理和工期可指派的單機(jī)串行批交付排序問題,目標(biāo)是極小化代理的目標(biāo)值,給出了擬多項式時間最優(yōu)算法和FPTAS。Yin等[11]研究了帶有交貨日期和2個競爭代理的單機(jī)串行批處理機(jī)問題,目標(biāo)是極小化加權(quán)誤工任務(wù)數(shù)并保證其他代理的標(biāo)準(zhǔn)值超過預(yù)先給定的閾值,證明了其是一般意義NP難的,并給出了FPTAS。Lu等[12]研究了單機(jī)串行批交付排序問題,目標(biāo)是極小化最大完工時間,證明了該問題是強(qiáng)NP難的并給出了3/2近似算法。Chen等[13]在其基礎(chǔ)上提出了改進(jìn)的4/3近似算法。鐘雪靈[14]對于給定截止期限的單機(jī)串行批處理機(jī)問題,目標(biāo)函數(shù)是最大提前完工時間,給出了計算復(fù)雜性為O(n3)的動態(tài)規(guī)劃算法。軒華等[15]研究了多階段柔性流水車間的極小化總加權(quán)完工時間串行批處理機(jī)排序問題,提出了改進(jìn)的遺傳算法。

對于不可用區(qū)間問題,趙玉芳等[16]研究了帶有退化工件、拒絕和不可用區(qū)間的2臺恒速機(jī)排序問題,其中一臺機(jī)器上帶有一段固定的不可用區(qū)間,此問題通過過程劃分的方法,提出了一個FPTAS,最后確定了其時間復(fù)雜性為O(n6L4/ε3)。金苗苗等[17]研究了機(jī)器具有不可用區(qū)間且工件可拒絕下的單機(jī)重新排序問題,該問題是NP-困難的,對此給出了偽多項式時間動態(tài)規(guī)劃精確算法,利用稀疏技術(shù)設(shè)計了完全多項式時間近似方案。

本文研究的問題與上述問題不同,增加了不可用區(qū)間,也就是機(jī)器帶有不可用區(qū)間,工件有2個不同的到達(dá)時間,并且到達(dá)時間與工期同序,每批工件加工前有安裝時間,批內(nèi)工件加工無需安裝時間,目標(biāo)函數(shù)為極小化加權(quán)誤工工件數(shù),不可用區(qū)間之后,機(jī)器恢復(fù)初始狀態(tài),每批工件加工前需要安裝時間。此問題目前還沒有人研究過。

1 問題描述

問題描述如下:設(shè)有n個工件J1,J2,…,Jn,按批在一臺批處理機(jī)上進(jìn)行加工。機(jī)器有不可用區(qū)間h1=[T1,T2)(其中,T1為不可用區(qū)間的左端點,T2為右端點),在不可用區(qū)間內(nèi)機(jī)器不能加工任何工件。工件有2個不同的到達(dá)時間r0,r1,不妨設(shè)r0=0,r1=r>0。工件Jj的加工時間為pj,工期為dj,且到達(dá)時間與工期是同序的(工件到達(dá)時間的大小順序與其工期大小順序相同),在某排序中的完工時間為Cj;如果Cj>dj,則稱工件Jj誤工,此時有Uj=1;否則,工件Jj未誤工,有Uj=0;誤工權(quán)為wj,j=1,…,n。Bi表示第i批,i≤n。批處理機(jī)的容量無限,只有當(dāng)同一批中的工件都到達(dá)后,這一批才可以進(jìn)行加工。假設(shè)所有的數(shù)據(jù)都為非負(fù)整數(shù)。批的加工時間為該批中所有工件加工完成的時間之和,同一批中的工件的完工時間相同并為該批中最后一個工件加工完成的時間,稱為批的完工時間。每一批工件在加工之前都有一個固定的安裝時間s,即批安裝時間。在批安裝時間內(nèi)機(jī)器不能加工任何工件,批內(nèi)的工件之間沒有安裝時間。工件加工時不允許中斷。不可用區(qū)間之后,機(jī)器恢復(fù)初始狀態(tài),批開始加工之前需要安裝時間。對于到達(dá)時間與工期同序并帶有不可用區(qū)間的極小化加權(quán)誤工工件數(shù)問題,用三參數(shù)表示法可表示為

1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj。

為了敘述方便,首先介紹一些符號。N表示要進(jìn)行加工的所有n個工件構(gòu)成的集合,Si表示在ri時刻到達(dá)的工件所組成的集合,i=0,1;N0表示在r0到r1之間開始加工的批構(gòu)成的集合,N1表示在r1或r1之后開始加工的批構(gòu)成的集合。則S0中的工件可能屬于N0,也可能屬于N1,而S1中的工件只能屬于N1。故S0∪S1=N,S0∩S1=φ,N0∪N1=N。若不可用區(qū)間在所有工件加工完成之后,不可用區(qū)間不起作用,這是平凡情況不考慮。

下面給出本文用到的定義。

定義1 批的工期定義為一批中所有工件的最小工期,批Bi的工期記為dBi;按時完工批是指由按時完工工件構(gòu)成的批。

定義1表明按時完工批中批的完工時間不超過批的工期。

定義2 某排序中,對于任意2個按時完工批P和Q,若批P在批Q前加工,則不存在P中的工件i和Q中的工件j,使得di>dj,稱此排序為批EDD序。

下面用例子來說明上述符號及定義。

例1 現(xiàn)有8個工件,加工時間分別為p=(4,1,2,1,6,2,3,3),s=1,不可用區(qū)間h1=[13,15),到達(dá)時間r=(0,0,0,0,0,0,10,10),工期d=(4,6,8,12,13,21,22,25)。

則S0={J1,J2,J3,J4,J5,J6},S1={J7,J8},若將工件分批為B1={J1},B2= {J2,J3},B3={J4,J5},B4={J6,J7,J8},則各批的工期為dB1=4,dB2=6,dB3=12dB4=21。若批的加工順序為B2,B3,B1,B4,則如圖1所示進(jìn)行加工,N0={B2,B3},N1={B1,B4},B1,B4為誤工批,B2,B3為未誤工批。

圖1 工件的加工時間表Fig.1 The processing timetable of the jobs

2 最優(yōu)解性質(zhì)

Hochbaum和Landy[4]證明了帶有安裝時間s及工期d,極小化加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)排序問題是NP難的。因此,帶有2個不同到達(dá)時間和1個不可用區(qū)間的問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj至少也是NP難的。下面給出該問題的最優(yōu)解性質(zhì),與文獻(xiàn)[8]證明類似,有

性質(zhì)1 對于問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj,存在一個最優(yōu)排序,使得其中同一按時完工批內(nèi)的工件都按照EDD序排列。

性質(zhì)2 對于問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj,存在一個最優(yōu)排序,使得N0和N1之中的按時完工批都按照批EDD序排列。

性質(zhì)3 對于問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj,存在一個最優(yōu)排序,使得按時完工批不含在不可用區(qū)間內(nèi)。

性質(zhì)4 對于問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj,存在一個最優(yōu)排序,其中不可用區(qū)間之前的按時完工批及不可用區(qū)間之后的按時完工批分別都按照批EDD序排列。

證明r和T1一共有3種位置關(guān)系,分別是r>T1,r=T1,r

由上述分析可知,在不可用區(qū)間之前,調(diào)換批P和Q之后,批P和Q中的工件依舊按時完工,并且其他批的開始加工時間都不增加,仍舊按時完工。經(jīng)過有限次這樣的調(diào)換后,得到了新排序,其中不可用區(qū)間之前的所有按時完工批都按批EDD序排列,目標(biāo)函數(shù)值不增加,因此依舊是最優(yōu)排序。

對于r

對于r≥T1的情況。與上述證明類似,可以得到不可用區(qū)間之前和不可用區(qū)間之后的所有按時完工批分別都按照批EDD序排序,目標(biāo)函數(shù)值不增加,排序依舊是最優(yōu)排序。

由此可知,任意一個最優(yōu)排序都可通過上述過程使得不可用區(qū)間前后的按時完工批都分別按照批EDD序排列。

由于所有工件的到達(dá)時間都與工期同序,由上述性質(zhì)1,4可推出以下推論。

推論對于問題1,h1|s-batch,rj∈{0,r},arg(rj,dj)|∑wjUj,存在一個最優(yōu)排序,其中不可用區(qū)間之前和之后的按時完工工件,都分別按照EDD序排列。

3 動態(tài)規(guī)劃算法

通過對j不誤工時可能的情況進(jìn)行討論,工件j的排序可歸納為以下2種情況:

由此可以得到下面的動態(tài)規(guī)劃算法(dynamic programming,DP):

步驟1 把工件按EDD序排列,即d1≤d2≤…≤dn;

步驟5 若j=n,計算W*=min{W:Cn(W)<+∞},利用反向追蹤得到工件的一個最優(yōu)分批,再將誤工工件以任意順序排在最后按時完工批的后面加工。否則,令j=j+1,轉(zhuǎn)步驟3。

定理1 基于上述動態(tài)規(guī)劃算法得到原調(diào)度問題的最優(yōu)解。

證明 下面用數(shù)學(xué)歸納法來證明這個結(jié)論。

當(dāng)j=1時,顯然成立。

當(dāng)j=2時,排序只能有2種分批情況:J1,J2分在一批或各自組成一批處理。比較其大小就可得到問題的解,這在算法中已經(jīng)體現(xiàn)。結(jié)論成立。

假設(shè)j-1時結(jié)論成立,即利用上述動態(tài)規(guī)劃算法可以得到問題的最優(yōu)分批。不失一般性,設(shè)工件按算法排序后的順序為J1,J2,…,Jj-1,則d1≤d2≤…≤dj-1;設(shè)最優(yōu)分批為π:B1,B2,…,Bl;且Bl={Jr+1,Jr+2,…,Jj-1}。

下面證明結(jié)論對于j個工件也成立。若按上述動態(tài)規(guī)劃算法得到j(luò)個工件的最優(yōu)分批的最后一批為Bq,其中d1≤d2≤…≤dj,Bq={Jr′+1,Jr′+2,…,Jj},則一定有Bq?Bl∪{Jj},也就是r′≥r。下面用反證法證明這一結(jié)論。

假設(shè)上述結(jié)論不成立,即r′

因此增加Jj工件后,最優(yōu)排序只能有3種情況:Jj誤工;Jj被分在Bl中加工;Jj單獨形成一批加工。而上述動態(tài)規(guī)劃算法是對這3種情況比較之后取最小值。故結(jié)論成立。

下面來分析此動態(tài)規(guī)劃算法的復(fù)雜性。

定理2 上述DP的時間復(fù)雜性為

例2 假設(shè)有4個工件Jj(i=1,2,3,4),加工時間pi=(3,5,2,4),工件權(quán)重wi=(1,4,2,5),工期di=(9,12,15,15),到達(dá)時間ri=(0,0,0,5),不可用區(qū)間h1=[8,9),工件安裝時間s=1。

∴C1(0)=4

∴C1(1)=0

2)j=2,C2(1)=6,C2(4)=4,C2(5)=0

3)j=3,C3(1)=8,C3(2)=4,C3(3)=6,C3(4)=6,C3(5)=3,C3(7)=0

4)j=4,C4(1)=14

最優(yōu)值W*=1,故只有J1誤工。利用反向追蹤可得到所有工件的一個最優(yōu)分批為B1={J2,J3},B2={J4},B3={J1},并且B1在不可用區(qū)間之前加工,B2在不可用區(qū)間之后加工,B3為誤工批排在最后。最優(yōu)排序如圖2所示。

圖2 工件的加工時間表Fig.2 The processing timetable of the jobs

4 結(jié) 論

本文主要研究了機(jī)器帶有不可用區(qū)間,工件帶有2個不同的到達(dá)時間且與工期同序的極小化加權(quán)誤工工件數(shù)的單機(jī)串行批處理機(jī)問題,分析了此問題的最優(yōu)解性質(zhì),給出了擬多項式動態(tài)規(guī)劃算法并證明了其時間復(fù)雜性。研究加工時間相同并且機(jī)器帶有不可用區(qū)間的極小化誤工工件數(shù)問題和機(jī)器帶拒絕且?guī)в胁豢捎脜^(qū)間的排序問題,具有較強(qiáng)的研究意義和實際背景。