到達時間與工期同序并帶有不可用區間的串行批處理機問題

趙玉芳, 陳狀狀, 何欣怡

(沈陽師范大學 數學與系統科學學院, 沈陽 110034)

0 引 言

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

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

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

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

本文研究的問題與上述問題不同,增加了不可用區間,也就是機器帶有不可用區間,工件有2個不同的到達時間,并且到達時間與工期同序,每批工件加工前有安裝時間,批內工件加工無需安裝時間,目標函數為極小化加權誤工工件數,不可用區間之后,機器恢復初始狀態,每批工件加工前需要安裝時間。此問題目前還沒有人研究過。

1 問題描述

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

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

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

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

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

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

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

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

例1 現有8個工件,加工時間分別為p=(4,1,2,1,6,2,3,3),s=1,不可用區間h1=[13,15),到達時間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所示進行加工,N0={B2,B3},N1={B1,B4},B1,B4為誤工批,B2,B3為未誤工批。

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

2 最優解性質

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

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

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

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

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

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

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

對于r

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

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

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

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

3 動態規劃算法

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

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

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

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

定理1 基于上述動態規劃算法得到原調度問題的最優解。

證明 下面用數學歸納法來證明這個結論。

當j=1時,顯然成立。

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

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

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

假設上述結論不成立,即r′

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

下面來分析此動態規劃算法的復雜性。

定理2 上述DP的時間復雜性為

例2 假設有4個工件Jj(i=1,2,3,4),加工時間pi=(3,5,2,4),工件權重wi=(1,4,2,5),工期di=(9,12,15,15),到達時間ri=(0,0,0,5),不可用區間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

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

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

4 結 論

本文主要研究了機器帶有不可用區間,工件帶有2個不同的到達時間且與工期同序的極小化加權誤工工件數的單機串行批處理機問題,分析了此問題的最優解性質,給出了擬多項式動態規劃算法并證明了其時間復雜性。研究加工時間相同并且機器帶有不可用區間的極小化誤工工件數問題和機器帶拒絕且帶有不可用區間的排序問題,具有較強的研究意義和實際背景。