唐紅濤，張 緩

(武漢理工大學(xué) 1.機(jī)電工程學(xué)院；2.湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430070)

混合流水車間調(diào)度問題(hybrid flow-shop scheduling problem,HFSP)[1]是一種最基本的調(diào)度問題。在HFSP問題中，加工機(jī)器的選擇具有一定的柔性，這使問題規(guī)模和求解難度較一般的流水車間調(diào)度問題更大，已被證明是NP-hard問題[2]。

砂型鑄造作為高能耗高污染的制造業(yè)之一[3]，由于生產(chǎn)過程的復(fù)雜性，其相關(guān)研究較少。Bewoor等[4]將鑄造車間調(diào)度問題描述為無等待約束的流水車間調(diào)度問題。鑄造生產(chǎn)過程中材料和動力消耗大，工藝過程復(fù)雜，所需設(shè)備品種繁多。高溫、高塵、高噪的生產(chǎn)環(huán)境直接影響車間工人的身體健康，因此對鑄造車間的粉塵、噪聲進(jìn)行控制，盡可能節(jié)約能源的消耗，完成節(jié)能減排的目標(biāo)是現(xiàn)代鑄造業(yè)生產(chǎn)的主要任務(wù)之一[5]。Wu等[6]根據(jù)機(jī)器運(yùn)行狀態(tài)的差異性，提出一種計(jì)算不同狀態(tài)下機(jī)器能耗的能量消耗模型。Kim等[7]提出能耗強(qiáng)度分解的方法對碳排放進(jìn)行分析，構(gòu)建鑄造過程中CO2排放計(jì)算公式。鄭軍等[8]使用砂型鑄造生產(chǎn)過程的碳效率模型和評價方法對碳排放量在一定標(biāo)準(zhǔn)內(nèi)進(jìn)行評估。尹瑞雪等[9]利用鑄造生產(chǎn)系統(tǒng)碳排放估算與評價邊界的方法，通過碳排放評估函數(shù)計(jì)算砂型鑄造生產(chǎn)過程中的碳排放量。機(jī)械制造過程都伴隨著噪聲。最具有危害性的工業(yè)噪音一般可分為4類：連續(xù)的機(jī)械噪音、由高速重復(fù)的動作產(chǎn)生的強(qiáng)烈的聲音、流動引起的噪音和機(jī)器加工時對工件的沖壓撞擊產(chǎn)生的噪音。與熔爐相關(guān)的燃燒過程，與沖孔過程，電機(jī)、發(fā)電機(jī)和其他機(jī)電設(shè)備相關(guān)的沖擊噪聲等都是工業(yè)環(huán)境產(chǎn)生噪聲的振動源的典型實(shí)例[10]。Lu等[11]考慮噪聲污染以及更常見的能源消耗和生產(chǎn)率問題，建立多目標(biāo)無線傳感器網(wǎng)絡(luò)的數(shù)學(xué)模型，用于解決焊接車間調(diào)度問題。Lu等[12]針對HFS車間生產(chǎn)效率低、能耗高和噪聲污染大的情形，構(gòu)建一個多目標(biāo)混合整數(shù)規(guī)劃模型，并提出一種量化節(jié)能降噪策略以求解該模型。

由于生產(chǎn)過程的復(fù)雜性，砂型鑄造綠色可持續(xù)生產(chǎn)的研究較少，將噪聲這一污染作為優(yōu)化目標(biāo)的探索更少。因此，本文建立以最大完工時間、碳排放以及噪聲為優(yōu)化目標(biāo)的混合流水車間調(diào)度模型，并提出一種混合離散多目標(biāo)帝國競爭算法(hybrid discrete multi-objective imperial competition algorithm,HDMICA)對模型進(jìn)行求解。運(yùn)用一種新的初始化策略改善算法的性能，采用新途徑進(jìn)行帝國競爭，合理均衡帝國勢力值。最后通過大量實(shí)驗(yàn)驗(yàn)證所提算法的有效性。

1 問題研究及數(shù)學(xué)模型構(gòu)建

1.1 問題描述

