井彩霞，吳瑞強(qiáng)，賈兆紅

(1.天津工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，天津 300387; 2.天津曙光存儲(chǔ)科技有限公司 存儲(chǔ)產(chǎn)品研發(fā)部，天津 300384; 3.安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230601)

0 引言

并行分批排序來(lái)源于半導(dǎo)體芯片的加工和成品檢驗(yàn)過(guò)程。在半導(dǎo)體芯片加工的擴(kuò)散區(qū)有批加工設(shè)備高溫?cái)U(kuò)散爐，在成品檢驗(yàn)的預(yù)燒區(qū)有批加工設(shè)備預(yù)燒爐。批加工是指一臺(tái)設(shè)備可同時(shí)加工多個(gè)工件，即批量加工。高溫?cái)U(kuò)散爐和預(yù)燒爐除了批加工外，還有一個(gè)共同點(diǎn)就是用時(shí)都比較長(zhǎng)。與其他工序用時(shí)幾分鐘、最多4個(gè)小時(shí)相比，高溫?cái)U(kuò)散爐一般需要6～24小時(shí)，預(yù)燒作業(yè)一般要120小時(shí)左右。加工耗時(shí)長(zhǎng)的特點(diǎn)，使其成為瓶頸機(jī)器。另外，批加工與非批加工方式的共存還會(huì)導(dǎo)致半導(dǎo)體生產(chǎn)線上加工流的不平穩(wěn)。因此，對(duì)批加工設(shè)備進(jìn)行優(yōu)化調(diào)度具有重要的現(xiàn)實(shí)意義。除了半導(dǎo)體生產(chǎn)線，批加工的特點(diǎn)還出現(xiàn)在冶金、電鍍等生產(chǎn)過(guò)程。日常生活中所用的烤箱也是一種批加工設(shè)備，可以同時(shí)烘烤一批面包，或面包和蛋糕一起烤。

以批加工為特點(diǎn)建立的排序模型即為廣義的分批排序(batch scheduling)。對(duì)分批排序，國(guó)內(nèi)外已有許多文獻(xiàn)研究，所研究問(wèn)題的種類也多種多樣。分批排序按批加工的方式可以分為兩大類：并行分批排序(parallel batch scheduling)和串行分批排序(serial batch scheduling)[1]。在并行分批排序中，同一批的工件同時(shí)加工，加工時(shí)間為批中所有工件的最大工時(shí)；在串行分批排序中，同一批的工件連續(xù)加工，加工時(shí)間為批中所有工件的工時(shí)之和。也有文獻(xiàn)稱這兩種分批方式下的排序?yàn)槠叫蟹峙判蚝屠^列分批排序[2]，或批處理機(jī)排序和成組分批排序[3]等。對(duì)并行分批排序也有文獻(xiàn)稱之為同時(shí)加工排序或批加工機(jī)器排序[4,5]等。

在早期的一些英文文獻(xiàn)中，稱分批排序?yàn)椤皊cheduling with batching and lot-sizing”[6]、“batch scheduling”[7]，“scheduling on batch processing machine”[8]，或“scheduling on burn-in oven”[9]等，在名字上并沒(méi)有對(duì)并行分批和串行分批做明顯區(qū)分。然而近期的很多文獻(xiàn)都用“parallel batch scheduling”[10,11]和“serial batch scheduling”[12,13]加以區(qū)別。隨著理論的成熟，問(wèn)題的分類更加細(xì)化，術(shù)語(yǔ)也越來(lái)越專業(yè)和科學(xué)化，這是科學(xué)研究發(fā)展的一個(gè)趨勢(shì)。

考慮到所描述問(wèn)題的機(jī)制和使用習(xí)慣，本文中采用 “并行分批”和“串行分批”來(lái)表示。本文主要對(duì)并行分批排序進(jìn)行綜述，且如無(wú)特別說(shuō)明，所涉及的問(wèn)題均為離線問(wèn)題。

一般認(rèn)為，Ikura和Gimple[14]是第一篇關(guān)于并行分批排序的文獻(xiàn)，在工件加工時(shí)間相等且到達(dá)時(shí)間與交付期一致(agreeable)的情況下，其針對(duì)是否存在可行排序的問(wèn)題，指出存在可行排序，并設(shè)計(jì)了一個(gè)時(shí)間復(fù)雜性為O(n2)的算法找出具有最小完工時(shí)間的可行排序。隨后90年代比較有影響力的相關(guān)文獻(xiàn)分別為L(zhǎng)ee等[15]和Brucker等[16]。其中Lee等[15]較詳細(xì)的闡述了并行分批排序產(chǎn)生的背景和研究的意義，并給出并行分批排序在單機(jī)和平行機(jī)環(huán)境下一些基本情形的解法。Brucker等[16]分別對(duì)批容量無(wú)限和批容量有限兩種情況下的單臺(tái)機(jī)器并行分批排序展開(kāi)研究，在所有工件具有相同到達(dá)時(shí)間的假設(shè)下，分析了問(wèn)題在多種目標(biāo)函數(shù)下的復(fù)雜性，并給出相應(yīng)算法。到了21世紀(jì)，關(guān)于并行分批排序問(wèn)題的文獻(xiàn)如雨后春筍般涌現(xiàn)，這種態(tài)勢(shì)至今有增無(wú)減，其中的成果大多來(lái)自國(guó)內(nèi)的科研工作者們。

關(guān)于并行分批排序問(wèn)題的綜述性文獻(xiàn)主要有Webster和Baker[17]、 Brucker等[16]、Potts和Kovalyov[18]、 Baptiste[19]、張玉忠[20]、Mathirajan和Sivakumar[21]、張玉忠和曹志剛[1]等。本文在前人工作的基礎(chǔ)上，對(duì)近10年來(lái)的研究成果和動(dòng)態(tài)進(jìn)行了綜述和分析，同時(shí)為了綜述的完整性，收錄了部分已有綜述文獻(xiàn)的內(nèi)容。

對(duì)已有成果涉及的并行分批排序問(wèn)題進(jìn)行梳理和分類如圖1所示。本文將以問(wèn)題為導(dǎo)向，按圖1中的框架結(jié)構(gòu)對(duì)并行分批排序進(jìn)行綜述。

圖1 已有成果中涉及的并行分批排序問(wèn)題分類示意圖

1 傳統(tǒng)機(jī)器環(huán)境和目標(biāo)函數(shù)框架下的并行分批排序

本節(jié)根據(jù)已有文獻(xiàn)中的成果，主要對(duì)單機(jī)和平行機(jī)機(jī)器環(huán)境下的并行分批排序問(wèn)題進(jìn)行綜述，在每種機(jī)器環(huán)境下，主要針對(duì)六個(gè)傳統(tǒng)目標(biāo)函數(shù)下的問(wèn)題進(jìn)行梳理，分別為極小化最大完工時(shí)間、極小化總完工時(shí)間、極小化最大延遲、極小化誤工工件數(shù)、極小化總延誤和極小化最大延誤。

1.1 單機(jī)并行分批排序

單機(jī)并行分批排序問(wèn)題的一般描述為：有n個(gè)工件J1,J2,…,Jn要在單臺(tái)機(jī)器上加工，記工件Jj的加工時(shí)間為pj，到達(dá)時(shí)間為rj，交貨期為dj，j=1,2,…,n。工件可成批加工，批容量為B，即機(jī)器每次最多可同時(shí)加工B個(gè)工件。同一批中的所有工件同時(shí)開(kāi)始加工，并同時(shí)結(jié)束，加工時(shí)間為批中所有工件的最大加工時(shí)間。一旦某批工件開(kāi)始加工，就不可中斷，加工期間也不能增加或減少工件，直至該批加工完成。以極小化最大完工時(shí)間的目標(biāo)函數(shù)為例，該問(wèn)題可用三參數(shù)法表示為1|B,rj|Cmax。如果所有工件的到達(dá)時(shí)間都相等，則可表示為1|B|Cmax。

1.1.1 極小化最大完工時(shí)間的單機(jī)并行分批排序

在極小化最大完工時(shí)間的目標(biāo)函數(shù)下，單機(jī)并行分批排序問(wèn)題又可根據(jù)批容量是否有限、工件是否同時(shí)到達(dá)等特點(diǎn)分為很多類，下面主要根據(jù)這兩個(gè)特點(diǎn)進(jìn)行分類介紹。

