周炳海， 劉文龍

(同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804)

符號(hào)說(shuō)明:

CD—單位時(shí)間延遲交貨成本

CI—單位時(shí)間庫(kù)存成本

Eijk—工件i在第j個(gè)加工階段機(jī)器k上的能耗

Ejk—第j個(gè)加工階段第k臺(tái)機(jī)器的能耗

pi—工件i的總體加權(quán)交貨懲罰

Pjk—第j個(gè)加工階段第k臺(tái)機(jī)器的功率

Pijk—工件i所在第j個(gè)加工階段第k臺(tái)機(jī)器的功率

tjk—第j個(gè)加工階段第k臺(tái)機(jī)器耗時(shí)

tiljk—第j個(gè)加工階段第k臺(tái)機(jī)器上工件l正好排在工件i后的加工時(shí)間

πjk—第j個(gè)加工階段第k臺(tái)機(jī)器上被指派的加工任務(wù)集合，πjk={πjk(1),πjk(2),…,πjk(njk)}

σπjk(r-1)πjk(r)—當(dāng)σπjk(r-1)πjk(r)=1時(shí)，表示第j個(gè)加工階段第k臺(tái)機(jī)器上被指派的第(r-1)和第r個(gè)加工任務(wù)中執(zhí)行1次開關(guān)機(jī)

φjkir—當(dāng)φjkir=1時(shí)，表示工件i在第j個(gè)加工階段第k臺(tái)機(jī)器上被指派的加工任務(wù)集合中排第r位

上標(biāo)

idel—閑時(shí)

off—關(guān)機(jī)

on—開機(jī)

pro—加工

set—換模

混合流水線調(diào)度問(wèn)題(HFSP)是傳統(tǒng)流水線調(diào)度問(wèn)題的一種推廣，具有很強(qiáng)的工程背景，廣泛存在于化工、汽車、紡織、半導(dǎo)體等領(lǐng)域.HFSP同時(shí)具有流水線作業(yè)和并行機(jī)兩者的綜合特征：工藝流程復(fù)雜、不確定性大、求解調(diào)度問(wèn)題難度高，在數(shù)學(xué)領(lǐng)域?qū)儆诜谴_定性多項(xiàng)式(NP-hard)問(wèn)題.因此，研究HFSP具有重要的學(xué)術(shù)意義和應(yīng)用價(jià)值[1].

在現(xiàn)實(shí)環(huán)境之中，由于人為因素和市場(chǎng)波動(dòng)，HFSP 的生產(chǎn)參數(shù)往往是不確定的，可以通過(guò)模糊集理論進(jìn)行描述[2].Hong等[3-4]首次將離散模糊概念從流水線系統(tǒng)推廣應(yīng)用于研究HFSP問(wèn)題，并在此后繼續(xù)推廣到了連續(xù)模糊領(lǐng)域.Pinedo等[5]提出與工件加工次序相關(guān)的換模時(shí)間可能會(huì)占據(jù)生產(chǎn)中機(jī)器20%的有效工作時(shí)間.

近年來(lái)，受到全球變暖和高環(huán)保要求等因素的影響[6]，耗能占全國(guó)可消費(fèi)能源總量 72.8%[7]的制造業(yè)開始集中關(guān)注如何在提升生產(chǎn)效率與減少能源消耗之間尋求一個(gè)平衡點(diǎn)，以達(dá)到綠色生產(chǎn)的目標(biāo).相關(guān)研究人員開始將研究?jī)?nèi)容聚焦于具有節(jié)能意識(shí)的調(diào)度目標(biāo)上[8].Dai等[9]針對(duì)HFSP提出一個(gè)節(jié)能模型，可以同時(shí)優(yōu)化最大完工時(shí)間和能源消耗.Luo等[10]在此研究基礎(chǔ)上提出電價(jià)變動(dòng)模型，基于高低電價(jià)優(yōu)化電力成本.然而，目前對(duì)于考慮能耗的混合流水線在生產(chǎn)中的不確定性及與工件加工次序相關(guān)的換模時(shí)間約束問(wèn)題的相關(guān)研究較少，缺乏可以參考的研究依據(jù).

