吳秀麗，曹 錚

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

0 引言

冷拔無(wú)縫鋼管主要應(yīng)用于石油運(yùn)輸、航空航天以及汽車制造等行業(yè)中，被人們稱為工業(yè)的“血管”。冷拔無(wú)縫鋼管的生產(chǎn)過(guò)程存在多道次重入的特征，在一個(gè)道次中包括酸洗、修磨、冷拔、退火等環(huán)節(jié)。其中冷拔階段是工藝流程中加工時(shí)間最長(zhǎng)的階段，在該階段往往有多臺(tái)并行機(jī)同時(shí)進(jìn)行加工。除此之外，在冷拔后的退火階段，需要使用退火爐來(lái)消除應(yīng)力，會(huì)消耗大量的能源。在企業(yè)實(shí)際生產(chǎn)中，常用的退火爐有環(huán)形加熱爐和輥底式爐等，這些退火爐具有連續(xù)式批處理機(jī)的特征，工件在連續(xù)式批處理機(jī)上加工時(shí)依次進(jìn)入和離開。因此，這類冷拔生產(chǎn)過(guò)程可以被建模為帶連續(xù)式批處理機(jī)的可重入混合流水車間調(diào)度問(wèn)題(Re-entrant Hybrid Flow shop Scheduling Problem with Continuous Batch Processing Machines, RHFSP-CBPM)。目前,無(wú)縫鋼管的冷拔生產(chǎn)仍依賴于傳統(tǒng)的人工排產(chǎn)方式，智能化程度不高，從而導(dǎo)致生產(chǎn)周期長(zhǎng)、環(huán)保壓力大的問(wèn)題。因此，對(duì)冷拔生產(chǎn)過(guò)程進(jìn)行智能調(diào)度，提高生產(chǎn)效率的同時(shí)減少能耗，具有非常重要的現(xiàn)實(shí)意義。

早在1988年，GUPTA等[1]就已證明了混合流水車間調(diào)度問(wèn)題是NP難問(wèn)題，而冷拔無(wú)縫鋼管的生產(chǎn)過(guò)程除了符合混合流水車間調(diào)度問(wèn)題的特征外，還具有可重入調(diào)度和連續(xù)式批調(diào)度的特征，這使得它的求解更加困難。截至目前，同時(shí)考慮可重入調(diào)度和批調(diào)度的研究還較少，JIA等[2]將半導(dǎo)體晶圓的制造過(guò)程抽象為帶時(shí)間窗的可重入批處理機(jī)調(diào)度問(wèn)題進(jìn)行了研究；林剛[3]將模具熱制造過(guò)程抽象為兩階段流水車間調(diào)度問(wèn)題，同時(shí)考慮了并行批處理機(jī)和可重入工件；顧濤[4]研究了無(wú)縫鋼管生產(chǎn)過(guò)程中的周期式退火爐作批處理機(jī)的可重入批離散機(jī)流水車間調(diào)度問(wèn)題。以上研究考慮了批處理機(jī)在各種可重入調(diào)度問(wèn)題中的應(yīng)用，建立了優(yōu)化模型和優(yōu)化算法進(jìn)行求解，但是仍有研究空間。上述研究中，批處理機(jī)的類型都是周期式批處理機(jī)，缺少對(duì)其他類型批處理機(jī)的研究，并且批處理機(jī)緩沖區(qū)因素的影響也沒(méi)有被考慮。因此，有必要對(duì)RHFSP-CBPM進(jìn)行研究。目前，分別對(duì)可重入混合流水車間調(diào)度問(wèn)題(Re-entrant Hybrid Flow shop Scheduling Problem, RHFSP)和批調(diào)度問(wèn)題的研究都有較為豐富的成果，這些成果可以作為研究RHFSP-CBPM問(wèn)題時(shí)的重要參考。

RHFSP近年引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，可重入調(diào)度問(wèn)題的特點(diǎn)是工件需要在同一個(gè)加工階段多次加工，常見于半導(dǎo)體制造[2]、冷拔無(wú)縫鋼管[5-6]和電路板印刷制造[7]等行業(yè)中。在對(duì)RHFSP的研究中，對(duì)于單目標(biāo)問(wèn)題，CHAMNANLOR等[8]研究了帶時(shí)間窗約束的RHFSP，結(jié)合遺傳算法和蟻群算法來(lái)最小化完工時(shí)間；ZHANG等[9]研究了具有機(jī)器可用性約束的RHFSP問(wèn)題，考慮了總延誤的最小化，對(duì)離散差分進(jìn)化算法進(jìn)行了改進(jìn)；ZHOU等[10]研究了以總加權(quán)完工時(shí)間最小為目標(biāo)的RHFSP問(wèn)題，并設(shè)計(jì)了基于集成模型的混合差分進(jìn)化算法。

在進(jìn)一步的研究中，更為復(fù)雜的目標(biāo)函數(shù)被考慮在內(nèi)，例如，CHO等[11]以生產(chǎn)效率和客戶滿意度為目標(biāo)，設(shè)計(jì)了多層遺傳算法和啟發(fā)式算法進(jìn)行了求解；YING等[12]提出一種迭代帕累托貪婪算法，求解具有最小化完工時(shí)間和總延誤雙目標(biāo)的RHFSP。除了時(shí)間相關(guān)的指標(biāo)外，為了實(shí)現(xiàn)低碳制造，滿足節(jié)能減排的需求，越來(lái)越多的研究開始考慮能耗相關(guān)的指標(biāo)。董君等[13]對(duì)考慮可再生能源的可重入混合流水車間調(diào)度問(wèn)題進(jìn)行了研究，同時(shí)考慮了生產(chǎn)中的制造階段和檢測(cè)修復(fù)階段，以完工時(shí)間、碳排放和總拖期為目標(biāo)，設(shè)計(jì)了基于樽海鞘群和帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm,NSGA-Ⅱ)的混合算法進(jìn)行求解。GENG等[14]考慮了機(jī)器的開關(guān)控制策略，以最大完工時(shí)間、最大延誤和空閑能耗為目標(biāo)，提出了一種改進(jìn)的多目標(biāo)多階段優(yōu)化算法求解RHFSP。并且,在進(jìn)一步的研究中，他們還研究了考慮多時(shí)間因素的綠色可重入混合流水車間調(diào)度問(wèn)題，以完工時(shí)間和總能耗為目標(biāo)，提出一種混合文化基因算法進(jìn)行求解。上述研究考慮了多種生產(chǎn)環(huán)境下的可重入調(diào)度問(wèn)題的求解，提出了一系列智能算法，對(duì)完工時(shí)間能耗等指標(biāo)進(jìn)行了優(yōu)化[15]。在冷拔無(wú)縫鋼管的生產(chǎn)過(guò)程中，主要的能耗來(lái)源于退火過(guò)程，而退火爐除了高能耗的特征外，還有批處理的特征，這也是需要考慮的因素。