(1)批容量無(wú)限

批容量無(wú)限是指B≥n，也記作B=∞。這時(shí)所有的工件都可放在一批加工。

①工件同時(shí)到達(dá)

顯然，對(duì)排序問(wèn)題1|B=∞|Cmax，只需把所有工件放在一批加工即得最優(yōu)排序。

②工件不同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B=∞,rj|Cmax，Brucker等[16]設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃最優(yōu)算法，說(shuō)明該問(wèn)題是多項(xiàng)式時(shí)間可解的，并給出一個(gè)定理。

定理1若記工件不同時(shí)到達(dá)、目標(biāo)函數(shù)為Cmax的排序問(wèn)題為P1，相應(yīng)的工件同時(shí)到達(dá)、目標(biāo)函數(shù)為L(zhǎng)max的排序問(wèn)題為P2，則P1和P2可以O(shè)(n)時(shí)間內(nèi)相互轉(zhuǎn)換。

Lee[22]也設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性為O(n2)。Poon和Zhang[23]給出了一個(gè)時(shí)間復(fù)雜性為O(nlogn)的算法，并猜測(cè)這是理論上可能的最好算法。Yuan等[24]指出具有不相容工件簇(incompatible families)的排序問(wèn)題1|B=∞,rj|Cmax是強(qiáng)NP-難的，這里“不相容工件簇”是指所有工件分成若干類、不同類的工件不能同批加工，有些文獻(xiàn)中也稱之為“不相容工件族”或“不相容工件組”。對(duì)該NP-難問(wèn)題，Yuan等[24]給出兩個(gè)時(shí)間復(fù)雜性分別為O(n(n/m+1)m)和O(mkk+1P2k-1)的動(dòng)態(tài)規(guī)劃算法，其中n為工件數(shù)，m為工件簇?cái)?shù)，k為工件到達(dá)時(shí)間的個(gè)數(shù)，P為所有工件簇的加工時(shí)間和；另外，還給出一個(gè)緊界為2的啟發(fā)式算法和一個(gè)多項(xiàng)式時(shí)間近似方案(polynomial time approximation scheme, PTAS)。

(2)批容量有限

批容量有限是指B

①工件同時(shí)到達(dá)

②工件不同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B,rj|Cmax，其復(fù)雜性可由定理1和Brucker等[16]給出的另一個(gè)定理(定理2)推出。

定理2對(duì)具有交付期的批容量有限的單機(jī)并行分批排序，判斷問(wèn)題是否存在可行排序是強(qiáng)NP-難的，即使批容量B=2。

由定理2可知，排序問(wèn)題1|B|Lmax、1|B|fmax、1|B|ΣUj、1|B|ΣwjUj、1|B|Tj和1|B|ΣwjTj都是強(qiáng)NP-難的。再由定理1可知，排序問(wèn)題1|B,rj|Cmax也是強(qiáng)NP-難的。

此外，針對(duì)問(wèn)題的一般情況，Deng等[27]給出了一個(gè)PTAS；孫錦萍等[28]給出了一個(gè)比Deng等[27]中時(shí)間復(fù)雜性更低的PTAS；Sung和Choung[9]給出分支定界算法和啟發(fā)式算法；Li等[29]在排序問(wèn)題1|B,rj|Cmax的基礎(chǔ)上，考慮工件具有不同尺寸的特點(diǎn)，給出一個(gè)最壞性能比為2+ε的近似算法，并指出該算法在解工件具有相同尺寸的問(wèn)題時(shí)，會(huì)成為一個(gè)近似方案(approximation scheme)，并且時(shí)間復(fù)雜性低于Deng等[27]中的算法；李曙光等[30]給出一個(gè)總運(yùn)行時(shí)間為O(nlogn+Cn)的PTAS，其中C僅與精度ε有關(guān)，改進(jìn)了Deng等[27]中的PTAS。

Poon和Zhang[23]對(duì)到達(dá)時(shí)間個(gè)數(shù)確定和輸入為整數(shù)的情況，設(shè)計(jì)了一個(gè)算法，時(shí)間復(fù)雜性為O(n(BRmax)m-1(2/m)m-3)，其中m為到達(dá)時(shí)間的個(gè)數(shù)，Rmax為最后一個(gè)工件與第一個(gè)工件到達(dá)時(shí)間之差；并對(duì)到達(dá)時(shí)間個(gè)數(shù)和加工時(shí)間個(gè)數(shù)都確定的情況設(shè)計(jì)了一個(gè)算法，時(shí)間復(fù)雜性為O(nlogm+kk+2Bk+1m2logm)，其中k為加工時(shí)間的個(gè)數(shù)。姜冠成[31]針對(duì)排序問(wèn)題1|B,rj|Cmax建立0-1整數(shù)規(guī)劃模型，并利用軟件進(jìn)行數(shù)值求解，得出能夠獲得最優(yōu)解的問(wèn)題規(guī)模。

另外，對(duì)排序問(wèn)題1|B,rj|Cmax，井彩霞等[5]研究了工件成批到達(dá)的情況，該問(wèn)題與工件到達(dá)時(shí)間個(gè)數(shù)為常數(shù)的問(wèn)題是等價(jià)的。當(dāng)只有兩批工件時(shí)，Lee[22]給出了一個(gè)優(yōu)勢(shì)性質(zhì)?；贚ee[22]的優(yōu)勢(shì)性質(zhì)和FBLPT算法，井彩霞等[5]分別給出針對(duì)只有兩批工件情況和一般情況的啟發(fā)式算法。

1.1.2 極小化總完工時(shí)間的單機(jī)并行分批排序

對(duì)目標(biāo)函數(shù)為極小化總完工時(shí)間的單機(jī)并行分批排序問(wèn)題，本節(jié)同樣也根據(jù)批容量是否有限和工件是否同時(shí)到達(dá)這兩個(gè)特點(diǎn)分類介紹。

(1)批容量無(wú)限

①工件同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B=∞|ΣwjCj，Brucker等[16]指出該問(wèn)題是多項(xiàng)式時(shí)間可解的，并分別給出一個(gè)動(dòng)態(tài)規(guī)劃算法和一個(gè)逆向動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性分別為O(nlogn)和O(n2)。曹國(guó)梅[32]考慮具有不相容工件簇的排序問(wèn)題1|B=∞|ΣwjCj，并給出多項(xiàng)式時(shí)間最優(yōu)算法。

②工件不同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B=∞,rj|ΣwjCj，Deng等[33]首先指出目標(biāo)函數(shù)Σwj(Cj-rj)/Σwj、Σwj(Cj-rj)和ΣwjCj是等價(jià)的；然后證明了該問(wèn)題是NP-難的；隨后給出問(wèn)題在工件加工時(shí)間的取值個(gè)數(shù)為常數(shù)時(shí)的多項(xiàng)式時(shí)間最優(yōu)算法；并為排序問(wèn)題1|B=∞,rj|ΣCj設(shè)計(jì)了一個(gè)PTAS。Li等[34]為排序問(wèn)題1|B=∞,rj|ΣwjCj設(shè)計(jì)了一個(gè)PTAS，隨后Liu和Cheng[35]設(shè)計(jì)了一個(gè)完全多項(xiàng)式時(shí)間近似方案(fully polynomial time approximation scheme，F(xiàn)PTAS)。曹國(guó)梅[32]考慮具有不相容工件簇的排序問(wèn)題1|B=∞,rj∈{r1,r2,…,rk}|ΣwjCj，并給出一個(gè)啟發(fā)式算法，時(shí)間復(fù)雜性為O(2k-1nlogn)。Liu和Cheng[36]指出排序問(wèn)題1|B=∞,rj|ΣCj在多重性編碼(id-encoding)下是NP-難的。

(2)批容量有限

①工件同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B|ΣCj，Chandru等[37]給出了一個(gè)分支定界算法和兩個(gè)啟發(fā)式算法。Brucker等[16]給出了一個(gè)動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性為O(nB(B-1))，這說(shuō)明當(dāng)B為常數(shù)時(shí)，問(wèn)題是多項(xiàng)式時(shí)間可解的。當(dāng)B為變量時(shí)，Poon和Yu[38]對(duì)充分大的B，設(shè)計(jì)了時(shí)間復(fù)雜性為O(n6B)的算法。Cai等[39]設(shè)計(jì)了一個(gè)PTAS。