本文研究基于綠色的混合流水車間調(diào)度問題。該問題描述如下。n個工件J={J1,J2,···,Jn}需要在m個加工資源M={M1,M2,···,Mm}上加工，任意工件Ji都有ni道工序Oi=，且每個工件的工序具有相同的加工順序，每道工序都有一個加工資源集Mij=，Mij?M，工件的每道工序可以由Mij中的任意一個加工資源加工。模型建立之前作出如下假設(shè)。

1) 工件加工之前所有機(jī)器均已開機(jī)并處于空閑狀態(tài)；

2) 每個工件的工序加工順序不可改變；

3) 任一時刻，工件的每道工序最多只能在一個加工資源上加工，且每個加工資源任一時刻最多只能加工一道工序；

4) 加工過程不允許中斷，每個工件在加工時必須連續(xù)加工。

1.2 模型構(gòu)建

1) 符號與參數(shù)。

n為待加工工件總數(shù)；m為總的加工資源數(shù)；s為加工階段數(shù)，即工件的工序總數(shù)；i,i'為工件序號，i,i′=1,2,···,n；j,j'為工序序號，j,j′=1,2,···,s；k為加工資源序號，k=1,2,···,m；Oij為工件i的第j道工序；Mij為工件i階段j可選加工資源集；Cijk為工件i的階段j在加工資源k上的加工時間；Stij為工件i的階段j開始加工的時間；Etij為工件i的階段j加工結(jié)束時間；Ci為工件i的最早完成時間；Pk為加工資源的工作功率；Be為電力標(biāo)準(zhǔn)折煤系數(shù)，0.122 9 kgce/(kW·h)，kgce是能量消耗量；EFe為電能的碳排放系數(shù)，4.035 kgCO2e/kgce；N為一個足夠大的正數(shù)。

2) 決策變量。

3) 目標(biāo)函數(shù)。

最大完工時間是指從一批訂單里的第1個工件的第1道工序加工開始，直至最后一個工件的最后一道工序加工完成所經(jīng)歷的時間。

碳排放量主要是加工設(shè)備加工時所產(chǎn)生的碳排放量。為了便于計(jì)算，考察國民經(jīng)濟(jì)各部門能源消耗及利用情況，常采用標(biāo)準(zhǔn)煤這一標(biāo)準(zhǔn)進(jìn)行折算，標(biāo)準(zhǔn)煤指的是熱值為7 000 kcal/kg的煤炭，碳排放可以引入碳排放系數(shù)由標(biāo)準(zhǔn)煤進(jìn)行計(jì)算，根據(jù)IPCC的假定，能源的碳排放系數(shù)是恒定的[13]。

聲音的大小一般可以用聲壓和聲壓級、聲強(qiáng)和聲強(qiáng)級、聲功率和聲功率等級等物理量來描述，通常使用2個物理量的比值——聲壓級，即分貝(dB)將聲音進(jìn)行量化，描述作為分子的物理量相對于分母這一基準(zhǔn)的大小。在鑄造車間，噪聲主要來源于機(jī)器運(yùn)行產(chǎn)生的噪聲、工件加工時工件和機(jī)器接觸產(chǎn)生的噪聲，對于這些結(jié)構(gòu)噪聲[14]，當(dāng)機(jī)器以一定的功率進(jìn)行工作時，噪聲以平穩(wěn)的寬頻帶進(jìn)行輻射。根據(jù)《工業(yè)企業(yè)廠界環(huán)境噪聲排放標(biāo)準(zhǔn)》 ，本文采用A級聲壓對加工噪聲的輻射進(jìn)行評價[15]，等效聲級可以表示為

其中，li為t時刻的瞬時A聲級；T為測量時間段。當(dāng)機(jī)器以一定功率工作時，可以認(rèn)為各階段的輻射聲級是確定且不變的。因此，聲效等級又可以表示為

其中，li表示時間段i的瞬時A聲級；Ti為時間段i。根據(jù)本文研究的問題，考慮到由各機(jī)器產(chǎn)生的噪聲來源不同導(dǎo)致瞬時聲壓級有所差異，針對各機(jī)器運(yùn)作產(chǎn)生的不同聲壓級，整個加工過程中所產(chǎn)生的噪聲為

式(6)和式(7)表示每個工件的工藝路線不可改變；式(8)和式(9)表示同一時刻一臺機(jī)器只能加工一道工序；式(10)限制每道工序只能在一臺機(jī)器上加工；式(11)表明每道工序一旦開始就不允許中斷。

