并行分批排序綜述

井彩霞，吳瑞強(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 引言

并行分批排序來源于半導(dǎo)體芯片的加工和成品檢驗(yàn)過程。在半導(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)過程。日常生活中所用的烤箱也是一種批加工設(shè)備，可以同時(shí)烘烤一批面包，或面包和蛋糕一起烤。

以批加工為特點(diǎn)建立的排序模型即為廣義的分批排序(batch scheduling)。對(duì)分批排序，國(guó)內(nèi)外已有許多文獻(xià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]等，在名字上并沒有對(duì)并行分批和串行分批做明顯區(qū)分。然而近期的很多文獻(xiàn)都用“parallel batch scheduling”[10,11]和“serial batch scheduling”[12,13]加以區(qū)別。隨著理論的成熟，問題的分類更加細(xì)化，術(shù)語(yǔ)也越來越專業(yè)和科學(xué)化，這是科學(xué)研究發(fā)展的一個(gè)趨勢(shì)。

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

一般認(rèn)為，Ikura和Gimple[14]是第一篇關(guān)于并行分批排序的文獻(xiàn)，在工件加工時(shí)間相等且到達(dá)時(shí)間與交付期一致(agreeable)的情況下，其針對(duì)是否存在可行排序的問題，指出存在可行排序，并設(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ì)批容量無限和批容量有限兩種情況下的單臺(tái)機(jī)器并行分批排序展開研究，在所有工件具有相同到達(dá)時(shí)間的假設(shè)下，分析了問題在多種目標(biāo)函數(shù)下的復(fù)雜性，并給出相應(yīng)算法。到了21世紀(jì)，關(guān)于并行分批排序問題的文獻(xiàn)如雨后春筍般涌現(xiàn)，這種態(tài)勢(shì)至今有增無減，其中的成果大多來自國(guó)內(nèi)的科研工作者們。

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

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

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

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

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

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

單機(jī)并行分批排序問題的一般描述為：有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í)開始加工，并同時(shí)結(jié)束，加工時(shí)間為批中所有工件的最大加工時(shí)間。一旦某批工件開始加工，就不可中斷，加工期間也不能增加或減少工件，直至該批加工完成。以極小化最大完工時(shí)間的目標(biāo)函數(shù)為例，該問題可用三參數(shù)法表示為1|B,rj|Cmax。如果所有工件的到達(dá)時(shí)間都相等，則可表示為1|B|Cmax。

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

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

(1)批容量無限

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

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

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

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

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

定理1若記工件不同時(shí)到達(dá)、目標(biāo)函數(shù)為Cmax的排序問題為P1，相應(yīng)的工件同時(shí)到達(dá)、目標(biāo)函數(shù)為L(zhǎng)max的排序問題為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)的排序問題1|B=∞,rj|Cmax是強(qiáng)NP-難的，這里“不相容工件簇”是指所有工件分成若干類、不同類的工件不能同批加工，有些文獻(xiàn)中也稱之為“不相容工件族”或“不相容工件組”。對(duì)該NP-難問題，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ì)排序問題1|B,rj|Cmax，其復(fù)雜性可由定理1和Brucker等[16]給出的另一個(gè)定理(定理2)推出。

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

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

此外，針對(duì)問題的一般情況，Deng等[27]給出了一個(gè)PTAS；孫錦萍等[28]給出了一個(gè)比Deng等[27]中時(shí)間復(fù)雜性更低的PTAS；Sung和Choung[9]給出分支定界算法和啟發(fā)式算法；Li等[29]在排序問題1|B,rj|Cmax的基礎(chǔ)上，考慮工件具有不同尺寸的特點(diǎn)，給出一個(gè)最壞性能比為2+ε的近似算法，并指出該算法在解工件具有相同尺寸的問題時(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ì)排序問題1|B,rj|Cmax建立0-1整數(shù)規(guī)劃模型，并利用軟件進(jìn)行數(shù)值求解，得出能夠獲得最優(yōu)解的問題規(guī)模。

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

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

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

(1)批容量無限

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

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

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

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

(2)批容量有限

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

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

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

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

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

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

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

(1)批容量無限

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

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

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

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

(2)批容量有限

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

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

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

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

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

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

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

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

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

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

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

(1)批容量無限

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

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

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

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

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

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

當(dāng)目標(biāo)函數(shù)為極小化最大延誤時(shí)，由排序問題1|rj|Tmax是強(qiáng)NP-難的，可知排序問題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í)間和交付期一致的排序問題1|B,rj|Tmax是強(qiáng)NP-難的，并研究了工件到達(dá)時(shí)間、交付期和加工時(shí)間都一致的情況。Baptiste[19]指出排序問題1|B,pj=p,rj|Tmax是多項(xiàng)式時(shí)間可解的。

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