Chandru等[40]考慮工件具有多重性(high multiplicity)的分批排序問(wèn)題1|B|ΣCj，給出一個(gè)動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性為O(r3Br+1)，其中r為工件類型數(shù)。Hochbaum和Landy[41]將該時(shí)間復(fù)雜性改進(jìn)為O(r23r)，并針對(duì)工件類型數(shù)r不確定的情況，設(shè)計(jì)了一個(gè)2-近似算法。

對(duì)排序問(wèn)題1|B|ΣwjCj，Uzsoy和Yang[42]以及Azizoglu和Webster[43]均給出分支定界算法；Liu和Tang[44]給出了分支定界算法和啟發(fā)式算法；張召生和劉家壯[45]建立該問(wèn)題的數(shù)學(xué)規(guī)劃模型，并利用對(duì)偶理論證明了SPT序是B=1情況下的最優(yōu)解。苗翠霞和張玉忠[46]對(duì)所有工件加工時(shí)間都相等的特殊情況，給出最優(yōu)算法。張玲玲等[47]給出問(wèn)題在兩種特殊情況下的多項(xiàng)式時(shí)間最優(yōu)算法：一種情況是工件到達(dá)時(shí)間為正整數(shù)和具有單位加工時(shí)間；另一種情況是工件到達(dá)時(shí)間個(gè)數(shù)為常數(shù)和加工時(shí)間相等。

②工件不同時(shí)到達(dá)

排序問(wèn)題1|B,rj|ΣCj是強(qiáng)NP-難的[48,49]。丁際環(huán)等[50]證明了排序問(wèn)題1|B,rj∈{0,r}|ΣCj是NP完備的，并設(shè)計(jì)了一個(gè)最壞性能比為2的近似算法。對(duì)排序問(wèn)題1|B,rj|ΣCj，Chang等[51]利用約束規(guī)劃給出分支定界算法。Deng等[52]針對(duì)批容量B為常數(shù)的情況，給出PTAS。Liu和Cheng[35]針對(duì)B為變量的情況，給出PTAS。

Baptiste[19]對(duì)排序問(wèn)題1|B,pj=p,rj|ΣwjCj給出了一個(gè)多項(xiàng)式時(shí)間的最優(yōu)算法。任建鋒和張玉忠[53]對(duì)排序問(wèn)題1|B,rj|ΣwjCj給出一個(gè)PTAS。苗翠霞和張玉忠[54]證明了排序問(wèn)題1|B,rj∈{0,r}|ΣwjCj是NP完備的。

1.1.3 極小化最大延遲的單機(jī)并行分批排序

當(dāng)目標(biāo)函數(shù)為極小化最大延遲時(shí)，根據(jù)批容量是否有限和工件是否同時(shí)到達(dá)這兩個(gè)特點(diǎn)分類介紹如下。

(1)批容量無(wú)限

①工件同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B=∞|Lmax，Brucker等[16]給出一個(gè)逆向動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性為O(n2)，這說(shuō)明該問(wèn)題是多項(xiàng)式時(shí)間可解的。

②工件不同時(shí)到達(dá)

對(duì)排序問(wèn)題1|B=∞,rj|Lmax，Cheng等[55]證明了該問(wèn)題是NP-難的，并針對(duì)幾種特殊情況給出多項(xiàng)式時(shí)間算法。

(2)批容量有限

①工件同時(shí)到達(dá)

由定理2可知，批容量有限、工件同時(shí)到達(dá)的排序問(wèn)題1|B|Lmax是強(qiáng)NP-難的。Uzsoy[56]研究了具有不相容工件簇的情況，并給出多項(xiàng)式時(shí)間最優(yōu)算法。李文華和王炳順[57]討論了問(wèn)題存在只分一批為最優(yōu)解的充分條件。Cabo等[58]設(shè)計(jì)鄰域搜索方法對(duì)排序問(wèn)題1|B|Lmax進(jìn)行求解。

②工件不同時(shí)到達(dá)

顯然，排序問(wèn)題1|B,rj|Lmax也是強(qiáng)NP-難的。Wang和Uzsoy[59]首先給出一個(gè)動(dòng)態(tài)規(guī)劃算法，判斷給定序列的所有工件是否都可在交付期前完工；針對(duì)不能按期完工的情況設(shè)計(jì)了一個(gè)啟發(fā)式算法來(lái)極小化最大延遲；然后以啟發(fā)式算法為適應(yīng)度函數(shù)設(shè)計(jì)了一個(gè)遺傳算法；最后又將遺傳算法和二分搜索(bisection search)相結(jié)合，給出了二分搜索遺傳算法。Zhang和Ma[60]對(duì)排序問(wèn)題1|B,rj|Lmax給出了一個(gè)PTAS。Uzsoy[56]研究了具有不相容工件簇的情況，并設(shè)計(jì)了啟發(fā)式算法。

1.1.4 極小化誤工工件數(shù)的單機(jī)并行分批排序

在極小化誤工工件數(shù)的目標(biāo)函數(shù)下，根據(jù)批容量是否有限和工件是否同時(shí)到達(dá)這兩個(gè)特點(diǎn)分類介紹如下。

(1)批容量無(wú)限

①工件同時(shí)到達(dá)

②工件不同時(shí)到達(dá)

Liu等[61]對(duì)排序問(wèn)題1|B=∞,rj|Σfj給出了偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法，其中fj=fj(Cj)，為工件Jj完工時(shí)間Cj的非減函數(shù)，可以為ΣUj，ΣwjUj，ΣTj，ΣwjTj，ΣCj或ΣwjCj等。

(2)批容量有限

①工件同時(shí)到達(dá)

當(dāng)批容量有限，且工件同時(shí)到達(dá)時(shí)，由定理2可知，排序問(wèn)題1|B|ΣUj和1|B|ΣwjUj都是強(qiáng)NP-難的。Jolai[62]考慮具有不相容工件簇的排序問(wèn)題1|B|ΣUj，并指出當(dāng)工件簇?cái)?shù)和批容量任意時(shí)，問(wèn)題是NP-難的，并給出了一個(gè)動(dòng)態(tài)規(guī)劃算法。Li和Chen[63]研究工件分組，同組工件交付期相同的排序問(wèn)題1|B|ΣwjUj，給出了一個(gè)偽多項(xiàng)式時(shí)間算法和一個(gè)FPTAS，并分別考慮了權(quán)重相等和加工時(shí)間相等的情況，并給出多項(xiàng)式時(shí)間最優(yōu)算法。王春香和王曦峰[64]對(duì)交付期相等的排序問(wèn)題1|B,dj=d|ΣUj，設(shè)計(jì)了一個(gè)時(shí)間復(fù)雜性為O(n3logn)的最優(yōu)算法。劉麗麗等[65]對(duì)相同問(wèn)題給出時(shí)間復(fù)雜性為O(nlogn)的最優(yōu)算法。

②工件不同時(shí)到達(dá)

當(dāng)工件具有到達(dá)時(shí)間時(shí)，Lee等[15]指出排序問(wèn)題1|B,rj|ΣUj是NP-難的，并考慮了工件到達(dá)時(shí)間和交付期一致情況下的排序問(wèn)題1|B,pj=p,rj|ΣUj，給出一個(gè)動(dòng)態(tài)規(guī)劃算法，時(shí)間復(fù)雜性為O(n2B)。Li和Lee[66]指出工件到達(dá)時(shí)間和交付期一致的排序問(wèn)題1|B,rj|ΣUj是強(qiáng)NP-難的，并研究了工件到達(dá)時(shí)間、交付期和加工時(shí)間都一致的情況。Baptiste[19]指出排序問(wèn)題1|B,pj=p,rj|ΣwjUj是多項(xiàng)式時(shí)間可解的。

1.1.5 極小化總延誤的單機(jī)并行分批排序

對(duì)極小化總延誤的單機(jī)并行分批排序問(wèn)題，根據(jù)批容量是否有限和工件是否同時(shí)到達(dá)這兩個(gè)特點(diǎn)分類介紹如下。

(1)批容量無(wú)限

①工件同時(shí)到達(dá)

