混合交叉熵算法求解模糊分布式裝配流水線低碳調(diào)度問題

佘明哲 錢 斌 胡 蓉吳麗萍向鳳紅

(1.昆明理工大學(xué)信息工程與自動化學(xué)院,云南昆明 650500;2.昆明理工大學(xué)云南省人工智能重點(diǎn)實(shí)驗(yàn)室,云南昆明 650500)

1 引言

隨著市場競爭的加劇以及經(jīng)濟(jì)全球化趨勢的深入發(fā)展,具有多個生產(chǎn)中心的制造方式變得越來越普遍,企業(yè)可從不同的供貨商處采購產(chǎn)品所需部件,后對其組裝.這種方式能夠在有效地把控產(chǎn)品質(zhì)量的同時降低生產(chǎn)成本與管理風(fēng)險.因此,對分布式裝配系統(tǒng)展開研究具有重要意義.同時,由于實(shí)際生產(chǎn)過程大多存在不確定性,這類因素的存在可能導(dǎo)致在確定條件假設(shè)下得到的優(yōu)質(zhì)調(diào)度方案在實(shí)際生產(chǎn)過程中變得不可行.所以利用模糊理論中的模糊數(shù)表征不確定的加工和裝配時間,有助于更為客觀地描述實(shí)際生產(chǎn)過程,并為生產(chǎn)過程提供指導(dǎo).另外,針對全球日益嚴(yán)峻的環(huán)境問題,綠色制造開始逐漸引起企業(yè)的重視[1-2].因此,研究模糊分布式裝配流水線低碳調(diào)度問題(fuzzy distributed assembly permutation flow-shop lowcarbon scheduling problem,FDAPFLSP)具有現(xiàn)實(shí)的經(jīng)濟(jì)價值和深遠(yuǎn)的社會意義.在計(jì)算復(fù)雜度上,分布式裝配流水線調(diào)度問題(distributed assembly permutation flow-shop scheduling problem,DAPFSP)已被證明具有非確定多項(xiàng)式難(non-deterministic polynomial hard,NP-hard)的屬性[3],而該問題又約歸為FDAPFLSP,故FDAPFLSP屬于NP-hard問題.因此,研究FDAPFLSP問題及其求解算法具有重要的理論價值和實(shí)際意義.

在計(jì)算模糊生產(chǎn)調(diào)度問題的不同工件排列或解對應(yīng)的目標(biāo)函數(shù)值時,需要對模糊加工和裝配時間進(jìn)行加、減、乘、取大等運(yùn)算;同時評價不同解的優(yōu)劣時,需要對不同解的目標(biāo)函數(shù)值進(jìn)行比較運(yùn)算.其中加、減、乘運(yùn)算可通過模糊數(shù)學(xué)的相關(guān)定義直接進(jìn)行,取大、比較運(yùn)算可通過對模糊數(shù)進(jìn)行排序?qū)崿F(xiàn).現(xiàn)已有學(xué)者對模糊生產(chǎn)調(diào)度問題中模糊數(shù)排序準(zhǔn)則進(jìn)行研究.Sakawa等[4]設(shè)計(jì)一種基于隸屬度參數(shù)值的三角模糊數(shù)排序準(zhǔn)則.Sakawa等[5]在文獻(xiàn)[4]的基礎(chǔ)上,設(shè)計(jì)3條排序準(zhǔn)則用以判斷模糊數(shù)的大小關(guān)系.Lei[6]證明文獻(xiàn)[5]所提排序準(zhǔn)則優(yōu)于文獻(xiàn)[4]所提準(zhǔn)則.Li 等[7]在充分考慮取大操作的近似誤差和模糊度基礎(chǔ)上,設(shè)計(jì)一種新穎的三角模糊數(shù)排序準(zhǔn)則.由文獻(xiàn)調(diào)研可知,模糊生產(chǎn)調(diào)度問題的已有研究多采用文獻(xiàn)[5]所提準(zhǔn)則對三角模糊數(shù)的大小關(guān)系進(jìn)行判斷.且上述3種排序準(zhǔn)則均從排序的準(zhǔn)確性角度對準(zhǔn)則進(jìn)行改進(jìn),并未考慮生產(chǎn)調(diào)度問題特性,故直接使用上述文獻(xiàn)所提準(zhǔn)則,易出現(xiàn)違反生產(chǎn)調(diào)度問題約束的情況,進(jìn)而導(dǎo)致算法在違反問題約束的解空間區(qū)域周圍進(jìn)行搜索,影響求解過程中的搜索方向與最終所得解的質(zhì)量,甚至使所得調(diào)度優(yōu)質(zhì)解在實(shí)際生產(chǎn)過程中變得不可行.因此,需要在原有模糊數(shù)排序準(zhǔn)則的基礎(chǔ)上進(jìn)行修正,以避免此類情況的出現(xiàn).目前,尚無針對此不足對模糊數(shù)排序準(zhǔn)則進(jìn)行改進(jìn)的研究.

