求解多目標(biāo)雙資源柔性車間調(diào)度問(wèn)題的改進(jìn)NSGA-Ⅱ算法

張守京,杜昊天,侯天天

(1. 西安工程大學(xué) 機(jī)電工程學(xué)院,西安 710600; 2. 西安工程大學(xué) 西安市現(xiàn)代智能紡織裝備重點(diǎn)實(shí)驗(yàn)室,西安 710048)

車間調(diào)度是智能制造管理和決策的基礎(chǔ)。柔性作業(yè)車間調(diào)度 (Flexible job scheduling problem,FJSP)作為傳統(tǒng)作業(yè)車間調(diào)度形式之一[1-3],已被證明是強(qiáng)NP-hard問(wèn)題。目前大多數(shù)的FJSP調(diào)度模型僅考慮到機(jī)器設(shè)備的約束,但在各類復(fù)雜人機(jī)系統(tǒng)中,大約有60%～90%的失效是由于人員操作失誤引起的[4]。因此,對(duì)人機(jī)雙資源柔性車間調(diào)度(Dual resource constrained flexible job shop scheduling problem,DRCFJSP)的研究具有更加重要的理論意義和實(shí)際價(jià)值。

雙資源柔性車間調(diào)度因?yàn)樯a(chǎn)實(shí)際需求而被廣大學(xué)者研究。Cao等將遺傳算法和免疫算法相結(jié)合,使設(shè)備資源和員工資源進(jìn)行了合理的分配,并達(dá)到了最大完工時(shí)間的最優(yōu)[5];Li等運(yùn)用分支種群遺傳算法對(duì)雙資源約束問(wèn)題進(jìn)行求解,采用精英進(jìn)化算子、基于扇形分割的輪盤賭選擇因子和鄰域搜索機(jī)制,達(dá)到了最大完工時(shí)間和成本最優(yōu)[6];Gong等設(shè)計(jì)一種新型混合遺傳算法,采用三層染色體編碼,完成了作業(yè)順序和工人資源合理的配置[7];在文獻(xiàn)[8]提出了一種混合粒子群算法,并引入可變領(lǐng)域結(jié)構(gòu)的模擬退火來(lái)解決DRCJSP問(wèn)題;文獻(xiàn)[9]提出了一種基于最大適應(yīng)度函數(shù)的混合粒子群算法,并采取動(dòng)態(tài)搜索策略來(lái)增強(qiáng)粒子群局部搜索能力;文獻(xiàn)[10]運(yùn)用蟻群算法和模擬退火算法結(jié)合的混合算法,實(shí)現(xiàn)了分階段性能的優(yōu)化。還有一些學(xué)者運(yùn)用新型的果蠅算法[11]、水滴算法[12]和鳥群算法[13]求解DRCJSP問(wèn)題。

分析上述學(xué)者的研究發(fā)現(xiàn):一方面,針對(duì)DRCFJSP的研究大多數(shù)是沒(méi)有考慮人員操作水平的差異性;另一方面,在算法上,大多數(shù)都是從單一種群出發(fā),優(yōu)化結(jié)果依賴初始種群。因此,本文考慮人員效率差異性,構(gòu)建了人-機(jī)雙資源多目標(biāo)柔性車間調(diào)度模型,并對(duì)傳統(tǒng)NSGA-Ⅱ加入小生境技術(shù)初始化種群策略、重復(fù)個(gè)體控制策略和熵權(quán)法選擇策略進(jìn)行改進(jìn),最后,通過(guò)實(shí)驗(yàn)求解和仿真對(duì)比說(shuō)明了改進(jìn)后的NSGA-Ⅱ?qū)鉀Q多目標(biāo)DRCFJSP具有優(yōu)越性。

1 多目標(biāo)DRCFJSP優(yōu)化建模

在一個(gè)加工系統(tǒng)中,有W名工人可以操控M臺(tái)機(jī)器中的一臺(tái)或者多臺(tái)來(lái)加工N個(gè)待加工的工件Ji(i∈{1,2,…,N}),每個(gè)工件Ji包含ni道工序,每道工序記為Oij。其中每道工序Oij必須在可選用的Mij={1,2,…,M}臺(tái)機(jī)器集中任選一臺(tái)進(jìn)行加工,并且每臺(tái)機(jī)器M可以從可操控該機(jī)器的工人集中選一位工人進(jìn)行操作。

