并行分批排序綜述

2020-10-23 08:05:30井彩霞吳瑞強賈兆紅

運籌與管理 2020年1期

關鍵詞：排序

井彩霞，吳瑞強，賈兆紅

(1.天津工業大學經濟與管理學院，天津 300387; 2.天津曙光存儲科技有限公司存儲產品研發部，天津 300384; 3.安徽大學計算機科學與技術學院，安徽合肥 230601)

0 引言

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

以批加工為特點建立的排序模型即為廣義的分批排序(batch scheduling)。對分批排序，國內外已有許多文獻研究，所研究問題的種類也多種多樣。分批排序按批加工的方式可以分為兩大類：并行分批排序(parallel batch scheduling)和串行分批排序(serial batch scheduling)[1]。在并行分批排序中，同一批的工件同時加工，加工時間為批中所有工件的最大工時；在串行分批排序中，同一批的工件連續加工，加工時間為批中所有工件的工時之和。也有文獻稱這兩種分批方式下的排序為平行分批排序和繼列分批排序[2]，或批處理機排序和成組分批排序[3]等。對并行分批排序也有文獻稱之為同時加工排序或批加工機器排序[4,5]等。

在早期的一些英文文獻中，稱分批排序為“scheduling with batching and lot-sizing”[6]、“batch scheduling”[7]，“scheduling on batch processing machine”[8]，或“scheduling on burn-in oven”[9]等，在名字上并沒有對并行分批和串行分批做明顯區分。然而近期的很多文獻都用“parallel batch scheduling”[10,11]和“serial batch scheduling”[12,13]加以區別。隨著理論的成熟，問題的分類更加細化，術語也越來越專業和科學化，這是科學研究發展的一個趨勢。

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

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

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

對已有成果涉及的并行分批排序問題進行梳理和分類如圖1所示。本文將以問題為導向，按圖1中的框架結構對并行分批排序進行綜述。

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

1 傳統機器環境和目標函數框架下的并行分批排序

本節根據已有文獻中的成果，主要對單機和平行機機器環境下的并行分批排序問題進行綜述，在每種機器環境下，主要針對六個傳統目標函數下的問題進行梳理，分別為極小化最大完工時間、極小化總完工時間、極小化最大延遲、極小化誤工工件數、極小化總延誤和極小化最大延誤。

1.1 單機并行分批排序

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

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

在極小化最大完工時間的目標函數下，單機并行分批排序問題又可根據批容量是否有限、工件是否同時到達等特點分為很多類，下面主要根據這兩個特點進行分類介紹。

(1)批容量無限

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

①工件同時到達

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

②工件不同時到達

對排序問題1|B=∞,rj|Cmax，Brucker等[16]設計了一個動態規劃最優算法，說明該問題是多項式時間可解的，并給出一個定理。

定理1若記工件不同時到達、目標函數為Cmax的排序問題為P1，相應的工件同時到達、目標函數為Lmax的排序問題為P2，則P1和P2可以O(n)時間內相互轉換。

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

(2)批容量有限

批容量有限是指B

①工件同時到達

②工件不同時到達

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

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

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

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

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

另外，對排序問題1|B,rj|Cmax，井彩霞等[5]研究了工件成批到達的情況，該問題與工件到達時間個數為常數的問題是等價的。當只有兩批工件時，Lee[22]給出了一個優勢性質。基于Lee[22]的優勢性質和FBLPT算法，井彩霞等[5]分別給出針對只有兩批工件情況和一般情況的啟發式算法。

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

對目標函數為極小化總完工時間的單機并行分批排序問題，本節同樣也根據批容量是否有限和工件是否同時到達這兩個特點分類介紹。

(1)批容量無限

①工件同時到達

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

②工件不同時到達

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

(2)批容量有限

①工件同時到達

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

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

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

②工件不同時到達

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

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

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

當目標函數為極小化最大延遲時，根據批容量是否有限和工件是否同時到達這兩個特點分類介紹如下。

(1)批容量無限

①工件同時到達

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

②工件不同時到達

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

(2)批容量有限

①工件同時到達

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

②工件不同時到達

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

1.1.4 極小化誤工工件數的單機并行分批排序

在極小化誤工工件數的目標函數下，根據批容量是否有限和工件是否同時到達這兩個特點分類介紹如下。

(1)批容量無限

①工件同時到達

②工件不同時到達

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

(2)批容量有限

①工件同時到達

②工件不同時到達

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

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

(1)批容量無限

①工件同時到達

②工件不同時到達

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

(2)批容量有限

①工件同時到達

②工件不同時到達

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

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

1.2 平行機并行分批排序

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

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

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

(2)極小化總完工時間

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

(3)極小化最大延遲

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

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

(4)極小化誤工工件數

在極小化誤工工件數的目標函數下，劉麗麗和張峰[79]為排序問題Pm|B=∞|ΣUj設計了偽多項式時間的順向動態規劃算法。

(5)極小化總延誤

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

(6)極小化最大延誤

在極小化最大延誤的目標函數下，劉麗麗和張峰[79]為排序問題Pm|B=∞|Tmax設計了偽多項式時間的順向動態規劃算法。

1.3 其他機器環境的并行分批排序

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

2 并行分批排序的擴展和衍生

前文主要以傳統的機器環境和目標函數為框架，對并行分批排序問題進行了綜述。隨著科學研究的發展和進步，以及新的需求的產生，并行分批排序問題不斷得到擴展和衍生，尤其近幾年來，出現了很多新特點下的并行分批排序問題。

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

在前面介紹的并行分批排序問題中，默認工件具有相同的尺寸。隨著相關領域設備與技術的不斷發展和進步，以及用戶需求的不斷變化，加工任務也更加多樣化，導致出現更加復雜的并行分批排序問題，其中工件或機器在尺寸或容量上出現差異性就是一個典型的新特點。下面將根據機器容量是否相同，對差異尺寸工件的并行分批排序問題進行分類介紹。

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

當機器容量相同時，已有文獻中對差異尺寸工件并行分批排序問題的研究主要集中在極小化最大完工時間的目標函數。下面將分別對該目標函數下的單機環境和平行機環境問題進行綜述。

(1)單機環境

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

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

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

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

(2)平行機環境

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

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

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

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

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

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

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

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

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

2.2 多目標和新目標函數下的并行分批排序

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

2.3 工件具有先后約束關系的并行分批排序

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

2.4 工件帶運輸時間的并行分批排序

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

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

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

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

2.7 工件加工時間具有學習效應的并行分批排序

2.8 機器具有禁用區間的并行分批排序

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

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

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

2.10 節能并行分批排序

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

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

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

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

2.12 帶有分批費用的并行分批排序

張喆和馮琪[184]、張喆等[185]、張喆和李文華[186,187]考慮帶有分批費用的單機并行分批排序問題，這里的分批費用是指每分一批就會產生一個固定費用，一般出于對實際生產中可能產生的人工費用或包裝費用的考慮。

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

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

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

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

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

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

2.16 半連續型并行分批排序

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

3 結語和展望

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

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

除了上述對已有問題的深入和擴展，還可根據實際應用背景結合新的特點，如在半導體生產中最典型的重入特點、在制品庫存目標和加工流平穩目標等。另外，目前已有的成果絕大部分停留在理論研究階段，如何將理論研究成果轉化為切實可用的實踐方法是一項具有重大意義的挑戰。