魏光艷 葉春明

上海理工大學(xué)管理學(xué)院,上海,200093

0 引言

在經(jīng)濟(jì)全球化的背景下,為應(yīng)對(duì)快速變化的市場(chǎng)環(huán)境,大量制造企業(yè)由單一工廠生產(chǎn)轉(zhuǎn)變?yōu)槎喙S生產(chǎn),因此, 分布式工廠調(diào)度問(wèn)題逐漸成為工業(yè)界和學(xué)術(shù)界的關(guān)注焦點(diǎn)。這種對(duì)多個(gè)制造單元進(jìn)行調(diào)度決策的需求,催生了分布式調(diào)度的相關(guān)研究[1]。借助于智能生產(chǎn)系統(tǒng),分布式制造可以實(shí)現(xiàn)對(duì)資源的統(tǒng)一配置,促進(jìn)分散制造資源的組合優(yōu)化與共享[2],因此,研究分布式車(chē)間調(diào)度問(wèn)題具有重要的現(xiàn)實(shí)意義和應(yīng)用價(jià)值。

分布式作業(yè)車(chē)間調(diào)度問(wèn)題是作業(yè)車(chē)間調(diào)度問(wèn)題的擴(kuò)展,通常包括兩個(gè)子調(diào)度問(wèn)題:工件在加工工廠之間的分配,以及對(duì)工序的操作順序進(jìn)行排序[3-5]。由于柔性制造系統(tǒng)在分布式制造工廠中的普遍應(yīng)用,分布式柔性作業(yè)車(chē)間調(diào)度問(wèn)題(distributed and flexible job-shop scheduling problem, DFJSP)引起了廣泛關(guān)注。MENG等[6]提出了四種混合規(guī)劃模型和一種約束規(guī)劃模型用于求解DFJSP,以最小化最大完工時(shí)間為優(yōu)化目標(biāo),在不同規(guī)模的DFJSP上進(jìn)行了有效性驗(yàn)證。吳秀麗等[7]構(gòu)建了以總成本和提前/延期為優(yōu)化目標(biāo)的雙目標(biāo)DFJSP模型,并利用改進(jìn)的差分進(jìn)化算法進(jìn)行求解。LI等[8]以最小化最大完工時(shí)間、最大工作負(fù)載、總負(fù)載和提前/延誤為優(yōu)化目標(biāo),構(gòu)建了多目標(biāo)DFJSP模型,并設(shè)計(jì)了混合禁忌搜索算法用于求解模型。其他一些學(xué)者在DFJSP的基礎(chǔ)上,考慮了一些更加復(fù)雜的約束,以使模型更適合實(shí)際生產(chǎn)環(huán)境,例如王凌等[9]、DU等[10]、張洪亮等[11]研究了考慮運(yùn)輸時(shí)間的分布式綠色柔性作業(yè)車(chē)間的調(diào)度問(wèn)題,并分別利用協(xié)同群智能算法、混合分布估計(jì)算法、改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解;XU等[12]考慮部分工件的操作需要外包的情況,構(gòu)建了多目標(biāo)DFJSP模型,并將遺傳算法和禁忌搜索算法相結(jié)合對(duì)模型進(jìn)行求解;LUO等[13]同時(shí)考慮了運(yùn)輸時(shí)間和允許工件操作外包的情況,構(gòu)建了多目標(biāo)DFJSP模型,并提出了一種模因算法用于求解模型;郭晨等[14]以最小化生產(chǎn)成本和拖期時(shí)間為目標(biāo),建立了分布式裝配柔性模糊車(chē)間調(diào)度模型,并利用混合分布估計(jì)算法進(jìn)行求解。還有一些學(xué)者結(jié)合實(shí)際生產(chǎn)案例對(duì)DFJSP進(jìn)行了研究,例如TANG等[15]以砂型鑄造作業(yè)車(chē)間為例,構(gòu)建了以最小化最大完工時(shí)間為目標(biāo)的DFJSP模型,通過(guò)試驗(yàn)證明了所提出的混合教學(xué)優(yōu)化算法的有效性;SANG等[16]基于分布式智能工廠生產(chǎn)系統(tǒng),構(gòu)建了多目標(biāo)DFJSP模型,并提出了一種模因算法用于求解模型,最后利用機(jī)床部件生產(chǎn)廠的生產(chǎn)信息進(jìn)行了試驗(yàn)。