在分布式裝配流水線調(diào)度問題研究方面,Hatami等[3]首次提出了該問題,以最小化最大完工時間為優(yōu)化目標(biāo)建立了其混合整數(shù)線性規(guī)劃(mixed integer linear program,MILP)模型,同時提出多個啟發(fā)式方法用于構(gòu)造初始解,并設(shè)計(jì)變鄰域下降算法(variable neighborhood descent algorithm,VND)進(jìn)行求解.Lin等[8]針對優(yōu)化目標(biāo)為最小化最大完工時間的分布式裝配流水線調(diào)度問題,設(shè)計(jì)一種回溯搜索超啟發(fā)式(backtracking search hyper-heuristic,BSHH)算法進(jìn)行求解,該算法高層利用回溯搜索算法對由10個低層啟發(fā)式操作組成的操作序列進(jìn)行優(yōu)化,低層按照高層所得排列進(jìn)行搜索.Sang等[9]針對優(yōu)化目標(biāo)為總流經(jīng)時間的分布式裝配流水線調(diào)度問題,設(shè)計(jì)3種離散雜草入侵優(yōu)化(discrete invasive weed optimization,DIWO)算法進(jìn)行求解.Ferone等[10]針對優(yōu)化目標(biāo)為最小化最大完工時間的分布式裝配流水線調(diào)度問題,設(shè)計(jì)一種有偏迭代局部搜索(biased-based iterated local search,BR-ILS)算法進(jìn)行求解,該算法采用引入有偏隨機(jī)行為的啟發(fā)式算法構(gòu)造初始解以提升其質(zhì)量.顯然,分布式裝配流水線調(diào)度問題正成為當(dāng)前的研究熱點(diǎn).

生產(chǎn)過程存在多種不確定性因素[11],譬如工藝不穩(wěn)定、設(shè)備老化、操作人員不同等導(dǎo)致工件或工序加工時間難以提前確定.因此,采用模糊數(shù)表示加工和裝配時間,有益于獲得魯棒、可行的調(diào)度方案.目前,已有學(xué)者對模糊加工時間的生產(chǎn)調(diào)度問題進(jìn)行研究.Yang等[12]針對優(yōu)化目標(biāo)為最小化模糊最大完工時間和最大化平均滿意度的帶堵塞模糊流水車間調(diào)度問題,設(shè)計(jì)了一種混合多目標(biāo)灰狼優(yōu)化(hybrid multiobjective gray wolf optimization,HMOGWO) 算法進(jìn)行求解,該算法在構(gòu)造初始解階段設(shè)計(jì)了一種以最大化平均滿意度為導(dǎo)向的啟發(fā)式算法,與PFE啟發(fā)式算法共同使用以提升初始解的質(zhì)量;另外,在局部搜索階段基于insert鄰域結(jié)構(gòu)設(shè)計(jì)了兩種局部搜索操作以提升算法的搜索能力.Li等[13]針對優(yōu)化目標(biāo)為最小化模糊最大完工時間的帶資源消耗約束的模糊同類機(jī)調(diào)度問題,設(shè)計(jì)了一種簡化群優(yōu)化(simplified swarm optimization,SSO)算法進(jìn)行求解,該算法引入了懲罰函數(shù)以引導(dǎo)算法向滿足資源消耗約束的解空間區(qū)域的方向進(jìn)行搜索.Zhong等[14]針對優(yōu)化目標(biāo)為同時最小化模糊最大完工時間和模糊最大機(jī)器負(fù)載、最大化加權(quán)滿意度的模糊柔性作業(yè)車間調(diào)度問題,設(shè)計(jì)了一種改進(jìn)人工蜂群(modified artificial bee colony,MABC)算法進(jìn)行求解,該算法設(shè)計(jì)了一種基于變鄰域搜索的局部搜索操作,以實(shí)現(xiàn)對不同解空間區(qū)域搜索的目的.然而,尚無人對模糊分布式裝配流水線調(diào)度問題進(jìn)行研究.

