基于強(qiáng)繁殖NSGA-Ⅱ算法的柔性車間調(diào)度多目標(biāo)優(yōu)化*

朱旭東

(無(wú)錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興 214200)

0 引言

根據(jù)市場(chǎng)的多變性和客戶的多樣性需求，產(chǎn)品的多樣化和小批量生產(chǎn)成了生產(chǎn)制造行業(yè)的主流模式，傳統(tǒng)單一品種大批量生產(chǎn)的剛性車間已經(jīng)無(wú)法滿足市場(chǎng)需求，使得柔性制造車間不斷涌現(xiàn)。對(duì)于柔性作業(yè)車間，產(chǎn)品的每道工序可由多個(gè)機(jī)器加工而成，因此存在產(chǎn)品的加工順序和工序的機(jī)器分配等諸多調(diào)度問題[1]。不同的調(diào)度方案對(duì)應(yīng)的完工時(shí)間、機(jī)器能耗、機(jī)器負(fù)荷也不同，因此研究車間調(diào)度問題具有重要的實(shí)際意義。

根據(jù)優(yōu)化目標(biāo)的數(shù)量，可以將柔性車間調(diào)度問題分為單目標(biāo)調(diào)度問題和多目標(biāo)調(diào)度問題。單目標(biāo)調(diào)度研究主要集中在最小化完工時(shí)間這一目標(biāo)上，文獻(xiàn)[2]在差分進(jìn)化算法中引入了一種新的轉(zhuǎn)化方法，使其能夠有效求解柔性車間調(diào)度問題，實(shí)現(xiàn)了對(duì)柔性車間完工時(shí)間的優(yōu)化。文獻(xiàn)[3]以最小化完工時(shí)間為車間優(yōu)化目標(biāo)，在算法中引入了反向?qū)W習(xí)策略和Metropolis準(zhǔn)則，實(shí)驗(yàn)驗(yàn)證了該方法在車間調(diào)度中的優(yōu)越性。多目標(biāo)優(yōu)化處理的多個(gè)目標(biāo)間一般存在沖突問題，一般包括先驗(yàn)法和后驗(yàn)法兩類。先驗(yàn)法是指根據(jù)先驗(yàn)知識(shí)為每個(gè)目標(biāo)線性加權(quán)得到單個(gè)目標(biāo)，文獻(xiàn)[4]針對(duì)柔性車間多目標(biāo)調(diào)度問題，提出了混合TS算法的求解方法。文獻(xiàn)[5]針對(duì)質(zhì)檢引起的完工時(shí)間延遲和耗能升高問題，提出了改進(jìn)頭腦風(fēng)暴的求解方法，在保證交付時(shí)間約束下降低了車間能耗。先驗(yàn)法中精準(zhǔn)確定每個(gè)目標(biāo)的權(quán)重非常困難，需要大量經(jīng)驗(yàn)的積累，而且基于聚合的方法無(wú)法解決Pareto解集非凸的問題，因此后驗(yàn)法成為了解決柔性車間多目標(biāo)優(yōu)化的熱點(diǎn)方法。文獻(xiàn)[6]設(shè)計(jì)了新的適應(yīng)度分配策略，有效解決了柔性車間完工時(shí)間、機(jī)器負(fù)荷等目標(biāo)的優(yōu)化。文獻(xiàn)[7]在粒子群算法中引入了鄰域搜索算法和無(wú)需半徑共享的小生境技術(shù)，實(shí)驗(yàn)驗(yàn)證了該方法在完工時(shí)間、車間總負(fù)荷、均負(fù)荷等多目標(biāo)優(yōu)化中的優(yōu)越性?；诤篁?yàn)法的柔性車間調(diào)度方法很多，但是多數(shù)在全局搜索和局部開發(fā)上存在矛盾，因此兩者的平衡是當(dāng)前研究的一個(gè)重要方向。

針對(duì)柔性車間調(diào)度的多目標(biāo)優(yōu)化問題，建立了以減小完工時(shí)間、機(jī)器總負(fù)荷和車間能耗為目標(biāo)的多目標(biāo)優(yōu)化模型，提出了強(qiáng)繁殖NSGA-Ⅱ算法的模型求解方法，實(shí)現(xiàn)了減小完工時(shí)間、機(jī)器負(fù)荷、車間能耗的優(yōu)化目標(biāo)。

1 柔性車間調(diào)度問題描述與建模

1.1 問題描述