以上學(xué)者針對(duì)DFJSP以及帶運(yùn)輸時(shí)間或允許工序外包的DFJSP模型進(jìn)行了研究,提高了模型的實(shí)用性。文獻(xiàn)[15-16]則分別基于砂型鑄造作業(yè)車(chē)間和機(jī)床部件生產(chǎn)廠的調(diào)度需求,對(duì)具體案例進(jìn)行了建模和求解。然而,該類(lèi)研究?jī)H考慮了調(diào)度過(guò)程中的機(jī)器柔性,而在集裝配和加工一體化的分布式多柔性裝配作業(yè)車(chē)間調(diào)度問(wèn)題(distributed and multi-flexible assembly job-shop scheduling problem, DMFAJSP)中,還需要考慮工人安排柔性和工序順序柔性[17-19]。

目前已有一些研究,在調(diào)度過(guò)程中考慮了工序順序柔性[20]和工人安排柔性。例如,胡瑞淇等[21]基于表達(dá)式樹(shù)結(jié)構(gòu)建立了考慮工序順序柔性的作業(yè)車(chē)間調(diào)度問(wèn)題(flexible job-shop scheduling problem, FJSP)模型,設(shè)計(jì)了一種工序順序的隨機(jī)生成方式,并以遺傳算法為例設(shè)計(jì)了求解流程;ZHANG等[22]研究了考慮工藝順序柔性的FJSP,構(gòu)建了帶裝配的FJSP模型,并利用分布式蟻群算法進(jìn)行求解;董海等[23]構(gòu)建了具有機(jī)器、工人和工序多柔性的FJSP模型,并設(shè)計(jì)了離散回溯搜索算法進(jìn)行求解;VITAL-SOTO等[24]利用有向無(wú)環(huán)圖表示工序的操作優(yōu)先級(jí),建立了具有排序柔性的雙資源約束FJSP模型,提出了帶有創(chuàng)新算子的精英非支配排序遺傳算法用于求解模型。

這些研究提供了工序順序柔性的表示方式,為構(gòu)建DMFAJSP模型提供了參考。然而,上述考慮工序順序柔性和工人安排柔性的調(diào)度研究都限定在單個(gè)柔性作業(yè)車(chē)間范圍內(nèi),缺乏對(duì)分布式多柔性制造系統(tǒng)的調(diào)度研究。因此,本文將對(duì)考慮工序順序柔性、工人安排柔性和機(jī)器選擇柔性的DMFAJSP進(jìn)行研究。

DMFAJSP需要對(duì)四個(gè)子調(diào)度問(wèn)題進(jìn)行決策,包括將工件分配給工廠、為工序執(zhí)行順序排序、為工序安排操作工人和為工序選擇機(jī)器。由于DMFAJSP的調(diào)度過(guò)程和可行解的結(jié)構(gòu)較為復(fù)雜,本文將采用模因算法(memetic algorithm, MA)進(jìn)行求解,該算法可以同時(shí)進(jìn)行全局搜索和局部搜索。

目前已有一些學(xué)者基于遺傳算法如NSGA-Ⅱ[13,25-26]、NSGA-Ⅲ[16]等,結(jié)合各類(lèi)局部搜索算子設(shè)計(jì)了模因算法,并通過(guò)大量試驗(yàn)證明了模因算法在求解DFJSP問(wèn)題上具有良好的性能。與遺傳算法通過(guò)交叉變異等操作產(chǎn)生種群的方法不同,分布估計(jì)算法(estimation of distribution algorithm, EDA)通過(guò)空間采樣和統(tǒng)計(jì)學(xué)習(xí),預(yù)測(cè)未來(lái)的搜索空間[27-28],從而利用概率模型解決多維調(diào)度問(wèn)題。EDA算法具有顯著的全局搜索優(yōu)勢(shì),但同時(shí)存在局部搜索能力較弱和易收斂早熟的缺點(diǎn)[14]。而模因算法通過(guò)將基于種群的全局搜索和基于個(gè)體的局部搜索相結(jié)合,可以有效提高算法的尋優(yōu)能力[29]。