本文的DRCFJSP調(diào)度模型用加工過(guò)程中的生產(chǎn)時(shí)間(T)、綠色制造評(píng)價(jià)系數(shù)(G)、生產(chǎn)成本(C)作為優(yōu)化目標(biāo),并對(duì)這3個(gè)目標(biāo)進(jìn)行了深層次的分析。

1) 最小化生產(chǎn)時(shí)間

在滿足員工、工藝和機(jī)器約束的前提下,最小化生產(chǎn)時(shí)間的數(shù)學(xué)描述如下:

minT=min(max{Ti})=

(1)

生產(chǎn)時(shí)間(T)屬性如表1所示。

表1 生產(chǎn)時(shí)間屬性表

2) 最小化綠色制造評(píng)價(jià)系數(shù)

制造企業(yè)在生產(chǎn)中也需要注意制造對(duì)環(huán)境造成的影響,綠色制造使減少產(chǎn)品在開發(fā)、引進(jìn)、成長(zhǎng)、成熟、衰退過(guò)程中對(duì)環(huán)境的影響,使得企業(yè)的經(jīng)濟(jì)效益和社會(huì)效益都滿足[14]。采用能耗、噪音、切屑回收這3個(gè)因素對(duì)綠色制造效果進(jìn)行評(píng)價(jià)。最小化綠色制造評(píng)價(jià)系數(shù)數(shù)學(xué)描述如下

(2)

綠色制造評(píng)價(jià)系數(shù)屬性如表2所示。

表2 綠色制造評(píng)價(jià)系數(shù)屬性表

在計(jì)算能耗、噪音和切屑回收這3個(gè)因素時(shí),需要將數(shù)據(jù)進(jìn)行無(wú)量綱處理,即

(3)

式中:x′為歸一化后的數(shù)據(jù);x為原始數(shù)據(jù);xmax、xmin表示x指標(biāo)的最大、最小值。

3) 最小化生產(chǎn)成本

制造企業(yè)追求的基本目標(biāo)是盈利最大化,而使生產(chǎn)成本最小化可以有效實(shí)現(xiàn)這個(gè)目標(biāo)。其中生產(chǎn)成本包括材料成本和加工成本。加工成本又包括機(jī)器成本和人工成本。最小化生產(chǎn)成本數(shù)學(xué)描述如下:

minC=min(MC+PC)=min(MC+PCM+PCH)

(4)

(5)

(6)

(7)

生產(chǎn)成本屬性如表3所示。

表3 生產(chǎn)成本屬性表

在DRCFJSP問(wèn)題中,除了滿足以上3個(gè)目標(biāo),還要有以下的約束條件:

1) 工藝約束

Tij-Ti(j-1)≥Pijkr×Xijkr

(8)

式中:i∈{1,2,…,N};j∈{1,2,…,ni}。式(8)確保工件加工過(guò)程中按照工序的優(yōu)先順序進(jìn)行加工。

2) 機(jī)器約束

[(Top-Tij-Popk)×Yopk×Yijk≥0]∨

[(Tij-Top-Pijk)×Yijk×Yopk≥0]

i,o∈{1,2,…,N};

p∈{1,2,…,no};k∈{1,2,…,M};

該式子確保任何一臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序。

3) 員工約束

(9)

式(9)確保任何一個(gè)工件的任何工序在同一時(shí)刻只能由一個(gè)工人來(lái)操作一臺(tái)機(jī)器進(jìn)行加工。

2 改進(jìn)NSGA-Ⅱ求解多目標(biāo)DRCFJSP