在批調(diào)度問(wèn)題的研究中，批處理機(jī)可以分為兩大類：周期式批處理機(jī)、連續(xù)式批處理機(jī)，其中周期式批處理機(jī)的研究更多。目前對(duì)周期式批處理機(jī)調(diào)度的研究中，單目標(biāo)問(wèn)題的研究以完工時(shí)間目標(biāo)為主，考慮了批處理機(jī)的不同能力[16-17]，針對(duì)作業(yè)的不同規(guī)模、釋放時(shí)間、動(dòng)態(tài)到達(dá)等特征進(jìn)行了研究[18-19]。在進(jìn)一步的研究中，更多的目標(biāo)函數(shù)被考慮在內(nèi)。在考慮作業(yè)交貨期的研究中，延誤時(shí)間往往會(huì)作為完工時(shí)間之外的另一個(gè)目標(biāo)函數(shù)[20-21]。在考慮成本問(wèn)題的研究中，能耗[22]、運(yùn)輸成本[23]和機(jī)器采購(gòu)成本[24]與完工時(shí)間結(jié)合作為多目標(biāo)優(yōu)化的指標(biāo)。上述研究考慮了機(jī)器和作業(yè)的多種特征，并設(shè)計(jì)了有效的啟發(fā)式算法對(duì)各類目標(biāo)進(jìn)行求解。

在對(duì)連續(xù)式批處理機(jī)的研究中，趙玉芳等[25]針對(duì)鋼鐵行業(yè)加熱爐對(duì)管坯的加熱過(guò)程，提出一種新的連續(xù)型批處理機(jī)調(diào)度問(wèn)題，并給出了一批工件的加工時(shí)間的計(jì)算方式，以保證批處理機(jī)同時(shí)加工的工件不超過(guò)其容量。在進(jìn)一步的研究中，趙玉芳等[26-27]考慮了釋放時(shí)間約束和鏈?zhǔn)郊s束等條件，并使用動(dòng)態(tài)規(guī)劃算法對(duì)單機(jī)連續(xù)型批調(diào)度問(wèn)題進(jìn)行了求解。上述對(duì)于連續(xù)式批處理機(jī)的研究，側(cè)重于組批和工件的排序，僅考慮了批處理一個(gè)階段。因此，對(duì)連續(xù)式批處理機(jī)的研究在問(wèn)題約束上以及求解方法上都還有進(jìn)一步的研究空間。

上述研究中，分別考慮了可重入工件和批處理機(jī)對(duì)調(diào)度的影響，開發(fā)了智能算法進(jìn)行求解。在可重入混合流水車間調(diào)度問(wèn)題的研究中，沒(méi)有考慮重入工件對(duì)組批的影響；在批調(diào)度問(wèn)題的研究中，緩沖區(qū)大小的影響未被研究。因此，對(duì)于可重入調(diào)度和批調(diào)度的研究還有很大的探索空間。本文以無(wú)縫鋼管的冷拔生產(chǎn)過(guò)程為研究背景，將工件可重入的特征與連續(xù)式批處理機(jī)相結(jié)合，建立RHFSP-CBPM的優(yōu)化模型，開發(fā)了一個(gè)改進(jìn)的基于分解的多目標(biāo)進(jìn)化算法(Improved Multi-objective Evolutionary Algorithm based on Decomposition, IMOEA/D)。本文的主要貢獻(xiàn)如下：①綜合考慮可重入工件、連續(xù)式批處理機(jī)和緩沖區(qū)3方面的特點(diǎn)，建立了數(shù)學(xué)優(yōu)化模型；②提出了IMOEA/D，設(shè)計(jì)了一種針對(duì)緩沖區(qū)約束和批處理機(jī)容量約束的解碼策略，在迭代過(guò)程中根據(jù)種群多樣性選擇局部搜索策略或多樣性增強(qiáng)策略，并對(duì)非支配解集進(jìn)行局部搜索來(lái)提高解的分布性；③討論了連續(xù)式批處理機(jī)的合適緩沖區(qū)大?。虎芨鶕?jù)批處理機(jī)內(nèi)的實(shí)時(shí)工件數(shù)量，設(shè)計(jì)了工件的靈活等待時(shí)間，在盡可能減少等待時(shí)間的同時(shí)，保證了批處理機(jī)同時(shí)加工的工件不超過(guò)其容量。

1 帶連續(xù)式批處理機(jī)的可重入混合流水車間調(diào)度優(yōu)化模型

1.1 問(wèn)題描述

隨著鋼管企業(yè)生產(chǎn)自動(dòng)化水平的不斷發(fā)展，連續(xù)式退火爐的應(yīng)用也越來(lái)越常見，連續(xù)式退火爐常用的有環(huán)形加熱爐、輥底式爐等，這類退火爐在加工一批工件時(shí)采用的是傳動(dòng)的方式，工件在批處理機(jī)內(nèi)連續(xù)移動(dòng)，受熱均勻，能夠較好地保證退火質(zhì)量。連續(xù)式退火爐和周期式退火爐的工作原理對(duì)比如圖1所示，連續(xù)式退火爐在加工的過(guò)程中，一個(gè)批次內(nèi)的鋼管依次勻速地進(jìn)入退火爐，并且在加熱完后依次離開，離開后即可進(jìn)行后續(xù)的加工流程；周期式退火爐在加工過(guò)程中，一個(gè)批次內(nèi)的鋼管同時(shí)進(jìn)入和離開機(jī)器，離開機(jī)器后所有鋼管同時(shí)可用。