柔性車間調(diào)度問題描述如下：車間需加工N個(gè)工件，記為{J1,J2,…,JN}；每個(gè)工件由若干個(gè)工序加工而成，以工件Ji為例其加工工序可記為Ji={Oi1,Oi2,…,Oij}，式中Oij為工件Ji的第j道工序；車間可提供的機(jī)器設(shè)備為K個(gè)，記為{M1,M2,…,MK}，每道工序Oij對(duì)應(yīng)一個(gè)可選機(jī)器集合，記為Mij。需解決的問題是，為各道工序選擇合適的加工設(shè)備、合理的加工時(shí)間，在滿足生產(chǎn)工藝約束的前提下，實(shí)現(xiàn)完工時(shí)間最小、機(jī)器總負(fù)荷最小、總能耗最低等目標(biāo)。

柔性車間調(diào)度問題需滿足的約束條件包括：

(1)在同一時(shí)刻，每個(gè)機(jī)器最多加工一道工序；

(2)工件之間的加工順序完全獨(dú)立，但是同一零件的工序間必須滿足順序要求；

(3)各工序開始加工后，不允許中斷。

柔性車間可以分為完全柔性車間和部分柔性車間[8]，完全柔性車間是指每道工序都可由車間內(nèi)任意機(jī)器加工，部分柔性車間是指每道工序只能由車間內(nèi)部分機(jī)器加工，其中部分柔性車間更加普遍，因此本文研究的是部分柔性車間調(diào)度問題。

1.2 柔性車間調(diào)度優(yōu)化模型

本文針對(duì)柔性車間的調(diào)度問題，設(shè)置3個(gè)優(yōu)化目標(biāo)，分別為完工時(shí)間最短、機(jī)器總負(fù)荷最小、車間總能耗最少。

(1)完工時(shí)間最短。工件的完工時(shí)間是指工件最后一道工序的完工時(shí)間，而車間的完工時(shí)間是指所有工件中最晚的完工時(shí)間，為：

(1)

式中，Ci為工件Ji的完工時(shí)間，f1為車間完工時(shí)間優(yōu)化的目標(biāo)函數(shù)。

(2)機(jī)器總負(fù)荷最小。車間內(nèi)機(jī)器負(fù)荷隨調(diào)度方案的變化而變化，減小車間內(nèi)機(jī)器總負(fù)荷可以有效提高機(jī)器的使用壽命，因此以減小車間內(nèi)機(jī)器總負(fù)荷為一個(gè)優(yōu)化目標(biāo)，即：

(2)

式中，f2為車間機(jī)器總負(fù)荷最小化目標(biāo)函數(shù)，hi為工件Ji的工序數(shù)量，tijk為工序Oij在機(jī)器Mk上的加工時(shí)間，xijk為工序Oij在機(jī)器Mk上的加工標(biāo)識(shí)，即：

(3)車間能耗最少。柔性生產(chǎn)車間的能耗包括加工能耗、空載能耗、轉(zhuǎn)運(yùn)能耗和固定能耗等，為：

(3)

(4)

式中，sij為工序Oij的開始時(shí)間，Ci為工件Ji的完工時(shí)間，cij為工序Oij的結(jié)束時(shí)間，Cmax=maxCi為車間完工時(shí)間。

式(4)中第1式表示工序Oij的結(jié)束時(shí)間應(yīng)小于工件Ji的完工時(shí)間，第2式表示工序Oij的結(jié)束時(shí)間應(yīng)小于工序Oi(j+1)的開始時(shí)間，第3式表示工序Oij只需加工一次，第4式表示工序Oij的開始時(shí)間和結(jié)束時(shí)間均應(yīng)為正值。

1.3 編碼與甘特圖解碼方法

在柔性車間調(diào)度問題中有兩個(gè)問題需要解決，一是確定各工序的生產(chǎn)順序，二是確定各工序的加工機(jī)器。為了同時(shí)解決這兩個(gè)問題，本文使用雙基因鏈編碼方式，基因鏈中的基因長(zhǎng)度與工件的所有工序數(shù)量一致。第一條基因鏈用于確定工序加工順序，第二條基因鏈用于確定各工序?qū)?yīng)的機(jī)器。

以3個(gè)工件加工為例，每個(gè)工件具有3道加工工序，可使用的生產(chǎn)設(shè)備具有3臺(tái)，分別記為M1、M2、M3。假設(shè)某染色體編碼方式如圖1所示。

圖1 染色體編碼方式

圖1中第一條基因鏈確定了工序的加工順序，工件2具有3道工序，因此在第一條基因鏈中出現(xiàn)了3次，第1次出現(xiàn)表示工件2的第1道工序。按照這種規(guī)定，第一條基因鏈對(duì)應(yīng)的工序順序?yàn)椋篛21O31O11O22O32O12O23O13O33，對(duì)應(yīng)的機(jī)器為M2M1M3M3M2M1M1M3M2。