由第1節(jié)的分析可以得到,本文建立的DRCFJSP模型是一個(gè)多目標(biāo)優(yōu)化問(wèn)題(Multi-objective optimization problem, MOP)。在MOP中,改善一個(gè)目標(biāo)往往會(huì)降低另一個(gè)目標(biāo)的性能,從而無(wú)法同時(shí)實(shí)現(xiàn)多個(gè)目標(biāo)。因此,只能在多個(gè)目標(biāo)中進(jìn)行權(quán)衡,使所有目標(biāo)盡量達(dá)到最優(yōu),得到Pareto解集[15]。其中非支配排序遺傳算法(NSGA-Ⅱ)算法在解決MOP上具有良好的表現(xiàn)。因此,結(jié)合DRCFJSP的特點(diǎn),加入小生境協(xié)同進(jìn)化策略、重復(fù)個(gè)體控制策略和熵權(quán)法選擇策略,設(shè)計(jì)了基于工序編碼的改進(jìn)NSGA-Ⅱ,算法流程如圖1所示。

圖1 改進(jìn)NSGA-Ⅱ算法流程圖

2.1 總體流程

改進(jìn)NSGA-Ⅱ算法流程的具體操作步驟為:

步驟1 小生境協(xié)同進(jìn)化策略初始化種群

1) 初始化參數(shù),通過(guò)量子編碼和小生境劃分種群生成初始群Q(t);

2) 對(duì)種群Q(t)進(jìn)行量子測(cè)量,得到二進(jìn)制編碼串,隨后轉(zhuǎn)化為十進(jìn)制編碼串P(t);

3) 對(duì)十進(jìn)制編碼串P(t)進(jìn)行解碼和個(gè)體評(píng)價(jià),保存Pareto解集;

步驟2 循環(huán)maxGEN代,得到Pareto解集

1) 對(duì)種群P(t)進(jìn)行快速非支配排序;

2) 對(duì)排序后的種群進(jìn)行競(jìng)標(biāo)法選擇、交叉、變異,得到子種群R(t);

3) 對(duì)種群P(t)和R(t)進(jìn)行合并;

4) 去除合并后的重復(fù)個(gè)體,若去除后的個(gè)體數(shù)量小于P(t)的數(shù)量,則轉(zhuǎn)到2),否則進(jìn)行快速非支配排序,選擇生成新的種群,轉(zhuǎn)到1);

步驟3 熵權(quán)法確定最優(yōu)解

1) 將Pareto解集的各項(xiàng)指標(biāo)進(jìn)行歸一化;

2) 根據(jù)熵權(quán)法確定各項(xiàng)因素的權(quán)重;

3) 通過(guò)權(quán)重對(duì)Pareto解集的每一個(gè)解進(jìn)行評(píng)價(jià),找出最優(yōu)序列;

4) 對(duì)最優(yōu)序列進(jìn)行解碼,畫出甘特圖和各項(xiàng)指標(biāo)的迭代圖。

2.2 詳細(xì)設(shè)計(jì)

2.2.1 量子編碼

在量子編碼中,量子比特是描述量子線路狀態(tài)的最基本單元。一個(gè)量比特位可以表示為

|φ〉=α|0〉+β|1〉

(10)

柔性車間調(diào)度問(wèn)題的量子編碼可以表示為

(11)

在一個(gè)DRCFSP問(wèn)題中,設(shè)工件N個(gè),機(jī)器M臺(tái),則量子編碼長(zhǎng)度就是L=(log2N+1)×M×N。

量子編碼為

二進(jìn)制編碼為

Pt=010|011|001|011|010|001

十進(jìn)制編碼為

Xt=2|3|1|3|2|1

則加工順序和加工機(jī)器可以表示為:P21,P31,P11,P32,P22,P12。

2.2.2 小生境協(xié)同進(jìn)化策略

小生境技術(shù)可以很好的保持父代和子代的多樣性,還可以提高算法的運(yùn)算速度和收斂性,從而找到更加適合問(wèn)題的Pareto解集,所以本文對(duì)NSGA-Ⅱ算法的初始化使用小生境技術(shù)。

(12)

式中:i表示子種群的序號(hào);N表示子種群的總數(shù)。

2.2.3 快速非支配排序

快速非支配排序可以將種群按照非劣解的程度進(jìn)行分層,運(yùn)用這種方法找出不被支配的解集就是所求的Pareto解集。其中,ni為支配i的個(gè)體數(shù),si為被i支配的集合。具體操作步驟如下:

1) 找到種群中所有ni=0的個(gè)體,保存在集合Ft中,t=1;