因此，本文以最小化系統(tǒng)能耗和準(zhǔn)時(shí)交貨懲罰作為雙優(yōu)化目標(biāo)，使用模糊數(shù)描述加工時(shí)間和交貨期.同時(shí)，考慮換模時(shí)間與工件加工次序相關(guān)及并行機(jī)不相關(guān)兩種約束，對(duì)HFSP開展研究.最后，通過(guò)理論分析和數(shù)值實(shí)驗(yàn)驗(yàn)證改進(jìn)型雙目標(biāo)差分進(jìn)化算法的可行性和有效性.

1 問(wèn)題描述

同時(shí)考慮換模時(shí)間與工件次序相關(guān)及并行機(jī)不相關(guān)兩種約束的HFSP可描述如下：n個(gè)工件在流水線上進(jìn)行s個(gè)階段的加工，每個(gè)階段至少有1臺(tái)機(jī)器且至少有1個(gè)階段存在并行機(jī)；同一階段的各機(jī)器加工同一工件所需的加工時(shí)間不同且互不相關(guān)，所需的換模時(shí)間與加工的上一個(gè)工件種類相關(guān)；在每一階段，各工件均要在其中任意1臺(tái)機(jī)器上完成1道工序.已知工件各道工序在各機(jī)器上的處理時(shí)間，要求確定所有工件的排序以及在每個(gè)階段機(jī)器的分配情況，使得某種調(diào)度指標(biāo)最小[1].HFSP 示意圖如圖1所示，其中ms表示階段s并行機(jī)數(shù)量.為了更加有效地描述HFSP，現(xiàn)做如下假設(shè)：① 工件的加工一旦開始不可中斷；② 1臺(tái)機(jī)器同一時(shí)刻只能加工1個(gè)工件；③ 1個(gè)工件同一時(shí)刻只能在1臺(tái)機(jī)器上加工；④ 工件可在每階段的任意機(jī)器上加工.

圖1 HFSP示意圖Fig.1 Illustration of HFSP

根據(jù)問(wèn)題描述和問(wèn)題假設(shè)對(duì)系統(tǒng)問(wèn)題的建模如下：

minF=(f1,f2)

(1)

(2)

(3)

式中：

(4)

(td2i-tCi)/(td2i-td1i),tCi≤td1i1-(tCi-td1i)/(td2i-td1i),td1i≤tCi≤td2i1,td2i≤tCi≤td3i(tCi-td3i)/(td4i-td3i),td3i≤tCi≤td4i (tCi-td3i)/(td4i-td3i),td4i≤tCiì?í?????????

(5)

(6)

(7)

(8)

(9)

σπjk(r-1)πjk(r)=

(10)

(11)

(12)

(13)

s.t.

(14)

(15)

(16)

(17)

(18)

(19)

l=1,2,…,ni=1,2,…,nj=1,2,…,s

當(dāng)r=1時(shí)，設(shè)

模型中，式(1)為模型的目標(biāo)；式(2)和(3)為目標(biāo)函數(shù)；約束(14)表示每個(gè)優(yōu)先級(jí)位置只能對(duì)應(yīng)1個(gè)工件；約束(15)表示任一階段每個(gè)工件只能由1臺(tái)機(jī)器加工；約束(16)表示每一工件在進(jìn)行下一道工序前必須完成當(dāng)前工序；約束(17)表示每個(gè)工件在任一階段上的加工完成時(shí)間小于其完工時(shí)間；約束(18)表示同一階段調(diào)度排列中排位越靠前的工件開始處理的時(shí)間越早；約束(19)表示同一階段分配在同一機(jī)器上的排位靠后的工件必須等排位靠前的工件加工完后才可進(jìn)行加工.

2 改進(jìn)型雙目標(biāo)差分進(jìn)化算法

采用傳統(tǒng)的解析方法并不能求解中大規(guī)模的調(diào)度問(wèn)題.目前，國(guó)內(nèi)外研究人員均基于啟發(fā)式算法對(duì)此類調(diào)度問(wèn)題進(jìn)行研究.Storn等[11]于1997年提出的一種非常有效的優(yōu)化算法——差分進(jìn)化(DE)算法，已經(jīng)被廣泛地應(yīng)用于各工程領(lǐng)域.本文基于DE算法提出一種改進(jìn)型雙目標(biāo)差分進(jìn)化(MODE)算法，使用非支配排序以及擁擠距離評(píng)價(jià)策略比較與排序可行解.同時(shí)，引入優(yōu)質(zhì)解挑戰(zhàn)機(jī)制[12]以及混沌搜索策略以保證算法的全局搜索能力.提前設(shè)置以下初始參數(shù)：種群規(guī)模(Q)；解的壽命(L)；解的年齡(A)；最大循環(huán)次數(shù)(Y).MODE算法的具體步驟如下.