與傳統(tǒng)調(diào)度問題相比,低碳調(diào)度問題通過資源分配、操作排序和運(yùn)行模式的綜合優(yōu)化,實(shí)現(xiàn)節(jié)能減排、降本增效,求解難度更大,也更具工程意義和理論價值[15].在分布式車間低碳調(diào)度問題研究方面,Fu等[16]針對帶有總延遲約束,優(yōu)化目標(biāo)為同時最小化最大完工時間和總能耗的分布式流水線低碳調(diào)度問題,設(shè)計(jì)了一種多目標(biāo)頭腦風(fēng)暴優(yōu)化算法(multi-objective brain storm optimization algorithm,MOBSO)進(jìn)行求解,該算法通過判斷種群中個體的支配等級對其進(jìn)行分組,然后采用二值選擇法確定一或兩組,對應(yīng)進(jìn)行不同操作以生成新個體.Chen 等[17]針對優(yōu)化目標(biāo)為同時最小化最大完工時間和總能耗的分布式零空閑流水線低碳調(diào)度問題,設(shè)計(jì)了一種協(xié)同進(jìn)化算法(collaborative optimization algorithm,COA)進(jìn)行求解,該算法采用兩種啟發(fā)式算法構(gòu)造初始解以提升其質(zhì)量,在局部搜索階段多種操作自適應(yīng)更新選擇概率以增強(qiáng)算法搜索能力.目前沒有分布式裝配流水線低碳調(diào)度問題(distributed assembly permutation flow-shop low-carbon scheduling problem,DAPFLSP)方面的研究報道.由上述文獻(xiàn)調(diào)研可知,尚無求FDAPFLSP這類重要問題的文獻(xiàn)報道,故對其開展建模和算法研究具有較大理論和實(shí)際意義.

交叉熵算法(cross-entropy algorithm,CEA)是由Rubinstein[18]提出的一種小概率事件估計(jì)算法.該算法利用稀有事件(即較優(yōu)解)信息更新相應(yīng)的概率模型參數(shù),并使用有效采樣方法對概率模型采樣以生成新種群,進(jìn)而引導(dǎo)搜索方向.CEA采用正反饋機(jī)制使得較優(yōu)解的模式信息得以更多積累,有利于引導(dǎo)算法到達(dá)問題解空間中存在優(yōu)質(zhì)解的區(qū)域.這使得算法具有較強(qiáng)的全局搜索能力,從而在多類優(yōu)化問題上得到成功應(yīng)用.譬如,Caserta等[19]針對優(yōu)化目標(biāo)為最大化裝包物品數(shù)量的帶裝包費(fèi)用的整數(shù)背包問題,設(shè)計(jì)了混合交叉熵算法(hybrid cross entropy algorithm,HCEA)進(jìn)行求解.該算法采用CEA確定放入背包的物品種類,進(jìn)而利用動態(tài)規(guī)劃算法確定各類物品的數(shù)量.Je?drzejowicz等[20]針對優(yōu)化目標(biāo)為最小化最大完工時間的同構(gòu)并行機(jī)調(diào)度問題,設(shè)計(jì)了基于交叉熵的群學(xué)習(xí)算法(cross-entropy-based population-learning algorithm,CPLA)進(jìn)行求解.該算法利用CEA和禁忌搜素算法共同產(chǎn)生種群,進(jìn)而采用島嶼進(jìn)化算法進(jìn)一步提高種群質(zhì)量.Santosa等[21]針對優(yōu)化目標(biāo)為最小化最大完工時間的零等待作業(yè)車間調(diào)度問題,設(shè)計(jì)了一種混合交叉熵遺傳算法(hybrid cross-entropy genetic algorithm,CEGA) 進(jìn)行求解.該算法在CEA基礎(chǔ)上,進(jìn)一步利用遺傳算法的交叉、變異操作來實(shí)現(xiàn)對解空間中更多不同區(qū)域的搜索.Wang等[22]針對優(yōu)化目標(biāo)為最小化總能耗的煉鋼-連鑄生產(chǎn)調(diào)度問題,設(shè)計(jì)了改進(jìn)交叉熵算法(improved cross entropy algorithm,ICEA)進(jìn)行求解.該算法在對CEA概率矩陣采樣時加入啟發(fā)式規(guī)則以改進(jìn)生成解的質(zhì)量,并對部分精英個體執(zhí)行基于交換操作的局部搜索.Li等[23]針對高維函數(shù)優(yōu)化問題設(shè)計(jì)了一種混合交叉熵螢火蟲算法(cross-entropy firefly algorithm,CEFA).該算法采用CEA和螢火蟲算法兩套不同搜索機(jī)制進(jìn)行協(xié)同搜索,以提高算法對解空間不同區(qū)域的搜索能力.從CEA在優(yōu)化問題上的研究現(xiàn)狀來看,將CEA與其他有效的算法和操作合理混合,可豐富搜索行為而提升算法性能,是設(shè)計(jì)有效CEA的關(guān)鍵.目前尚無CEA求解分布式生產(chǎn)調(diào)度問題的相關(guān)研究.