在平行機(jī)環(huá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í)開始加工，并同時(shí)結(jié)束，加工時(shí)間為批中所有工件的最大加工時(shí)間。一旦某批工件開始加工，就不可中斷，加工期間也不能增加或減少工件，直至該批加工完成。以同型平行機(jī)和極小化最大完工時(shí)間的目標(biāo)函數(shù)為例，該問題可用三參數(shù)法表示為P|B,rj|Cmax。如果所有工件的到達(dá)時(shí)間都相等，則可表示為P|B|Cmax。下面本節(jié)根據(jù)目標(biāo)函數(shù)的不同對(duì)平行機(jī)并行分批排序問題進(jìn)行分類介紹。

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

在極小化最大完工時(shí)間的目標(biāo)函數(shù)下，Lee等[15]指出并行分批排序問題P|B|Cmax是強(qiáng)NP-難的，并給出最壞性能比為4/3-1/3m的算法，其中m為機(jī)器數(shù)。張玉忠等[69]利用轉(zhuǎn)換引理對(duì)排序問題P|B|Cmax給出最壞性能比為2-1/m的算法，并指出該界是緊的，同時(shí)對(duì)排序問題Q|B|Cmax給出了近似算法。劉麗麗和張峰[70]為排序問題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)的并行分批排序問題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ì)排序問題P|B|ΣCj，給出兩個(gè)啟發(fā)式算法。任建鋒和張玉忠[53]對(duì)排序問題Pm|B,rj|ΣCj給出批容量B和機(jī)器數(shù)m為常數(shù)情況下的PTAS。Li等[71]對(duì)排序問題P|B=∞,rj|ΣwjCj給出一個(gè)PTAS。李曙光等[72]對(duì)排序問題P|B,rj|ΣCj也給出了一個(gè)PTAS。苗翠霞和張玉忠[54]證明了排序問題P2|B|ΣwjCj是NP-完備的。

(3)極小化最大延遲

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

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

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

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

(5)極小化總延誤

在極小化總延誤的目標(biāo)函數(shù)下，M?nch等[80]考慮具有不相容工件簇的排序問題Pm|B,rj|ΣwjTj，并給出啟發(fā)式算法。M?nch 和Almeder[81]對(duì)具有不相容工件簇的排序問題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í)間的排序問題Pm|B,rj,prec|ΣwjTj，并設(shè)計(jì)了啟發(fā)式算法。

(6)極小化最大延誤

在極小化最大延誤的目標(biāo)函數(shù)下，劉麗麗和張峰[79]為排序問題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)境下的并行分批排序問題，如流水作業(yè)[83]、柔性流水作業(yè)[84]、混合流水作業(yè)[85]和柔性異序作業(yè)(flexible job shop)[86]等。

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

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

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

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

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

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

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

Uzsoy[87]證明排序問題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算法的最壞性能比不超過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ì)排序問題1|S,sj|Cmax提出了兩個(gè)啟發(fā)式算法，分別為BFLPT(best fit & longest processing time)算法和SKP(successive knapsack problem)算法，并證明了BFLPT算法是當(dāng)時(shí)求解該問題的最優(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)用于該問題的求解。Melouk等[91]首先引入模擬退火算法對(duì)問題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è)是先生成批序列，然后再通過啟發(fā)式的過程來保證解的可行性，最后通過合并和拆分來構(gòu)建批序列。Damodaran等[93]也采用遺傳算法求解了該問題，通過對(duì)工件序列進(jìn)行編碼，針對(duì)問題包含的加工序列和分批兩個(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ì)排序問題1|S,sj|Cmax給出了一個(gè)下界，并提出一種改進(jìn)的最大最小蟻群算法，計(jì)算實(shí)驗(yàn)表明，該算法優(yōu)于Uzsoy[87]中的FFDECR算法和FFLPT算法、Kashan等[92]中的遺傳算法，和Chen等[95]中的聚類算法等。

此外，對(duì)排序問題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ī)并行分批排序問題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í)間和尺寸大小一致的情況，并給出最壞性能比不超過33/14的算法；馬冉和張玉忠[104]研究了具有特殊到達(dá)時(shí)間、工件加工時(shí)間相等且具有優(yōu)先約束的情況，給出最壞性能比不超過2的近似算法。

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

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

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

另外，對(duì)排序問題Pm|S,sj|Cmax，張?chǎng)蔚萚112]研究了工件可以按尺寸拆分的情況，指出該問題是NP-完備的，并給出一個(gè)最壞性能比不超過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ī)排序問題Rm|S,sj|Cmax，給出了一個(gè)下界，并基于BFLPT算法設(shè)計(jì)了幾個(gè)啟發(fā)式算法。Arroyo和Leung[117]考慮工件具有到達(dá)時(shí)間的排序問題Rm|S,sj,rj|Cmax，給出混合整數(shù)規(guī)劃模型和下界，并設(shè)計(jì)了幾個(gè)有效的啟發(fā)式算法。

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

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

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