RHFSP-CBPM可以描述為：混合流水車間包含多個(gè)加工階段，每個(gè)階段包含多臺(tái)加工能力不同的并行機(jī)，工件在每個(gè)加工階段都可在任一并行機(jī)上加工。在整個(gè)工藝流程中，工件要按照順序經(jīng)過(guò)這些加工階段，且在某些加工階段需要重復(fù)加工，從第一個(gè)加工階段到最后一個(gè)加工階段的完整流程稱為一個(gè)重入道次，在不同的道次工件的加工時(shí)間不同。在一個(gè)道次的所有加工階段中，最后一個(gè)階段是批處理階段，其他階段均為離散加工階段。批處理階段對(duì)應(yīng)的加工機(jī)器是連續(xù)式批處理機(jī)，在連續(xù)式批處理機(jī)前存在緩沖區(qū)，用于存放待批處理的工件；離散加工階段對(duì)應(yīng)的加工機(jī)器是離散機(jī)。如圖2所示為RHFSP-CBPM的示意圖。

為了簡(jiǎn)化問(wèn)題，作出如下假設(shè)：

(1)工件之間相互獨(dú)立，互不影響。

(2)所有工件在零時(shí)刻都可以被加工。

(3)工件到達(dá)機(jī)器的搬運(yùn)時(shí)間以及在機(jī)器上的準(zhǔn)備時(shí)間都包含在加工時(shí)間內(nèi)。

(4)機(jī)器在加工過(guò)程中不允許中途停止或插入其他工件。

(5)連續(xù)式批處理機(jī)的容量和緩沖區(qū)大小已知，離散機(jī)上緩沖區(qū)大小無(wú)限。

(6)連續(xù)式批處理機(jī)在第一個(gè)工件開工時(shí)開機(jī)，在最后一個(gè)工件完工時(shí)關(guān)機(jī)。

(7)連續(xù)式批處理機(jī)的加工功率和空閑功率已知，且加工過(guò)程中功率恒定。

1.2 符號(hào)定義

本文用到的符號(hào)定義如表1所示。

表1 符號(hào)定義

1.3 數(shù)學(xué)模型

(1)目標(biāo)函數(shù)

式(1)表示RHFSP-CBPM的優(yōu)化目標(biāo)，即最小化最大完工時(shí)間和批處理機(jī)的總能耗。

(1)

(2)約束條件

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

Rii′k∈{0,1},?i,i′,k。

(18)

式(2)是次序柔性約束，對(duì)于同一工件的先后兩道工序，后道工序必須在前道工序完工后才能開始加工；式(3)表示在離散機(jī)上任意兩個(gè)工件加工時(shí)間不重疊；式(4)表示工序柔性約束，在任意時(shí)刻，一個(gè)工件只能在一臺(tái)機(jī)器上進(jìn)行加工；式(5)反映了工件的道次約束，工件只能完成前一個(gè)道次的所有工序后才能開始下一道次的加工；式(6)表示工序的完工時(shí)間的計(jì)算公式；式(7)表示在任意時(shí)刻，批處理機(jī)內(nèi)同時(shí)加工的工件數(shù)不超過(guò)批處理機(jī)容量；式(8)表示批處理機(jī)上批次的次序約束，只有前一批次的所有工件完成加工后，后一批次才能開始加工；式(9)表示在任意時(shí)刻，批處理機(jī)緩沖區(qū)內(nèi)等待的工件數(shù)不超過(guò)批處理機(jī)容量；式(10)表示一個(gè)批次的完工時(shí)間的計(jì)算公式；式(11)表示批次內(nèi)每個(gè)工件的加工時(shí)間等于該批工件中處理時(shí)間最長(zhǎng)的工件所需的時(shí)間；式(12)表示一批工件的開始時(shí)間等于該批最早開始加工的工件的開工時(shí)間；式(13)表示一批工件總加工時(shí)間的計(jì)算公式；式(14)表示批處理機(jī)上一批工件的加工能耗的計(jì)算公式；式(15)表示批處理機(jī)加工兩批工件間的空閑能耗的計(jì)算公式；式(16)～式(18)表示決策變量的取值范圍。

2 IMOEA/D

2.1 算法描述

早在1988年，混合流水車間調(diào)度問(wèn)題就被證明是NP難的問(wèn)題[1]，RHFSP-CBPM在其基礎(chǔ)上考慮了工件可重入的特征以及連續(xù)式批處理機(jī)加工的特征，使得問(wèn)題的求解更加困難。在對(duì)NP難問(wèn)題的求解中，智能算法一直有著良好的表現(xiàn)[28-29]，2007年ZHANG等[30]首次提出基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)，在近年來(lái)的研究中，MOEA/D及其相關(guān)的改進(jìn)算法在求解各類優(yōu)化問(wèn)題上都表現(xiàn)出了良好的性能[31]。

MOEA/D的原理是將多目標(biāo)問(wèn)題拆解為單目標(biāo)問(wèn)題，然后同時(shí)進(jìn)行求解，分別逼近Pareto前沿。MOEA/D得到的解在分布范圍和均勻性上有良好的表現(xiàn)，但是MOEA/D在收斂過(guò)程中，種群的多樣性隨著迭代次數(shù)的增加逐漸降低，算法可能陷入局部最優(yōu)。為了有效解決該問(wèn)題，設(shè)計(jì)了IMOEA/D算法，在迭代過(guò)程中根據(jù)多樣性的好壞來(lái)采用局部搜索或多樣性增強(qiáng)策略，在提高算法局部搜索能力的同時(shí)避免陷入局部最優(yōu)。算法的流程圖如圖3所示。

算法具體步驟為：

