帶有限緩沖區(qū)的混合流水車間多目標(biāo)調(diào)度

袁慶欣，董紹華

北京科技大學(xué)機(jī)械工程學(xué)院，北京 100083

考慮工件以批量形式運(yùn)輸、車間中各個(gè)工序前后生產(chǎn)節(jié)拍不同等因素，在混合流水車間中建立緩沖區(qū)是非常必要的. 流水車間中（Flow shop,FS）的緩沖區(qū)一般有兩種形式，加工工序間共享緩沖區(qū)[1]和機(jī)器獨(dú)立配置緩沖區(qū)[2]，第一種類型常見(jiàn)于物料搬運(yùn)較為容易、加工形式單一的串型生產(chǎn)線當(dāng)中[3]，而對(duì)于運(yùn)輸能力有限、車間布局不易更改的混合流水車間，機(jī)器獨(dú)立配置緩沖區(qū)更具備研究意義.

求解混合流水車間的調(diào)度問(wèn)題已經(jīng)被Gupta[4]證明是非確定性多項(xiàng)式（Non-deterministic polynomial, NP）難度問(wèn)題，目前解決這類問(wèn)題有適用于低復(fù)雜度、小規(guī)模問(wèn)題的精確計(jì)算[5?7]、啟發(fā)式方法[8?9]以及當(dāng)下被廣泛使用的智能搜索算法[10?13]，Smutnicki[14]較早的針對(duì)含有容量限制的中間緩沖區(qū)的兩機(jī)排列的混合流水車間，以最小化完工時(shí)間為目標(biāo)，采用了一種基于禁忌搜索的近似算法；Nowicki[15]采用禁忌算法，將其擴(kuò)展為每個(gè)加工工序中可以含有任意數(shù)量的機(jī)器；Qian等[16]針對(duì)有限緩沖區(qū)位于連續(xù)機(jī)器之間的流水車間調(diào)度問(wèn)題，設(shè)計(jì)一種混合差分進(jìn)化算法(HDE)，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法的有效性；Wang與Tang[17]采用一種回溯啟發(fā)式算法，針對(duì)加工階段間有限等待時(shí)間的混合流水車間調(diào)度問(wèn)題，以最小化完工時(shí)間為目標(biāo)進(jìn)行求解同時(shí)驗(yàn)證了算法的有效性.

遺傳算法（Genetic algorithm，GA）已經(jīng)廣泛的應(yīng)用在車間調(diào)度問(wèn)題上[18?20]，本文也擬采用遺傳算法進(jìn)行求解. NSGA-II（Non-dominated sorting genetic algorithm 2，NSGA-II）是由 Deb 等[21]提出，且已經(jīng)廣泛應(yīng)用在處理多目標(biāo)混合流水車間調(diào)度問(wèn)題當(dāng)中[22?24]的智能算法. NSGA-III（Nondominated sorting genetic algorithm 3，NSGA-III）是在NSGA-II基礎(chǔ)上提出的[25]，與NSGA-II有著相同的框架，但是在精英選擇策略關(guān)于同一級(jí)非支配個(gè)體間的選擇機(jī)制上，NSGA-II算法采用根據(jù)擁擠度大小的方式進(jìn)行個(gè)體選擇，NSGA-III則是基于參考點(diǎn)的方式，改進(jìn)了NSGA-II算法在處理三個(gè)及其以上目標(biāo)時(shí)解在非支配層上分布不均勻、易陷入局部最優(yōu)的缺點(diǎn).

綜上，現(xiàn)有的文獻(xiàn)中多數(shù)都是假定車間中為無(wú)限制緩沖區(qū)，或者為工序間共享緩沖區(qū)，研究帶有限機(jī)器獨(dú)立配置緩沖區(qū)混合流水車間調(diào)度問(wèn)題的文獻(xiàn)較少，本文將對(duì)帶有限緩沖區(qū)的混合流水車間調(diào)度問(wèn)題進(jìn)行研究，以最小化完工時(shí)間、最小化運(yùn)載設(shè)備運(yùn)輸時(shí)間、最小化并行機(jī)前置緩沖區(qū)空間占用率均衡指數(shù)為目標(biāo)，考慮運(yùn)載設(shè)備運(yùn)輸能力限制、機(jī)器不確定性加工時(shí)間、緩沖區(qū)容積有限等資源限制條件，建立模型，并采用NSGAII與NSGA-III算法進(jìn)行求解，對(duì)比不同算法在求解過(guò)程的差異. 最后，將針對(duì)實(shí)際車間進(jìn)行實(shí)例驗(yàn)證，并對(duì)產(chǎn)生的優(yōu)化結(jié)果加以分析.

