并行分批排序綜述

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

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

0 引言

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

以批加工為特點(diǎn)建立的排序模型即為廣義的分批排序(batch scheduling)。對分批排序，國內(nèi)外已有許多文獻(xiàn)研究，所研究問題的種類也多種多樣。分批排序按批加工的方式可以分為兩大類：并行分批排序(parallel batch scheduling)和串行分批排序(serial batch scheduling)[1]。在并行分批排序中，同一批的工件同時加工，加工時間為批中所有工件的最大工時；在串行分批排序中，同一批的工件連續(xù)加工，加工時間為批中所有工件的工時之和。也有文獻(xiàn)稱這兩種分批方式下的排序?yàn)槠叫蟹峙判蚝屠^列分批排序[2]，或批處理機(jī)排序和成組分批排序[3]等。對并行分批排序也有文獻(xiàn)稱之為同時加工排序或批加工機(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]等，在名字上并沒有對并行分批和串行分批做明顯區(qū)分。然而近期的很多文獻(xiàn)都用“parallel batch scheduling”[10,11]和“serial batch scheduling”[12,13]加以區(qū)別。隨著理論的成熟，問題的分類更加細(xì)化，術(shù)語也越來越專業(yè)和科學(xué)化，這是科學(xué)研究發(fā)展的一個趨勢。

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

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

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

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

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

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

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

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

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

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

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

(1)批容量無限

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

①工件同時到達(dá)

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

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

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

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

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

(2)批容量有限

批容量有限是指B

①工件同時到達(dá)

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

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