步驟1隨機(jī)產(chǎn)生初始種群，計(jì)算初始種群適應(yīng)值，進(jìn)行非支配解排序得到第一代非支配解集。

步驟2判斷是否滿足終止條件，若滿足則轉(zhuǎn)步驟9，否則進(jìn)入步驟3。

步驟3給種群中的每一個(gè)個(gè)體分配子問(wèn)題的權(quán)重向量。

步驟4在該個(gè)體的鄰域隨機(jī)選擇兩個(gè)不相同的鄰居，依次進(jìn)行交叉變異，得到子代個(gè)體。

步驟5計(jì)算子代個(gè)體適應(yīng)值，使用切比雪夫方法更新鄰域個(gè)體及其適應(yīng)值，更新非支配解集。

步驟6根據(jù)鄰域個(gè)體適應(yīng)值是否相同來(lái)計(jì)算鄰域多樣性。

步驟7若鄰域多樣性好，則對(duì)鄰域個(gè)體進(jìn)行局部搜索；若鄰域多樣性差，則采用鄰域多樣性增強(qiáng)策略，采用隨機(jī)生成或鄰域內(nèi)個(gè)體交叉的方式產(chǎn)生新的鄰域個(gè)體。

步驟8計(jì)算局部搜索或多樣性增強(qiáng)產(chǎn)生的新個(gè)體的適應(yīng)值，并更新對(duì)應(yīng)的鄰域個(gè)體，返回步驟2。

步驟9對(duì)非支配解集進(jìn)行局部搜索，更新最終的非支配解集。

步驟10輸出最終的非支配解集。

2.2 算法詳細(xì)設(shè)計(jì)

2.2.1 編碼與初始化

根據(jù)RHFSP-CBPM特點(diǎn)，采用工序染色體的編碼方式[32]。工序染色體用于確定各工件的工序的加工順序。工序染色體由工件編號(hào)組成，染色體的長(zhǎng)度等于所有工件的總工序數(shù)，工件編號(hào)第幾次出現(xiàn)就代表是第幾道工序。在工序染色體中一個(gè)工件的編號(hào)可能出現(xiàn)多次，因此采用原始編碼序號(hào)結(jié)合隨機(jī)排列序號(hào)的方式來(lái)初始化一條染色體，以4個(gè)工件3道工序的問(wèn)題為例，初始化染色體的過(guò)程如圖4所示。

首先根據(jù)工件數(shù)和工序數(shù)，確定原始編碼序號(hào)，其中藍(lán)色表示第一道工序；橘色表示第二道工序；綠色表示第三道工序。然后根據(jù)染色體長(zhǎng)度，生成原始編碼序號(hào)對(duì)應(yīng)位置的隨機(jī)排列序號(hào)，該序號(hào)用于決定原始編碼序號(hào)在染色體中的實(shí)際位置，結(jié)合這兩個(gè)序號(hào)得到最終生成的染色體。

2.2.2 解碼

在對(duì)染色體的適應(yīng)值進(jìn)行評(píng)估時(shí)，需要使用相應(yīng)的解碼算法。RHFSP-CBPM的難點(diǎn)在于批處理階段，需要將合適的工件組批的同時(shí)，保證同時(shí)加工的工件數(shù)量不超過(guò)批處理機(jī)容量，并在批處理機(jī)前緩沖區(qū)等待的工件數(shù)不超過(guò)緩沖區(qū)容量。因此，提出了針對(duì)緩沖區(qū)大小約束的緊前工序后移調(diào)度規(guī)則和針對(duì)批處理機(jī)容量約束的工件等待時(shí)間計(jì)算公式，并設(shè)計(jì)了如下解碼算法，在滿足約束條件的同時(shí)最小化這兩個(gè)目標(biāo)。

(1)緊前工序后移調(diào)度規(guī)則

連續(xù)式批處理機(jī)在對(duì)一批工件進(jìn)行加工時(shí)，工件通過(guò)傳動(dòng)的方式進(jìn)入批處理機(jī)，因此連續(xù)式批處理機(jī)的前置緩沖區(qū)往往是有限的。在解碼過(guò)程中，當(dāng)工件到達(dá)批處理機(jī)時(shí)，需要判斷工件能否立即開始加工。若能立即開始加工，則不占用緩沖區(qū)資源；若工件到達(dá)后無(wú)法立即開始加工，則需要在緩沖區(qū)中進(jìn)行等待；若緩沖區(qū)已滿，工件無(wú)法在緩沖區(qū)中等待，則需要將當(dāng)前工件的緊前工序進(jìn)行后移，使得工件到達(dá)批處理機(jī)時(shí)緩沖區(qū)未滿，或工件能夠立即開始加工。

以極端情況下緩沖區(qū)容量為0為例，使用緊前工序后移調(diào)度規(guī)則調(diào)整調(diào)度方案的過(guò)程如圖5所示。其中階段C是連續(xù)式批處理階段，階段A和B是離散加工階段，機(jī)器C1是連續(xù)式批處理機(jī)。當(dāng)前的染色體是“1-2-3-1-2-3-1-3-2”，在圖5a調(diào)度方案中，工件2的工序2-3占用了紅色部分的緩沖區(qū)，違背了緩沖區(qū)容量為0的約束條件，因此需要對(duì)該工序的緊前工序2-2進(jìn)行后移。調(diào)整后的調(diào)度方案如圖5b所示，此時(shí)3個(gè)工件完成階段B的加工后都可以立刻在機(jī)器C1上加工，符合緩沖區(qū)容量為0的約束條件。

(2)工件等待時(shí)間計(jì)算方法

工件在連續(xù)式批處理機(jī)上加工時(shí)，由于加工同一批工件時(shí)，輥?zhàn)愚D(zhuǎn)速是相同的，所以一批內(nèi)各工件的批處理時(shí)間是相同的，都等于這批中處理時(shí)間最長(zhǎng)的工件的處理時(shí)間；同一批中工件的進(jìn)入、處理和離開都是連續(xù)的。連續(xù)式批處理機(jī)的容量是有限的，為保證批處理機(jī)同時(shí)加工的工件數(shù)不超過(guò)其容量，提出了一種批次內(nèi)工件等待時(shí)間的計(jì)算方法。