在排序問題Pm|Si,sj|Cmax中，若工件具有到達(dá)時(shí)間，就成為排序問題Pm|Si,sj,rj|Cmax。Xu和Bean[122]構(gòu)建了排序問題Pm|Si,sj,rj|Cmax的整數(shù)規(guī)劃模型，提出基于隨機(jī)鍵的遺傳算法。Chen等[113]指出排序問題Pm|Si,sj,rj|Cmax是強(qiáng)NP難的，分別基于FBLPT算法和機(jī)器負(fù)載給出了問題的兩個(gè)下界，并分別設(shè)計(jì)蟻群優(yōu)化算法和遺傳算法對(duì)工件分批問題進(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ì)排序問題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ī)排序問題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ù)下的并行分批排序問題，如張召生等[128]、李文華[129,130]、He等[131]、焦峰亮等[132,133]、Liu等[134]、李小襯[135]、Geng和Yuan[136,137]、Zhang等[138]等。除了常見的目標(biāo)函數(shù)，張玉忠和王琳[139]研究目標(biāo)函數(shù)為加權(quán)延遲工作和的排序問題1|B=∞|ΣwjVj，其中Vj=min{Tj,pj}；李文華[130]討論了目標(biāo)函數(shù)為極小化完工時(shí)間平方之和的單機(jī)并行分批排序問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在實(shí)際加工過程中，制造商往往會(huì)因?yàn)橘Y源有限的原因拒絕加工部分訂單，而選擇加工那些來自其重要客戶或能夠帶來更多利潤(rùn)的訂單。將這類實(shí)際問題抽象出來即為工件可拒絕的排序問題。工件可拒絕是指在加工過程中，可以拒絕加工某些工件，但需要支付一定的拒絕費(fèi)用。王珍等[177]、Cao和Yang[178]、Lu等[179]、翟大偉[180]、李修倩等[181]、Zou和Miao[156]、He等[182]研究工件可拒絕的單機(jī)并行分批排序問題。Jia等[183]研究了極小化最大完工時(shí)間和被拒絕工件成本總和的雙目標(biāo)排序問題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ī)并行分批排序問題，這里的分批費(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ī)并行分批排序問題。在該類問題中，工件Jj的實(shí)際加工時(shí)間取值范圍為[aj,(1+α)aj]，其中aj為基本加工時(shí)間，α>0為某個(gè)給定的數(shù)；同批工件必須具有相容性，即所有工件的實(shí)際加工時(shí)間取值范圍相交非空；同批工件具有相同的開始加工時(shí)間，該時(shí)間由批中所有工件加工時(shí)間范圍交集的左端點(diǎn)確定，即p(B)=max{aj:Jj∈B}。

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

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

2.15 并行分批排序的重新排序問題

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

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

另外，還有一種分批排序問題，既有并行分批的特征又有串行分批的特點(diǎn)，但又不同于這兩種形式，稱為半連續(xù)型(semi-continuous)或連續(xù)型分批排序問題。在該類問題中，所有工件可任意分成若干批；分批后，批中所有工件的加工時(shí)間就都變?yōu)橥兴泄ぜ淖畲蠹庸r(shí)間；在批加工的過程中，同批中的工件依次勻速進(jìn)入和離開機(jī)器，每個(gè)工件都有自己的開始加工時(shí)間和完工時(shí)間；機(jī)器可同時(shí)容納的最大工件數(shù)稱為機(jī)器容量，這里需要說明一下，因工件依次勻速進(jìn)入和離開，所以有可能存在同一批中有的工件已經(jīng)完工了，但還有工件沒進(jìn)入機(jī)器的情況，所以批中工件數(shù)可以大于機(jī)器的容量；任一批中所有工件都完工后才可進(jìn)行下一批的加工。Tang和Zhao[194]分別研究了極小化最大完工時(shí)間和極小化總完工時(shí)間的單機(jī)半連續(xù)型分批排序問題，給出最優(yōu)性質(zhì)和動(dòng)態(tài)規(guī)劃算法；趙玉芳[195]考慮了平行鏈約束情況下，目標(biāo)函數(shù)為極小化最大完工時(shí)間的單機(jī)半連續(xù)型分批排序問題；呂緒華等[196]研究極小化加權(quán)總完工時(shí)間目標(biāo)函數(shù)下的單機(jī)半連續(xù)型分批排序問題；王松麗等[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)取得了豐碩的成果，但還是存在很多有待解決和研究的問題。如有些問題的復(fù)雜性還沒有解決，有些問題的已有算法還可以改進(jìn)等。另外，本文歸納出的16類新型并行分批排序都具有較強(qiáng)的應(yīng)用背景，對(duì)這些問題進(jìn)行深入研究具有重要的理論意義和現(xiàn)實(shí)意義。

除了上述對(duì)已有問題的深入和擴(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)。