本文研究FDAPFLSP的建模與求解.首先,在模糊數(shù)排序準(zhǔn)則方面,分析目前常用排序準(zhǔn)則的特點(diǎn),充分考慮生產(chǎn)調(diào)度問題約束,在原有排序準(zhǔn)則的基礎(chǔ)上設(shè)計(jì)一種實(shí)用的三角模糊數(shù)排序修正準(zhǔn)則.其次,在問題建模方面,針對實(shí)際生產(chǎn)中廣泛存在的加工和裝配時間不確定性,采用三角模糊數(shù)進(jìn)行表征,建立以同時最小化模糊最大完工時間和模糊總能耗為優(yōu)化目標(biāo)的FDAPFLSP問題模型.然后,在算法設(shè)計(jì)方面,考慮到CEA具有較強(qiáng)全局搜索能力但收斂較慢,故引入局部搜索并提出一種混合交叉熵算法(hybrid cross-entropy algorithm,HCEA)進(jìn)行求解.在HCEA中,全局搜索階段采用CEA的概率模型學(xué)習(xí)和積累部分較優(yōu)排列的信息,進(jìn)而通過采樣該模型以實(shí)現(xiàn)對解空間中優(yōu)質(zhì)區(qū)域的搜索;局部搜索階段提出基于多種鄰域操作的自適應(yīng)變鄰域局部搜索,在算法進(jìn)化過程中根據(jù)各鄰域操作的貢獻(xiàn)率自適應(yīng)選擇合適的鄰域操作進(jìn)行搜索,可對全局搜索發(fā)現(xiàn)的優(yōu)質(zhì)區(qū)域進(jìn)行更為細(xì)致的搜索,從而增強(qiáng)算法性能.最后,通過仿真實(shí)驗(yàn)和算法比較驗(yàn)證所提算法的有效性.

2 模糊分布式裝配流水線低碳調(diào)度問題

2.1 符號定義

本文所涉及的數(shù)學(xué)符號及定義如表1所示.

表1 符號表Table 1 Notations

2.2 問題模型

2.3 模糊數(shù)

2.3.1 模糊數(shù)的運(yùn)算

在計(jì)算FDAPFLSP不同個體或解對應(yīng)的目標(biāo)函數(shù)值時,需對模糊數(shù)(即加工和裝配時間)進(jìn)行加、減、乘、取大等運(yùn)算.根據(jù)模糊數(shù)學(xué)的有關(guān)定義和擴(kuò)張?jiān)?設(shè)=(u1,u2,u3)和=(w1,w2,w3)為兩個三角模糊數(shù)(triangular fuzzy number,TFN),定義其加法運(yùn)算如式(18)所示:

2.3.2 模糊數(shù)排序修正準(zhǔn)則

通過第2.3.1節(jié)的描述可知,Sakawa等[5]所提排序準(zhǔn)則是對兩個TFN進(jìn)行近似精確化處理后,通過對其近似精確值進(jìn)行比較后,確定兩個TFN之間的大小關(guān)系.Li等[7]所提排序準(zhǔn)則也是對TFN進(jìn)行近似精確化處理后再進(jìn)行比較.

但若將此類排序準(zhǔn)則直接用于生產(chǎn)調(diào)度問題,可能會出現(xiàn)同一時刻同一臺機(jī)器上安排兩個工件進(jìn)行加工(即違反問題約束)的情況,譬如,使用Sakawa等[5]所提排序準(zhǔn)則對O1,2和O2,1的完工時間進(jìn)行比較,得到O2,2的開工時間,此時O2,2開工時間的最樂觀值小于O1,2完工時間的最樂觀值,如圖1(a)所示;O2,2開工時間的最悲觀值小于O1,2完工時間的最悲觀值,如圖1(b)所示.圖1中下方為操作的模糊開工時間,上方為操作的模糊完工時間.此類情況的出現(xiàn),使得該準(zhǔn)則在實(shí)際生產(chǎn)過程中不可行.