2) 對(duì)于當(dāng)前的集合Ft中每個(gè)個(gè)體i,其所支配的個(gè)體集合為si,遍歷si每個(gè)個(gè)體,執(zhí)行ni=ni-1,如果ni=0,t=t+1,并保存在集合Ft中;

3) 重復(fù)步驟2),直到整個(gè)種群被分級(jí)。

2.2.4 交叉和變異

交叉為將原有的兩條染色體的一部分進(jìn)行互換,這樣就可以得到兩條不同的染色體。在2.2.1中的編碼序列表現(xiàn)為半Lamarckian性,通過(guò)文獻(xiàn)[15]表明,采用PBX和LOX交叉算子相結(jié)合的方式優(yōu)化的效果優(yōu)于單一交叉算子。因此本文在交叉過(guò)程中各按50%的概率進(jìn)行隨機(jī)選擇。

變異是將染色體中間的一部分基因通過(guò)一系列操作進(jìn)行改變得到新的染色體。因?yàn)楸疚牟捎玫氖腔诠ば虻木幋a方式,為了保證變異操作之后的染色體具有實(shí)際意義,不會(huì)出現(xiàn)太多的無(wú)效解集,所以采用兩段基因相互交換的方式和某段基因插入的方式相結(jié)合的作為變異操作。

2.2.5 重復(fù)個(gè)體控制策略

由于NSGA-Ⅱ算法中,新的種群是通過(guò)父代和子代合并后進(jìn)行適應(yīng)度計(jì)算、競(jìng)標(biāo)法選擇、交叉、變異確定的,而在交叉和變異不為1的時(shí)候,父代總有一些個(gè)體沒(méi)有交叉和變異,這些個(gè)體是子代的一部分。因此,在父代和子代進(jìn)行合并的時(shí)候,就會(huì)有重復(fù)個(gè)體出現(xiàn)。隨后對(duì)新的種群進(jìn)行非支配排序的時(shí)候,這些重復(fù)個(gè)體是不會(huì)互相支配的,部分重復(fù)的個(gè)體會(huì)被選入新的父代種群。這樣多代之后,新的父代被越來(lái)越多的重復(fù)解占據(jù),導(dǎo)致最后的Pareto解集中的非支配解十分的少。

通過(guò)文獻(xiàn)[16]中提到的重復(fù)個(gè)體刪除算法,本文在NSGA-Ⅱ框架上增加重復(fù)個(gè)體控制策略改進(jìn),其具體步驟如下:

1) 對(duì)父代P(t)和子代R(t)合并后的種群S(t)進(jìn)行刪除重復(fù)個(gè)體;

2) 判斷刪除后的種群個(gè)數(shù)是否小于P(t)的個(gè)數(shù),若小于,繼續(xù)進(jìn)行競(jìng)標(biāo)法選擇、交叉、變異,合并種群,返回1),否則,對(duì)該種群進(jìn)行快速非支配排序,選出前N個(gè)個(gè)體作為新的父代種群。

2.2.6 熵權(quán)法選擇策略

在MOP問(wèn)題中,最終得到的是一組Pareto最優(yōu)解集,為了避免選擇方案過(guò)程的主觀性,因此本文采用熵權(quán)法選擇最優(yōu)解策略。熵權(quán)法可以通過(guò)利用一組指標(biāo)之中所含有的信息量的大小對(duì)這些指標(biāo)進(jìn)行賦權(quán)值,之后可以利用這些權(quán)值對(duì)這些指標(biāo)進(jìn)行綜合的評(píng)價(jià),得到Pareto解集中綜合評(píng)價(jià)最好的解[17]。具體步驟如下:

5) 利用加權(quán)求和對(duì)解集中的每個(gè)解進(jìn)行評(píng)價(jià)。

3 實(shí)例分析