2 算法設(shè)計(jì)

帝國競爭算法(imperial competition algorithm,ICA)是一種受帝國競爭行為啟發(fā)的智能優(yōu)化算法[16]。該算法具有較強(qiáng)的全局搜索性能，而且算法利用殖民地向帝國主義國家移動進(jìn)行局部搜索保證算法具有較強(qiáng)的局部搜索能力，同時帝國競爭操作使帝國內(nèi)的殖民地向其他帝國移動，突破了原來的搜索范圍，提高種群多樣性。此外，該算法具有收斂速度快、精度高等優(yōu)點(diǎn)，近幾年被廣泛應(yīng)用到車間調(diào)度問題研究中[17-18]。原始的ICA主要通過初始化帝國、殖民地同化及革命和帝國競爭實(shí)現(xiàn)種群的迭代尋優(yōu)。

2.1 編碼與解碼

針對混合流水車間調(diào)度這一離散空間的組合優(yōu)化問題，本文基于ROV的編碼方式生成第1階段的解決方案。首先，生成矢量數(shù)組X={x1,x2,···,xn}，x為[?1,1]中的隨機(jī)數(shù)，n為工件的總數(shù)，加工工件時依據(jù)x的大小從小到大依次進(jìn)行加工。若有6個待加工工件，則生成一個6維數(shù)組X={0.12,?0.78,?0.52,0.17,0.62,?0.19}，可以求得該矢量數(shù)組對應(yīng)的加工順序?yàn)?-3-6-1-4-5。這種編碼機(jī)制極大地縮小解的搜索空間，有利于算法快速尋優(yōu)，因此廣泛應(yīng)用于流水車間調(diào)度問題中。

對于機(jī)器選擇以及后續(xù)階段的加工順序通過解碼確定。解碼是將矢量數(shù)組映射為實(shí)際問題的解決方案。首先，針對第1階段的矢量數(shù)組，解碼可獲得工件加工順序，根據(jù)工序的可選加工資源集依次進(jìn)行資源分配。其次，計(jì)算第1階段加工資源的釋放時間，并與工件釋放時間相比較，時間差距較小的加工資源具有優(yōu)先選擇權(quán)。如果出現(xiàn)多個差距較小的加工資源，則隨機(jī)選擇一個加工資源進(jìn)行加工。若加工資源從未加工過工件，則認(rèn)為該加工資源的釋放時間為0；否則為上個工件在此加工資源上的加工完成時間。若工件從未被加工過，則工件的釋放時間為0。對于后續(xù)階段，將工件的釋放時間按升序排序依次進(jìn)行加工，加工資源延續(xù)第1階段的方式進(jìn)行排序。

2.2 基于混沌反向?qū)W習(xí)策略的種群初始化

初始化種群是算法尋優(yōu)的第1步，其質(zhì)量和多樣性將直接影響算法的性能。本文采用基于混沌反向?qū)W習(xí)的初始化策略?；诨煦绶聪?qū)W習(xí)的初始化策略利用混沌運(yùn)動隨機(jī)性及遍歷性的特點(diǎn)對當(dāng)前解進(jìn)行反向搜索，進(jìn)而生成多樣性高質(zhì)量的初始種群。具體優(yōu)化策略如下。

步驟1構(gòu)建種群規(guī)模為N，維度為D的混沌序列Z={Zd,d=1,2,···,D}，Zd={Zid,i=1,2,···,N}，混沌映射函數(shù)為

步驟2通過混沌序列映射到解空間生成初始化種群X={Xi,i=1,2,···,N}，Xi={Xid,d=1,2,···,D}，Xid可以通過混沌映射函數(shù)表達(dá)式(13)得到。

其中，Xmax和Xmin分別為個體位置序列隨機(jī)值的上、下界。

步驟3計(jì)算初始種群X的反向種群OX。

步驟4將反向解和初始解進(jìn)行比較，若反向解優(yōu)于初始解，則替換初始解形成新的種群X。

2.3 初始化帝國

本文所研究問題為多目標(biāo)優(yōu)化，帝國的成本計(jì)算更加復(fù)雜。為避免計(jì)算的復(fù)雜度，給出一種簡化的帝國初始化機(jī)制，具體構(gòu)建過程如下。

