離散水波優(yōu)化算法求解帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題

王文艷， 徐震浩， 顧幸生

（華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237）

隨著生產(chǎn)方式的不斷改進(jìn)，一些特殊工藝如鋼鐵煉制中的熱處理操作、半導(dǎo)體芯片的預(yù)燒工序等常需要進(jìn)行批處理[1]。目前，涉及批處理的混合生產(chǎn)方式已成為混合流水車(chē)間調(diào)度問(wèn)題的一個(gè)重要研究方向，有很多學(xué)者針對(duì)帶批處理的混合流水車(chē)間調(diào)度問(wèn)題進(jìn)行了研究。Qin 等[2]考慮了機(jī)器有限等待時(shí)間，研究了同時(shí)具有批處理機(jī)和離散機(jī)的兩級(jí)混合流水車(chē)間調(diào)度問(wèn)題。張煜等[3]和Liu 等[4]針對(duì)三階段混合批處理機(jī)和非批處理機(jī)的混合流水車(chē)間問(wèn)題進(jìn)行了研究。王君妍等[5]和軒華等[6]在不同約束條件下，研究了中間階段有多臺(tái)批處理機(jī)、其他階段為離散機(jī)的多階段混合流水車(chē)間調(diào)度問(wèn)題。然而，這些研究成果都是針對(duì)單個(gè)加工工件，沒(méi)有考慮工件的批量性。在實(shí)際制造過(guò)程中，批量生產(chǎn)工件的情況普遍存在，因此，批量流調(diào)度的研究對(duì)于制造業(yè)具有重要的現(xiàn)實(shí)意義。

批量流調(diào)度是將批量生產(chǎn)的工件劃分為多個(gè)子批，并以子批為單位進(jìn)行轉(zhuǎn)移以減少機(jī)器閑置時(shí)間，提高生產(chǎn)效率。目前已有大量文獻(xiàn)對(duì)批量流調(diào)度問(wèn)題進(jìn)行了研究。Zhang 等[7]和Qin 等[8]分別提出了改進(jìn)候鳥(niǎo)優(yōu)化算法和兩階段蟻群算法，以解決等量分批的混合流水車(chē)間批量流調(diào)度問(wèn)題。Nejati 等[9]研究了帶有輪班約束的混合流水車(chē)間調(diào)度問(wèn)題，在一致分批下采用GA 算法對(duì)工件排序進(jìn)行優(yōu)化。Wang 等[10]研究了可變分批下的混合流水車(chē)間批量流調(diào)度問(wèn)題，提出了一種混合線(xiàn)性規(guī)劃模型，確定了工件的劃分與排序。就分批方法而言，對(duì)等量分批和一致分批的研究相對(duì)較多，可變分批因其較靈活、子批的數(shù)量和大小具有不確定性使得模型求解難度增加，因此到目前為止相關(guān)研究較少。本文將帶批處理的混合流水車(chē)間問(wèn)題與批量流調(diào)度問(wèn)題相結(jié)合，對(duì)帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題進(jìn)行研究，針對(duì)批處理機(jī)與離散機(jī)不同的加工特點(diǎn)，提出了一種基于批處理機(jī)容量與不相關(guān)離散機(jī)加工能力的可變分批方法，能夠減少分批的不確定性，降低搜索空間的維度。

水波優(yōu)化(Water Wave Optimization, WWO)[11]算法是一種針對(duì)連續(xù)優(yōu)化問(wèn)題的智能算法。受淺水波模型的啟發(fā)，WWO 算法利用傳播、折射和碎浪來(lái)實(shí)現(xiàn)算法的搜索過(guò)程，該算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、易于實(shí)現(xiàn)等特點(diǎn)，可用于調(diào)度[12]、經(jīng)濟(jì)開(kāi)發(fā)[13]、發(fā)電機(jī)組檢修調(diào)度[14]等實(shí)際問(wèn)題。本文在WWO 算法的基礎(chǔ)上，提出了一種離散水波優(yōu)化(DWWO)算法來(lái)解決帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題。

1 問(wèn)題描述

帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題可以描述為：n種工件進(jìn)行m道工序的加工，每道工序k上有xk(xk≥1) 臺(tái)不相關(guān)并行機(jī)，每臺(tái)機(jī)器的加工批量有限。其中，第a( 1

1.1 參數(shù)符號(hào)

1.2 決策變量

其中：ls和le分別為工件i在工序k的子批l中最先到達(dá)工件和最后到達(dá)工件在工序k?1 中的子批號(hào)；RSikl為子批l中在轉(zhuǎn)折點(diǎn)之前到達(dá)的工件數(shù)；Po 為到達(dá)即可加工的剩余工件所屬子批在工序k?1 的序號(hào)，即子批l中在轉(zhuǎn)折點(diǎn)到達(dá)的工件在工序k?1 的子批序號(hào)。

（6）一般工序k上機(jī)器加工完工件i的空閑時(shí)刻：

（7）批處理工序的批處理子批批量：

（10）若當(dāng)前子批是批處理機(jī)的第一個(gè)加工子批，則批處理機(jī)在準(zhǔn)備操作之后即可工作，否則需等待批處理機(jī)完成前一子批的加工。

2 離散水波優(yōu)化算法設(shè)計(jì)

WWO 算法結(jié)構(gòu)簡(jiǎn)單、參數(shù)較少，目前只用于解決連續(xù)問(wèn)題。本文將WWO 算法進(jìn)行離散化處理并進(jìn)行了改進(jìn)，使其能更好地解決混合流水車(chē)間環(huán)境下的批量流調(diào)度問(wèn)題。

2.1 編碼 / 解碼方案

以工件在第一道工序的加工順序?yàn)榫幋a方案，如有6 種工件，編碼后產(chǎn)生個(gè)體 π =[2, 5, 3, 6, 4, 1] ：在此個(gè)體中，數(shù)字代表各工件的序號(hào)，數(shù)字的排序?yàn)楦鞴ぜ诘谝坏拦ば蛏系募庸ろ樞?。為了獲得切實(shí)有效的調(diào)度方案，解碼時(shí)需要解決兩個(gè)問(wèn)題：一是各工件在后續(xù)工序的加工順序；二是工件在每道工序的機(jī)器選擇。對(duì)于工件在后續(xù)工序的加工順序，本文根據(jù)先入先出(First In First Out，F(xiàn)IFO)規(guī)則，設(shè)計(jì)了兩種策略：

（1）子批優(yōu)先，根據(jù)每種工件的第一個(gè)子批在工序k的完工時(shí)間決定工件在工序k+1 的加工順序；

（2）工件優(yōu)先，考慮工件最后一個(gè)子批在工序k的完工時(shí)間，若工件在工序k上優(yōu)先完工，則安排此工件在工序k+1 上優(yōu)先加工。

針對(duì)工件在每道工序上機(jī)器的選擇問(wèn)題，設(shè)計(jì)了如下兩種策略：

(1) 機(jī)器最短完工策略 m in(EPikh) 。若工件i在工序k上選擇第h臺(tái)機(jī)器上加工，則機(jī)器h的完工時(shí)間為

Ⅱ. 子批優(yōu)先+機(jī)器加工均衡。采用機(jī)器加工均衡策略選擇機(jī)器，其他過(guò)程與方案Ⅰ類(lèi)似。

Ⅲ. 工件優(yōu)先+機(jī)器最短完工。在后續(xù)工序，工件加工順序按照各工件在上一工序的最后一個(gè)子批的加工結(jié)束時(shí)間升序排列生成，其他過(guò)程與方案Ⅰ類(lèi)似。

Ⅳ. 工件優(yōu)先+機(jī)器加工均衡。采用機(jī)器加工均衡策略選擇機(jī)器，其他過(guò)程與方案Ⅰ類(lèi)似。

2.2 操作算子的改進(jìn)

3 數(shù)據(jù)仿真與分析

目前針對(duì)考慮了批處理機(jī)容量和不相關(guān)離散機(jī)加工能力的混合流水車(chē)間批量流調(diào)度問(wèn)題的研究成果較少，且沒(méi)有標(biāo)準(zhǔn)算例可供參考比較，因此根據(jù)參考文獻(xiàn)中的設(shè)置，設(shè)計(jì)了如下數(shù)據(jù)集：各工件批量隨機(jī)分布在[10,30] 中；一般工序階段的機(jī)器數(shù)在[1,3]中隨機(jī)產(chǎn)生，機(jī)器最大加工能力和加工時(shí)間分別分布在[5,15]和[4,16]中，可分離準(zhǔn)備時(shí)間分布在[1,4]中；批處理工序隨機(jī)分布在[2,m]中；批處理階段，批處理機(jī)的加工容量和加工時(shí)間分別在[10,30]和[10,99]中隨機(jī)產(chǎn)生，批處理機(jī)的準(zhǔn)備時(shí)間分布在[6,15] 中。此數(shù)據(jù)集由50 種工件和15 道工序構(gòu)成，由于考慮了工件分批且工序存在不相關(guān)并行機(jī)，對(duì)于帶批處理的混合流水車(chē)間批量流調(diào)度來(lái)說(shuō)，數(shù)據(jù)集的規(guī)模較大且相對(duì)復(fù)雜。本文中的所有程序在Windows 10 系統(tǒng)、Intel Corei7 處理器、內(nèi)存為8 GB 的PC 上使用MATLAB R2019a 軟件編寫(xiě)并運(yùn)行。