因此,本文嘗試根據(jù)DMFAJSP的特點(diǎn),提出一種以分布估計(jì)算法作為全局搜索組件,以一些鄰域搜索算子作為局部搜索組件的多維模因算法(multi-dimensional memetic algorithm, MDMA)。通過(guò)與其他算法進(jìn)行對(duì)比試驗(yàn),驗(yàn)證所提算法在求解DMFAJSP模型上的有效性。

1 DMFAJSP問(wèn)題及模型

1.1 具有工序順序柔性的作業(yè)車(chē)間調(diào)度問(wèn)題

工件的工序順序柔性分為圖1所示的5種柔性等級(jí)[17],可以看出:當(dāng)圖1c中每個(gè)優(yōu)先級(jí)中只有一道工序時(shí),與圖1a情況相同;當(dāng)圖1c中只存在一種優(yōu)先級(jí)時(shí),與圖1b情況相同;而圖1d和圖1e則可以看作圖1c的組合與變形。因此本文以圖1c工序順序非完全確定性工件為代表,研究考慮該類(lèi)工序順序柔性的DMFAJSP。

(a)工序順序完全確定

1.2 分布式多柔性裝配作業(yè)車(chē)間調(diào)度問(wèn)題

在分布式多柔性裝配作業(yè)車(chē)間的環(huán)境中,裝配和加工過(guò)程被統(tǒng)一作為工序進(jìn)行調(diào)度。DMFAJSP具有地理分布式、多柔性以及集加工和裝配一體化的特點(diǎn),除了上述提到的工序順序柔性外,本文還考慮了工人安排柔性和機(jī)器選擇柔性。該問(wèn)題中有F個(gè)柔性工廠U,每個(gè)工廠Uf(f=1,2,…,F)中有Wf名工人,每名工人均會(huì)操作多臺(tái)機(jī)器,Uf中的機(jī)器數(shù)量為Mf,每一臺(tái)機(jī)器均具有多種加工功能。假設(shè)該問(wèn)題中有N個(gè)工件J需要處理,工件Jn的工序有Rn個(gè)優(yōu)先級(jí),工件Jn中優(yōu)先級(jí)為r的工序O有Knr個(gè)。其中,同一工件的工序若具有同樣的優(yōu)先級(jí),則工序加工無(wú)次序要求;否則,低優(yōu)先級(jí)的工序需在所有高優(yōu)先級(jí)的工序加工完成后才可以進(jìn)行加工。在DMFAJSP中,工序由不同的工人和機(jī)器組合進(jìn)行加工時(shí),加工時(shí)間可能不同。

1.3 相關(guān)假設(shè)

本文以最小化最大完工時(shí)間和總能耗為優(yōu)化目標(biāo),相關(guān)的假設(shè)如下:

(1)每個(gè)工件只能由一個(gè)工廠進(jìn)行加工;

(2)屬于同一工件的工序,加工順序受優(yōu)先級(jí)約束,不同工件間的工序無(wú)優(yōu)先級(jí)約束;

(3)每個(gè)工人均會(huì)操作多臺(tái)機(jī)器,每臺(tái)機(jī)器均可以加工多道工序;

(4)一個(gè)工人同一時(shí)刻只能操作一臺(tái)機(jī)器,一臺(tái)機(jī)器同一時(shí)刻只能加工一道工序;

(5)工序加工不可中斷,直至該工序加工結(jié)束。

1.4 符號(hào)定義

DMFAJSP模型的數(shù)學(xué)描述中使用的符號(hào)及其含義如表1所示。

表1 符號(hào)表

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

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

minMK=max(Tn) ?n

(1)

minTE=EP+EI

(2)

其中,

(3)

?f,w,m,n

(4)

?w,n,r,k

(5)

?w,n,r,k

式(1)和式(2)為目標(biāo)函數(shù),式(1)表示最小化最大完工時(shí)間,其中Tn的計(jì)算方式如式(3)所示;式(2)表示最小化總能耗,為所有機(jī)器的加工能耗和空轉(zhuǎn)能耗的總和,所有機(jī)器的總加工能耗的計(jì)算如式(4)所示,總空轉(zhuǎn)能耗的計(jì)算如式(5)所示。

約束條件:

(6)

(7)

(8)

(9)

(10)

Efwmnrk=Sfwmnrk+Pfwmnrk?f,w,m,n,r,k