步驟1對大小為N的種群P進(jìn)行帕累托非支配解排序，得到大小為η的非支配解集π；

步驟2判斷η和帝國主義國家的個數(shù)Nemp的大小關(guān)系。若η

步驟3隨機(jī)選擇π中的Nemp個個體作為帝國主義國家，由式(15)可計(jì)算每個帝國分配的殖民地數(shù)，最后一個的殖民地數(shù)可由式(16)得出。

步驟4將p中剩余的N?Nemp個個體的層次Rank按升序排序，并交替分配給各帝國。

2.4 同化及革命

同化是指使殖民地向帝國主義國家移動，通過殖民地和帝國主義國家不斷進(jìn)行文化交流，實(shí)現(xiàn)優(yōu)異個體帶動弱勢群體的發(fā)展，進(jìn)而提高帝國的整體成本。通常通過殖民地和帝國主義國家的交叉來實(shí)現(xiàn)[19]。本文采用POX交叉來實(shí)現(xiàn)殖民地的進(jìn)化，交叉示意圖如圖1所示，將工件集Jobset={J1,J2,J3,···,Jn}隨機(jī)分成兩部分：Jobset1和Jobset2，將父代P1中屬于Jobset1的工件保持原位置不變復(fù)制到子代C中，并把父代P2中屬于Jobset2的工件保持順序不變依次添加到子代C的空閑位置中。

圖1 POX交叉示意圖Figure 1 Schematic diagram of POX crossover

帝國革命類似于遺傳算法(genetic algorithm,GA)，為了提高種群的多樣性產(chǎn)生某種不可預(yù)測的變異，主要對殖民地局部搜索。一般的帝國革命是根據(jù)革命率隨機(jī)選擇殖民地進(jìn)行變異操作。這種做法忽視了殖民地質(zhì)量的差異性，若質(zhì)量較差的殖民地發(fā)生革命，新個體的質(zhì)量可能難以達(dá)到革命的目的。因此，本文依據(jù)Pareto算法對殖民地進(jìn)行非支配解排序，優(yōu)先選擇第1前沿解集發(fā)起革命。設(shè)計(jì)3種鄰域結(jié)構(gòu)對個體進(jìn)行局部搜索，獲取新的個體。3種鄰域結(jié)構(gòu)如圖2所示。

圖2 鄰域結(jié)構(gòu)示意圖Figure 2 Schematic diagram of neighborhood structure

1) NS1。隨機(jī)生成兩個位置，并反轉(zhuǎn)兩個位置間的工序碼。

2) NS2?；陉P(guān)鍵路徑的交換。關(guān)鍵路徑是指從操作開始到操作結(jié)束的最長加工路線，它決定調(diào)度的完成時間。本文采用Nowicki等[20]提出的N5鄰域結(jié)構(gòu)，隨機(jī)選擇一個關(guān)鍵路徑，并在每個關(guān)鍵塊中交換前兩個(和后兩個)操作來實(shí)現(xiàn)。

3) NS3。工序插入操作，從工序碼隨機(jī)選擇兩道工序a和b，并將工序b插到工序a之前。

帝國主義國家作為精英個體，其相互之間的學(xué)習(xí)將有更大可能產(chǎn)生優(yōu)秀個體。針對這一特性，隨機(jī)選擇帝國主義國家進(jìn)行RPX交叉?？梢悦枋鰹樯砷L度為工序總數(shù)的向量R，R中的每個元素都是[0,1]中的隨機(jī)數(shù)，并與機(jī)器碼呈一一對應(yīng)的關(guān)系。首先，將父代P1的工序碼復(fù)制到子代C中，計(jì)算pf值，并將P1中對應(yīng)的R中元素大于pf的機(jī)器碼保持順序及位置不變復(fù)制到C中。記錄剩余機(jī)器碼的位置索引，并將父代P2中和工序段對應(yīng)位置的機(jī)器碼復(fù)制到C中的空缺位置。

其中，It為當(dāng)前迭代數(shù)；Max It為總迭代次數(shù)；pfmax和pfmin分別為自適應(yīng)度值的最大值和最小值。圖3為pf=0.6時的交叉示意圖。

圖3 RPX交叉示意圖Figure 3 Schematic diagram of RPX crossover