1 帶有限緩沖區(qū)的混合流水車間建模

1.1 問(wèn)題描述

混合流水車間生產(chǎn)加工階段s=1～S，加工設(shè)備k=1～N，每一臺(tái)加工設(shè)備都配置了獨(dú)立的前置緩沖區(qū)和后置緩沖區(qū)，受到有限的車間空間和設(shè)備生產(chǎn)線布局的影響，除第一道加工工序的前置緩沖區(qū)和最后一道加工工序的后置緩沖區(qū)視為容量無(wú)限大，其他剩下所有的緩沖區(qū)均為容量有限的緩沖區(qū)，車間中運(yùn)載設(shè)備i=1～Y用于工序間工件運(yùn)輸，每一個(gè)加工階段中都包含著生產(chǎn)精度不同、加工效率不等、工件適用情況存在差異的一定數(shù)量的并行機(jī)，工件集O按照批次進(jìn)行劃分為A個(gè)批次，O={1,2,···,a,···,A?1,A}，工件總數(shù)量為J.假設(shè)：（1）所有工件的加工順序一致，均要從第一加工工序開(kāi)始，完成一個(gè)工序的加工任務(wù)后，進(jìn)入下一個(gè)加工工序，直到完成最后一個(gè)加工工序的加工任務(wù)；（2）其中緩沖區(qū)的容積可以進(jìn)行調(diào)節(jié)，但會(huì)受到車間空間和天車運(yùn)輸距離的限制，且加工作業(yè)一旦開(kāi)始，緩沖區(qū)容積就不能再更改：（3）所有加工批次均為合理劃分，既能滿足天車運(yùn)輸能力的要求，同時(shí)也符合緩沖區(qū)容積要求；（4）不考慮工件的換裝時(shí)間，且同批次內(nèi)工件之間無(wú)確定先后加工順序要求.

1.2 模型建立

相關(guān)參數(shù)設(shè)計(jì)如表1.

表1 參數(shù)及變量設(shè)計(jì)Table 1 Design of the parameters and decision variables

車間資源約束條件如下：

上述模型中，式（1）～（3）為機(jī)器能力、運(yùn)載設(shè)備運(yùn)輸能力約束，具體為一臺(tái)機(jī)器一次只能加工一個(gè)工件，一臺(tái)運(yùn)載設(shè)備一次也只能運(yùn)輸一個(gè)批次的工件；式（4）～（5）為緩沖區(qū)容積限制；式（6）、式（11）分別為加工時(shí)間約束和運(yùn)輸時(shí)間約束；式（7）～（10）和式（12）～（13）為車間工藝約束；式（14）為加工時(shí)間、起運(yùn)時(shí)間均大于零.

目標(biāo)函數(shù)如下：

考慮車間工作效率和車間內(nèi)相關(guān)運(yùn)營(yíng)成本，將最小化完工時(shí)間和最小化運(yùn)載設(shè)備運(yùn)輸時(shí)間作為本文研究的兩個(gè)目標(biāo)，建立兩目標(biāo)帶有限緩沖區(qū)的混合流水車間調(diào)度模型，記為模型1，如式（15）和式（16）所示.

由于緩沖區(qū)容積有限，在一些未考慮工件占用緩沖區(qū)空間均衡的排產(chǎn)方案中，會(huì)導(dǎo)致部分緩沖區(qū)出現(xiàn)“擁堵”的現(xiàn)象，即緩沖區(qū)空間被工件占滿，導(dǎo)致上一工序加工完的工件無(wú)法進(jìn)入到下一工序，而停留在上一工序的緩沖區(qū)和機(jī)器中，增加了等待時(shí)間. 本文中以緩沖區(qū)占用率來(lái)衡量加工過(guò)程中各緩沖區(qū)占用情況，以并行機(jī)前置緩沖區(qū)占用率均衡作為第3個(gè)目標(biāo)，建立3目標(biāo)帶有限緩沖區(qū)的混合流水車間調(diào)度模型，記為模型2，并行機(jī)前置緩沖區(qū)占用率均衡指數(shù)如式（19）所示，Ps,k為機(jī)器緩沖區(qū)占用率，為第s工序并行機(jī)中的各個(gè)機(jī)器的平均占用率.