為了說(shuō)明改進(jìn)算法的有效性,以某企業(yè)實(shí)例為基準(zhǔn)進(jìn)行數(shù)據(jù)驗(yàn)證,并與改進(jìn)前的NSGA-Ⅱ算法進(jìn)行求解對(duì)比。該車間要在6臺(tái)設(shè)備(M1～M6)上安排6種工件(J1～J6)的生產(chǎn),車間工人有6名(W1～W6)。其中,每個(gè)工件的每道工序是否可以在機(jī)器上加工及加工標(biāo)準(zhǔn)時(shí)間如表4所示,工人是否可以操作機(jī)器及操控效率如表5所示,工人單位時(shí)間成本及機(jī)器設(shè)備單位成本如表6,表7所示。能耗、噪音、切屑回收這3個(gè)數(shù)據(jù)通過(guò)文獻(xiàn)[18]的Algorithm3.2在一定范圍內(nèi)生成。

表4 工序標(biāo)準(zhǔn)時(shí)間表

表5 工人可操控機(jī)器及操控效率

表6 工人單位時(shí)間成本

表7 機(jī)器單位時(shí)間成本

NSGA-Ⅱ與改進(jìn)NSGA-Ⅱ參數(shù)設(shè)置如下:種群規(guī)模為200,迭代次數(shù)為200,交叉率為0.9,變異率為0.1。

圖2表示通過(guò)NSGA-Ⅱ和改進(jìn)NSGA-Ⅱ進(jìn)行多目標(biāo)雙資源柔性車間調(diào)度求解仿真得到的Pareto前沿,圖3表示通過(guò)Pareto前沿點(diǎn)集進(jìn)行擬合得到的Pareto前沿面。對(duì)比可知改進(jìn)后的NSGA-Ⅱ算法相比于NSGA-Ⅱ算法總體上解的個(gè)數(shù)更多,且生產(chǎn)時(shí)間,綠色制造評(píng)價(jià)系數(shù)和生產(chǎn)成本都更加優(yōu)化。證明了改進(jìn)NSGA-Ⅱ算法的有效性和可行性。

圖2 Pareto前沿圖

圖3 擬合Pareto前沿面

圖4～圖6分別表示生產(chǎn)時(shí)間、綠色制造評(píng)價(jià)系數(shù)和生產(chǎn)成本的迭代過(guò)程。表8為改進(jìn)NSGA-Ⅱ求解后得到的Pareto解集,一共包含31組解。

圖4 生產(chǎn)時(shí)間迭代圖

圖5 綠色制造評(píng)價(jià)系數(shù)迭代圖

圖6 生產(chǎn)成本迭代圖

表8 最終的得到的31組解集

算法最后通過(guò)熵權(quán)法選擇策略選出一組最優(yōu)解,生產(chǎn)時(shí)間T=24.56,綠色制造評(píng)價(jià)系數(shù)G=15.79,生產(chǎn)成本C=7 660.75。對(duì)應(yīng)甘特圖如圖7所示,其中P(i,j)=h表示第i個(gè)工件的第j道工序的實(shí)際生產(chǎn)時(shí)間,h;下方對(duì)應(yīng)的R=w表示該工序是由工人w進(jìn)行加工操作。

圖7 最優(yōu)解的調(diào)度甘特圖

4 結(jié)論

考慮車間中員工操控機(jī)床加工工件熟練度不同的情況下,以生產(chǎn)時(shí)間最小化,生產(chǎn)成本最小化和綠色制造評(píng)價(jià)系數(shù)最小化為目標(biāo),建立了考慮人員的多目標(biāo)DRCFJSP模型,并引入改進(jìn)NSGA-Ⅱ算法來(lái)求解該問(wèn)題。針對(duì)傳統(tǒng)量子遺傳算法的收斂速度慢,容易陷入早熟而且容易多個(gè)重復(fù)解的問(wèn)題,采用了小生境初始化種群、充分個(gè)體控制策略和熵權(quán)法選擇最優(yōu)解來(lái)提升算法效率,避免算法早熟收斂和重復(fù)無(wú)效解集。最后通過(guò)實(shí)例分析,并與改進(jìn)前的NSGA-Ⅱ進(jìn)行對(duì)比,證明本文改進(jìn)的NSGA-Ⅱ具有很好的收斂性和不會(huì)陷入早熟的能力。下一步將對(duì)算法進(jìn)一步改進(jìn),對(duì)動(dòng)態(tài)DRCFJSP多目標(biāo)問(wèn)題進(jìn)行研究。