②工件不同時(shí)到達(dá)

Liu等[61]對(duì)排序問(wèn)題1|B=∞,rj|Σfj給出了偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法，其中fj=fj(Cj)，為工件Jj完工時(shí)間Cj的非減函數(shù)，可以為ΣTj，ΣwjTj，ΣUj，ΣwjUj，ΣCj或ΣwjCj等。

(2)批容量有限

①工件同時(shí)到達(dá)

當(dāng)批容量有限，工件同時(shí)到達(dá)時(shí)，由定理2可知，排序問(wèn)題1|B|ΣTj和1|B|ΣwjTj都是強(qiáng)NP-難的。Mehta和Uzsoy[68]考慮具有不相容工件簇的排序問(wèn)題1|B|ΣTj，指出當(dāng)工件簇?cái)?shù)和批容量為任意數(shù)時(shí)該問(wèn)題是強(qiáng)NP-難的，并給出動(dòng)態(tài)規(guī)劃算法和啟發(fā)式算法。劉麗麗等[65]對(duì)交付期相等的排序問(wèn)題1|B,dj=d|ΣTj給出偽多項(xiàng)式時(shí)間最優(yōu)算法，時(shí)間復(fù)雜性為O(B2dnB2-B+2)。

②工件不同時(shí)到達(dá)

同樣由定理2可知，排序問(wèn)題1|B,rj|ΣTj是強(qiáng)NP-難的。Baptiste[19]指出排序問(wèn)題1|B,pj=p,rj|ΣTj是多項(xiàng)式時(shí)間可解的。

1.1.6 極小化最大延誤的單機(jī)并行分批排序

當(dāng)目標(biāo)函數(shù)為極小化最大延誤時(shí)，由排序問(wèn)題1|rj|Tmax是強(qiáng)NP-難的，可知排序問(wèn)題1|B,rj|Tmax也是NP-難的。Ikura 和 Gimple[14]研究了工件到達(dá)時(shí)間與交付期一致的情況。Lee等[15]給出優(yōu)于Ikura和Gimple[14]中算法的動(dòng)態(tài)規(guī)劃算法，并研究了加工時(shí)間和交付期一致，以及所有工件加工時(shí)間相等的情況。Li 和Lee[66]指出工件到達(dá)時(shí)間和交付期一致的排序問(wèn)題1|B,rj|Tmax是強(qiáng)NP-難的，并研究了工件到達(dá)時(shí)間、交付期和加工時(shí)間都一致的情況。Baptiste[19]指出排序問(wèn)題1|B,pj=p,rj|Tmax是多項(xiàng)式時(shí)間可解的。

1.2 平行機(jī)并行分批排序

在平行機(jī)環(huán)境下，并行分批排序問(wèn)題一般可描述為：有n個(gè)工件J1,J2,…,Jn要在m臺(tái)平行機(jī)上加工，記工件Jj的到達(dá)時(shí)間為rj，交付期為dj，在機(jī)器Mi上的加工時(shí)間為pij,j=1,2,…,n,i=1,2,…,m。工件在每臺(tái)機(jī)器上都可成批加工，批容量為B，即機(jī)器每次最多可同時(shí)加工B個(gè)工件。同一批中的所有工件同時(shí)開(kāi)始加工，并同時(shí)結(jié)束，加工時(shí)間為批中所有工件的最大加工時(shí)間。一旦某批工件開(kāi)始加工，就不可中斷，加工期間也不能增加或減少工件，直至該批加工完成。以同型平行機(jī)和極小化最大完工時(shí)間的目標(biāo)函數(shù)為例，該問(wèn)題可用三參數(shù)法表示為P|B,rj|Cmax。如果所有工件的到達(dá)時(shí)間都相等，則可表示為P|B|Cmax。下面本節(jié)根據(jù)目標(biāo)函數(shù)的不同對(duì)平行機(jī)并行分批排序問(wèn)題進(jìn)行分類介紹。

(1)極小化最大完工時(shí)間

在極小化最大完工時(shí)間的目標(biāo)函數(shù)下，Lee等[15]指出并行分批排序問(wèn)題P|B|Cmax是強(qiáng)NP-難的，并給出最壞性能比為4/3-1/3m的算法，其中m為機(jī)器數(shù)。張玉忠等[69]利用轉(zhuǎn)換引理對(duì)排序問(wèn)題P|B|Cmax給出最壞性能比為2-1/m的算法，并指出該界是緊的，同時(shí)對(duì)排序問(wèn)題Q|B|Cmax給出了近似算法。劉麗麗和張峰[70]為排序問(wèn)題Pm|B=∞,rj|Cmax設(shè)計(jì)了一個(gè)偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法和一個(gè)FPTAS。Li[10]研究了平行多功能機(jī)環(huán)境下加工集合具有嵌套結(jié)構(gòu)的并行分批排序問(wèn)題PMPM|B,rj|Cmax，給出一個(gè)近似比為4-1/m的快速算法和一個(gè)PTAS，并對(duì)工件具有相同到達(dá)時(shí)間的特殊情況給出一個(gè)近似比為3-1/m的快速算法。

(2)極小化總完工時(shí)間

在極小化總完工時(shí)間的目標(biāo)函數(shù)下，Chandru等[37]對(duì)排序問(wèn)題P|B|ΣCj，給出兩個(gè)啟發(fā)式算法。任建鋒和張玉忠[53]對(duì)排序問(wèn)題Pm|B,rj|ΣCj給出批容量B和機(jī)器數(shù)m為常數(shù)情況下的PTAS。Li等[71]對(duì)排序問(wèn)題P|B=∞,rj|ΣwjCj給出一個(gè)PTAS。李曙光等[72]對(duì)排序問(wèn)題P|B,rj|ΣCj也給出了一個(gè)PTAS。苗翠霞和張玉忠[54]證明了排序問(wèn)題P2|B|ΣwjCj是NP-完備的。

(3)極小化最大延遲

在極小化最大延遲的目標(biāo)函數(shù)下，Lee等[15]指出并行分批排序問(wèn)題P|B|Lmax是強(qiáng)NP-難的，并給出了一個(gè)列表算法滿足不等式

其中L為列表算法所得的目標(biāo)函數(shù)值，L*為問(wèn)題的最優(yōu)目標(biāo)函數(shù)值，dmax表示最大交付期。另外Lee等[15]還指出即使在交付期相同、且交付期和加工時(shí)間一致的情況下，排序問(wèn)題P|B|Lmax也是強(qiáng)NP-難的。張玉忠等[69]對(duì)排序問(wèn)題Q|B|Lmax給出了近似算法。Li等[77]對(duì)排序問(wèn)題P|B,rj|Lmax給出一個(gè)PTAS。Liu等[78]指出所有具有到達(dá)時(shí)間和交付期的批容量無(wú)限的平行機(jī)并行分批排序問(wèn)題都是NP-難的，即使到達(dá)時(shí)間和交付期是一致的，且m=2；另外還對(duì)排序問(wèn)題Pm|B=∞,rj|Lmax設(shè)計(jì)了一個(gè)PTAS。

(4)極小化誤工工件數(shù)

在極小化誤工工件數(shù)的目標(biāo)函數(shù)下，劉麗麗和張峰[79]為排序問(wèn)題Pm|B=∞|ΣUj設(shè)計(jì)了偽多項(xiàng)式時(shí)間的順向動(dòng)態(tài)規(guī)劃算法。

(5)極小化總延誤

在極小化總延誤的目標(biāo)函數(shù)下，M?nch等[80]考慮具有不相容工件簇的排序問(wèn)題Pm|B,rj|ΣwjTj，并給出啟發(fā)式算法。M?nch 和Almeder[81]對(duì)具有不相容工件簇的排序問(wèn)題Pm|B|ΣwjTj，提出了一個(gè)螞蟻系統(tǒng)(ant system，AS)，與已有的基于調(diào)度規(guī)則的方法和遺傳算法相比，可以獲得稍好的解質(zhì)量，且運(yùn)算時(shí)間大大減少；另外，與最大最小螞蟻系統(tǒng)(max-min ant system)比較，兩者所得解的質(zhì)量相當(dāng)，但最大最小螞蟻系統(tǒng)需要更多的運(yùn)算時(shí)間。Bilyk等[82]考慮了具有不相容工件簇且同簇工件具有相同加工時(shí)間的排序問(wèn)題Pm|B,rj,prec|ΣwjTj，并設(shè)計(jì)了啟發(fā)式算法。