甘特圖可以對(duì)以上編碼和解碼結(jié)果進(jìn)行更加直觀的表達(dá)，圖1中的染色體使用甘特圖可表示如圖2所示。

圖2 圖1對(duì)應(yīng)的甘特圖

由圖2可以直觀看出各工序的加工順序、各工序使用的加工機(jī)器、各工序的加工耗時(shí)、總完工時(shí)間等。因此，柔性車間的調(diào)度結(jié)果一般使用甘特圖給出。

2 強(qiáng)繁殖NSGA-Ⅱ求解算法

2.1 強(qiáng)繁殖NSGA-Ⅱ算法構(gòu)造思路

NSGA-Ⅱ算法原理可參考文獻(xiàn)[9-10]，這里不再贅述。由于NSGA-Ⅱ算法沿襲了遺傳算法中的交叉、變異、自然選擇等操作思路，因此遺傳算法存在的算法收斂性與個(gè)體多樣性之間的矛盾，NSGA-Ⅱ算法也必然存在[11]。為了克服算法的這一缺陷，有效平衡NSGA-Ⅱ算法的多樣性和收斂性，本文提出了具有強(qiáng)繁殖能力的NSGA-Ⅱ算法。

強(qiáng)繁殖NSGA-Ⅱ算法的構(gòu)造思路為，首先定義染色體的繁殖能力，根據(jù)繁殖能力將染色體分為強(qiáng)繁殖個(gè)體和普通個(gè)體。將強(qiáng)繁殖個(gè)體(繁殖能力大于均值)劃為一個(gè)子群，將普通個(gè)體劃分為一個(gè)子群。其中強(qiáng)繁殖子群具有較強(qiáng)的繁殖能力，使用傳統(tǒng)的交叉變異方式即可；普通子群的繁殖能力較弱，使用染色體變化較大的改進(jìn)交叉變異方法。兩個(gè)子群每進(jìn)化5代進(jìn)行一次混合，并重新劃分子群。

2.2 染色體繁殖能力

染色體的繁殖能力以其遺傳操作后的繁殖能力為標(biāo)準(zhǔn)進(jìn)行衡量。將染色體規(guī)模記為N，以染色體n為例對(duì)繁殖能力度量方法進(jìn)行介紹。

步驟2：將測(cè)試染色體逐個(gè)與染色體n進(jìn)行交叉操作，交叉操作使用傳統(tǒng)交叉方式，傳統(tǒng)交叉方法在后文中明確；

步驟3：染色體n交叉后，若2個(gè)子代個(gè)體中存在支配染色體n的個(gè)體，說明實(shí)現(xiàn)了染色體進(jìn)化，此時(shí)染色體n的繁殖能力+1；若2個(gè)子代個(gè)體均無(wú)法支配染色體n，說明染色體未進(jìn)化，此時(shí)染色體n的繁殖能力維持不變；

步驟4：當(dāng)染色體n與所有測(cè)試染色體完成交叉測(cè)試后，計(jì)算染色體n的繁殖能力，迭代過程結(jié)束。

2.3 種群分割與遺傳操作

將所有染色體分為兩個(gè)種群，繁殖能力大于均值的個(gè)體屬于強(qiáng)繁殖能力種群；繁殖能力低于均值的屬于普通種群。下面依據(jù)兩個(gè)種群的特點(diǎn)，為兩個(gè)種群施加不同的遺傳操作。

(1)強(qiáng)繁殖能力種群的遺傳操作。強(qiáng)繁殖能力種群的染色體繁殖能力較強(qiáng)，使用傳統(tǒng)的交叉變異方式就能夠保持種群的全局優(yōu)勢(shì)。柔性車間調(diào)度問題的遺傳操作分為工序遺傳操作和機(jī)器遺傳操作。工序遺傳操作使用傳統(tǒng)的POX交叉和插入變異方法[12]。機(jī)器遺傳操作使用單點(diǎn)交叉和單點(diǎn)變異。

(2)普通種群的遺傳操作。普通種群繁殖能力相對(duì)較弱，因此設(shè)置遺傳操作時(shí)，采用使染色體變化較大的操作方法，強(qiáng)制性提高染色體的繁殖能力。