圖1 違反問題約束情況示意圖Fig.1 Illustrations of two cases that constrains are violated

對此,提出一種適用于生產(chǎn)調(diào)度問題的模糊數(shù)修正排序準(zhǔn)則.記機(jī)器j上工件的加工序列為πj.

圖1所舉示例經(jīng)修正準(zhǔn)則處理后如圖2所示,其中:O2,2的理論開工時間用實(shí)線表示,經(jīng)修正準(zhǔn)則處理后所得實(shí)際開工時間用虛線表示.

圖2 修正準(zhǔn)則處理后情況示意圖Fig.2 Illustrations of two cases that correction rule is used

3 混合交叉熵算法

3.1 編碼與解碼

個體的編碼由產(chǎn)品裝配序列πA和工件加工序列π兩部分組成.其中,屬于同一產(chǎn)品的工件在π中相鄰放置.個體編碼示意圖如圖3所示.

圖3 個體編碼示意圖Fig.3 Illustration of individual coding

對于每個個體,均對其工件加工序列π采用文獻(xiàn)[3]中所提NR2規(guī)則進(jìn)行解碼.例如,對于

編碼如圖3所示的問題.各階段數(shù)據(jù)如表2所示.解碼后所得甘特圖如圖4所示.

表2 各階段數(shù)據(jù)Table 2 Data of each stage

圖4 解碼后所得甘特圖Fig.4 Gantt chart obtained after decoded

3.2 種群初始化

本文采用隨機(jī)初始化方法生成種群,以保證種群的多樣性與分散性.

3.3 交叉熵算法

使用CEA對種群進(jìn)行全局搜索.首先,使用概率分布矩陣Λ表示ρ個優(yōu)質(zhì)個體所包含信息,矩陣元素ζi,j表示工件i出現(xiàn)在π中第j位的概率,矩陣Λ如式(21)所示:

其中:k為迭代次數(shù),η ∈(0,1)為學(xué)習(xí)率,為指示函數(shù),ρ為優(yōu)質(zhì)個體數(shù)量.

其次,按照如下步驟逐位對概率分布矩陣Λ進(jìn)行采樣以生成新個體:

步驟1若πA中當(dāng)前已確定產(chǎn)品位置的個數(shù)?等于總產(chǎn)品數(shù)Q,轉(zhuǎn)至步驟2;否則,轉(zhuǎn)至步驟3.

步驟2記πA第?位所對應(yīng)產(chǎn)品為Pπ?,若π中當(dāng)前已確定Pπ?包含工件的位置的個數(shù)?π?小于Pπ?所包含的總工件數(shù)Nπ?,轉(zhuǎn)至步驟4;?π?等于Nπ?,終止循環(huán).

步驟3若?=0,轉(zhuǎn)至步驟5.否則,記πA第?位所對應(yīng)產(chǎn)品為Pπ?,若π中當(dāng)前已確定Pπ?包含工件的位置的個數(shù)?π?小于Pπ?所包含的總工件數(shù)Nπ?,轉(zhuǎn)至步驟4;若?π?等于Nπ?,轉(zhuǎn)至步驟5.

步驟4從Pπ?的剩余可選工件中進(jìn)行采樣,確定出現(xiàn)在π中當(dāng)前位置(當(dāng)?=1時,為第?π?+1位;當(dāng)? >1時,為第+1位)的工件;若剩余可選工件出現(xiàn)在該位置的概率均為0,則隨機(jī)從中選擇一個置于該位置,轉(zhuǎn)至步驟1.

步驟5從可選工件中進(jìn)行采樣,確定出現(xiàn)在π中當(dāng)前位置(當(dāng)?=0 時,為第1位;當(dāng)0 時,為第+1 位)的工件;若可選工件出現(xiàn)在該位置的概率均為0,則隨機(jī)從中選擇一個置于該位置.且將該工件所對應(yīng)產(chǎn)品置于πA中第?+1位,轉(zhuǎn)至步驟1.

3.4 自適應(yīng)變鄰域局部搜索