(11)

Sfwmnrk≥max(Efwmn(r-1)k|k=1,2,…,knr)

(12)

?f,w,m,n,r∈[2,Rn]

Lwm′-Lwm≥V·(Gwmm′-1) ?w,m,m′

(13)

Efwmn′r′k′-Efwmnrk≥Pfwmn′r′k′+V·(Dnrkn′r′k′-1)

(14)

?f,w,m,n,r,k

(Sfwmnrk-Lwm)·Cfwmnrk≥0

(15)

(16)

(17)

約束條件中式(6)和式(7)表示每個(gè)工件只能分配給一個(gè)工廠,每個(gè)工廠可以分配到0至N個(gè)工件;式(8)表示工人為多能工,均會(huì)操作多臺(tái)機(jī)器;式(9)表示每臺(tái)機(jī)器都可以處理多道工序;式(10)保證每道工序只由一名工人操作一臺(tái)機(jī)器加工;式(11)保證工序加工不中斷,直到該工序結(jié)束;式(12)表示屬于同一工件的工序,需在所有高優(yōu)先級(jí)的工序加工完成后,才可以進(jìn)行低優(yōu)先級(jí)工序的加工;式(13)和式(14)表示同一時(shí)刻,每名工人只能操作一臺(tái)機(jī)器,每臺(tái)機(jī)器只能加工一道工序;式(15)表示每道工序只有在約定工人空閑時(shí)才可以開(kāi)始加工;式(16)表示每名工人只能操作其會(huì)操作的機(jī)器且機(jī)器只能加工其可以加工的工序;式(17)保證所有工件的工序總數(shù)為所有工件中各優(yōu)先級(jí)所包含的工序數(shù)量的總和。

1.6 問(wèn)題案例

為了更好地理解DMFAJSP,以2個(gè)柔性工廠的生產(chǎn)環(huán)境為例{U1:[[w1,w2],[m1,m2,m3]],U2:[[w1,w2],[m1,m2]]},每個(gè)工廠各有2名操作工人以及分別有3臺(tái)和2臺(tái)機(jī)器,有3個(gè)工件{J1:[[2],[2],[1]],J2:[[1],[3],[1]],J3:[[1],[2],[2],[1]]}待分配,其中工件J1的工序具有3個(gè)優(yōu)先級(jí),每個(gè)優(yōu)先級(jí)中分別有2道、2道和1道工序,其他工件的優(yōu)先級(jí)和工序數(shù)量的表示方法與J1類(lèi)似。工廠U1中工人W1所對(duì)應(yīng)的Q11矩陣如表2所示,其他工人對(duì)應(yīng)的Q矩陣與Q11類(lèi)似。該案例在U1和U2中的一種調(diào)度安排結(jié)果如圖2所示。

表2 案例問(wèn)題中U1的Q表

(a)U1

2 應(yīng)用MDMA算法求解DMFAJSP

本文針對(duì)DMFAJSP可行解的多維特點(diǎn)構(gòu)建了MDMA算法,該算法綜合運(yùn)用全局搜索和局部搜索進(jìn)行尋優(yōu)。其中全局搜索組件以分布估計(jì)算法為核心,局部搜索組件包括3種鄰域搜索算子。

2.1 編碼與解碼

由于DMFAJSP問(wèn)題可以根據(jù)需求將其分解為四個(gè)子問(wèn)題:為工件分配工廠,為工序加工順序排序,為工序分配加工工人以及為工序選擇加工機(jī)器,因此,本文設(shè)計(jì)了多維編碼方案來(lái)表示DMFAJSP模型的可行解。如圖3中的編碼圖所示,每個(gè)解包含4個(gè)變量,各變量的釋義如下:

圖3 編碼與解碼

UJ表示工件-工廠的分配方案,該變量中的數(shù)字代表工廠編號(hào),位置索引表示工件編號(hào);

WS表示工人序列,該變量中的數(shù)字代表工人編號(hào),工人編號(hào)的排列順序與OS對(duì)應(yīng),即WS某位置上的工人將被安排加工OS對(duì)應(yīng)位置上的工序;

