趙玉芳, 陳狀狀, 何欣怡

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

0 引 言

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

定義1表明按時(shí)完工批中批的完工時(shí)間不超過(guò)批的工期。

定義2 某排序中,對(duì)于任意2個(gè)按時(shí)完工批P和Q,若批P在批Q前加工,則不存在P中的工件i和Q中的工件j,使得di>dj,稱此排序?yàn)榕鶨DD序。

下面用例子來(lái)說(shuō)明上述符號(hào)及定義。

例1 現(xiàn)有8個(gè)工件,加工時(shí)間分別為p=(4,1,2,1,6,2,3,3),s=1,不可用區(qū)間h1=[13,15),到達(dá)時(shí)間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。若批的加工順序?yàn)锽2,B3,B1,B4,則如圖1所示進(jìn)行加工,N0={B2,B3},N1={B1,B4},B1,B4為誤工批,B2,B3為未誤工批。

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

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

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

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

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

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

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

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

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

對(duì)于r

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面證明結(jié)論對(duì)于j個(gè)工件也成立。若按上述動(dòng)態(tài)規(guī)劃算法得到j(luò)個(gè)工件的最優(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單獨(dú)形成一批加工。而上述動(dòng)態(tài)規(guī)劃算法是對(duì)這3種情況比較之后取最小值。故結(jié)論成立。

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

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

例2 假設(shè)有4個(gè)工件Jj(i=1,2,3,4),加工時(shí)間pi=(3,5,2,4),工件權(quán)重wi=(1,4,2,5),工期di=(9,12,15,15),到達(dá)時(shí)間ri=(0,0,0,5),不可用區(qū)間h1=[8,9),工件安裝時(shí)間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誤工。利用反向追蹤可得到所有工件的一個(gè)最優(yōu)分批為B1={J2,J3},B2={J4},B3={J1},并且B1在不可用區(qū)間之前加工,B2在不可用區(qū)間之后加工,B3為誤工批排在最后。最優(yōu)排序如圖2所示。

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

4 結(jié) 論

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