2 帶有限緩沖區(qū)的混合流水車間調(diào)度問(wèn)題

針對(duì)所建立的調(diào)度模型，分別采用NSGA-II，NSGA-III算法對(duì)模型進(jìn)行求解，算法框架與兩算法不同的個(gè)體選擇方式詳見(jiàn)文獻(xiàn)[25]. 本文中由于各機(jī)器配置了容積有限的緩沖區(qū)，增加了工序與工序之間的關(guān)聯(lián)性，初始種群的生成方式為隨機(jī)生成，終止準(zhǔn)則為達(dá)到預(yù)定的終止時(shí)間，適應(yīng)度為個(gè)體的目標(biāo)值，基因編碼、交叉變異的具體設(shè)計(jì)如下.

2.1 基因編碼

本文中建立的模型涉及工件排序和并行機(jī)選擇兩部分，在編碼方式上采用了雙層編碼的方式，第1層為工件碼，按照工藝順序劃分為多個(gè)加工階段，每個(gè)基因位中的數(shù)字代表工件的批次編號(hào)；第2層為機(jī)器碼，對(duì)應(yīng)第一層中的工件所選擇的機(jī)器，每個(gè)基因位中的數(shù)字代表該批次工件在該階段可選機(jī)器集中所選擇的機(jī)器索引號(hào)，若2個(gè)不同批次的工件在某階段選擇同一臺(tái)機(jī)器，則以工件碼中出現(xiàn)的先后順序確定排產(chǎn)順序，同時(shí)基因的編碼順序滿足工序間關(guān)聯(lián)性的要求. 例：如圖1所示[2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1,1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1,1,2]為一個(gè)3加工階段6批次工件模型的其中1條染色體，[2,1,3,5,4,6,3,2,4,5,1,6,4,6,3,5,2,1]是工件碼部分，[1,2,2,1,2,3,2,1,2,3,2,1,2,3,3,1,1,2]是機(jī)器碼部分，工件碼與機(jī)器碼為一一對(duì)應(yīng)關(guān)系，既包含全部加工階段與全部工件編號(hào)的工件碼同時(shí)也有對(duì)應(yīng)機(jī)器碼的染色體為一個(gè)完整的調(diào)度方案.

圖1 編碼示意圖（a）與交叉示意圖（b）Fig.1 Coding diagram (a) and cross diagram (b)

2.2 交叉與變異

采用基于工序編碼的交叉算子 (Precedence operation crossover，POX)所生成的新基因，保留了父代中工件分配到機(jī)器的機(jī)器碼部分，可以保證滿足新產(chǎn)生的子代符合生產(chǎn)工藝的約束，同時(shí)滿足本文中對(duì)工序間關(guān)聯(lián)性的要求. 具體操作如圖1中示例所示， p 1、 p 2是隨機(jī)選擇的兩個(gè)父代個(gè)體，在工件碼部分隨機(jī)生成交叉點(diǎn)，并首先在該部分進(jìn)行交叉，保留兩個(gè)父代個(gè)體中保持關(guān)聯(lián)性的相關(guān)基因，隨后機(jī)器碼部分對(duì)應(yīng)工件碼相關(guān)部分的交叉方式進(jìn)行交叉，對(duì)其中不符合工藝要求的基因調(diào)整方式為，在滿足工藝要求的基因組合中隨機(jī)選擇，保證種群的多樣性，最終生成子代c.

多點(diǎn)變異是遺傳算法中常見(jiàn)的變異方式，本文中基因變異主要針對(duì)機(jī)器碼部分，根據(jù)變異率隨機(jī)選取個(gè)體進(jìn)行變異，為保證個(gè)體的多樣性，變異過(guò)程為全隨機(jī)變異方式.

3 實(shí)例驗(yàn)證