普通種群工序排序使用的交叉方式為改進(jìn)POX交叉方式，如圖3a所示。改進(jìn)POX交叉的執(zhí)行方法為：將工件按照大致等量的原則分為兩組，圖3a中將4個(gè)工件分為兩組，其中{2，3}為一組，{1，4}為一組。父代1的1、4基因保持不變遺傳給子代2，父代2的2、3基按照順序左移一個(gè)基因位并嵌入到子代2的空位中。父代2的2、3基因位保持不變遺傳給子代1，父代1的1、4基因按照順序左移一個(gè)基因位嵌入到子代1的空位中。

工序排序的變異方式為基因串逆序變異方式，如圖3b所示。具體操作方法為：隨機(jī)產(chǎn)生兩個(gè)基因位，將兩個(gè)基因位之間的基因進(jìn)行逆序排列。圖3b中隨機(jī)產(chǎn)生的基因位為4和9，將兩個(gè)基因位之間的基因逆序排列后放入到染色體中，即實(shí)現(xiàn)了基因串逆序變異。

(a) 改進(jìn)POX交叉操作

(b) 基因逆序變異操作圖3 工序的遺傳操作

機(jī)器基因鏈的交叉操作使用均勻交叉方法，如圖4a所示。具體執(zhí)行方法為：隨機(jī)選擇若干個(gè)基因位，父代1和父代2被選基因位的基因保持不變，其余基因位的基因按照對(duì)應(yīng)關(guān)系進(jìn)行交叉，即可得到子代1和子代2。

機(jī)器基因鏈的變異操作使用定向變異方法，如圖4b所示。首先隨機(jī)選擇兩個(gè)基因位，圖4b中隨機(jī)選擇了基因位4和9。而后從兩個(gè)基因位的可選機(jī)器集種隨機(jī)選擇一個(gè)機(jī)器，并替換到原基因，圖4b中的基因位4，使用機(jī)器2替換原機(jī)器5，基因位9，使用機(jī)器6替換機(jī)器1。

(a) 均勻交叉操作

(b) 定向變異操作圖4 機(jī)器的遺傳操作

在普通種群中，設(shè)置一個(gè)隨機(jī)數(shù)p∈(0,1)，再設(shè)置一個(gè)隨機(jī)數(shù)閾值p0，當(dāng)p>p0時(shí)針對(duì)工序基因鏈?zhǔn)┘舆z傳操作，當(dāng)p≤p0時(shí)針對(duì)機(jī)器基因鏈?zhǔn)┘舆z傳操作。強(qiáng)繁殖子群與普通子群之間的交流方式為融合交流，也即每迭代5次，將強(qiáng)繁殖子群和普通子群進(jìn)行混合，再次計(jì)算各染色體的繁殖能力，并進(jìn)行種群的重新劃分。

2.4 強(qiáng)繁殖NSGA-Ⅱ算法步驟

根據(jù)強(qiáng)繁殖NSGA-Ⅱ算法的構(gòu)造思路，得到強(qiáng)繁殖NSGA-Ⅱ算法步驟如下：

步驟1：設(shè)置算法參數(shù)，即染色體規(guī)模、交叉概率、變異概率、最大迭代次數(shù)等；

步驟2：染色體以隨機(jī)方式進(jìn)行初始化；

步驟3：計(jì)算各染色體的繁殖能力，并依據(jù)繁殖能力將染色體劃分為強(qiáng)繁殖子群和普通子群；

步驟4：強(qiáng)繁殖子群和普通子群按照各自的方式進(jìn)行交叉變異和選擇，每迭代一次則迭代次數(shù)+1；

步驟5：判斷迭代次數(shù)是否達(dá)到最大值，若否則判斷迭代次數(shù)是否為5的倍數(shù)，若為5的倍數(shù)則轉(zhuǎn)至步驟3，若不為5的倍數(shù)則轉(zhuǎn)至步驟4；若迭代次數(shù)達(dá)到了上限，則算法結(jié)束。

3 柔性車間調(diào)度實(shí)驗(yàn)

3.1 柔性車間調(diào)度設(shè)置

本文研究的車間調(diào)度算例中需生產(chǎn)的工件為8個(gè)，車間可提供的生產(chǎn)設(shè)備為8臺(tái)，各工件的加工工序不等，不同工序在各生產(chǎn)設(shè)備上的加工時(shí)間如表1所示。

表1 工序加工時(shí)間表 (h)

續(xù)表

表1中數(shù)字表示工序在對(duì)應(yīng)機(jī)器上的加工時(shí)間，單位為小時(shí)，“--”表示工序無(wú)法在相應(yīng)機(jī)器上加工。各機(jī)器加工功率和空載功率如表2所示。

表2 機(jī)器的加工功率與空載功率

3.2 調(diào)度結(jié)果與分析