MS表示機(jī)器序列,該變量中的數(shù)字代表機(jī)器編號(hào),機(jī)器編號(hào)的排列順序與OS和WS對(duì)應(yīng),即MS某位置上的機(jī)器被安排由WS中對(duì)應(yīng)位置上的工人操作,一起加工OS中對(duì)應(yīng)位置的工序;

圖3中的甘特圖展示了編碼示意圖中各變量彩色代碼的解碼結(jié)果,即工件J1的各工序在U1中被工廠內(nèi)的工人和機(jī)器加工的調(diào)度安排。

2.2 概率模型

EDA算法中的概率模型用于描述候選解的分布信息,在迭代過(guò)程中通過(guò)對(duì)精英解和前代概率矩陣的統(tǒng)計(jì)學(xué)習(xí)完成概率矩陣的更新,從而實(shí)現(xiàn)解的進(jìn)化。本文根據(jù)DMFAJSP的多維編碼方案,構(gòu)建了概率模型UJM、OSM和WMM對(duì)應(yīng)的概率矩陣MUJM、MOSM、MWMM用于抽樣生成種群。

2.2.1概率模型的構(gòu)建

MUJM是工件-工廠分配概率矩陣,其元素unf表示第n個(gè)工件Jn分配到第f個(gè)工廠Uf進(jìn)行加工的概率。MUJM在第0代的初始狀態(tài)為

(18)

第g次迭代過(guò)程中的更新方式為

(19)

(20)

?n,f,z∈[1,μ·P]

其中,α為學(xué)習(xí)率;μ為每代種群的精英選擇率,本文設(shè)置為0.2;P為種群。

MOSM是工序序列概率矩陣,其元素sni表示工件Jn的工序出現(xiàn)在第i個(gè)位置上的概率,其中i∈[1,K]。MOSM的初始狀態(tài)為

(21)

在迭代過(guò)程中的更新方式為

(22)

?n,i

(23)

?n,i,z∈[1,P]

其中,β為學(xué)習(xí)率。

(24)

?f,w,m,n,k

在迭代過(guò)程中的更新方式為

(25)

?f,w,m,n,k

yfwmnk(g)=(1-γ)·yfwmnk(g-1)+γ·ρ

(26)

?f,w,m,i

(27)

(28)

其中,γ為學(xué)習(xí)率。

2.2.2概率模型的通用性證明

為保證概率模型的通用性,需確保以下條件成立:

本文利用數(shù)學(xué)歸納法給出與條件(1)、(2)和(3)相關(guān)的模型通用性證明,如引理1、引理2和引理3所示。

證明:當(dāng)g= 0 時(shí),有

(29)

(30)

證明成立。

證明:當(dāng)g=0時(shí),有

(31)

(32)

證明:當(dāng)g= 0時(shí),有

(33)

(34)

(35)

2.3 種群

2.3.1初始化種群

初始化種群采用全局生成方式、局部生成方式和隨機(jī)生成方式,按照6∶3∶1的比例[9,13]生成。

全局生成方式:將工件分配給加工其所有工序總用時(shí)最少的工廠。

局部生成方式:為工件隨機(jī)分配一個(gè)工廠,然后在該工廠為每道工序選擇可用的且用時(shí)最少的工人和機(jī)器組合進(jìn)行加工。

隨機(jī)生成方式:將工件隨機(jī)分配給一個(gè)工廠,并為每一道工序隨機(jī)安排加工機(jī)器和操作工人。

2.3.2抽樣生成種群

在迭代過(guò)程中,通過(guò)采樣2.2節(jié)中的概率模型生成UJ、OS、WS和MS變量組成新的個(gè)體。為方便操作,分別對(duì)UJM、OSM和WMM模型的概率矩陣MUJM、MOSM和MWMM中的元素進(jìn)行累加,形成輔助矩陣MUJSM、MOSSM和MWMSM。第g代輔助矩陣中的元素u′nf(g)、s′ni(g)和y′fwmnk(g)如下所示:

(36)

(37)

(38)

在一次迭代過(guò)程中,利用輔助矩陣生成變量UJ、OS、WS和MS的過(guò)程如算法1、算法2和算法3所示。

算法1抽樣生成UJ

輸入:MUJSM

輸出:UJ

01: forn←1 toNdo

02:θ1←random(0,1)

03: forf←1 toFdo

04: ifθ1

05:UJ[n]←f