3.1 參數(shù)調(diào)節(jié)

為了使算法能在較優(yōu)的狀態(tài)下運(yùn)行，需要對(duì)參數(shù)進(jìn)行合理設(shè)置[18]。設(shè)置種群規(guī)模為30，波長(zhǎng)上界λmax=L/3 ，波長(zhǎng)下界 λmin=λmax/2[19]。因算法的迭代次數(shù)M、波高上限hmax、碎浪操作中循環(huán)次數(shù)上限P和折射操作中折射長(zhǎng)度len也會(huì)影響算法的運(yùn)行結(jié)果，為了保證算法具有最佳的運(yùn)行狀態(tài)，采用正交實(shí)驗(yàn)法對(duì)上述4 個(gè)參數(shù)進(jìn)行設(shè)置。在兼顧算法性能和運(yùn)行時(shí)間的情況下，本文設(shè)置為M=150 ，hmax=3 ，P=15 ，len=L/5 。圖1 為參數(shù)水平影響趨勢(shì)圖，其中AVG 為算法運(yùn)行10 次時(shí)makespan 的平均值。

圖1 參數(shù)水平影響趨勢(shì)圖Fig. 1 Trend graphs of influence of parameters

3.2 解碼方案對(duì)模型的影響

為了評(píng)估不同的解碼方案的性能，對(duì)2. 1 節(jié)的4 種解碼方案進(jìn)行對(duì)比。每種方案都在不同規(guī)模的算例上測(cè)試10 次，結(jié)果如表1 所示，較優(yōu)值用黑體顯示。

表1 不同解碼方案對(duì)比結(jié)果Table 1 Comparison results of different decoding schemes

通過(guò)方案Ⅰ與方案Ⅱ、方案Ⅲ與方案Ⅳ的兩兩對(duì)比，可以觀察出針對(duì)大部分算例，方案Ⅱ的AVG比方案Ⅰ的值小。同樣地，方案IV 的AVG 也優(yōu)于方案Ⅲ。因此，對(duì)于工件排序問(wèn)題，工件優(yōu)先策略比子批優(yōu)先策略更適用于本文研究的問(wèn)題，這是因?yàn)楣ぜ?yōu)先策略能夠減小因先到達(dá)工件不足一個(gè)子批時(shí)等待的時(shí)間。另外，通過(guò)方案Ⅰ與方案Ⅲ、方案Ⅱ與方案Ⅳ的兩兩對(duì)比，可以觀察出針對(duì)大部分算例，方案Ⅰ與方案Ⅱ的結(jié)果分別優(yōu)于其他兩種方案。因此，對(duì)于機(jī)器選擇問(wèn)題，機(jī)器最短完工策略?xún)?yōu)于機(jī)器加工均衡策略，由于機(jī)器最短完工策略綜合考慮機(jī)器空閑時(shí)間和子批在機(jī)器上的加工時(shí)間，相比于機(jī)器加工均衡策略只考慮機(jī)器加工總時(shí)間均衡，更能選擇到合適的機(jī)器使子批在各道工序上盡快完工。綜上所述，在基于批處理機(jī)容量和離散機(jī)加工能力的可變分批下，方案Ⅱ的性能優(yōu)于其他3 種方案。因此，本文采用方案Ⅱ較為適合。

3.3 動(dòng)態(tài)連續(xù)加工對(duì)模型的影響

為測(cè)試動(dòng)態(tài)連續(xù)加工策略的有效性，將其與不帶動(dòng)態(tài)連續(xù)加工策略的調(diào)度方案進(jìn)行了比較。表2示出了兩種策略下針對(duì)不同規(guī)模算例運(yùn)行10 次的AVG 對(duì)比結(jié)果，黑體為較優(yōu)值。