強(qiáng)繁殖NSGA-Ⅱ算法的參數(shù)設(shè)置為：染色體規(guī)模為100，最大迭代次數(shù)為100，交叉概率設(shè)置為0.5，變異概率設(shè)置為0.1。為了進(jìn)行對(duì)比，同時(shí)使用傳統(tǒng)NSGA-Ⅱ算法進(jìn)行柔性車間調(diào)度優(yōu)化，算法參數(shù)設(shè)置與強(qiáng)繁殖NSGA-Ⅱ算法一致。兩種算法的車間調(diào)度結(jié)果如圖5所示。

圖5 兩種遺傳算法得到的Pareto解集

本文的3個(gè)優(yōu)化目標(biāo)均為最小化優(yōu)化目標(biāo)，對(duì)應(yīng)到圖5所示的3維空間中，圖中藍(lán)色“☆”位置為本文的優(yōu)化方向，因此強(qiáng)繁殖NSGA-Ⅱ算法的Pareto解集明顯優(yōu)于傳統(tǒng)NSGA-Ⅱ算法的Pareto解集。這是因?yàn)閺?qiáng)繁殖NSGA-Ⅱ算法中按照染色液的繁殖能力，將染色體劃分為2個(gè)種群，兩個(gè)種群按照各自的特點(diǎn)設(shè)置遺傳操作，有效提高了算法繁殖能力和進(jìn)化能力，因此解集優(yōu)于傳統(tǒng)NSGA-Ⅱ算法的Pareto解集。

按照各優(yōu)化目標(biāo)重要度折中的原則，從兩個(gè)Pareto解集中選擇居中的兩個(gè)解進(jìn)行對(duì)比，被選擇的解為圖5中圓圈圈出的解。兩個(gè)解對(duì)應(yīng)的生產(chǎn)甘特圖如圖6所示。

圖6 兩種算法解的甘特圖

統(tǒng)計(jì)圖6兩個(gè)解的完工時(shí)間、機(jī)器總負(fù)荷、車間能耗，結(jié)果如表3所示。

表3 兩個(gè)解的調(diào)度統(tǒng)計(jì)參數(shù)

結(jié)合圖6和表3可以看出，從傳統(tǒng)NSGA-Ⅱ算法和強(qiáng)繁殖NSGA-Ⅱ算法中選擇的折中解，傳統(tǒng)NSGA-Ⅱ算法解的完工時(shí)間為81 h，機(jī)器總負(fù)荷為378 h，車間能耗為6460 kW；強(qiáng)繁殖NSGA-Ⅱ算法解的完工時(shí)間為70 h，機(jī)器總負(fù)荷為364 h，車間能耗為6380 kW，以上參數(shù)均小于傳統(tǒng)NSGA-Ⅱ解的參數(shù)。從表象上看，圖6中強(qiáng)繁殖NSGA-Ⅱ解對(duì)應(yīng)甘特圖中機(jī)器工作量分配更加平均，而傳統(tǒng)NSGA-Ⅱ解的甘特圖中機(jī)器工作量分配相對(duì)集中，因此強(qiáng)繁殖NSGA-Ⅱ解的調(diào)度結(jié)果更優(yōu)。從算法原理角度講，強(qiáng)繁殖NSGA-Ⅱ算法按照染色液的繁殖能力，將染色體劃分為2個(gè)種群，兩個(gè)種群按照各自的特點(diǎn)設(shè)置遺傳操作，有效提高了算法繁殖能力和進(jìn)化能力。以上柔性車間的調(diào)度結(jié)果和分析驗(yàn)證了強(qiáng)繁殖NSGA-Ⅱ算法在柔性車間調(diào)度中的有效性和優(yōu)越性。

4 結(jié)論

本文研究了柔性車間的調(diào)度優(yōu)化問題，建立了車間調(diào)度的多目標(biāo)優(yōu)化模型，在傳統(tǒng)NSGA-Ⅱ算法中引入了強(qiáng)繁殖度量、多種群遺傳等操作，有效改善了算法的優(yōu)化能力，經(jīng)驗(yàn)證得出以下結(jié)論：

(1)與傳統(tǒng)NSGA-Ⅱ算法相比，強(qiáng)繁殖NSGA-Ⅱ算法的解集質(zhì)量更高，優(yōu)化能力更好；

(2)強(qiáng)繁殖能力NSGA-Ⅱ算法應(yīng)用于柔性車間調(diào)度多目標(biāo)優(yōu)化是有效的，可以有效減少完工時(shí)間、機(jī)器總負(fù)荷和車間能耗。