06: end if

07: end for

08: end for

算法2抽樣生成OS

輸入:MOSSM

輸出:OS,OK

01: forn←1 toNdo

03:θ2←random(0,1)

04: fori←1 toKdo

05: ifθ2

06:OS[i]←n

07:OK[i]←k

08: forj←1 toNdo

09:ossni← 0

10: end for

11: end if

12: end for

13: end for

14: end for

算法3抽樣生成WM

輸入:UJ,OS,OK,MWMSM

輸出:WM

01: fori←1 toKdo

02:n←OS[i]

03:f←UJ[n]

04:k←OK[i]

05:θ3←random(0,1)

06: forw←1 toWfdo

07: form←1 toMfdo

08: ifθ3

09:MS[i]←m

10:WS[i]←w

11: end if

12: break

13: end for

14: end for

15: end for

2.4 局部搜索算子

本文設(shè)計(jì)了3種鄰域結(jié)構(gòu)NS1、NS2、NS3,以提高種群多樣性和收斂速度。鄰域結(jié)構(gòu)的性能取決于鄰域結(jié)構(gòu)的連通性和規(guī)模[30],只有對(duì)關(guān)鍵路徑上的工序進(jìn)行操作才有可能減少最大完工時(shí)間[31]。因此,本文針對(duì)UJ變量設(shè)計(jì)了鄰域結(jié)構(gòu)Ⅰ,并基于關(guān)鍵路徑構(gòu)建了針對(duì)OS、WS和MS變量的鄰域結(jié)構(gòu)Ⅱ和Ⅲ。具體操作如下所示:

(1)鄰域結(jié)構(gòu)Ⅰ。選擇完工時(shí)間最晚工廠,將其中最后完工的工件分配給最早完工的工廠。工序序列保持不變,將原工廠中為該工件工序分配的工人和機(jī)器編號(hào)剔除,并在新工廠中隨機(jī)為該工件的工序安排工人和機(jī)器。

(2)鄰域結(jié)構(gòu)Ⅱ。如圖4所示,首先,對(duì)原個(gè)體中的變量對(duì)應(yīng)關(guān)系進(jìn)行存檔。然后,在關(guān)鍵路徑(OS變量中填充陰影的工序)中隨機(jī)選擇一個(gè)關(guān)鍵工序,將其移動(dòng)到頭關(guān)鍵工序之前(或尾關(guān)鍵工序之后),并為移動(dòng)后的工序選擇加工時(shí)間最小的工人和機(jī)器。其他工序的加工工人和機(jī)器依照之前存檔的對(duì)應(yīng)信息保持不變。

圖4 鄰域結(jié)構(gòu)Ⅱ示意圖

(3)鄰域結(jié)構(gòu)Ⅲ。首先,對(duì)原個(gè)體中的變量對(duì)應(yīng)關(guān)系存檔。然后,在關(guān)鍵路徑上隨機(jī)選擇一個(gè)與頭關(guān)鍵工序(或尾關(guān)鍵工序)不屬于同一工件的工序,并將該工序與頭關(guān)鍵工序(或尾關(guān)鍵工序)進(jìn)行位置交換。所有工序?qū)?yīng)的加工工人和機(jī)器與存檔中的對(duì)應(yīng)信息保持一致。

2.5 算法框架

本文設(shè)計(jì)的MDMA框架如圖5所示。首先,根據(jù)2.3.1節(jié)中的初始化種群策略生成初始種群。接著,對(duì)初始化種群進(jìn)行局部搜索,根據(jù)貪心策略保留初始個(gè)體或其鄰域解。然后進(jìn)行全局搜索,按照2.2.2節(jié)中描述的方法通過(guò)快速非支配排序和擁擠距離篩選精英解。根據(jù)2.3.2節(jié)的方法,利用新的概率模型抽樣生成新一代種群。再對(duì)新種群循環(huán)進(jìn)行局部搜索和全局搜索,直到達(dá)到迭代停止條件,輸出最終的帕累托前沿解。

圖5 MDMA框架

3 試驗(yàn)與分析