在解碼過(guò)程中，根據(jù)批處理機(jī)內(nèi)工件的開工時(shí)間和完工時(shí)間，實(shí)時(shí)判斷批處理機(jī)內(nèi)的工件數(shù)量，當(dāng)新的工件到達(dá)批處理機(jī)時(shí)，計(jì)算工件最早能夠開始加工的時(shí)刻和工件到達(dá)時(shí)刻的差值，若該差值大于零，則將該差值作為工件的等待時(shí)間。假設(shè)批處理機(jī)容量為b，一個(gè)批次內(nèi)有k個(gè)工件，每個(gè)工件記為Ti(i=1,2,…k)，批次內(nèi)工件加工時(shí)間為Pc，批次內(nèi)工件的到達(dá)時(shí)間為Ai，批次內(nèi)工件的開工時(shí)間為Si，完工時(shí)間為Fi。此外，給定一個(gè)工件間的最小等待時(shí)間Pmin=0.15Pc。批次內(nèi)工件Ti的等待時(shí)間Pi計(jì)算公式如式(19)所示，這種等待時(shí)間計(jì)算方式使得工件能夠盡快進(jìn)入到批處理機(jī)中，并且滿足了批處理機(jī)的容量約束。

(19)

(3)解碼算法

對(duì)工件工序染色體解碼的詳細(xì)步驟如下：

步驟1依次獲取工件工序染色體上的每一個(gè)基因，判斷其代表的是哪個(gè)工件的哪一道工序，計(jì)算其所處的階段。

步驟2若該工件處于離散加工階段，則轉(zhuǎn)步驟3；若該工件處于批處理加工階段，則轉(zhuǎn)步驟4。

步驟3遍歷該工序所處階段的所有并行機(jī)，使用間隙插空法[32]尋找能夠插入的空隙，記錄每個(gè)機(jī)器上該工序的完工時(shí)間，轉(zhuǎn)步驟5。

步驟4遍歷批處理機(jī)上的所有批次，尋找加工時(shí)間不小于當(dāng)前工序的批次，并按照從小到大排序。依次判斷當(dāng)前工件與批次內(nèi)工件能否進(jìn)行組批。若能組批，則轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟7。

步驟5標(biāo)記能夠最早加工完該工序的機(jī)器，作為最終選擇的機(jī)器，將該工序安排到機(jī)器上進(jìn)行加工。返回步驟1，直到所有的基因?qū)?yīng)的工序都被加工完畢。

步驟6將該工序加入到最早能夠完工的批次中，根據(jù)緩沖區(qū)約束和批處理機(jī)容量約束調(diào)整開工時(shí)間。返回步驟1，直到所有的基因?qū)?yīng)的工序都加工完畢。

步驟7使用間隙插空法[32]尋找批處理機(jī)上的所有空隙，將該工序插入到最早能完工的空隙中，該工序?qū)?yīng)的工件作為新批次的第一個(gè)工件。返回步驟1，直到所有的基因?qū)?yīng)的工序都被加工完畢。

解碼算法的偽代碼如下。

算法1解碼算法。

1：依次獲取染色體上的每一個(gè)基因，計(jì)算對(duì)應(yīng)工序所處的階段k；

2：ifk∈離散加工階段then

3： 遍歷該階段的所有并行機(jī)Mk，尋找能夠插入的空隙；

4： 記錄每個(gè)機(jī)器上該工序的完工時(shí)間FMk；

5： 將該工序安排到FMk最小的機(jī)器上進(jìn)行加工，返回步驟1；

6：else

7： 遍歷批處理機(jī)上的所有批次b；

8： 如果能加入到現(xiàn)有批次中，則insert=1，否則insert=0；

9： ifinsert=1 then

10： 將該工序加入到最早能夠完工的批次中，返回步驟1；

11： else

12： 將該工序安排到批處理機(jī)上的最早能插入的批次空隙中。返回步驟1；

13： end

14：end

15：解碼完畢。

2.2.3 交叉和變異

在IMOEA/D中，合適的交叉和變異算子能夠提高算法的全局搜索能力。對(duì)于工序編碼的染色體而言，直接進(jìn)行片段交叉會(huì)產(chǎn)生非法染色體，在交叉后還需要對(duì)其進(jìn)行合理化的操作，并在交叉過(guò)程中父代的特征可能因?yàn)楹侠砘獾狡茐?。因此，提出分?交叉-還原的染色體交叉方式，來(lái)避免非法染色體的出現(xiàn)，其中交叉方式采用兩點(diǎn)映射式交叉(Two-point Mapping crossover operation, TMX)[33]。在分解的過(guò)程中，按照階段對(duì)工序編碼染色體進(jìn)行分解，得到每一個(gè)階段內(nèi)工件加工的順序，對(duì)父代兩條染色體的分解過(guò)程如圖6所示。

按階段對(duì)父代染色體分解后，再針對(duì)每個(gè)階段的染色體片段采用兩點(diǎn)映射式交叉，交叉過(guò)程如圖7所示，黑色箭頭所在位置為選擇的兩點(diǎn)。在交叉過(guò)程中，染色體1的兩點(diǎn)間片段需要根據(jù)染色體2對(duì)應(yīng)的次序來(lái)映射，而染色體2的兩點(diǎn)間片段需要根據(jù)染色體1對(duì)應(yīng)的次序來(lái)映射，交叉前后的染色體片段如圖7所示，這樣的映射交叉方式不會(huì)得到非法的染色體片段，保證了染色體的可行性。

在對(duì)每個(gè)階段的染色體片段進(jìn)行交叉后，再根據(jù)基因在原染色體上的位置進(jìn)行還原，得到最終交叉后的染色體。以染色體1第一段交叉后還原為例，還原的過(guò)程如圖8所示，黃色片段是交叉后得到的片段，根據(jù)原本在染色體中所在的位置，將其還原到染色體中，得到交叉后的子代染色體。