對于多目標(biāo)組合優(yōu)化問題,每個最優(yōu)非劣解集中的解(簡稱最優(yōu)非劣解)在所有鄰域結(jié)構(gòu)下均為局部最優(yōu)非劣解,而接近最優(yōu)非劣解的優(yōu)質(zhì)非劣解往往在多種鄰域結(jié)構(gòu)下均為局部最優(yōu)非劣解.采用單一鄰域的迭代搜索容易較早達(dá)到并陷入該鄰域結(jié)構(gòu)的局部最優(yōu)非劣解(可能有多個),但該非劣解的質(zhì)量大都一般.相對于常規(guī)的流水線調(diào)度問題,本文研究的FDAPFLSP中約束和決策變量明顯變多.這使得本文問題的解空間更加龐大和不規(guī)則,大量優(yōu)質(zhì)局部最優(yōu)非劣解不規(guī)則地分散在FDAPFLSP 的解空間內(nèi),增加了算法獲取優(yōu)質(zhì)非劣解集的難度.因此,本節(jié)設(shè)計(jì)基于多種鄰域操作的自適應(yīng)變鄰域局部搜索,在算法進(jìn)化過程中根據(jù)各鄰域操作的貢獻(xiàn)率動態(tài)選擇合適的鄰域操作執(zhí)行搜索,可在算法到達(dá)多種鄰域結(jié)構(gòu)共同的局部最優(yōu)非劣解前以較高效率一直持續(xù)逼近最優(yōu)非劣解集,從而增強(qiáng)搜索的深度,有利于算法獲得優(yōu)質(zhì)非劣解集.具體來說,本節(jié)采用交換、插入、逆序操作(即求解調(diào)度問題常用的有效鄰域操作)設(shè)計(jì)基于產(chǎn)品序列與基于工件序列的兩類自適應(yīng)局部搜索,用于對CEA發(fā)現(xiàn)的解空間優(yōu)質(zhì)區(qū)域進(jìn)行深入搜索.

3.4.1 基于產(chǎn)品序列的自適應(yīng)局部搜索

設(shè)計(jì)了6種作用于產(chǎn)品序列πA的鄰域操作.πA中的任意產(chǎn)品調(diào)整,工件序列π中對應(yīng)部分工件整體進(jìn)行調(diào)整.

每種操作的初始選擇概率相同,當(dāng)一次迭代完成(即種群中全部個體均進(jìn)行了鄰域操作)后,其選擇概率seLS(g)的更新步驟如下:

步驟1按式(23)分別計(jì)算每種鄰域操作的貢獻(xiàn)率eLS(g):

其中:NGLS(g)為一次迭代完成后,鄰域操作g所執(zhí)行的總次數(shù);NDLS(g)為一次迭代完成后,鄰域操作g對個體進(jìn)行更新后所得新解不被更新前的舊解支配的次數(shù).

步驟2計(jì)算=0,則不對鄰域操作的選擇概率seLS(g)進(jìn)行更新,并終止循環(huán);否則轉(zhuǎn)到步驟3.

步驟3按式(24)分別計(jì)算更新每種鄰域操作的選擇概率seLS(g):

6種鄰域操作分別如下所示:

1) 產(chǎn)品序列交叉操作,從產(chǎn)品序列中隨機(jī)選擇兩位并進(jìn)行交換.

2) 產(chǎn)品序列逆序操作,從產(chǎn)品序列中隨機(jī)選擇兩位,將包含所選兩位及其之間的部分進(jìn)行逆序排列.

3) 產(chǎn)品序列前向插入操作,從產(chǎn)品序列中隨機(jī)選擇兩位,位置編號大的產(chǎn)品插入到位置編號小的產(chǎn)品之前.

4) 產(chǎn)品序列后向插入操作,從產(chǎn)品序列中隨機(jī)選擇兩位,位置編號小的產(chǎn)品插入到位置編號大的產(chǎn)品之后.

5) 產(chǎn)品序列前向相鄰交叉操作,從產(chǎn)品序列中隨機(jī)選擇一位,向前和相鄰產(chǎn)品交換位置.

6) 產(chǎn)品序列后向相鄰交叉操作,從產(chǎn)品序列中隨機(jī)選擇一位,向后和相鄰產(chǎn)品交換位置.

3.4.2 基于工件序列的自適應(yīng)局部搜索

設(shè)計(jì)了6種作用于產(chǎn)品Ph的工件加工序列的鄰域操作.進(jìn)行此類操作時,需要先確定產(chǎn)品號,后對其所對應(yīng)的中工件進(jìn)行調(diào)整.

每種操作的初始選擇概率相同,隨著迭代過程的進(jìn)行,其選擇的概率seLS(g)的更新步驟如第2.4.1節(jié)所示.