從表2 中可以看出，針對(duì)不同規(guī)模的算例，帶動(dòng)態(tài)連續(xù)加工策略的方案均能取得更優(yōu)的目標(biāo)值。以6×4 規(guī)模為例，帶動(dòng)態(tài)連續(xù)加工策略獲得的加工序列為 π1=[1,5,2,3,4,6] ，AVG 為1 122；不帶動(dòng)態(tài)連續(xù)加工策略獲得的加工序列為 π2=[5,6,1,4,3,2] ，AVG為1 220。用兩種策略分別對(duì) π1進(jìn)行調(diào)度，對(duì)應(yīng)的甘特圖如圖2 所示，子批用白色方框表示，機(jī)器準(zhǔn)備時(shí)間用黑色方框表示。在一般工序中，方框上的數(shù)字表示子批所屬工件，方框中的數(shù)字表示子批批量；在批處理工序中，由于子批包含不同種類(lèi)的工件，因此方框中的數(shù)字表示為工件-批量。白色方框下的數(shù)字表示子批的開(kāi)始加工時(shí)間。

表2 兩種策略下的實(shí)驗(yàn)結(jié)果對(duì)比Table 2 Comparison of experimental results under two strategies

從圖2 可以看出，采用動(dòng)態(tài)連續(xù)加工策略進(jìn)行調(diào)度得到的目標(biāo)值更優(yōu)。因?yàn)椴捎脦?dòng)態(tài)連續(xù)加工策略時(shí), 在保證子批加工連續(xù)的情況下，子批中先到達(dá)的工件可以提前加工，減少了后續(xù)機(jī)器的等待時(shí)間，提高了生產(chǎn)效率。以圖2(a)和(b)為例，對(duì)于工序3 上工件1 第2 個(gè)子批的加工，由于批處理子批1 中包含11 個(gè)工件1，因此當(dāng)批處理子批1 完成批處理到達(dá)工序3 時(shí)，批處理子批1 中工件1 的其中9 個(gè)工件作為其在工序3 上第1 個(gè)子批，另外2 個(gè)工件1 將放入第2 個(gè)子批。采用帶動(dòng)態(tài)連續(xù)加工策略時(shí)，在工序3 上工件1 的第2 個(gè)子批連續(xù)加工的情況下，先到達(dá)的這2 個(gè)工件可提前加工，因此此子批比不帶動(dòng)態(tài)連續(xù)加工策略時(shí)的開(kāi)始加工時(shí)間早了16 個(gè)單位時(shí)間，由此可以驗(yàn)證動(dòng)態(tài)連續(xù)加工策略的有效性。

圖2 加工序列為 π1 時(shí)兩種策略下的甘特圖Fig. 2 Gantt charts under two strategies when the processing sequence is π1

3.4 算法性能比較與分析

為了驗(yàn)證DWWO 算法的有效性，選取不同規(guī)模的算例，并與果蠅優(yōu)化算法(FOA)[20]、變鄰域改進(jìn)遺傳算法(IGA_VNS)[16]、基本水波優(yōu)化算法(WWO)[11]、候鳥(niǎo)優(yōu)化算法(MMBO)[21]進(jìn)行了對(duì)比。所有算法都具有相同的編程語(yǔ)言和實(shí)驗(yàn)環(huán)境且終止條件都為迭代150 次。離散水波優(yōu)化算法的參數(shù)設(shè)置如3.1 節(jié)所述，其他算法的參數(shù)根據(jù)其文獻(xiàn)確定。所有算法都運(yùn)行10 次，實(shí)驗(yàn)結(jié)果見(jiàn)表3。表中各項(xiàng)性能指標(biāo)的最優(yōu)值用黑體顯示。算法性能采用相對(duì)百分比偏差平均值(MRPD)、相對(duì)百分比偏差標(biāo)準(zhǔn)差 (SDRPD)、相對(duì)百分比偏差最優(yōu)值(BRPD)進(jìn)行評(píng)估。計(jì)算公式如下：

其中：ck表示算法第k次運(yùn)算的結(jié)果(k=1,2,···,s)；c?為所有算法得到的最優(yōu)值。