步驟1編碼.根據(jù)模型特點(diǎn)，采用雙染色體形式表示可行解的編碼.編碼的每一個(gè)元素包含一個(gè)工件在1個(gè)階段中的機(jī)器指派情況和待加工次序.例如，一個(gè)HFSP中有5個(gè)待加工工件和3個(gè)階段，各階段中的機(jī)器數(shù)分別為2、1、3，一個(gè)可行解的編碼可寫成：

編碼首行的3個(gè)元素表示工件1分別在3個(gè)階段的1,1,3號(hào)機(jī)器上加工，且在各機(jī)器上的排序分別是1,2,1.

步驟2初始化階段.引入了NEH(Nanaz, Enscore, Ham)啟發(fā)式方法[13]初始化MODE算法，建立基于NEH和隨機(jī)生成的混合方法產(chǎn)生初始種群.首先，利用NEH啟發(fā)式方法構(gòu)建一個(gè)基礎(chǔ)可行解，再通過(guò)成對(duì)交換方法生成Q/2個(gè)可行解，剩余Q/2個(gè)可行解隨機(jī)生成.

步驟3基于反向的搜索.反向?qū)W習(xí)(OBL)是由Tizhoosh[14]為機(jī)器智能的種群初始化提出的一種方法.對(duì)初始種群Q0反向?qū)W習(xí)后可以得到反向解集，將該解集與Q0合并后共同評(píng)估選擇得到新解集.OBL的應(yīng)用能夠有效地提高群體的多樣性，避免算法陷入局部最優(yōu).

步驟4差分變異.使用DE/current-to-best/1策略以精英解針對(duì)新解集的每一個(gè)解xi生成其變異解νi.變異解經(jīng)過(guò)與原解的交叉操作得到試驗(yàn)解，通過(guò)比較適應(yīng)值決定是否替代原解.差分變異過(guò)程完成后得到的解集將再次經(jīng)過(guò)反向?qū)W習(xí)得到新解集，與原解集合并后利用非支配排序和擁擠距離計(jì)算得到新種群及作為領(lǐng)導(dǎo)解集的最優(yōu)Pareto前沿.其中，以擁擠距離最小的解作為精英解.

步驟5挑戰(zhàn)機(jī)制.為避免陷入局部最優(yōu)解，1次循環(huán)內(nèi)領(lǐng)導(dǎo)解集中的每個(gè)優(yōu)質(zhì)解都需要比較當(dāng)前年齡值(未更新迭代數(shù))和壽命，判斷其是否需要接受挑戰(zhàn).一個(gè)解每經(jīng)過(guò)1次差分變異或混沌搜索，若被更新，則其對(duì)應(yīng)年齡值置0，壽命重置為初始年齡；否則，其年齡值加1.一旦達(dá)到壽命限制，啟動(dòng)對(duì)該解的挑戰(zhàn)機(jī)制.為了生成更具多樣性和競(jìng)爭(zhēng)力的挑戰(zhàn)解，每次該算法都將從以下兩種鄰域搜索策略中隨機(jī)選取一種用于生成挑戰(zhàn)解，生成的挑戰(zhàn)解分別為GPBX-α[12]和下式：

(20)

與經(jīng)過(guò)多代進(jìn)化的“年老”優(yōu)質(zhì)解相比，挑戰(zhàn)解難以立即具備足夠的競(jìng)爭(zhēng)力，故較難在挑戰(zhàn)機(jī)制中獲勝.因此，對(duì)失敗的挑戰(zhàn)解再進(jìn)行一次差分進(jìn)化操作給予第2次挑戰(zhàn)機(jī)會(huì).挑戰(zhàn)解一旦通過(guò)比較適應(yīng)值戰(zhàn)勝對(duì)應(yīng)優(yōu)質(zhì)解，則取代優(yōu)質(zhì)解并為挑戰(zhàn)解設(shè)置初始年齡值和壽命；若2次挑戰(zhàn)均失敗，則優(yōu)質(zhì)解的年齡值減1，并允許其進(jìn)入下一次循環(huán).