2.5 帝國競爭

帝國競爭就是通過計(jì)算國家的總質(zhì)量，勢力最弱的國家將被其他國家一步步按一定概率吞并，越是強(qiáng)大的國家概率值越大，吞并殖民地的可能性越大，直至弱勢國家的殖民地變?yōu)?，該帝國主義國家也被占領(lǐng)，至此整個國家消亡。為實(shí)現(xiàn)帝國競爭需要計(jì)算國家的總成本，個體i的成本值ci為

其中，Ranki為通過非支配解排序生成的個體i的Rank值；disti為解i的擁擠度距離，由個體i的目標(biāo)上相鄰兩個個體的目標(biāo)值的和組成；表示與目標(biāo)k相鄰的兩目標(biāo)值之間的距離；總的目標(biāo)數(shù)為m；表示Rank值為Ranki的集合，μ為一個接近于0的正數(shù)，目的是防止分母為0。

所以帝國k的總成本TCk=ck+ξmean{Cost(colonies of empirek)}，其中，ξ為系數(shù)，且ξ=0.1。將總成本歸一化NTCk=2max{TC}?TCk，最大帝國成本乘以2的目的是防止帝國k的勢力為0，將帝國間的勢力差距大大減小，使每個帝國都有可能成為競爭中的勝利者，使帝國競爭更加充分。帝國k的勢力Epk為

基于以上描述，本文改進(jìn)的算法流程如圖4所示。

圖4 算法流程Figure 4 Algorithm flow chart

3 仿真結(jié)果與分析

3.1 參數(shù)確定

針對本文研究的混合流水車間調(diào)度問題，結(jié)合問題模型實(shí)際情況設(shè)置參數(shù)值，并參考Carlier算例[21]設(shè)計(jì)24個測試算例。其中，工件數(shù)n∈{10,15,30}，階段s∈{5,10}，每個算例由3個字符和3個整數(shù)表示，“J”表示工件，“c”表示加工階段，第3個字符表示階段機(jī)器布局方式，“a”指中間階段一臺加工機(jī)器，其余階段有3臺加工和機(jī)器；“b”指第1階段有一臺機(jī)器，其他階段3臺機(jī)器；“c”是中間階段有2臺加工機(jī)器，其他階段3臺機(jī)器；“d”指每個階段都是3臺機(jī)器。例如，“J10c5a1”表示該問題有10個工件，5個加工階段，中間階段一臺加工機(jī)器的第1種布局，其余階段有3臺加工和機(jī)器。各階段加工資源的加工時間在區(qū)間[3,20]上服從均勻分布，各階段加工資源單位時間能耗在[0.3,3]上均勻產(chǎn)生，各階段加工資源產(chǎn)生的噪聲在區(qū)間[70,90]上均勻產(chǎn)生。當(dāng)階段數(shù)為5時，工序加工機(jī)器編號在{1,9}之間選擇，第10臺機(jī)器對應(yīng)瓶頸工序；當(dāng)階段數(shù)為10時，工序加工機(jī)器編號在{1,19}之間選擇，第20臺機(jī)器對應(yīng)瓶頸工序。

針對多目標(biāo)問題采用3種評價標(biāo)準(zhǔn)[22]對非支配解的質(zhì)量以及多樣性進(jìn)行評價，具體方法如下。

1) 平均理想距離(MID)，顯示非支配解與理想點(diǎn)(0,0,0)之間的距離。該值越小表示非支配解與理想值越接近，結(jié)果越好。

其中，ci=是目標(biāo)值平方和的平方根；n為非支配解的數(shù)量。

2) SNS，是對非支配解多樣性地衡量，SNS越大表示非支配解的多樣性越豐富，解的質(zhì)量越好。

3) RAS，同時達(dá)到三目標(biāo)值的概率。

其中，fi=min{f1i,f2i,f3i}，RAS越小解的質(zhì)量越好。

影響HDMICA算法性能的參數(shù)主要有國家總數(shù)N、帝國主義國家數(shù)Nemp、殖民地革命概率的閾值p和迭代次數(shù)Max It。經(jīng)大量實(shí)驗(yàn)可確定，當(dāng)殖民國家數(shù)Nemp占國家總數(shù)N的10%～20%之間時，算法性能最好。通過正交試驗(yàn)可確定，當(dāng)種群大小N=100，帝國主義國家數(shù)Nemp=10，殖民地革命概率p=0.98，迭代Max It=150次時為算法的最優(yōu)參數(shù)。