本文試驗(yàn)采用python3編程語(yǔ)言進(jìn)行編寫(xiě),運(yùn)行環(huán)境為Intel Core i7, 3.6 GHz,4×8 GB RAM。為驗(yàn)證MDMA在求解DMFAJSP方面的有效性,將MDMA與EDA、NSGA-Ⅱ[32]和HEDA(hybrid estimation of distribution algorithm)[14]進(jìn)行對(duì)比試驗(yàn)。本文算例為基于BRANDIMARTE[33]提出的MK01-10算例,擴(kuò)展形成的20個(gè)試驗(yàn)算例,如表3所示。

表3 試驗(yàn)算例

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

MDMA需要確定的參數(shù)包括:種群規(guī)模popsize、精英選擇率μ和3個(gè)概率模型的學(xué)習(xí)率α、β、γ。通過(guò)田口試驗(yàn)[34]確定參數(shù)的最優(yōu)組合,其中每個(gè)因素設(shè)置4個(gè)水平,并采用L16(45)正交表進(jìn)行試驗(yàn)設(shè)計(jì)。測(cè)試算例為表3中的算例10,迭代停止時(shí)間設(shè)置為100 s,每組參數(shù)組合獨(dú)立運(yùn)行10次。參數(shù)試驗(yàn)的評(píng)價(jià)指標(biāo)選用多目標(biāo)偏差和(objectives deviation sum, ODS)[13],其計(jì)算方法如下所示:

(39)

i=1,2,…,9n=1,2,…,in

其中,in為算法基于參數(shù)組合i得到的前沿解總數(shù)量;bjn為第n個(gè)前沿解第j個(gè)目標(biāo)的值。參數(shù)組合及10次運(yùn)行的平均ODS如表4所示,參數(shù)水平趨勢(shì)如圖6a所示,根據(jù)參數(shù)水平趨勢(shì)確定MDMA的最優(yōu)參數(shù)組合為:α=0.5,β=0.3,γ=0.4,μ=0.2,popsize=150。

表4 MDMA算法參數(shù)組合及平均ODS

(a)MDMA

此外,為保證對(duì)比算法的公平性,對(duì)比算法的最優(yōu)參數(shù)組合同樣采用田口試驗(yàn)設(shè)計(jì)方法進(jìn)行設(shè)置。對(duì)比算法的參數(shù)及水平如表5所示,其中NSGA-Ⅱ的參數(shù)cr為交換率,mu為變異率;HEDA中的f為縮放因子?；趯?duì)比算法的參數(shù)數(shù)量,分別采用L16(45)、L9(33)、L16(44)正交表進(jìn)行參數(shù)組合試驗(yàn)。各算法的參數(shù)水平趨勢(shì)如圖6所示,EDA的最優(yōu)參數(shù)組合為:α=0.5,β=0.2,γ=0.4,μ=0.2,popsize=50;NSGA-Ⅱ的最優(yōu)參數(shù)組合為:popsize=50,cr=0.6,mu=0.1;HEDA的最優(yōu)參數(shù)組合為:α=0.4,f=0.2,cr=0.2,popsize=150。

表5 對(duì)比算法參數(shù)水平

3.2 對(duì)比試驗(yàn)及結(jié)果分析

為測(cè)試所提算法MDMA對(duì)求解DMFAJSP模型的性能,本文將MDMA與EDA、NSGA-Ⅱ和HEDA進(jìn)行對(duì)比。其中EDA算法為不包含局部搜索算子的MDMA,因此通過(guò)對(duì)比MDMA與EDA,可以驗(yàn)證MDMA中局部搜索算子的有效性。所有算法的初始種群生成方式一致。所有算法在每個(gè)算例上獨(dú)立運(yùn)行10次。由于NSGA-Ⅱ是解決車(chē)間調(diào)度類(lèi)問(wèn)題最為經(jīng)典的算法之一,為保證試驗(yàn)公平,對(duì)于每個(gè)算例,所有算法的運(yùn)行時(shí)間統(tǒng)一設(shè)定為NSGA-Ⅱ迭代100次所需的時(shí)間。

對(duì)比試驗(yàn)的評(píng)價(jià)指標(biāo)選擇常見(jiàn)的世代距離(generational distance, GD)、反轉(zhuǎn)世代距離(inverted generational distance, IGD)和解集覆蓋率(coverage,C)指標(biāo),各指標(biāo)的計(jì)算公式如下:

(40)

(41)

(42)