(6)極小化最大延誤

在極小化最大延誤的目標(biāo)函數(shù)下，劉麗麗和張峰[79]為排序問(wèn)題Pm|B=∞|Tmax設(shè)計(jì)了偽多項(xiàng)式時(shí)間的順向動(dòng)態(tài)規(guī)劃算法。

1.3 其他機(jī)器環(huán)境的并行分批排序

除了單機(jī)和平行機(jī)，還有文獻(xiàn)考慮其他機(jī)器環(huán)境下的并行分批排序問(wèn)題，如流水作業(yè)[83]、柔性流水作業(yè)[84]、混合流水作業(yè)[85]和柔性異序作業(yè)(flexible job shop)[86]等。

2 并行分批排序的擴(kuò)展和衍生

前文主要以傳統(tǒng)的機(jī)器環(huán)境和目標(biāo)函數(shù)為框架，對(duì)并行分批排序問(wèn)題進(jìn)行了綜述。隨著科學(xué)研究的發(fā)展和進(jìn)步，以及新的需求的產(chǎn)生，并行分批排序問(wèn)題不斷得到擴(kuò)展和衍生，尤其近幾年來(lái)，出現(xiàn)了很多新特點(diǎn)下的并行分批排序問(wèn)題。

2.1 差異尺寸工件的并行分批排序

在前面介紹的并行分批排序問(wèn)題中，默認(rèn)工件具有相同的尺寸。隨著相關(guān)領(lǐng)域設(shè)備與技術(shù)的不斷發(fā)展和進(jìn)步，以及用戶需求的不斷變化，加工任務(wù)也更加多樣化，導(dǎo)致出現(xiàn)更加復(fù)雜的并行分批排序問(wèn)題，其中工件或機(jī)器在尺寸或容量上出現(xiàn)差異性就是一個(gè)典型的新特點(diǎn)。下面將根據(jù)機(jī)器容量是否相同，對(duì)差異尺寸工件的并行分批排序問(wèn)題進(jìn)行分類介紹。

2.1.1 相同機(jī)器容量的差異尺寸工件并行分批排序

當(dāng)機(jī)器容量相同時(shí)，已有文獻(xiàn)中對(duì)差異尺寸工件并行分批排序問(wèn)題的研究主要集中在極小化最大完工時(shí)間的目標(biāo)函數(shù)。下面將分別對(duì)該目標(biāo)函數(shù)下的單機(jī)環(huán)境和平行機(jī)環(huán)境問(wèn)題進(jìn)行綜述。

(1)單機(jī)環(huán)境

Uzsoy[87]證明排序問(wèn)題1|S,sj|Cmax是NP難的，并基于FF(first fit)規(guī)則，給出了幾種啟發(fā)式算法，仿真實(shí)驗(yàn)表明其中的FFLPT(batch first fit & longest processing time)算法性能較優(yōu)。此外，Uzsoy[87]還給出了一個(gè)基于工件尺寸排序的啟發(fā)式算法，即FFDECR(batch first fit & decreasing order of sizes)算法。Zhang等[88]證明了FFLPT算法的最壞性能比不超過(guò)2，F(xiàn)FDECR算法的最壞性能比可能任意大；提出了一個(gè)啟發(fā)式算法，最壞性能比為7/4；同時(shí)還考慮了尺寸大于1/2的大工件的加工時(shí)間不少于尺寸小于1/2的小工件加工時(shí)間的情況，并設(shè)計(jì)了一個(gè)最壞性能比為3/2的啟發(fā)式算法。Dupont和Dhaenens-flipo[89]對(duì)排序問(wèn)題1|S,sj|Cmax提出了兩個(gè)啟發(fā)式算法，分別為BFLPT(best fit & longest processing time)算法和SKP(successive knapsack problem)算法，并證明了BFLPT算法是當(dāng)時(shí)求解該問(wèn)題的最優(yōu)啟發(fā)式算法。Kashan等[90]將Zhang等[88]中假設(shè)的工件尺寸1/2擴(kuò)展為1/m，其中m≥2為整數(shù)，并給出了絕對(duì)性能比(absolute worst-case ratio)為3/2、漸進(jìn)性能比(asymptotic worst-case ratio)為(m+1)/m的算法。

還有一些研究者致力于將智能算法應(yīng)用于該問(wèn)題的求解。Melouk等[91]首先引入模擬退火算法對(duì)問(wèn)題1|S,sj|Cmax進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明該模擬退火算法所得解的質(zhì)量?jī)?yōu)于商用軟件CPLEX，并提出目前通用的一種基于隨機(jī)方式生成仿真實(shí)驗(yàn)測(cè)試算例的方法。Kashan等[92]給出了兩個(gè)不同思路的遺傳算法，其中一個(gè)思路是先生成工件序列，然后再對(duì)工件進(jìn)行分批；另一個(gè)是先生成批序列，然后再通過(guò)啟發(fā)式的過(guò)程來(lái)保證解的可行性，最后通過(guò)合并和拆分來(lái)構(gòu)建批序列。Damodaran等[93]也采用遺傳算法求解了該問(wèn)題，通過(guò)對(duì)工件序列進(jìn)行編碼，針對(duì)問(wèn)題包含的加工序列和分批兩個(gè)方面的約束，對(duì)遺傳算法的交叉與變異算子進(jìn)行了新的設(shè)計(jì)，實(shí)驗(yàn)結(jié)果表明該算法優(yōu)于Melouk等[91]中的模擬退火算法。Cheng等[94]考慮了模糊制造系統(tǒng)下的單機(jī)并行分批排序，并提出一種結(jié)合Metropolis準(zhǔn)則的改進(jìn)型蟻群優(yōu)化算法，其中Metropolis準(zhǔn)則是一種隨機(jī)選擇機(jī)制，可以使算法以一定的概率接受差的解從而避免陷入局部最優(yōu)。Chen等[95]從聚類的角度給出一個(gè)聚類算法，計(jì)算實(shí)驗(yàn)表明該算法優(yōu)于BFLPT算法和Damodaran等[93]中的遺傳算法。Jia和Leung[96]對(duì)排序問(wèn)題1|S,sj|Cmax給出了一個(gè)下界，并提出一種改進(jìn)的最大最小蟻群算法，計(jì)算實(shí)驗(yàn)表明，該算法優(yōu)于Uzsoy[87]中的FFDECR算法和FFLPT算法、Kashan等[92]中的遺傳算法，和Chen等[95]中的聚類算法等。

此外，對(duì)排序問(wèn)題1|S,sj|Cmax，Cheng和Kovalyov[97]考慮了工件加工時(shí)間隨著加工資源數(shù)量減少而減小、具有交付期和批帶有準(zhǔn)備時(shí)間的情況，提出了兩種動(dòng)態(tài)規(guī)劃算法極小化最大完工時(shí)間。Dupont和Dhaenens-flipo[89]和Koh等[98]都考慮了工件具有不相容工件簇的情況，其中Dupont和Dhaenens-flipo[89]給出一個(gè)分支定界算法；Koh等[98]給出了一系列的啟發(fā)式算法和遺傳算法，并且除了極小化最大完工時(shí)間，還考慮了極小化總完工時(shí)間和極小化總加權(quán)完工時(shí)間的目標(biāo)函數(shù)。程八一 等[99]研究了具有模糊批加工時(shí)間和模糊批間隔時(shí)間的情況，并提出一種集成粒子群優(yōu)化和差異演化的混合算法。

對(duì)工件具有到達(dá)時(shí)間的差異尺寸工件單機(jī)并行分批排序問(wèn)題1|S,sj,rj|Cmax，Sung和Choung[9]提出了性能較好的啟發(fā)式算法；Li等[29]給出一個(gè)最壞性能比為2+ε的近似算法；Chou等[100]給出一個(gè)混合遺傳算法；Xu等[101]給出混合整數(shù)規(guī)劃模型和下界，并設(shè)計(jì)了一個(gè)啟發(fā)式算法和一個(gè)蟻群優(yōu)化算法，計(jì)算實(shí)驗(yàn)表明，所提蟻群優(yōu)化算法比Chou等[100]中的混合遺傳算法具有更好的性能；吳翠連[102]針對(duì)尺寸大于1/2的大工件的加工時(shí)間不少于尺寸小于1/2的小工件加工時(shí)間的情況，給出最壞性能比為3/2+ε的近似算法；張玉忠等[103]考慮只有兩個(gè)到達(dá)時(shí)間且工件加工時(shí)間和尺寸大小一致的情況，并給出最壞性能比不超過(guò)33/14的算法；馬冉和張玉忠[104]研究了具有特殊到達(dá)時(shí)間、工件加工時(shí)間相等且具有優(yōu)先約束的情況，給出最壞性能比不超過(guò)2的近似算法。