為提高算法的局部搜索能力，設(shè)計(jì)了如下變異操作。在變異過(guò)程中，若對(duì)某個(gè)或者某一段基因進(jìn)行變異，可能會(huì)產(chǎn)生非法解，因此，采用基于工件的變異方式，選擇兩個(gè)不同的工件，將其對(duì)應(yīng)的所有基因位置進(jìn)行互換，得到新的染色體。變異過(guò)程如圖9所示，其中黑色箭頭指向選擇的工件序號(hào)。

2.2.4 根據(jù)多樣性的鄰域更新

在迭代過(guò)程中，根據(jù)對(duì)當(dāng)前個(gè)體鄰域的多樣性進(jìn)行計(jì)算，若多樣性好，則對(duì)鄰域個(gè)體以一定概率進(jìn)行局部搜索；若多樣性差，則進(jìn)行多樣性增強(qiáng)。在鄰域多樣性的計(jì)算過(guò)程中，需要對(duì)鄰域個(gè)體進(jìn)行對(duì)比，因?yàn)槿旧w長(zhǎng)度較長(zhǎng)，對(duì)每個(gè)基因點(diǎn)位進(jìn)行對(duì)比需要花費(fèi)很長(zhǎng)時(shí)間，所以采用鄰域個(gè)體的適應(yīng)值作為比較對(duì)象。這樣的對(duì)比方式能夠節(jié)省多樣性計(jì)算的時(shí)間，并且能夠反映解空間上鄰域個(gè)體的多樣性。

鄰域更新的具體步驟如下：

步驟1獲取鄰域個(gè)體的所有適應(yīng)值集合，建立空集合non_repeat_set，進(jìn)入步驟2。

步驟2遍歷所有鄰域個(gè)體的適應(yīng)值，若該適應(yīng)值在集合non_repeat_set中，則訪問(wèn)下一個(gè)個(gè)體適應(yīng)值；若該適應(yīng)值不在集合non_repeat_set中，則將其加入到該集合。遍歷完后進(jìn)入步驟3。

步驟3計(jì)算non_repeat_set的大小，該集合表示所有不重復(fù)的個(gè)體，若該集合小于鄰域大小的一半，則認(rèn)為鄰域多樣性差，進(jìn)入步驟4；否則，轉(zhuǎn)步驟5。

步驟4標(biāo)記適應(yīng)值不在集合non_repeat_set中的鄰域個(gè)體，用隨機(jī)生成的個(gè)體替換該鄰域個(gè)體。

步驟5遍歷鄰域中的個(gè)體，對(duì)當(dāng)前個(gè)體生成一個(gè)0到1范圍內(nèi)的隨機(jī)數(shù)，若大于局部搜索概率，則進(jìn)入步驟6；否則，對(duì)下一個(gè)個(gè)體進(jìn)行判斷。

步驟6計(jì)算當(dāng)前非支配解集中個(gè)體的擁擠度，隨機(jī)選擇擁擠度最大的一個(gè)個(gè)體與鄰域個(gè)體進(jìn)行交叉，交叉方式與2.2.3節(jié)中相同，返回適應(yīng)值更優(yōu)的一個(gè)個(gè)體作為新的鄰域個(gè)體。

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境

IMOEA/D算法在Intel Core i5 2.7 GHz CPU、16 GB RAM、Windows 10操作系統(tǒng)和Python編程環(huán)境下進(jìn)行計(jì)算。

3.2 實(shí)驗(yàn)數(shù)據(jù)

針對(duì)RHFSP-CBPM，結(jié)合冷拔生產(chǎn)的特征，設(shè)計(jì)算例集進(jìn)行實(shí)驗(yàn)，算例生成規(guī)則如表2所示，其中數(shù)量單位均為個(gè)，時(shí)間單位均為min，功率單位均為kW。

表2 算例表

3.3 實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證優(yōu)化模型的正確性和算法的優(yōu)越性，設(shè)計(jì)了如下5個(gè)實(shí)驗(yàn)：

(1)IMOEA/D參數(shù)優(yōu)化實(shí)驗(yàn)。設(shè)計(jì)正交試驗(yàn)確定算法參數(shù)。

(2)緩沖區(qū)大小對(duì)比實(shí)驗(yàn)。對(duì)比不同緩沖區(qū)大小的影響，確定連續(xù)式批處理機(jī)的合適緩沖區(qū)大小。

(3)工件等待時(shí)間對(duì)比實(shí)驗(yàn)。對(duì)比批次內(nèi)工件等待時(shí)間的不同計(jì)算方式，驗(yàn)證考慮批處理機(jī)容量約束解碼的有效性。

(4)算法策略驗(yàn)證實(shí)驗(yàn)。對(duì)比使用策略前后的算法對(duì)算例求解的效果，驗(yàn)證提出的策略的有效性。

(5)IMOEA/D性能驗(yàn)證實(shí)驗(yàn)。將設(shè)計(jì)的IMOEA/D與其他算法對(duì)比，驗(yàn)證IMOEA/D的優(yōu)越性。

3.4 實(shí)驗(yàn)結(jié)果

3.4.1 IMOEA/D參數(shù)優(yōu)化實(shí)驗(yàn)

IMOEA/D算法的參數(shù)對(duì)實(shí)驗(yàn)結(jié)果具有一定的影響，為了確定實(shí)驗(yàn)參數(shù)的大小，設(shè)計(jì)了如下的四因素三水平的正交試驗(yàn)。如表3所示，其中參數(shù)有：鄰域大小與種群大小的比例關(guān)系(T)、交叉概率(Pc)、變異概率(Pm)，以及局部搜索概率(Pl)。選取按照表2規(guī)則生成的第一個(gè)實(shí)驗(yàn)算例進(jìn)行正交試驗(yàn)，該算例有10個(gè)工件，6道工序，并且工件重入了1次，記為P10_6_1。