步驟6混沌搜索.在每次MODE算法循環(huán)的末尾引入混沌搜索，以徹底探索解空間.由于其獨(dú)特的周期規(guī)律、固有的隨機(jī)屬性等特點(diǎn)，混沌搜索能夠有效地更改粒子的位置，從而有助于提高算法的多樣性.

利用下式將解向量連續(xù)化后計(jì)算每個(gè)維度對(duì)應(yīng)的混沌數(shù)以構(gòu)建混沌序列：

(21)

其中：t為混沌迭代數(shù),t=1,2,…,10.同樣地，混沌解若戰(zhàn)勝對(duì)應(yīng)原解，則取代原解并為混沌解設(shè)置初始年齡值和壽命.

步驟7算法終止判斷.若算法迭代次數(shù)達(dá)到規(guī)定上限Y，則輸出當(dāng)前的最優(yōu)Pareto前沿及其適應(yīng)值；否則，進(jìn)入步驟4.

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

所有算法都在MATLAB(2016a)環(huán)境下編程實(shí)現(xiàn)，并在主頻為 3.2 GHz，內(nèi)存為8 GB、Intel(R) Core(TM) i5-4570 CPU的PC機(jī)上進(jìn)行數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)分析和結(jié)果如下.

3.1 評(píng)價(jià)指標(biāo)

對(duì)于多目標(biāo)優(yōu)化問(wèn)題，僅將獲得的最優(yōu)Pareto前沿及算法運(yùn)行時(shí)間(CPU)作為評(píng)價(jià)指標(biāo)不足以評(píng)判算法的性能優(yōu)劣.因此，為了更為有效地判斷得到的最優(yōu)Pareto解的性能，還將選用Pareto解的個(gè)數(shù)(NS)、世代距離(GD)、解間距(SP)作為比較各算法的性能指標(biāo).其中，GD越小，表明算法收斂性越好；SP越小，表明算法多樣性越佳.

3.2 參數(shù)設(shè)置

測(cè)試算例中，有n=20，40，60共3個(gè)水平.每個(gè)水平各自對(duì)應(yīng)2個(gè)階段數(shù)和機(jī)器數(shù)，共有12個(gè)組合.由于研究考慮的是確定性的調(diào)度問(wèn)題，所以每次計(jì)算的初始階段都會(huì)隨機(jī)生成完整的測(cè)試數(shù)據(jù)：工件加工時(shí)間的模糊數(shù)最可能值服從[10,120]的均勻分布；模糊上下限取最可能值的75%與125%；加工功率服從[3,7]的均勻分布；工件的換模時(shí)間服從[10,20]的均勻分布；換模功率服從[2,6]的均勻分布；機(jī)器的開機(jī)時(shí)間服從[5,10]的均勻分布；關(guān)機(jī)時(shí)間服從[2,7]的均勻分布；開機(jī)功率服從[2,6]的均勻分布；關(guān)機(jī)功率服從[1,5]的均勻分布；閑時(shí)功率服從[2,6]的均勻分布；每個(gè)工件交貨期的可能值表示為

將n=20，s=3，m=5的算例組合記為n20s3m5.數(shù)值實(shí)驗(yàn)中，將n=20，40，60的3類問(wèn)題分別記為小、中、大規(guī)模問(wèn)題.

3.3 數(shù)值實(shí)驗(yàn)分析

將MODE算法與帶精英策略的非支配選擇遺傳算法(NSGA-II)、強(qiáng)度帕累托進(jìn)化算法(SPEA2)進(jìn)行對(duì)比實(shí)驗(yàn)，以測(cè)試問(wèn)題的求解性能.這兩種經(jīng)典算法在解決多目標(biāo)問(wèn)題上都具有較好的求解性能.由于此問(wèn)題的真實(shí)Pareto前沿難以得到，故采用以下方法獲得近似前沿：各算法獨(dú)立運(yùn)行多次并記錄每次獲得的Pareto解集，從Pareto解合集中集結(jié)新的Pareto解集作為近似前沿.

MODE算法的參數(shù)設(shè)置對(duì)于其表現(xiàn)和效率有著重要的影響，實(shí)驗(yàn)采用田口方法確定各參數(shù)值，以保證算法的高效性.首先進(jìn)行正交組合，然后測(cè)試各組參數(shù)以確定最優(yōu)組合.據(jù)測(cè)試，當(dāng)交叉率CR=0.7,第1個(gè)權(quán)重因子W1=0.6,第2個(gè)權(quán)重因子W2=0.4，可行解的初始?jí)勖麹=8時(shí)，MODE算法能以較高的質(zhì)量對(duì)問(wèn)題進(jìn)行求解.MODE算法以及NSGA-II、SPEA2算法的參數(shù)設(shè)置如表1所示.