從表3 中可以看出，對(duì)于較小規(guī)模的算例，5 種算法的結(jié)果相差不大，說(shuō)明對(duì)于小規(guī)模算例，這5 種算法都能取得最優(yōu)值且性能較穩(wěn)定；但隨著規(guī)模的增加，DWWO 算法的優(yōu)勢(shì)逐漸體現(xiàn)出來(lái)，針對(duì)工件數(shù)為15、20、35 和50，工序數(shù)為10 和15 的8 個(gè)較大規(guī)模的算例，DWWO 算法在其中8 個(gè)算例都獲得了最小的MRPD 和BRPD 值，且在其中5 個(gè)算例上獲得了最小的SDRPD 值，說(shuō)明DWWO 算法在求解較大規(guī)模問(wèn)題時(shí)，尋優(yōu)性能和穩(wěn)定性相對(duì)優(yōu)于其他對(duì)比算法。對(duì)于所有規(guī)模的問(wèn)題，WWO 算法只在其中10 個(gè)較小規(guī)模的算例中取得了最小的BRPD 值，而DWWO 算法在24 個(gè)算例中都取得了最小的BRPD 值，說(shuō)明DWWO 算法的搜索質(zhì)量相比于WWO 算法有了極大的改善。

表3 DWWO，F(xiàn)OA，MMBO，WWO，IGA_V 算法對(duì)比結(jié)果Table 3 Comparison results of DWWO, FOA, MMBO, WWO and IGA_V

圖3 示出了5 種算法針對(duì)4 種不同規(guī)模實(shí)例的收斂曲線(xiàn)。在求解不同規(guī)模的問(wèn)題時(shí)，DWWO 算法在第1 代都具有較好的解，主要是由于DWWO 算法采用了NEH 方法對(duì)種群進(jìn)行初始化，從而提高了初始解的質(zhì)量；DWWO 算法的收斂曲線(xiàn)在迭代前期會(huì)發(fā)生較大幅度的下降，之后會(huì)表現(xiàn)出逐步下降的趨勢(shì)。主要是因?yàn)樗惴ㄔ趯?yōu)過(guò)程中采用塊最優(yōu)插入及多鄰域搜索提高了操作算子的性能，增強(qiáng)了算法的局部搜索能力，使算法能夠快速跳出局部最優(yōu)；在每代中不斷替換當(dāng)前代的最差解，提升了DWWO 算法解的整體質(zhì)量從而加快了收斂速度，提高了全局搜索能力。但是在求解 50 ×15 的算例時(shí)，DWWO 算法的收斂速度卻較慢，從圖3(d) 也可以看出，DWWO 算法的收斂曲線(xiàn)在100 代左右下降趨勢(shì)才有所減緩。

圖3 各算法求解不同規(guī)模問(wèn)題的迭代曲線(xiàn)Fig. 3 Iterative curves of each algorithm for solving problems of different scales

相對(duì)于其他算法，DWWO 算法具有更好的解決帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題的能力，其穩(wěn)定性和收斂能力均較優(yōu)，且由于DWWO 算法對(duì)操作算子進(jìn)行了改進(jìn)并提出了一種替換差解操作，因此具有較優(yōu)的局部和全局搜索能力。

4 結(jié) 論

本文在考慮機(jī)器可分離準(zhǔn)備時(shí)間的情況下，以最大完工時(shí)間最小化為優(yōu)化目標(biāo)，研究了帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題：

（1）結(jié)合實(shí)際生產(chǎn)中批處理機(jī)與離散機(jī)混合加工的特點(diǎn)，首次提出了一種可變分批方法將兩種機(jī)器的加工方式相結(jié)合對(duì)工件進(jìn)行分批。

（2）針對(duì)可變分批下工件在不同工序批量不同這一特點(diǎn)，提出了一種動(dòng)態(tài)連續(xù)加工策略，能夠減小工件的等待時(shí)間，提高生產(chǎn)效率。

（3）提出了一種離散水波優(yōu)化算法，采用基于工件在第一道工序上加工順序的編碼方案，并設(shè)計(jì)了4 種解碼方案確定后續(xù)工序工件的加工順序及機(jī)器的選擇；采用啟發(fā)式算法提高種群初始解質(zhì)量；利用塊最優(yōu)插入、交叉操作、多鄰域搜索分別對(duì)基本操作進(jìn)行了改進(jìn)，并加入替換差解操作以協(xié)調(diào)算法的局部和全局搜索的能力，提高了算法的收斂速度。

（4）采用實(shí)驗(yàn)設(shè)計(jì)方法生成隨機(jī)算例，并對(duì)算法參數(shù)進(jìn)行標(biāo)定，測(cè)試了本文算法的性能。實(shí)驗(yàn)結(jié)果驗(yàn)證了DWWO 算法求解帶批處理的混合流水車(chē)間批量流調(diào)度問(wèn)題的可行性和有效性。