對(duì)比不同參數(shù)水平下的解的質(zhì)量，需要將一組非支配解轉(zhuǎn)化為一個(gè)綜合目標(biāo)值，計(jì)算綜合目標(biāo)值的計(jì)算方法詳見文獻(xiàn)[29]。對(duì)算例P10_6_1在不同參數(shù)水平下進(jìn)行求解，得到的正交試驗(yàn)結(jié)果如表3所示。

結(jié)合表3正交試驗(yàn)結(jié)果，IMOEA/D算法的參數(shù)設(shè)置如下：種群規(guī)模(N)100，迭代次數(shù)(S)50次，鄰域占比(T)為0.15，交叉概率(Pc)為0.9，變異概率(Pm)為0.2，局部搜索概率(Pl)為0.5。后續(xù)實(shí)驗(yàn)中IMOEA/D算法均使用上述參數(shù)設(shè)置。

表3 參數(shù)正交試驗(yàn)

3.4.2 緩沖區(qū)大小對(duì)比實(shí)驗(yàn)

在連續(xù)式退火爐的應(yīng)用場(chǎng)景中，其往往有傳送帶狀的前置緩沖區(qū)，來(lái)滿足工件連續(xù)進(jìn)入的需求。在現(xiàn)有考慮緩沖區(qū)大小的調(diào)度問(wèn)題研究中，一般將緩沖區(qū)大小設(shè)置為批處理機(jī)容量的倍數(shù)或者其他固定值，僅將其作為一個(gè)約束條件，而未考慮該緩沖區(qū)大小是否合適。緩沖區(qū)大小對(duì)比實(shí)驗(yàn)將緩沖區(qū)分為5個(gè)等級(jí)進(jìn)行對(duì)比，各等級(jí)緩沖區(qū)大小如表4所示，其中B是批處理機(jī)容量。

表4 緩沖區(qū)各等級(jí)大小

使用與3.4.1節(jié)中相同的算例P10_6_1進(jìn)行實(shí)驗(yàn)，在每種緩沖區(qū)等級(jí)下，取IMOEA/D算法運(yùn)行10次后得到的非支配解作為最終解。實(shí)驗(yàn)結(jié)果如圖10和圖11所示，在等級(jí)1的零緩沖約束下得到的調(diào)度方案，能耗和完工時(shí)間遠(yuǎn)大于另外4個(gè)等級(jí)。在實(shí)際生產(chǎn)中，除了少數(shù)工藝要求嚴(yán)格的零緩沖/等待約束，大部分情況下都是存在一定緩沖區(qū)的。在緩沖區(qū)等級(jí)為2和4時(shí)，得到的解具有較為良好的分布性，但是在整個(gè)解空間上，等級(jí)3和5得到的解更優(yōu)?？梢钥吹?，在緩沖區(qū)等級(jí)3下，緩沖區(qū)大小等于批處理機(jī)容量大小，此時(shí)得到的解與無(wú)限緩沖的最為接近，綜合表現(xiàn)較好，在圖11箱線圖的對(duì)比中，也可以看出等級(jí)3和5的分布最為接近。

緩沖區(qū)在生產(chǎn)過(guò)程中會(huì)占用一定的空間資源和生產(chǎn)資源，同時(shí)緩沖區(qū)的大小也會(huì)對(duì)調(diào)度的完工時(shí)間和能耗造成影響。在保證生產(chǎn)效率的同時(shí)，盡可能降低緩沖區(qū)的成本，能夠給企業(yè)帶來(lái)更大收益。實(shí)驗(yàn)結(jié)果表明，當(dāng)緩沖區(qū)大小等于批處理機(jī)容量大小時(shí)，調(diào)度方案的效果已經(jīng)接近無(wú)限緩沖的情況了，因此將緩沖區(qū)容量設(shè)置成批處理機(jī)容量大小較為合適。后續(xù)實(shí)驗(yàn)緩沖區(qū)大小均采用上述設(shè)置。

3.4.3 工件等待時(shí)間對(duì)比實(shí)驗(yàn)

除了2.2.2節(jié)解碼中提出的工件等待時(shí)間計(jì)算方式外，趙玉芳等[25]在單機(jī)連續(xù)型批調(diào)度問(wèn)題中，也提出了一個(gè)批次加工時(shí)間的計(jì)算公式，批次內(nèi)工件間的等待時(shí)間等于該批次加工時(shí)間除以批處理機(jī)容量。為了驗(yàn)證本文的計(jì)算方式的有效性，使用算例P10_6_1，分別在解碼中使用兩種計(jì)算方式進(jìn)行求解。實(shí)驗(yàn)結(jié)果如圖12所示，其中計(jì)算方式1使用了式(20)的計(jì)算公式，計(jì)算方式2使用了文獻(xiàn)[25]的公式。

3.4.4 算法策略驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證算法提出的策略的有效性，分別在完整算法策略、不使用多樣性判斷后的局部搜索和不使用多樣性判斷后的鄰域更新策略這3種情況下進(jìn)行對(duì)比實(shí)驗(yàn)。仍然使用P10_6_1算例作為測(cè)試算例，實(shí)驗(yàn)結(jié)果如圖13所示，在多樣性判斷中，若僅采用一種策略，得到的解較為接近，但是都明顯劣于采用二者結(jié)合的策略得到的解。在綜合使用兩種策略后，最終非支配解集的完工時(shí)間和能耗目標(biāo)都得到了優(yōu)化。

3.4.5 IMOEA/D性能驗(yàn)證實(shí)驗(yàn)

為了驗(yàn)證IMOEA/D的性能，選用MODE算法、MOPSO算法和經(jīng)典的多目標(biāo)算法NSGA-Ⅱ作為對(duì)比算法，其中MODE算法是文獻(xiàn)[34]提出的求解帶緩沖區(qū)批調(diào)度問(wèn)題的MODE算法，MOPSO算法是文獻(xiàn)[4]提出的求解可重入批調(diào)度問(wèn)題的V-NSPSO算法。分別使用4種算法求解表2生成的10個(gè)算例。