3.2 算法對比

為驗(yàn)證所提算法的有效性，選擇經(jīng)典算法NSGAII、DPSO以及MODVOA與之進(jìn)行對比。為保證各算法結(jié)果對比的有效性，所有實(shí)驗(yàn)的運(yùn)行環(huán)境均為2.7 GHz CPU，8 G內(nèi)存，64位Windows 7系統(tǒng)計(jì)算機(jī)，編程環(huán)境為Matlab 2016。為避免結(jié)果的隨機(jī)性，每個算例均獨(dú)立運(yùn)行30次，計(jì)算目標(biāo)值的均值以及平均運(yùn)行時間驗(yàn)證算法的求解質(zhì)量，計(jì)算3種評價指標(biāo)MID、SNS、RAS的均值驗(yàn)證非支配解的質(zhì)量。24個算例的對比結(jié)果如表1～3所示。

表1 算例仿真結(jié)果對比Table 1 Comparison table of simulation results of calculation examples

表1和表2分別給出24個算例仿真結(jié)果以及運(yùn)行時間，從目標(biāo)值最小化最大完工時間、最小化碳排放以及最小噪聲值來看，幾乎在所有算例中由HDMICA算法所求結(jié)果明顯優(yōu)于其他算法所求結(jié)果，且所提算法運(yùn)行時間同對比算法相差無幾，綜合分析所提算法具有明顯的優(yōu)越性。由表3可以看出HDMICA雖無法做到所有指標(biāo)最優(yōu)，但是相較于其他3種算法從HDMICA的MID以及RAS的大小可以看出，由HDMICA所求得的非支配解能夠同時保證3個目標(biāo)均接近全局最優(yōu)，最優(yōu)解最接近全局最優(yōu)解，算法在收斂性以及解的質(zhì)量的性能優(yōu)于其他算法。但是SNS值一般，非支配解的多樣性沒有明顯優(yōu)勢?？傮w來看，所提算法相較于其他3種算法具有更強(qiáng)的優(yōu)越性。

表2 算例仿真運(yùn)行時間Table 2 Simulation running timetable of the calculation examples

表3 算例仿真評價指標(biāo)對比Table 3 Comparison table of simulation evaluation indicators for calculation examples

以算例“J15c10d1”為例，圖5為4種算法所求Pareto第1前沿的目標(biāo)分布對比圖。從圖5中可以看出，由HDMICA求得的非支配解分布在靠近坐標(biāo)最小值的一側(cè)，解的質(zhì)量明顯優(yōu)于其他算法。

圖5 Pareto第1前沿分布圖Figure 5 Distribution of Pareto first frontier

圖6是從HDMICA所求非支配解中選擇的擁擠度距離最大的一個解決方案的甘特圖。圖中矩形的每種顏色表示一個工件，數(shù)字表示加工階段，例如1003可以描述為工件J10的第3個加工階段。該解決方案的目標(biāo)值為加工時間157 h，碳排放量為1 009.90 kgCO2e，噪聲為80.03 dB。

圖6 算例J15c10d1調(diào)度甘特圖Figure 6 Example J15c10d1 scheduling Gantt chart

4 結(jié)束語

本文以綠色可持續(xù)為理論，基于混合流水車間調(diào)度問題，建立多目標(biāo)數(shù)學(xué)模型，并設(shè)計(jì)了一種混合離散多目標(biāo)帝國競爭算法進(jìn)行求解。最后以24種標(biāo)準(zhǔn)案例證實(shí)算法的可行性。在未來的研究中可以對算法求解方面更加優(yōu)化，尋找更加高質(zhì)量有效的初始化方法，并同多種經(jīng)典算法進(jìn)行對比，而且可以考慮人的行為效應(yīng)對模型的影響，使模型更加貼近實(shí)際生產(chǎn)。對于綠色調(diào)度，本文只考慮碳排放以及噪聲兩個因素，在實(shí)際的鑄造生產(chǎn)中會產(chǎn)生大量的廢渣廢氣，以后可以在此方向深入研究。