由于算法的單次運(yùn)行結(jié)果具有一定的隨機(jī)性，所以分別用上述3種算法對(duì)各算例進(jìn)行20次獨(dú)立數(shù)值實(shí)驗(yàn)，結(jié)果如表2所示.

由表2可知，當(dāng)問(wèn)題規(guī)模較小時(shí)，SPEA2與NSGA-II的解的個(gè)數(shù)、世代距離以及解間距性能指標(biāo)都十分接近，略劣于MODE的相應(yīng)性能指標(biāo).但是，在運(yùn)算時(shí)間上，NSGA-II以及SPEA2所需要的運(yùn)行時(shí)間略優(yōu)于MODE；當(dāng)問(wèn)題規(guī)模逐漸變大時(shí)，MODE相對(duì)于NSGA-II、SPEA2在解個(gè)數(shù)、世代距離和解間距方面的優(yōu)勢(shì)逐漸擴(kuò)大，其相對(duì)較大的運(yùn)算時(shí)間也在可接受范圍內(nèi).其中，MODE在Pareto解個(gè)數(shù)上的優(yōu)勢(shì)意味著有更多備選決策可供從業(yè)人員選擇.

圖2以n20s3m5，n60s7m15兩個(gè)算例為例，表明了在小、大兩種規(guī)模下各算法之間的Pareto前沿比較情況.由圖2(a)可知，當(dāng)問(wèn)題規(guī)模較小時(shí)，NSGA-II、SPEA2求得的解集互有支配，并且都被MODE求得的解集所支配，但在部分位置差距較?。欢S著問(wèn)題規(guī)模的擴(kuò)大，如圖2(b)所示，MODE的Pareto解集基本支配了NSGA-II與SPEA2的 Pareto 解集，且分布更為均勻.數(shù)值實(shí)驗(yàn)對(duì)比結(jié)果證明了MODE算法的有效性.而MODE算法的優(yōu)秀求解能力應(yīng)該歸功于算法基于DE算法的多個(gè)改進(jìn)之處，其中包括基于NEH算法得到優(yōu)質(zhì)初始解、優(yōu)質(zhì)差分進(jìn)化策略帶來(lái)更好的鄰域挖掘能力、挑戰(zhàn)優(yōu)質(zhì)解更易于跳出局部最優(yōu)解、反向?qū)W習(xí)和混沌搜索策略保證算法的全局搜索能力.

表1 不同算法的參數(shù)設(shè)置表Tab.1 Parameter settings of different algorithms

表2 不同規(guī)模調(diào)度問(wèn)題的數(shù)值實(shí)驗(yàn)結(jié)果Tab.2 Experimental results for different instances

圖2 兩個(gè)算例下的Pareto解集Fig.2 Pareto solutions for two instances

4 結(jié)論

(1) 針對(duì)考慮并行機(jī)不相關(guān)、換模時(shí)間與工件加工次序相關(guān)兩種約束的混合流水線系統(tǒng)，以保證準(zhǔn)時(shí)交貨和降低生產(chǎn)能耗為雙調(diào)度目標(biāo)，使用模糊數(shù)描述加工時(shí)間和交貨期以處理系統(tǒng)的不確定性.

(2) 以差分進(jìn)化算法為基礎(chǔ)，引入NEH啟發(fā)式方法構(gòu)建高質(zhì)量初始解，建立優(yōu)質(zhì)解挑戰(zhàn)機(jī)制避免種群陷入局部最優(yōu)，通過(guò)反向?qū)W習(xí)和混沌搜索探索全局解空間，提出改進(jìn)雙目標(biāo)差分進(jìn)化算法.

(3) 仿真實(shí)驗(yàn)驗(yàn)證MODE算法的有效性和較好的求解性能，豐富解決此類調(diào)度問(wèn)題的理論方法.

(4) 未來(lái)的研究可在本文基礎(chǔ)上考慮有限緩沖區(qū)，增加研究的復(fù)雜性和現(xiàn)實(shí)意義.