6種鄰域操作分別如下所示:

1) 工件序列交叉操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇兩位并進(jìn)行交換.

2) 工件序列逆序操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇兩位,將包含所選兩位及其之間的部分進(jìn)行逆序排列.

3) 工件序列前向插入操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇兩位,位置編號大的工件插入到位置編號小的工件之前.

4) 工件序列后向插入操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇兩位,位置編號小的工件插入到位置編號大的工件之后.

5) 工件序列前向相鄰交叉操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇一位,向前和相鄰工件交換位置.

6) 工件序列后向相鄰交叉操作,從產(chǎn)品Ph的工件加工序列中隨機(jī)選擇一位,向后和相鄰工件交換位置.

3.5 算法流程

根據(jù)上述算法描述,整個算法流程描述如下:

步驟1初始化種群.

步驟2對種群中個體進(jìn)行評價.

步驟3對個體的支配關(guān)系進(jìn)行判斷,并計(jì)算個體對應(yīng)的支配等級與擁擠距離.對其排序后,選擇前popsize×θα個精英個體直接保留至新種群.

步驟4選擇當(dāng)代種群中前popsize×θα個個體更新交叉熵算法的概率模型,并生成新種群中剩余popsize×(1-θα)個個體.

步驟5對新種群中每個個體,分別依據(jù)6種基于產(chǎn)品序列的鄰域操作的選擇概率,隨機(jī)選擇一種操作對其進(jìn)行更新.個體更新完成后判斷個體是否改善,若改善,則接受新解;否則,有一定的概率接受新解.全部個體完成操作后,更新基于產(chǎn)品序列的自適應(yīng)局部搜索的選擇概率.

步驟6對新種群中每個個體,分別依據(jù)6種基于工件序列的鄰域操作的選擇概率,隨機(jī)選擇一種操作對其進(jìn)行更新.個體更新完成后判斷個體是否改善,若改善,則接受新解;否則,有一定的概率接受新解.全部個體完成操作后,更新基于工件序列的自適應(yīng)局部搜索的選擇概率.

步驟7使用所得非支配解集更新Pareto檔案集.

步驟8判斷是否滿足終止條件,若不滿足則轉(zhuǎn)到步驟2;否則,終止循環(huán).

4 實(shí)驗(yàn)分析與設(shè)計(jì)

由于目前沒有適合FDAPFLSP的標(biāo)準(zhǔn)算例,本文所有測試問題均在由Hatami等[3]為解決DAPFSP所提供算例的基礎(chǔ)上生成,每個測試問題均包含工件的模糊加工時間、產(chǎn)品的模糊裝配時間與產(chǎn)品約束3部分.

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

FDAPFLSP中參數(shù)取值如下:加工機(jī)器單位時間的空載能耗εidle=2、加工機(jī)器執(zhí)行開關(guān)機(jī)所需能耗=(8,8,8)、加工機(jī)器執(zhí)行一次開關(guān)機(jī)所需時間=(5,5,5)、裝配機(jī)器單位時間的空載能耗=3、裝配機(jī)器執(zhí)行開關(guān)機(jī)所需能耗=(20,20,20)、裝配機(jī)器執(zhí)行一次開關(guān)機(jī)所需時間=(9,9,9);加工機(jī)器的可執(zhí)行開關(guān)機(jī)次數(shù)T可通過T=「[(N/F)-2]/5」計(jì)算獲取,裝配機(jī)器的可執(zhí)行開關(guān)機(jī)次數(shù)TA可通過TA=「(Q-2)/5」計(jì)算獲取.

HCEA中的關(guān)鍵參數(shù)為種群容量popsize,學(xué)習(xí)率η,精英個體所占比例θα,統(tǒng)計(jì)樣本的ρ分位數(shù)與種群容量的比值θρ,進(jìn)行基于產(chǎn)品序列的局部操作后差解的接受概率φP,進(jìn)行基于工件序列的局部操作后差解的接受概率φJ(rèn).對于小規(guī)模問題,HCEA的參數(shù)設(shè)置如下:popsize=100,η=0.3,θα=0.2,θρ=0.3,φP=0.07,φJ(rèn)=0.07;對于大規(guī)模問題,HCEA的參數(shù)設(shè)置如下:popsize=100,η=0.3,θα=0.3,θρ=0.1,φP=0.07,φJ(rèn)=0.03.

4.2 仿真結(jié)果與比較