(2)平行機(jī)環(huán)境

相對(duì)于差異尺寸工件的單機(jī)并行分批排序問(wèn)題，平行機(jī)并行分批排序問(wèn)題的求解難度更大。當(dāng)問(wèn)題因約束復(fù)雜而求解難度增大時(shí)，研究者往往采用智能算法對(duì)問(wèn)題進(jìn)行求解。

針對(duì)差異尺寸工件的平行機(jī)并行分批排序問(wèn)題Pm|S,sj|Cmax，Chang等[105]提出了模擬退火算法，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所提模擬退火算法的求解性能優(yōu)于商業(yè)軟件CPLEX。Damodaran和Chang[106]提出了若干啟發(fā)式算法，他們將問(wèn)題分解為工件分批和批分配至機(jī)器兩個(gè)子問(wèn)題，分別采用了FFLPT算法和BFLPT算法分批，再利用LPT和Multifit啟發(fā)式規(guī)則對(duì)批進(jìn)行排序，其中Multifit規(guī)則本質(zhì)上是一種二分法，其通過(guò)判斷問(wèn)題目標(biāo)值上下界的平均值是否可行來(lái)不斷減小上界或增大下界，從而逐漸縮小上下界的距離，獲得問(wèn)題的近似解。實(shí)驗(yàn)結(jié)果表明Damodaran和Chang[106]所提啟發(fā)式算法在大規(guī)模問(wèn)題上的性能優(yōu)于CPLEX，與Chang等[105]中的模擬退火算法相當(dāng)。Shao等[107]將神經(jīng)網(wǎng)絡(luò)應(yīng)用于該問(wèn)題，通過(guò)與Damodaran和Chang[106]中所提的啟發(fā)式算法進(jìn)行對(duì)比，驗(yàn)證了神經(jīng)網(wǎng)絡(luò)方法的優(yōu)越性。Kashan等[108]提出一種混合遺傳啟發(fā)式算法，該算法通過(guò)遺傳算子產(chǎn)生隨機(jī)批來(lái)搜索解空間。在該算法中，對(duì)每一個(gè)生成的后代染色體，采用一個(gè)隨機(jī)分批過(guò)程用于保證其可行性；然后通過(guò)LPT規(guī)則將生成的可行批排序到機(jī)器上；最后通過(guò)兩個(gè)局部搜索啟發(fā)式算法進(jìn)一步改進(jìn)算法的求解效果。實(shí)驗(yàn)結(jié)果表明混合遺傳啟發(fā)式算法優(yōu)于Chang等[105]提出的模擬退火算法。Damodaran等[109]設(shè)計(jì)遺傳算法來(lái)求解排序問(wèn)題Pm|S,sj|Cmax，仿真實(shí)驗(yàn)結(jié)果表明，所提遺傳算法的性能優(yōu)于模擬退火算法、隨機(jī)鍵遺傳算法和混合遺傳啟發(fā)式算法。杜冰等[110]論證了平行機(jī)并行分批排序問(wèn)題Pm|S,sj|Cmax實(shí)質(zhì)為一種廣義聚類問(wèn)題，并基于批的空間浪費(fèi)比，提出批的約束凝聚聚類算法，為分批排序問(wèn)題的求解提供了一種新的途徑。Jia和Leung[111]基于最大最小螞蟻系統(tǒng)算法和Multifit規(guī)則提出一種智能算法ASM(Ant system based meta-heuristic)求解排序問(wèn)題Pm|S,sj|Cmax，計(jì)算實(shí)驗(yàn)表明，ASM算法的性能優(yōu)于Damodaran和Chang[106]中的啟發(fā)式算法和Kashan等[108]所提的混合遺傳啟發(fā)式算法。

另外，對(duì)排序問(wèn)題Pm|S,sj|Cmax，張?chǎng)蔚萚112]研究了工件可以按尺寸拆分的情況，指出該問(wèn)題是NP-完備的，并給出一個(gè)最壞性能比不超過(guò)11/4-1/m的近似算法；Chen等[113]針對(duì)工件具有到達(dá)時(shí)間的情況，分別設(shè)計(jì)了蟻群優(yōu)化算法和遺傳算法；吳翠連和陳俊[114]考慮工件具有到達(dá)時(shí)間、且尺寸大于1/2的大工件的加工時(shí)間不少于尺寸小于1/2的小工件加工時(shí)間的情況，并設(shè)計(jì)了一個(gè)最壞性能比為3/2+ε的多項(xiàng)式時(shí)間近似算法；Zhou等[115]針對(duì)工件具有到達(dá)時(shí)間的情況，設(shè)計(jì)了幾個(gè)啟發(fā)式算法，計(jì)算實(shí)驗(yàn)表明，這些算法在解的質(zhì)量上優(yōu)于已有的幾個(gè)啟發(fā)式算法和智能算法。

Li等[116]研究了非同類機(jī)排序問(wèn)題Rm|S,sj|Cmax，給出了一個(gè)下界，并基于BFLPT算法設(shè)計(jì)了幾個(gè)啟發(fā)式算法。Arroyo和Leung[117]考慮工件具有到達(dá)時(shí)間的排序問(wèn)題Rm|S,sj,rj|Cmax，給出混合整數(shù)規(guī)劃模型和下界，并設(shè)計(jì)了幾個(gè)有效的啟發(fā)式算法。

2.1.2 不同機(jī)器容量的差異尺寸工件并行分批排序

當(dāng)排序問(wèn)題Pm|S,sj|Cmax中機(jī)器容量由相同擴(kuò)展到不同時(shí)，就得到機(jī)器容量不同且差異尺寸工件的平行機(jī)并行分批排序問(wèn)題，用三參數(shù)法可表示為Pm|S,sj|Cmax，其中Si表示第i臺(tái)機(jī)器Mi的容量。

已有研究中，對(duì)不同機(jī)器容量的并行分批排序問(wèn)題涉及的較少。對(duì)排序問(wèn)題Pm|Si,sj|Cmax，Damodaran等[118]給出了一個(gè)粒子群優(yōu)化算法；Jia等[119]設(shè)計(jì)了兩個(gè)啟發(fā)式算法，并通過(guò)計(jì)算實(shí)驗(yàn)表明其性能優(yōu)于Damodaran等[118]中的粒子群優(yōu)化算法。賈兆紅等[120]基于工件松弛的方法給出了一個(gè)下界的計(jì)算方法，并設(shè)計(jì)了一個(gè)啟發(fā)式算法H和一個(gè)蟻群優(yōu)化算法，計(jì)算實(shí)驗(yàn)表明，所提蟻群優(yōu)化算法性能優(yōu)于啟發(fā)式算法H和Damodaran等[118]中的粒子群優(yōu)化算法。Zhou等[121]研究了同類機(jī)排序問(wèn)題Qm|Si,sj|Cmax，給出混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了基于差分進(jìn)化算法的混合算法，計(jì)算實(shí)驗(yàn)表明該算法在解的質(zhì)量和魯棒性方面優(yōu)于CPLEX商業(yè)軟件、隨機(jī)鍵遺傳算法和粒子群優(yōu)化算法。