本文以某船用管類生產(chǎn)企業(yè)為研究對(duì)象，對(duì)其生產(chǎn)加工車間進(jìn)行考慮緩沖區(qū)容積有限的混合流水車間多目標(biāo)優(yōu)化調(diào)度的相關(guān)研究. 其車間生產(chǎn)布局圖如圖2所示，車間被分為2跨4區(qū)，其中共有6個(gè)加工工序，工件在各個(gè)加工工序間通過(guò)天車進(jìn)行運(yùn)輸，每道工序都包含數(shù)量不等，加工精度、工作效率、工件適用情況不同的并行機(jī)，每臺(tái)機(jī)器都配置了獨(dú)立的前置后置緩沖區(qū)，該車間可以認(rèn)為是一個(gè)帶有限緩沖區(qū)的混合流水車間. 車間生產(chǎn)工件信息如表2所示.

圖2 生產(chǎn)車間布局圖Fig.2 Production workshop layout

表2 工件編號(hào)以及對(duì)應(yīng)各階段機(jī)器適用狀況統(tǒng)計(jì)表Table 2 Workpiece number and statistics of applicable conditions of themachine at each stage

現(xiàn)擬設(shè)計(jì)3個(gè)實(shí)驗(yàn)，（1）以該車間為研究基礎(chǔ)，分別采用NSGA-II與NSGA-III處理多目標(biāo)車間調(diào)度問(wèn)題，驗(yàn)證算法的有效性，探究2個(gè)算法處理3目標(biāo)優(yōu)化問(wèn)題時(shí)的區(qū)別；（2）通過(guò)改變緩沖區(qū)的容積，比較不同緩沖區(qū)容積時(shí)，模型2中3個(gè)目標(biāo)值的變化；（3）采用NSGA-III處理模型1，統(tǒng)計(jì)3個(gè)指標(biāo)值并與模型2的3個(gè)目標(biāo)值進(jìn)行對(duì)比分析. 所處理訂單為企業(yè)實(shí)際訂單，訂單中將工件劃分為6個(gè)批次，批次1到批次6在各個(gè)階段的機(jī)器適用情況分別對(duì)應(yīng)表2中工件編號(hào)，每個(gè)批次的批量都是8.

實(shí)驗(yàn)一：分別采用NSGA-II與NSGA-III解決3目標(biāo)帶有限緩沖區(qū)的混合流水車間調(diào)度模型，共2組實(shí)驗(yàn)，每組實(shí)驗(yàn)進(jìn)行10次，2個(gè)算法均設(shè)置為初始種群數(shù)量為500，交叉率為0.8，變異率為0.2，算法迭代10次即完成10次交叉變異之后達(dá)到終止條件.

圖3為優(yōu)化的結(jié)果，通過(guò)結(jié)果可知，在處理3目標(biāo)問(wèn)題時(shí)，NSGA-III的收斂性要明顯好于NSGA-II，圖4中為分別統(tǒng)計(jì)10次NSGA-II與NSGA-III算法處理該模型時(shí)一級(jí)個(gè)體（最優(yōu)解）的個(gè)數(shù)，通過(guò)對(duì)比可知在處理3目標(biāo)帶有限緩沖區(qū)的混合流水車間調(diào)度模型時(shí)，NSGA-III的一級(jí)個(gè)體更多，也說(shuō)明收斂效果更好.

圖3 NSGA-II（a）與 NSGA-III（b）優(yōu)化結(jié)果圖Fig.3 NSGA-II (a) and NSGA-III (b) optimization results

圖4 NSGA-II與NSGA-III一級(jí)個(gè)體數(shù)量對(duì)比圖Fig.4 Comparison of the number of NSGA-II and NSGA-III individuals

實(shí)驗(yàn)二：為更貼近車間實(shí)際情況，除第一階段機(jī)器的前置緩沖區(qū)和最后一階段的后置緩沖區(qū)，其余各個(gè)機(jī)器的前置后置緩沖區(qū)容積均相等且統(tǒng)一變化，以緩沖區(qū)可容納工件數(shù)量作為描述緩沖區(qū)容積的指標(biāo)，緩沖區(qū)可調(diào)整的最小容量為訂單中單個(gè)批次最大工件數(shù)，當(dāng)前訂單中為8，逐步增加緩沖區(qū)容量至50，對(duì)比不同緩沖區(qū)容積下，3個(gè)目標(biāo)值的變化，如圖5所示.

圖5 優(yōu)化3目標(biāo)有限緩沖區(qū)的混合流水車間調(diào)度模型三指標(biāo)統(tǒng)計(jì)結(jié)果Fig.5 Three statistical results of hybrid flow shop scheduling model with optimized three-object limited buffer zone