使用超體積(HV)指標(biāo)來(lái)比較不同算法的綜合性能，選用坐標(biāo)原點(diǎn)作為參考點(diǎn)，將Pareto集歸一化后，計(jì)算Pareto集與參考點(diǎn)圍成的區(qū)域體積大小，得到HV值。四種算法的HV指標(biāo)對(duì)比結(jié)果如表5所示，其中加粗的表示最優(yōu)結(jié)果，IMOEA/D算法在大部分算例中表現(xiàn)出了較好的綜合性能。

表5 算法HV指標(biāo)對(duì)比結(jié)果

使用世代距離(GD)指標(biāo)比較不同算法的收斂性，選用參考點(diǎn)坐標(biāo)原點(diǎn)作為參考點(diǎn)，將Pareto集歸一化后，計(jì)算Pareto集與參考點(diǎn)的平均最小距離，平均距離越小的收斂性越好。GD指標(biāo)對(duì)比結(jié)果如表6所示，IMOEA/D算法在大部分算例中都表現(xiàn)出最好的收斂性。

表6 算法GD指標(biāo)對(duì)比結(jié)果

使用反轉(zhuǎn)世代距離(IGD)指標(biāo)比較不同算法得到的解的多樣性，計(jì)算每個(gè)參考點(diǎn)到最近的解的距離的平均值，IGD值越小，說(shuō)明解的多樣性越好。由于問(wèn)題沒(méi)有已知的最優(yōu)Pareto前沿，因此采用ISHIBUCHI等[35]提出的方法，通過(guò)分解的方式生成一組Pareto前沿面，來(lái)輔助計(jì)算IGD指標(biāo)。最終得到的IGD指標(biāo)對(duì)比結(jié)果如表7所示，IMOEA/D算法在大部分算例都表現(xiàn)出較好的多樣性。

表7 算法IGD指標(biāo)對(duì)比結(jié)果

將IMOEA/D依次與另外3個(gè)算法的各指標(biāo)計(jì)算值進(jìn)行Wilcoxon符號(hào)秩檢驗(yàn)，設(shè)置置信水平α=0.05，若所求得P值小于其給定的顯著性水平，則拒絕零假設(shè)，H值為1。Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果如表8所示，檢驗(yàn)結(jié)果表明，IMOEA/D求解10個(gè)算例的各指標(biāo)結(jié)果與另外3個(gè)算法有顯著差異，IMOEA/D得到的Pareto解集在大部分情況下明顯優(yōu)于另外3種算法。

表8 Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果

為了直觀展現(xiàn)調(diào)度結(jié)果，使用IMOEA/D求解算例P10_6_1得到的一個(gè)Pareto解的甘特圖如圖14所示。圖中機(jī)器12-15是冷拔階段的冷拔機(jī)，機(jī)器16是批處理階段的連續(xù)式批處理機(jī)。每個(gè)矩形色塊代表一個(gè)工序在機(jī)器上加工，色塊內(nèi)的數(shù)字表示對(duì)應(yīng)的工件-工序編號(hào)。在整個(gè)調(diào)度過(guò)程的離散加工階段，冷拔機(jī)上工件的加工時(shí)間占據(jù)了大部分的完工時(shí)間；而在批加工階段，工件在批處理機(jī)上依次進(jìn)入和離開?？梢钥吹剑{(diào)度結(jié)果中，連續(xù)式批處理機(jī)的利用效率很高，算例P10_6_1的批處理機(jī)容量為4，甘特圖中每一個(gè)批次都達(dá)到了滿批，并且沒(méi)有違背緩沖區(qū)和批處理機(jī)容量的約束。根據(jù)上述實(shí)驗(yàn)對(duì)比結(jié)果可知，所提出的IMOEA/D算法能夠有效地求解RHFSP-CBPM問(wèn)題。

4 結(jié)束語(yǔ)

本文將無(wú)縫鋼管的冷拔生產(chǎn)過(guò)程抽象為帶連續(xù)式批處理機(jī)的可重入混合流水車間調(diào)度問(wèn)題。首先，綜合考慮緩沖區(qū)和批處理機(jī)容量等約束條件，為該問(wèn)題建立了數(shù)學(xué)優(yōu)化模型，以優(yōu)化完工時(shí)間和批處理機(jī)能耗。然后，設(shè)計(jì)了IMOEA/D作為多目標(biāo)優(yōu)化算法進(jìn)行求解。根據(jù)問(wèn)題的可重入特征設(shè)計(jì)了基于工序的編碼，考慮緩沖區(qū)大小約束和批處理機(jī)容量約束設(shè)計(jì)了解碼算法，開發(fā)了針對(duì)染色體的交叉變異算子，并根據(jù)鄰域多樣性設(shè)計(jì)了局部搜索和多樣性增強(qiáng)策略。最后，進(jìn)行了5個(gè)實(shí)驗(yàn)。通過(guò)正交試驗(yàn)確定了算法的最佳參數(shù)設(shè)置；通過(guò)緩沖區(qū)大小對(duì)比實(shí)驗(yàn)確定了批處理機(jī)緩沖區(qū)的合適大小，當(dāng)批處理機(jī)緩沖區(qū)大小等于批處理機(jī)容量，能夠在保證得到較好調(diào)度方案的同時(shí)節(jié)約緩沖區(qū)資源；通過(guò)工件等待時(shí)間對(duì)比實(shí)驗(yàn)表明了本文設(shè)計(jì)的等待時(shí)間計(jì)算方式的有效性，在滿足批處理機(jī)容量的情況下，工件能夠更及時(shí)地進(jìn)入批處理機(jī)，進(jìn)而減少批處理機(jī)能耗；通過(guò)算法策略驗(yàn)證實(shí)驗(yàn)，證明了所提算法改進(jìn)策略的有效性。在最后一個(gè)實(shí)驗(yàn)中，通過(guò)與不同算法的比較，驗(yàn)證了IMOEA/D相對(duì)其他算法的優(yōu)越性，所提出的IMOEA/D能夠有效求解RHFSP-CBPM。

在進(jìn)一步的研究中，可以考慮其余工藝階段的工件準(zhǔn)備時(shí)間和緩沖區(qū)大小約束，以及更有效的智能算法的開發(fā)。