在排序問(wèn)題Pm|Si,sj|Cmax中，若工件具有到達(dá)時(shí)間，就成為排序問(wèn)題Pm|Si,sj,rj|Cmax。Xu和Bean[122]構(gòu)建了排序問(wèn)題Pm|Si,sj,rj|Cmax的整數(shù)規(guī)劃模型，提出基于隨機(jī)鍵的遺傳算法。Chen等[113]指出排序問(wèn)題Pm|Si,sj,rj|Cmax是強(qiáng)NP難的，分別基于FBLPT算法和機(jī)器負(fù)載給出了問(wèn)題的兩個(gè)下界，并分別設(shè)計(jì)蟻群優(yōu)化算法和遺傳算法對(duì)工件分批問(wèn)題進(jìn)行求解，再采用ERT-LPT(earliest release time-longest processing time)啟發(fā)式規(guī)則將批分配到平行批處理機(jī)上。Wang和Chou[123]首先分別用模擬退火算法和遺傳算法將工件分配到機(jī)器上，然后采用多階段動(dòng)態(tài)規(guī)劃算法對(duì)每臺(tái)機(jī)器上的工件進(jìn)行分批。Jia等[124]基于松弛的方法提出了一個(gè)下界，并設(shè)計(jì)了一個(gè)啟發(fā)式算法和一個(gè)蟻群算法，計(jì)算實(shí)驗(yàn)表明，所提蟻群算法優(yōu)于Wang 和Chou[123]中的遺傳算法和Damodaran等[118]中的粒子群優(yōu)化算法。

另外，對(duì)排序問(wèn)題Pm|Si,sj,rj|Cmax，Li[125]針對(duì)不同批容量數(shù)固定的情況，給出近似比任意接近2的算法；Li[126]針對(duì)具有包含關(guān)系結(jié)構(gòu)的多功能機(jī)環(huán)境，設(shè)計(jì)了一個(gè)PTAS。Arroyo和Leung[127]研究了非同類機(jī)排序問(wèn)題Rm|Si,sj,rj|Cmax，給出了下界和混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了基于迭代貪婪算法的智能算法。

2.2 多目標(biāo)和新目標(biāo)函數(shù)下的并行分批排序

除了單目標(biāo)函數(shù)，還有文獻(xiàn)研究雙目標(biāo)或多目標(biāo)函數(shù)下的并行分批排序問(wèn)題，如張召生等[128]、李文華[129,130]、He等[131]、焦峰亮等[132,133]、Liu等[134]、李小襯[135]、Geng和Yuan[136,137]、Zhang等[138]等。除了常見(jiàn)的目標(biāo)函數(shù)，張玉忠和王琳[139]研究目標(biāo)函數(shù)為加權(quán)延遲工作和的排序問(wèn)題1|B=∞|ΣwjVj，其中Vj=min{Tj,pj}；李文華[130]討論了目標(biāo)函數(shù)為極小化完工時(shí)間平方之和的單機(jī)并行分批排序問(wèn)題。

2.3 工件具有先后約束關(guān)系的并行分批排序

Cheng等[140]研究了工件具有先后約束且加工時(shí)間相等的單機(jī)并行分批排序問(wèn)題。鄒娟和張玉忠[141]、馬冉等[142]、卜憲敏等[143]和劉偉[144]考慮了具有平行鏈約束的單機(jī)并行分批排序問(wèn)題。

2.4 工件帶運(yùn)輸時(shí)間的并行分批排序

2.5 加工時(shí)間離散可控的并行分批排序

柏孟卓和唐國(guó)春[151]、王磊和張玉忠[152]研究加工時(shí)間離散可控的單機(jī)并行分批排序問(wèn)題。這里加工時(shí)間離散可控是指工件具有若干可選的加工時(shí)間，每個(gè)備選加工時(shí)間都對(duì)應(yīng)一個(gè)控制費(fèi)用，一般要使工件在比較短的時(shí)間內(nèi)完工，需要付出比較大的費(fèi)用，加工時(shí)間和費(fèi)用因素均在目標(biāo)函數(shù)的考慮之中。

2.6 工件具有惡化加工時(shí)間的并行分批排序

在并行分批排序問(wèn)題中，工件具有惡化加工時(shí)間(deteriorating job)是指工件的實(shí)際加工時(shí)間與開(kāi)始時(shí)間有關(guān)，開(kāi)始加工時(shí)間越晚，需要的加工時(shí)間越長(zhǎng)，一般這種關(guān)系用線性函數(shù)來(lái)表示。在Qi等[153]、Miao等[154]、Li等[155]、Zou和Miao[156]所研究的模型中，工件Jj的實(shí)際加工時(shí)間為pj=bjt，其中t為開(kāi)始加工時(shí)間，bj為惡化率；余英等[157]考慮了惡化加工時(shí)間為pj=p(a+bt)的單機(jī)并行分批排序問(wèn)題，其中p為基本加工時(shí)間，a,b為正的常數(shù)，t為開(kāi)始加工時(shí)間；在Miao等[158]中，惡化加工時(shí)間計(jì)算公式為pj=αj(A+Dt)，其中αj為惡化率，A,D為正的常數(shù)，t為開(kāi)始加工時(shí)間。

2.7 工件加工時(shí)間具有學(xué)習(xí)效應(yīng)的并行分批排序

2.8 機(jī)器具有禁用區(qū)間的并行分批排序

Yuan等[161]和齊祥來(lái)等[162]考慮機(jī)器具有禁用區(qū)間(forbidden interval)的單機(jī)并行分批排序問(wèn)題，這里機(jī)器具有禁用區(qū)間是指機(jī)器在給定的禁用時(shí)間區(qū)間內(nèi)不能加工工件，一般出于機(jī)器需要定期維護(hù)的考慮。

2.9 工件具有交付時(shí)間窗的并行分批排序

Zhao和Li[163]、韓國(guó)勇等[164]和趙洪鑾等[165]研究工件具有交付時(shí)間窗(due window)的單機(jī)并行分批排序問(wèn)題。交付時(shí)間窗由交付期擴(kuò)展而來(lái)，通常給定交付期為某個(gè)時(shí)間點(diǎn)，而交付時(shí)間窗為某個(gè)時(shí)間區(qū)間，若工件在該時(shí)間區(qū)間內(nèi)完工，則是按期完工；如果完工時(shí)間早于區(qū)間開(kāi)始時(shí)間或晚于區(qū)間結(jié)束時(shí)間，則是提前或延遲完工，會(huì)產(chǎn)生懲罰費(fèi)用。顯然，交付時(shí)間窗可給予工件完工時(shí)間更大的靈活性。如果給定工件交付期，完工時(shí)間早于或晚于交付期都會(huì)受到懲罰，則為準(zhǔn)時(shí)(just-in-time)排序問(wèn)題，李文華等[166]研究了準(zhǔn)時(shí)單機(jī)分批排序問(wèn)題。

2.10 節(jié)能并行分批排序

在生產(chǎn)調(diào)度中考慮能源效率即得節(jié)能排序問(wèn)題。已有考慮節(jié)能并行分批排序的文獻(xiàn)多數(shù)都是針對(duì)單機(jī)環(huán)境的。在單機(jī)環(huán)境下：Mouzon和Yildirim[167]研究同時(shí)極小化總能耗和總延遲時(shí)間的問(wèn)題；Yildirim和Mouzon[168]考慮了同時(shí)極小化總完工時(shí)間和能源消耗的問(wèn)題，并給出了一個(gè)多目標(biāo)的遺傳算法；Shrouf等[169]建立了一個(gè)極小化能源消耗成本的數(shù)學(xué)規(guī)劃模型；Liu等[170]考慮了到達(dá)時(shí)間確定的雙目標(biāo)并行分批排序，優(yōu)化的目標(biāo)為總完工時(shí)間和總二氧化碳排放量；Che等[171]研究了極小化總電力成本的并行分批排序問(wèn)題，并給出啟發(fā)式算法； Cheng等[172]研究了實(shí)時(shí)電價(jià)下的并行分批排序問(wèn)題，同時(shí)極小化最大完工時(shí)間和總的電力成本，給出混合整數(shù)規(guī)劃模型并證明該問(wèn)題是NP難的；Wang等[173]考慮實(shí)時(shí)電價(jià)下、具有不同的能源消耗功率，且工件有不同尺寸的雙目標(biāo)問(wèn)題，目標(biāo)函數(shù)為極小化最大完工時(shí)間和總能源成本。