通過(guò)該實(shí)驗(yàn)結(jié)果可知，緩沖區(qū)的容積逐漸變大，工序間獨(dú)立性增強(qiáng)，運(yùn)輸時(shí)間與緩沖區(qū)占用率均衡指數(shù)明顯下降，其中緩沖區(qū)容積增大至14后，運(yùn)輸時(shí)間變化開(kāi)始趨于穩(wěn)定，不再有明顯的下降，緩沖區(qū)占用率均衡指數(shù)在緩沖區(qū)容積增大至10后，下降速度放緩，增大至20后再次放緩，但整體上仍繼續(xù)下降，完工時(shí)間則基本保持不變.

實(shí)驗(yàn)結(jié)果分析如下. 緩沖區(qū)容積較小則加工過(guò)程中發(fā)生“擁堵”的概率會(huì)增大，從而會(huì)延長(zhǎng)工件在天車上的滯留時(shí)間，致使運(yùn)輸時(shí)間增多；在同一緩沖區(qū)中，緩沖區(qū)中相同工件數(shù)量時(shí)，緩沖區(qū)容積大的緩沖區(qū)空間占用率低，使得緩沖區(qū)均衡指數(shù)下降，同時(shí)隨著緩沖區(qū)容積增大，工序間獨(dú)立性增強(qiáng)，可選擇加工方案增多，其中可使緩沖區(qū)占用率更均衡的方案數(shù)量也會(huì)增加，以上兩點(diǎn)都是導(dǎo)致緩沖區(qū)占用率均衡指數(shù)下降的原因；完工時(shí)間不受緩沖區(qū)容積影響.

實(shí)驗(yàn)三：使用NSGA-III處理模型1，統(tǒng)計(jì)3個(gè)指標(biāo)值情況，與實(shí)驗(yàn)二中統(tǒng)計(jì)模型2的3個(gè)目標(biāo)值情況對(duì)比，探究模型1與模型2在不同緩沖區(qū)容積下3個(gè)指標(biāo)值的區(qū)別，如圖6所示.

圖6 模型 1 與模型 2 對(duì)比. （a）完工時(shí)間；（b）運(yùn)輸時(shí)間；（c）緩沖區(qū)均衡指數(shù)Fig.6 Comparison of model 1 and model 2: (a) completion time; (b) transportation time; (c) buffer equilibrium index

通過(guò)實(shí)驗(yàn)結(jié)果可知，模型1與模型2完工時(shí)間基本相同，且隨著緩沖區(qū)容積改變，完工時(shí)間基本無(wú)變化，在緩沖區(qū)容積較小時(shí)，模型1的運(yùn)輸時(shí)間要小于模型2的運(yùn)輸時(shí)間，但緩沖區(qū)均衡指數(shù)較高，說(shuō)明在生產(chǎn)過(guò)程中出現(xiàn)了緩沖區(qū)空間占用率不均衡和機(jī)器負(fù)載不均衡的情況，緩沖區(qū)容積增大后，兩模型的運(yùn)輸時(shí)間指標(biāo)與緩沖區(qū)占用率均衡指數(shù)分別趨于相等.

4 結(jié)論

（1）同時(shí)采用NSGA-II與NSGA-III兩個(gè)算法對(duì)3目標(biāo)調(diào)度模型進(jìn)行優(yōu)化，得出在處理3個(gè)目標(biāo)的問(wèn)題時(shí)，NSGA-III在收斂性和生成一級(jí)個(gè)體數(shù)量上要好于NSGA-II的結(jié)論.

（2）求解3目標(biāo)帶有限緩沖區(qū)的混合流水車間調(diào)度模型，不斷增加緩沖區(qū)容積，得出緩沖區(qū)容積越大，完工時(shí)間基本不變，運(yùn)輸時(shí)間越短和緩沖區(qū)占用率更均衡的結(jié)論.

（3）若不考慮緩沖區(qū)占用率均衡，在緩沖區(qū)容積較小時(shí)模型1可以得到與模型2相比更小的運(yùn)輸時(shí)間，但會(huì)導(dǎo)致緩沖區(qū)占用率均衡性較差，緩沖區(qū)容積增大后，模型1的緩沖區(qū)占用率均衡性逐漸得到改善，則得出在緩沖區(qū)容積較小時(shí)，考慮緩沖區(qū)占用率均衡更具備研究意義.