為驗(yàn)證HCEA求解FDAPFLSP的有效性,本節(jié)將HCEA 與SPEA2[24],IMMOGLS[25],MOBSO[16]進(jìn)行比較.SPEA2與IMMOGLS是廣泛應(yīng)用于求解多種車間調(diào)度問題的經(jīng)典多目標(biāo)算法.MOBSO是近年來求解分布式流水線低碳調(diào)度問題的有效算法.各算法均采用本文提出的模糊數(shù)排序修正準(zhǔn)則.

對于不同規(guī)模問題,設(shè)定每種算法的運(yùn)行時間均為N ×M ×20 ms.所有測試問題均進(jìn)行20次獨(dú)立實(shí)驗(yàn).每個問題對應(yīng)最優(yōu)結(jié)果用粗體表示.

為評價各算法性能,采用2個指標(biāo)對不同算法所得非支配解集Sj進(jìn)行評價.第1 個指標(biāo)如式(25)所示,衡量的是算法所得Sj的整體質(zhì)量;第2 個指標(biāo)如式(26)所示,衡量的是算法獲取非支配解的能力.顯然,這兩個指標(biāo)的值越大,Sj表現(xiàn)越好.

其中:S表示所有算法所產(chǎn)生的非支配解集的集合,y ?x表示解x被y支配,|Sj|表示非支配解集中解的數(shù)量.

對于小規(guī)模問題,各算法比較結(jié)果如表3所示.對于大規(guī)模問題,各算法比較結(jié)果如表4所示.由表3-4可知,HCEA在絕大部分問題上的測試結(jié)果都明顯優(yōu)于比較算法,這表明HCEA是求解FDAPFLSP的有效算法.

在比較算法中,SPEA2,IMMOGLS和MOBSO均采用交叉、變異等傳統(tǒng)操作生成新種群以實(shí)現(xiàn)全局搜索,同時SPEA2無局部搜索,IMMOGLS在各目標(biāo)函數(shù)隨機(jī)加權(quán)和的方向上執(zhí)行基于常規(guī)插入鄰域的局部搜索,MOBSO執(zhí)行基于常規(guī)插入、交換鄰域的局部搜索.HCEA通過采樣CEA概率模型生成新種群來實(shí)現(xiàn)全局搜索,可在一定程度上避免傳統(tǒng)交叉、變異等操作存在的對較優(yōu)解優(yōu)良模式破壞的問題[26],從而能更好地保留較優(yōu)解信息并合理引導(dǎo)搜索方向.同時,HCEA的局部搜索將更多的常規(guī)鄰域操作(即插入、逆序、交換)進(jìn)一步細(xì)分為12種基于產(chǎn)品或工件的鄰域操作,并依據(jù)每種鄰域操作在搜索過程中的效果動態(tài)擇優(yōu)確定應(yīng)執(zhí)行的鄰域搜索,可實(shí)現(xiàn)對鄰域搜索行為更精細(xì)的控制,從而能進(jìn)行更深入和更高效率的搜索.由于HCEA具有這些優(yōu)勢,故在上述實(shí)驗(yàn)中取得整體最好的成績.

5 結(jié)論

本文結(jié)合模糊數(shù)建立模糊分布式裝配流水線低碳調(diào)度問題(fuzzy distributed assembly permutation flow-shop low-carbon scheduling problem,FDAPFLSP)的模型,并提出一種混合交叉熵算法(hybrid cross-entropy algorithm,HCEA)進(jìn)行求解.主要貢獻(xiàn)包括:1)采用模糊數(shù)表示加工和裝配時間,并以同時最小化模糊最大完工時間和模糊總能耗為優(yōu)化目標(biāo),首次建立FDAPFLSP的問題模型;2) 在已有排序準(zhǔn)則的基礎(chǔ)上,設(shè)計(jì)一種三角模糊數(shù)排序修正準(zhǔn)則,以確保由準(zhǔn)則獲得的解(即調(diào)度方案)能更好滿足機(jī)器在同一時刻只能加工一個工件的基本約束,從而提升準(zhǔn)則的實(shí)用性;3)在采用CEA執(zhí)行全局搜索的基礎(chǔ)上,設(shè)計(jì)基于鄰域操作貢獻(xiàn)率的變鄰域局部搜索對全局搜索發(fā)現(xiàn)的優(yōu)質(zhì)區(qū)域執(zhí)行深入、細(xì)致的搜索,可增強(qiáng)算法性能.未來研究將把HCEA擴(kuò)展用于求解不確定車輛配送問題.