在平行機(jī)環(huán)境下，Moon等[174]研究了同時(shí)極小化最大完工時(shí)間和電力成本的非同類機(jī)并行分批排序問(wèn)題，并提出一種混合的遺傳算法；Jia等[175]研究了同時(shí)極小化最大完工時(shí)間和電力成本的同型機(jī)并行分批排序問(wèn)題，并給出一個(gè)基于Pareto優(yōu)化的蟻群優(yōu)化算法。在混合流水作業(yè)環(huán)境下，Luo等[176]研究同時(shí)極小化最大完工時(shí)間和電力成本的并行分批排序問(wèn)題，并提出一種基于蟻群的智能算法。

2.11 工件可拒絕的并行分批排序

在實(shí)際加工過(guò)程中，制造商往往會(huì)因?yàn)橘Y源有限的原因拒絕加工部分訂單，而選擇加工那些來(lái)自其重要客戶或能夠帶來(lái)更多利潤(rùn)的訂單。將這類實(shí)際問(wèn)題抽象出來(lái)即為工件可拒絕的排序問(wèn)題。工件可拒絕是指在加工過(guò)程中，可以拒絕加工某些工件，但需要支付一定的拒絕費(fèi)用。王珍等[177]、Cao和Yang[178]、Lu等[179]、翟大偉[180]、李修倩等[181]、Zou和Miao[156]、He等[182]研究工件可拒絕的單機(jī)并行分批排序問(wèn)題。Jia等[183]研究了極小化最大完工時(shí)間和被拒絕工件成本總和的雙目標(biāo)排序問(wèn)題Pm|pj=p,sj,ωj,S|Cmax+Rtot和Pm|pj=p,sj,ωj,S|(Cmax,Rtot)，其中ωj表示被拒絕工件Jj的拒絕成本，Rtot表示被拒絕工件的成本總和。

2.12 帶有分批費(fèi)用的并行分批排序

張喆和馮琪[184]、張喆等[185]、張喆和李文華[186,187]考慮帶有分批費(fèi)用的單機(jī)并行分批排序問(wèn)題，這里的分批費(fèi)用是指每分一批就會(huì)產(chǎn)生一個(gè)固定費(fèi)用，一般出于對(duì)實(shí)際生產(chǎn)中可能產(chǎn)生的人工費(fèi)用或包裝費(fèi)用的考慮。

2.13 同批工件加工時(shí)間具有相容性的并行分批排序

Bellanger等[188]和Li等[189]考慮同批工件加工時(shí)間具有相容性(job processing time compatibility)的單機(jī)并行分批排序問(wèn)題。在該類問(wèn)題中，工件Jj的實(shí)際加工時(shí)間取值范圍為[aj,(1+α)aj]，其中aj為基本加工時(shí)間，α>0為某個(gè)給定的數(shù)；同批工件必須具有相容性，即所有工件的實(shí)際加工時(shí)間取值范圍相交非空；同批工件具有相同的開(kāi)始加工時(shí)間，該時(shí)間由批中所有工件加工時(shí)間范圍交集的左端點(diǎn)確定，即p(B)=max{aj:Jj∈B}。

2.14 具有雙代理的并行分批排序

Feng等[190]和Tang等[191]研究具有雙代理的單機(jī)并行分批排序問(wèn)題。在雙代理問(wèn)題中，有兩個(gè)代理A和B，各自都有自己的工件集合和目標(biāo)函數(shù)，但都在同一臺(tái)批處理機(jī)器上進(jìn)行分批加工；如果代理A和代理B相容，則不同代理的工件可同批加工，否則不能同批加工。

2.15 并行分批排序的重新排序問(wèn)題

郭曉[192]和Xu等[193]研究了單機(jī)并行分批排序的重新排序(rescheduling)問(wèn)題。重新排序是指原始工件集按目標(biāo)函數(shù)分批排好順序后，又有新的工件集到來(lái)，決策者需要將新工件集中的工件插入到已排好的順序中，插入的原則為在不過(guò)分打擾原工件集中工件順序的條件下，使新的目標(biāo)值最優(yōu)。這里不過(guò)分打擾可以具體為限制序列錯(cuò)位量和時(shí)間錯(cuò)位量等。

2.16 半連續(xù)型并行分批排序

另外，還有一種分批排序問(wèn)題，既有并行分批的特征又有串行分批的特點(diǎn)，但又不同于這兩種形式，稱為半連續(xù)型(semi-continuous)或連續(xù)型分批排序問(wèn)題。在該類問(wèn)題中，所有工件可任意分成若干批；分批后，批中所有工件的加工時(shí)間就都變?yōu)橥兴泄ぜ淖畲蠹庸r(shí)間；在批加工的過(guò)程中，同批中的工件依次勻速進(jìn)入和離開(kāi)機(jī)器，每個(gè)工件都有自己的開(kāi)始加工時(shí)間和完工時(shí)間；機(jī)器可同時(shí)容納的最大工件數(shù)稱為機(jī)器容量，這里需要說(shuō)明一下，因工件依次勻速進(jìn)入和離開(kāi)，所以有可能存在同一批中有的工件已經(jīng)完工了，但還有工件沒(méi)進(jìn)入機(jī)器的情況，所以批中工件數(shù)可以大于機(jī)器的容量；任一批中所有工件都完工后才可進(jìn)行下一批的加工。Tang和Zhao[194]分別研究了極小化最大完工時(shí)間和極小化總完工時(shí)間的單機(jī)半連續(xù)型分批排序問(wèn)題，給出最優(yōu)性質(zhì)和動(dòng)態(tài)規(guī)劃算法；趙玉芳[195]考慮了平行鏈約束情況下，目標(biāo)函數(shù)為極小化最大完工時(shí)間的單機(jī)半連續(xù)型分批排序問(wèn)題；呂緒華等[196]研究極小化加權(quán)總完工時(shí)間目標(biāo)函數(shù)下的單機(jī)半連續(xù)型分批排序問(wèn)題；王松麗等[197]考慮了工件具有到達(dá)時(shí)間、目標(biāo)函數(shù)為極小化最大完工時(shí)間的情況，并給出動(dòng)態(tài)規(guī)劃算法。

3 結(jié)語(yǔ)和展望

本文綜述了并行分批排序的已有成果，主要分為兩部分，第一部分主要介紹了兩種機(jī)器環(huán)境和六個(gè)目標(biāo)函數(shù)組合下的并行分批排序成果，其中兩種機(jī)器環(huán)境分別為單機(jī)和平行機(jī)，六個(gè)目標(biāo)函數(shù)分別為極小化最大完工時(shí)間、極小化總完工時(shí)間、極小化最大延遲、極小化誤工工件數(shù)、極小化總延誤和極小化最大延誤；第二部分主要梳理了16類新型并行分批排序，這些新型排序由一般分批排序和新特點(diǎn)結(jié)合產(chǎn)生，16個(gè)新特點(diǎn)分別為差異尺寸工件、多目標(biāo)和新目標(biāo)函數(shù)、工件具有先后約束關(guān)系、工件帶運(yùn)輸時(shí)間、加工時(shí)間離散可控、工件具有惡化加工時(shí)間、工件加工時(shí)間具有學(xué)習(xí)效應(yīng)、機(jī)器具有禁用區(qū)間、工件具有交付時(shí)間窗、節(jié)能、工件可拒絕、帶有分批費(fèi)用、同批工件加工時(shí)間具有相容性、具有雙代理、重新排序和半連續(xù)型等。

雖然到目前為止，對(duì)并行分批排序的研究已經(jīng)取得了豐碩的成果，但還是存在很多有待解決和研究的問(wèn)題。如有些問(wèn)題的復(fù)雜性還沒(méi)有解決，有些問(wèn)題的已有算法還可以改進(jìn)等。另外，本文歸納出的16類新型并行分批排序都具有較強(qiáng)的應(yīng)用背景，對(duì)這些問(wèn)題進(jìn)行深入研究具有重要的理論意義和現(xiàn)實(shí)意義。

除了上述對(duì)已有問(wèn)題的深入和擴(kuò)展，還可根據(jù)實(shí)際應(yīng)用背景結(jié)合新的特點(diǎn)，如在半導(dǎo)體生產(chǎn)中最典型的重入特點(diǎn)、在制品庫(kù)存目標(biāo)和加工流平穩(wěn)目標(biāo)等。另外，目前已有的成果絕大部分停留在理論研究階段，如何將理論研究成果轉(zhuǎn)化為切實(shí)可用的實(shí)踐方法是一項(xiàng)具有重大意義的挑戰(zhàn)。