試驗(yàn)結(jié)果如表6～表8和圖7所示。其中,表6展示了對(duì)比試驗(yàn)中每個(gè)算法在每個(gè)算例上運(yùn)行10次得到的最小MK、TE的非支配解。對(duì)比試驗(yàn)的平均GD、IGD指標(biāo)結(jié)果和每個(gè)算例的運(yùn)行時(shí)間如表7所示,C指標(biāo)如表8所示。此外,利用箱形圖展示了對(duì)比算法C指標(biāo)的分布情況,如圖7所示。

表6 對(duì)比試驗(yàn)最小單目標(biāo)值的非支配解

表7 對(duì)比試驗(yàn)的平均GD和平均IGD

表8 對(duì)比試驗(yàn)的C指標(biāo)

圖7 C指標(biāo)箱線圖

表6中第1列表示算例編號(hào),第2列表示MDMA算法在每個(gè)算例上10次運(yùn)行結(jié)果中得到的最小MK對(duì)應(yīng)的非支配解,第3列表示其得到的最小TE對(duì)應(yīng)的非支配解,后續(xù)4～9列分別表示EDA、NSGA-Ⅱ和HEDA獲得的最小MK和TE對(duì)應(yīng)的非支配解。從表6中可以看出,MDMA在75%的算例上取得的MK最小值優(yōu)于其他算法,且在85%的算例上取得的TE最小值優(yōu)于其他算法。由表7可以看出,除了算例11,MDMA的GD和 IGD指標(biāo)均優(yōu)于EDA,說(shuō)明MDMA求得的解在收斂性和多樣性方面均優(yōu)于EDA。結(jié)合表8和圖7中C(MDMA,EDA)、C(EDA,MDMA)指標(biāo)及分散情況,MDMA獲得的非支配解占比均高于EDA,可以驗(yàn)證MDMA中局部搜索算子可以顯著提高M(jìn)DMA的解的質(zhì)量。另外,從表7、表8和圖7中可以看出MDMA的GD、IGD和C指標(biāo)均優(yōu)于NSGA-Ⅱ和HEDA,說(shuō)明MDMA算法所求得的解在收斂性、多樣性以及非支配解占比方面均優(yōu)于NSGA-Ⅱ和HEDA求得的解。驗(yàn)證了MDMA算法在求解DMFAJSP問(wèn)題上具有明顯優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文針對(duì)分布式多柔性裝配作業(yè)車(chē)間的調(diào)度問(wèn)題,構(gòu)建了以最小化最大完工時(shí)間和最小化總能耗為優(yōu)化目標(biāo)的數(shù)學(xué)模型。該模型考慮了調(diào)度過(guò)程中存在的機(jī)器選擇柔性、工人安排柔性和工序順序柔性。為了求解該模型,本文提出了一種多維模因算法(MDMA)。首先,根據(jù)調(diào)度模型的特點(diǎn),設(shè)計(jì)了多維編碼方案,用于表示問(wèn)題模型的可行解。隨后,在MDMA算法的全局搜索階段,根據(jù)編碼方案設(shè)計(jì)了3種概率模型,用于抽樣生成種群。并且,為了驗(yàn)證概率模型的通用性,采用數(shù)學(xué)歸納法進(jìn)行了推理和證明。在MDMA的局部搜索階段,設(shè)計(jì)了3種鄰域結(jié)構(gòu),其中有2種鄰域結(jié)構(gòu)基于關(guān)鍵路徑進(jìn)行設(shè)計(jì),以有效提高算法的局部搜索效率。最后,在20個(gè)分布式多柔性裝配作業(yè)車(chē)間調(diào)度問(wèn)題(DMFAJSP)算例上,將所提算法與分布估計(jì)算法、遺傳算法和混合分布估計(jì)算法進(jìn)行了對(duì)比。結(jié)果驗(yàn)證了所提MDMA算法對(duì)于求解DMFAJSP問(wèn)題具有顯著優(yōu)勢(shì)。

此外,本文在研究分布式多柔性裝配作業(yè)車(chē)間的調(diào)度問(wèn)題時(shí),僅考慮了靜態(tài)的調(diào)度過(guò)程。后續(xù)將對(duì)更復(fù)雜的動(dòng)態(tài)DMFAJSP模型進(jìn)行研究。