定理2對具有交付期的批容量有限的單機(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-難的。

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

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

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

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

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

(1)批容量無限

①工件同時到達(dá)

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

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

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

(2)批容量有限

①工件同時到達(dá)

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

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

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

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

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

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

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

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

(1)批容量無限

①工件同時到達(dá)

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

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

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

(2)批容量有限

①工件同時到達(dá)

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

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

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

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

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

(1)批容量無限

①工件同時到達(dá)

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

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

(2)批容量有限

①工件同時到達(dá)

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

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

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

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

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

(1)批容量無限

①工件同時到達(dá)

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

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

(2)批容量有限

①工件同時到達(dá)

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

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

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

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

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

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

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

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

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

(2)極小化總完工時間

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

(3)極小化最大延遲

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

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

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

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

(5)極小化總延誤

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

(6)極小化最大延誤

在極小化最大延誤的目標(biāo)函數(shù)下，劉麗麗和張峰[79]為排序問題Pm|B=∞|Tmax設(shè)計了偽多項(xià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ù)為框架，對并行分批排序問題進(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)差異性就是一個典型的新特點(diǎn)。下面將根據(jù)機(jī)器容量是否相同，對差異尺寸工件的并行分批排序問題進(jìn)行分類介紹。

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

當(dāng)機(jī)器容量相同時，已有文獻(xiàn)中對差異尺寸工件并行分批排序問題的研究主要集中在極小化最大完工時間的目標(biāo)函數(shù)。下面將分別對該目標(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]還給出了一個基于工件尺寸排序的啟發(fā)式算法，即FFDECR(batch first fit & decreasing order of sizes)算法。Zhang等[88]證明了FFLPT算法的最壞性能比不超過2，F(xiàn)FDECR算法的最壞性能比可能任意大；提出了一個啟發(fā)式算法，最壞性能比為7/4；同時還考慮了尺寸大于1/2的大工件的加工時間不少于尺寸小于1/2的小工件加工時間的情況，并設(shè)計了一個最壞性能比為3/2的啟發(fā)式算法。Dupont和Dhaenens-flipo[89]對排序問題1|S,sj|Cmax提出了兩個啟發(fā)式算法，分別為BFLPT(best fit & longest processing time)算法和SKP(successive knapsack problem)算法，并證明了BFLPT算法是當(dāng)時求解該問題的最優(yōu)啟發(fā)式算法。Kashan等[90]將Zhang等[88]中假設(shè)的工件尺寸1/2擴(kuò)展為1/m，其中m≥2為整數(shù)，并給出了絕對性能比(absolute worst-case ratio)為3/2、漸進(jìn)性能比(asymptotic worst-case ratio)為(m+1)/m的算法。

還有一些研究者致力于將智能算法應(yīng)用于該問題的求解。Melouk等[91]首先引入模擬退火算法對問題1|S,sj|Cmax進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明該模擬退火算法所得解的質(zhì)量優(yōu)于商用軟件CPLEX，并提出目前通用的一種基于隨機(jī)方式生成仿真實(shí)驗(yàn)測試算例的方法。Kashan等[92]給出了兩個不同思路的遺傳算法，其中一個思路是先生成工件序列，然后再對工件進(jìn)行分批；另一個是先生成批序列，然后再通過啟發(fā)式的過程來保證解的可行性，最后通過合并和拆分來構(gòu)建批序列。Damodaran等[93]也采用遺傳算法求解了該問題，通過對工件序列進(jìn)行編碼，針對問題包含的加工序列和分批兩個方面的約束，對遺傳算法的交叉與變異算子進(jìn)行了新的設(shè)計，實(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]從聚類的角度給出一個聚類算法，計算實(shí)驗(yàn)表明該算法優(yōu)于BFLPT算法和Damodaran等[93]中的遺傳算法。Jia和Leung[96]對排序問題1|S,sj|Cmax給出了一個下界，并提出一種改進(jìn)的最大最小蟻群算法，計算實(shí)驗(yàn)表明，該算法優(yōu)于Uzsoy[87]中的FFDECR算法和FFLPT算法、Kashan等[92]中的遺傳算法，和Chen等[95]中的聚類算法等。

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

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

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

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

針對差異尺寸工件的平行機(jī)并行分批排序問題Pm|S,sj|Cmax，Chang等[105]提出了模擬退火算法，并通過仿真實(shí)驗(yàn)驗(yàn)證所提模擬退火算法的求解性能優(yōu)于商業(yè)軟件CPLEX。Damodaran和Chang[106]提出了若干啟發(fā)式算法，他們將問題分解為工件分批和批分配至機(jī)器兩個子問題，分別采用了FFLPT算法和BFLPT算法分批，再利用LPT和Multifit啟發(fā)式規(guī)則對批進(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)行對比，驗(yàn)證了神經(jīng)網(wǎng)絡(luò)方法的優(yōu)越性。Kashan等[108]提出一種混合遺傳啟發(fā)式算法，該算法通過遺傳算子產(chǎn)生隨機(jī)批來搜索解空間。在該算法中，對每一個生成的后代染色體，采用一個隨機(jī)分批過程用于保證其可行性；然后通過LPT規(guī)則將生成的可行批排序到機(jī)器上；最后通過兩個局部搜索啟發(fā)式算法進(jìn)一步改進(jìn)算法的求解效果。實(shí)驗(yàn)結(jié)果表明混合遺傳啟發(fā)式算法優(yōu)于Chang等[105]提出的模擬退火算法。Damodaran等[109]設(shè)計遺傳算法來求解排序問題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，計算實(shí)驗(yàn)表明，ASM算法的性能優(yōu)于Damodaran和Chang[106]中的啟發(fā)式算法和Kashan等[108]所提的混合遺傳啟發(fā)式算法。

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

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

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

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

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

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

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

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ù)為極小化完工時間平方之和的單機(jī)并行分批排序問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在實(shí)際加工過程中，制造商往往會因?yàn)橘Y源有限的原因拒絕加工部分訂單，而選擇加工那些來自其重要客戶或能夠帶來更多利潤的訂單。將這類實(shí)際問題抽象出來即為工件可拒絕的排序問題。工件可拒絕是指在加工過程中，可以拒絕加工某些工件，但需要支付一定的拒絕費(fèi)用。王珍等[177]、Cao和Yang[178]、Lu等[179]、翟大偉[180]、李修倩等[181]、Zou和Miao[156]、He等[182]研究工件可拒絕的單機(jī)并行分批排序問題。Jia等[183]研究了極小化最大完工時間和被拒絕工件成本總和的雙目標(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)用是指每分一批就會產(chǎn)生一個固定費(fèi)用，一般出于對實(shí)際生產(chǎn)中可能產(chǎn)生的人工費(fèi)用或包裝費(fèi)用的考慮。

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

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

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

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

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

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

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

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

3 結(jié)語和展望

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

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

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