安友軍,陳曉慧

(重慶大學(xué)機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室,重慶 400030)

1 引言

隨著經(jīng)濟(jì)全球化的不斷推進(jìn),市場(chǎng)競(jìng)爭(zhēng)日趨激烈,產(chǎn)品生命周期不斷縮短,為快速響應(yīng)顧客個(gè)性化需求,多品種、小批量的生產(chǎn)模式已成為制造型企業(yè)的首選.而生產(chǎn)調(diào)度是影響企業(yè)生產(chǎn)效率的主要因素之一[1],采用先進(jìn)的優(yōu)化技術(shù)能有效地縮短訂單完工時(shí)間、提高設(shè)備利用率和確保按期交貨,從而提高企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力.其中柔性作業(yè)車間調(diào)度問題(FJSP)是經(jīng)典作業(yè)車間調(diào)度問題(JSP)的拓展,其突破了資源唯一性的約束[2].在FJSP 中,至少存在一道工序可在多臺(tái)設(shè)備上加工,但在不同設(shè)備上的加工時(shí)間存在差異.由于工序和加工設(shè)備的柔性與當(dāng)前生產(chǎn)環(huán)境更加貼近,因此,對(duì)FJSP 的研究也更加具有現(xiàn)實(shí)意義.

在實(shí)際生產(chǎn)過程中,調(diào)度計(jì)劃的制定和選擇不僅涉及到最大完工時(shí)間、交貨期和機(jī)器負(fù)荷等性能指標(biāo),還涉及到生產(chǎn)成本等費(fèi)用指標(biāo),單一目標(biāo)的優(yōu)化很難反映實(shí)際的車間調(diào)度問題,而如何有效的進(jìn)行多目標(biāo)車間調(diào)度聯(lián)合優(yōu)化是目前研究的熱點(diǎn)之一.Rifai 等[3]利用智能優(yōu)化算法求解了基于柔性制造系統(tǒng)的雙目標(biāo)調(diào)度問題.文獻(xiàn)[4–10]對(duì)最大完工時(shí)間、瓶頸機(jī)器負(fù)荷及設(shè)備總負(fù)荷的三目標(biāo)調(diào)度實(shí)例進(jìn)行了深入研究,但優(yōu)化目標(biāo)多為性能指標(biāo),而對(duì)費(fèi)用指標(biāo)的研究較少.其中文獻(xiàn)[11–13]對(duì)多目標(biāo)FJSP 的研究不僅涉及到性能指標(biāo),還涉及到費(fèi)用和碳排放量等指標(biāo),這也引起了廣大學(xué)者對(duì)其它調(diào)度目標(biāo)的關(guān)注.因此,基于多評(píng)價(jià)指標(biāo)的調(diào)度聯(lián)合優(yōu)化是目前及未來制定生產(chǎn)計(jì)劃時(shí)必須要考慮的問題之一.

為對(duì)多目標(biāo)優(yōu)化問題進(jìn)行深入研究,首先需要設(shè)計(jì)出高效的求解算法.目前,許多學(xué)者已提出多種典型求解多目標(biāo)優(yōu)化問題的先進(jìn)算法,如Ded 等[14]提出的非支配排序遺傳算法NSGA-II,Zhang 等[15]提出的基于分解式的多目標(biāo)進(jìn)化算法MOEA/D,畢曉君等[16]提出的基于模糊支配的高維多目標(biāo)進(jìn)化算法MFEA,Zitzler 等[17]提出的SPEA 等.此外,基于實(shí)際工程優(yōu)化問題的先進(jìn)智能算法研究成果也在不斷涌現(xiàn)[18,19].其中Ded 等[20]提出的NSGA-III 算法克服了NSGA-II 算法中擁擠距離無窮大的缺陷,有效的解決了在高維多目標(biāo)優(yōu)化過程中對(duì)種群個(gè)體多樣性保持不足的問題,并在多目標(biāo)優(yōu)化過程中被廣泛應(yīng)用[21-23],同時(shí)也是本文的研究對(duì)象.但隨著目標(biāo)維度的增加,標(biāo)準(zhǔn)NSGA-III 算法的計(jì)算復(fù)雜度高、最優(yōu)參數(shù)設(shè)置及種群收斂性等方面的不足也逐漸暴露.

在多目標(biāo)優(yōu)化算法中,支配策略的選取對(duì)優(yōu)化結(jié)果具有決定性的作用.由于Pareto 非支配排序無法產(chǎn)生足夠的選擇壓力去促使種群進(jìn)化,因此新型支配關(guān)系也逐漸涌現(xiàn),如Zou 等[24]提出的L–最優(yōu)性,畢曉君等[16]提出的模糊支配,Zhang 等[25-26]等提出的ENS 和A-ENS 等.由于NSGA-III 過多的強(qiáng)調(diào)種群個(gè)體的多樣性,導(dǎo)致收斂性不足.為克服這一缺陷,畢曉君等[27]提出了基于參考點(diǎn)的約束支配關(guān)系,但在仿真過程中存在種群震蕩且易丟失當(dāng)前最優(yōu)解的缺陷.Yuan 等[28]提出了基于懲罰參數(shù)支配的進(jìn)化算法,但懲罰參數(shù)需事先定義且對(duì)算法性能有較大影響.由此可見,在標(biāo)準(zhǔn)NSGA-III算法的基礎(chǔ)上,如何進(jìn)行有效改進(jìn)以提高算法性能,是一個(gè)有待急需解決的問題.

針對(duì)標(biāo)準(zhǔn)NSGA-III 算法存在收斂性、局部搜索和精英存儲(chǔ)上的不足,本文對(duì)其進(jìn)行了如下改進(jìn):1)為克服Pareto 支配關(guān)系對(duì)種群個(gè)體進(jìn)化壓力的不足,提出利用近似支配原則對(duì)個(gè)體間的支配關(guān)系進(jìn)行判斷,避免了目標(biāo)值維度對(duì)支配關(guān)系的干擾,且每個(gè)等級(jí)層的個(gè)體數(shù)較少,保證了種群個(gè)體的收斂性.2)由于標(biāo)準(zhǔn)NSGA-III 算法具有較強(qiáng)的全局搜索能力,但局部搜索能力較差.為此,提出面向空閑時(shí)間的鄰域結(jié)構(gòu),以加強(qiáng)對(duì)機(jī)器空閑時(shí)間的利用,從而提高算法對(duì)局部鄰域的搜索能力.3)在標(biāo)準(zhǔn)NSGA-III 算法中,將迭代最后的子代種群作為最優(yōu)輸出,而在生成子代種群時(shí)需要考慮種群個(gè)體的多樣性,存在易丟失部分迭代最優(yōu)解的缺陷.為此,提出建立面向迭代過程的精英記憶庫(kù),將完成局部搜索后的種群與當(dāng)前精英記憶庫(kù)進(jìn)行合并,并選取Pareto 非支配層個(gè)體進(jìn)入精英記憶庫(kù),從而避免了為保持種群個(gè)體多樣性對(duì)最優(yōu)解集的干擾.

本文首先分析了標(biāo)準(zhǔn)NSGA-III 算法存在的不足,針對(duì)這些不足提出了具體的改進(jìn)措施,這些改進(jìn)措施包括近似支配原則、變鄰域局部搜索和精英存儲(chǔ)策略,并將標(biāo)準(zhǔn)NSGA-III 算法與這些措施進(jìn)行有效結(jié)合,提出了近似支配(AD)的NSGA-III 算法,簡(jiǎn)稱NSGA-III-AD.其次,針對(duì)FJSP 的特點(diǎn),依次設(shè)計(jì)了染色體的編碼與解碼、種群初始化方法、近似支配的選擇操作和變鄰域的遺傳操作,并總結(jié)了NSGA-III-AD 算法求解多目標(biāo)FJSP 的一般流程.最后,結(jié)合基準(zhǔn)調(diào)度算例從兩方面對(duì)提出算法的性能進(jìn)行測(cè)試,一方面是利用三個(gè)優(yōu)化目標(biāo)的Kacem 標(biāo)準(zhǔn)算例對(duì)算法的整體性能進(jìn)行測(cè)試,以驗(yàn)證其有效性.另一方面是利用六個(gè)優(yōu)化目標(biāo)的生產(chǎn)實(shí)例對(duì)算法中的參數(shù)設(shè)置和創(chuàng)新操作進(jìn)行有效性分析,并與其它多目標(biāo)優(yōu)化算法進(jìn)行對(duì)比.此外,利用收斂性、多樣性、分布性和超體積指標(biāo)及綜合加權(quán)法對(duì)調(diào)度實(shí)例所獲的非支配解集進(jìn)行綜合評(píng)價(jià).

2 多目標(biāo)FJSP 優(yōu)化模型

2.1 問題描述

FJSP 一般描述為[2],有n個(gè)工件J={J1,J2,...,Jn},在m臺(tái)機(jī)器上加工M={M1,M2,...,Mm}.且每個(gè)工件Ji擁有一道或多道加工順序(工藝路線)已知的工序集O={Oi,1,Oi,2,...,Oi,ni}.此外,FJSP具有柔性加工路徑的特點(diǎn),即在工件集J中至少存在一個(gè)工件的某道工序可在多臺(tái)設(shè)備上加工,且不同機(jī)器對(duì)同一工序的加工時(shí)間存在差異(該工序的多臺(tái)可供選擇的機(jī)器構(gòu)成了該工序的可選機(jī)器集Jm).因此,FJSP 包含兩個(gè)子問題[12]:1)機(jī)器選擇問題,每道工序需在當(dāng)前可選機(jī)器集Jm中選擇合適的加工設(shè)備.2)工序排序問題,由于每臺(tái)設(shè)備可加工若干道工序,則需對(duì)設(shè)備上進(jìn)行加工的不同工件的工序或同一工件的不同工序進(jìn)行優(yōu)化排序.

2.2 符號(hào)說明

為便于描述,定義以下符號(hào)和變量:

1)索引、元素和集合

i和i′為工件索引,J′={1,2,...,n}為含有所有工件序號(hào)的集合,n為待加工的工件總數(shù),即有i,i′ ∈J′,且J′中的元素個(gè)數(shù)為n;k和k′′為的機(jī)器索引,M′={1,2,...,m}為含有所有機(jī)器序號(hào)的集合,即有k,k′ ∈M′,且M′中的元素個(gè)數(shù)為機(jī)器總數(shù)m;j為工序索引,Ii={1,2,...,ni}和ni分別為工件Ji的所有工序序號(hào)集合和總工序數(shù),即有j ∈Ii,且1 ≤j≤ni;Oi,j為工件Ji的第j道工序;Ck為機(jī)器Mk的單位時(shí)間加工成本,MCi為工件Ji的原材料成本.此外,z和z′為目標(biāo)個(gè)數(shù)索引,g為總目標(biāo)數(shù);r為參考點(diǎn)索引,λr為參考點(diǎn)r的方向向量,Zr為參考點(diǎn)集合,即有λr ∈Zr.

2)時(shí)間參數(shù)

Ci,ni為工件Ji的完工時(shí)間; STijk,Pijk和ETijk分別為工序Oi,j在機(jī)器Mk上的開始加工時(shí)刻、加工時(shí)間和結(jié)束時(shí)刻,同理,STi(j-i)k′,Pi(j-1)k′和ETi(j-1)k′分別為工件Ji的第j-1 道工序Oi,(j-1)在機(jī)器Mk′上的開始加工時(shí)刻、加工時(shí)間和結(jié)束時(shí)刻; ETi′j′k為機(jī)器Mk在加工工序Oi,j之前的緊前工序Oi′,j′(工件Ji′的第j′道工序)的結(jié)束時(shí)刻;Ri和Di分別為工件Ji的釋放時(shí)間和交貨期; MIk為機(jī)器Mk開始處于空閑的時(shí)刻.

3)決策變量

Xijk為0-1變量,當(dāng)Xijk=1 時(shí),表示工序Oi,j在機(jī)器Mk上加工,否則,表示工序Oi,j不在機(jī)器Mk上加工.

2.3 數(shù)學(xué)模型的建立

在實(shí)際生產(chǎn)過程中,根據(jù)不同部門追求的績(jī)效考核指標(biāo)(例如:生產(chǎn)部門要求生產(chǎn)成本最低,銷售部門要求按時(shí)交貨,設(shè)備管理部門要求機(jī)器損耗最低等),吳秀麗[29]將車間調(diào)度方案的決策指標(biāo)主要分為四大類:完工時(shí)間指標(biāo)、交貨期指標(biāo)、生產(chǎn)成本指標(biāo)和機(jī)器負(fù)荷指標(biāo).其中完工時(shí)間是指加工完所有工件工序所需的時(shí)間;交貨期為企業(yè)接受訂單時(shí)對(duì)客戶承諾的交貨時(shí)間;生產(chǎn)成本指標(biāo)是直接反映調(diào)度方案對(duì)企業(yè)經(jīng)濟(jì)效益的影響;機(jī)器負(fù)荷則是對(duì)企業(yè)資源利用水平的反映.

為綜合考慮上述多個(gè)指標(biāo),給出了以下具有實(shí)際意義的優(yōu)化目標(biāo):1)縮短最大完工時(shí)間、平均流經(jīng)時(shí)間(四舍五入)和總拖期時(shí)間,以提高車間生產(chǎn)效率,并保證按時(shí)交貨;2)降低機(jī)器總負(fù)荷和瓶頸機(jī)器負(fù)荷,從而避免瓶頸堵塞,以提高設(shè)備利用率;3)降低生產(chǎn)成本,以提高企業(yè)的經(jīng)濟(jì)效益.此外,考慮工件的釋放時(shí)間、交貨期及工藝順序等信息.

1)最大完工時(shí)間

2)平均流經(jīng)時(shí)間

3)總拖期

4)機(jī)器總負(fù)荷

5)瓶頸機(jī)器負(fù)荷

6)總生產(chǎn)成本

多目標(biāo)柔性作業(yè)車間調(diào)度的優(yōu)化模型為

s.t.

其中約束(8)表示每個(gè)工件的工序加工順序約束,即每道工序的完工時(shí)間在開工時(shí)間之后;約束(9)表示同一工件的當(dāng)前工序Oi,j的開始時(shí)刻與上一道工序Oi,(j-1)的結(jié)束時(shí)刻、當(dāng)前加工機(jī)器開始空閑時(shí)刻MIk及工件釋放時(shí)間Ri的約束關(guān)系;約束(10)為每個(gè)工件的完工時(shí)間,即最后一道工序的結(jié)束時(shí)刻;約束(11)定義了機(jī)器開始處于空閑的時(shí)刻與該機(jī)器上的工序結(jié)束時(shí)刻的關(guān)系;約束(12)表示一道工序只能被一臺(tái)可選機(jī)器進(jìn)行加工;約束(13)表示一臺(tái)機(jī)器同時(shí)只能加工一道工序;約束(14)為0-1 變量;式(15)～式(18)為非負(fù)約束.

3 NSGA-III 算法與改進(jìn)方法

3.1 NSGA-III 算法

NSGA-III 保留了NSGA-II 的基本框架,不同的是種群多樣性的保持策略,在NSGA-III 中采用一組均勻分布的參考點(diǎn)對(duì)種群多樣性進(jìn)行保持,參考點(diǎn)規(guī)模為H.假設(shè)第t代的父代種群Pt和子代種群Qt的個(gè)體數(shù)都為N(H ≈N),合并父代和子代種群得Ut=Pt∪Qt,為從種群Ut中選出N個(gè)個(gè)體進(jìn)入下一代種群Pt+1中.首先,對(duì)種群Ut的個(gè)體目標(biāo)值進(jìn)行自適應(yīng)歸一化處理[20],并利用Pareto 非支配原則對(duì)種群Ut進(jìn)行分層,如F1表示第一層,F2表示第二層等,等級(jí)層的序號(hào)越小則該層中的個(gè)體越優(yōu).然后依次將每一層的個(gè)體加入到種群St中,直到種群St中的個(gè)體數(shù)大于或等于N,最后加入的個(gè)體所在的等級(jí)層稱為臨界層Fl,其中l(wèi)滿足表示第k層的個(gè)體數(shù).臨界層之前的個(gè)體(St/Fl)直接存活至下一代種群Pt+1中.對(duì)種群Pt+1中缺少的個(gè)體則利用小生境技術(shù)從Fl中選取.其中小生境技術(shù)的操作過程如下:1)計(jì)算種群St中每個(gè)個(gè)體到參考線(從原點(diǎn)出發(fā)經(jīng)過參考點(diǎn)的射線)的距離(投影距離和垂直距離),并將個(gè)體關(guān)聯(lián)到首個(gè)垂直距離最小的參考點(diǎn)上,定義參考點(diǎn)r被關(guān)聯(lián)的次數(shù)為小生境數(shù)ρr.2)尋找與臨界層Fl中個(gè)體關(guān)聯(lián)且具有最少的參考點(diǎn))若參考點(diǎn)的小生境數(shù)=0,則從Fl中選取與之垂直距離最短的個(gè)體加入Pt+1中,同時(shí)增加1.若,則從Fl中隨機(jī)選取一個(gè)個(gè)體加入Pt+1,同時(shí),增加1.反復(fù)執(zhí)行上述小生境技術(shù),直到種群Pt+1中的個(gè)體數(shù)等于N.

3.2 改進(jìn)動(dòng)機(jī)與策略

NSGA-III 算法的核心是Pareto 非支配排序和小生境技術(shù),具有保持種群多樣性的優(yōu)點(diǎn),盡管Ded[20]提出的NSGA-III 算法在多目標(biāo)優(yōu)化問題中取得了較好效果,但仍有許多有待改進(jìn)之處.

在高維多目標(biāo)車間調(diào)度優(yōu)化過程中,利用Pareto 非支配原則進(jìn)行非支配排序時(shí),由于個(gè)體間的目標(biāo)值大多都處于Pareto 非支配狀態(tài),即缺乏對(duì)種群個(gè)體進(jìn)化的壓力,導(dǎo)致種群個(gè)體的收斂性不足,而過多的強(qiáng)調(diào)種群個(gè)體的多樣性.為克服Pareto 非支配排序的不足,提出了基于參考點(diǎn)近似支配的新型支配原則.在近似支配原則中,首先對(duì)個(gè)體的投影距離、垂直距離及參考點(diǎn)的小生境數(shù)進(jìn)行計(jì)算.然后利用Pareto 原則和個(gè)體自適應(yīng)歸一化目標(biāo)值到原點(diǎn)的距離對(duì)個(gè)體間的支配關(guān)系進(jìn)行判斷.在新型支配原則中,可將任意多維的非支配目標(biāo)函數(shù)值轉(zhuǎn)換為一個(gè)目標(biāo)值進(jìn)行比較,避免了直接利用目標(biāo)值進(jìn)行支配關(guān)系的判斷,提高了非支配排序的速度,且每個(gè)等級(jí)層的個(gè)體數(shù)較少,降低了小生境技術(shù)的重復(fù)次數(shù),提高了算法的計(jì)算速度.

NSGA-III 算法中的交叉和變異操作使算法具有較強(qiáng)的全局搜索能力,但局部搜索能力較差,為提高算法求解柔性作業(yè)車間調(diào)度問題的局部搜索能力,引入了變鄰域搜索算法.其中在車間調(diào)度優(yōu)化的局部搜索研究中,基于鄰域結(jié)構(gòu)的變鄰域搜索算法取得了較好效果[?].為此,構(gòu)建了面向空閑時(shí)間的鄰域結(jié)構(gòu),并對(duì)同機(jī)器的工序移動(dòng)和跨機(jī)器的工序移動(dòng)進(jìn)行了探索.

在最優(yōu)解的存儲(chǔ)過程中,標(biāo)準(zhǔn)NSGA-III 算法直接將子代種群作為最優(yōu)解集,存在易丟失迭代過程最優(yōu)解的缺陷.為防止在生成子代種群時(shí),種群多樣性對(duì)最優(yōu)或近似最優(yōu)種群收斂性的影響,構(gòu)建了面向迭代過程的精英記憶庫(kù).

此外,NSGA-III 算法有種群規(guī)模、迭代次數(shù)、交叉概率及變異概率等參數(shù),參數(shù)設(shè)置對(duì)算法的迭代效果具有較大的影響.但在不同優(yōu)化問題中的最佳參數(shù)設(shè)置存在差異,進(jìn)行特定問題優(yōu)化前,需要尋找最佳或近似最佳的參數(shù)組合.同時(shí),需對(duì)算法中的創(chuàng)新操作進(jìn)行有效性分析,以驗(yàn)證其存在的科學(xué)性和必要性.

3.3 具體改進(jìn)方法

3.3.1 基于參考點(diǎn)的近似支配原則

近似支配原則從以下兩個(gè)方面進(jìn)行闡述,首先計(jì)算個(gè)體的關(guān)聯(lián)參考點(diǎn)及參考點(diǎn)的小生境數(shù),其次定義了個(gè)體間的近似支配關(guān)系.

1)關(guān)聯(lián)參考點(diǎn)與小生境數(shù)的計(jì)算

種群歸一化完成后(個(gè)體X的g個(gè)目標(biāo)值記為,利用個(gè)體到參考線的垂直距離,對(duì)個(gè)體與參考點(diǎn)的關(guān)聯(lián)關(guān)系進(jìn)行評(píng)估.若個(gè)體X與參考點(diǎn)r關(guān)聯(lián),則個(gè)體X在第r條參考線上的投影距離dr1(X)和垂直距離dr2(X)的計(jì)算式如下[27]

圖1 給出了個(gè)體X在二維歸一化目標(biāo)空間中d21(X)d22(X)的計(jì)算示意圖.投影距離dr1(·)表征了個(gè)體的收斂性,其值越小則收斂性越好.垂直距離dr2(·)表征了個(gè)體的多樣性,其值越小則個(gè)體的多樣性越好.

圖1 二維目標(biāo)空間中d21(X),d22(X)和F(X)的計(jì)算示意圖Fig.1 Schematic diagram of d21(X),d22(X)and F(X)in a two-dimensional target space

2)基于參考點(diǎn)的近似支配關(guān)系

若種群個(gè)體均勻離散的分布在目標(biāo)空間中,則種群個(gè)體具有較好的多樣性.為使目標(biāo)函數(shù)盡快收斂,提出利用個(gè)體自適應(yīng)歸一化目標(biāo)值到原點(diǎn)的距離F(X)和Pareto 原則進(jìn)行支配關(guān)系的判斷,使個(gè)體目標(biāo)值盡量均勻的分布在原點(diǎn)附近,以保持種群個(gè)體的收斂性和多樣性,F(X)的計(jì)算式如下

為讓Pareto 非支配層個(gè)體保存至下一代種群,進(jìn)行個(gè)體非支配排序時(shí),首先利用Pareto 原則進(jìn)行個(gè)體間支配關(guān)系的準(zhǔn)確判斷,若兩個(gè)體是Pareto 互不支配關(guān)系,則利用F(X)進(jìn)行判斷,即近似支配是一種混合支配原則.如圖1 所示,利用近似支配原則對(duì)個(gè)體間支配關(guān)系進(jìn)行判斷時(shí),需滿足以下情形之一:

(a)當(dāng)且僅當(dāng)對(duì)任意z ∈{1,2,...,g}有,且至少存在一個(gè)下標(biāo)z′ ∈{1,2,...,g},使成立,則X支配S.同理,個(gè)體Z和個(gè)體Y都支配個(gè)體S,否則執(zhí)行(b).

(b)當(dāng)任意兩個(gè)體都處于Pareto 互不支配狀態(tài)時(shí)(如個(gè)體X,Y和Z),則利用F(X)進(jìn)行判斷.由圖1可知F(Y)＜F(X)＜F(Z),則Y同時(shí)支配X和Z,且有X支配Z存在.

其中準(zhǔn)則(a)利用Pareto 非支配原則進(jìn)行支配關(guān)系的精確判斷,保證非支配個(gè)體保留至下一代種群中,保證了算法的收斂性.準(zhǔn)則(b)規(guī)定了兩個(gè)體的近似支配策略,當(dāng)兩個(gè)體處于Pareto 非支配狀態(tài)時(shí),利用F(X)進(jìn)行支配關(guān)系的近似判斷,從而達(dá)到減少比較次數(shù)和每個(gè)等級(jí)層個(gè)體數(shù)的目的.

3.3.2 面向空閑時(shí)間的鄰域結(jié)構(gòu)

在車間調(diào)度優(yōu)化過程中,工序的加工機(jī)器及機(jī)器加工工序的順序?qū)δ繕?biāo)函數(shù)都有較大的影響.為此,對(duì)機(jī)器選擇和工序排序部分設(shè)計(jì)了面向空閑時(shí)間的局部搜索算法.

面向機(jī)器空閑時(shí)間的鄰域結(jié)構(gòu)[30]如圖2 所示.其中w為工序塊上的工序,JP[w]和JS[w]分別為與工序w相鄰的同工件的前序工序和后序工序,makespan 為最大完工時(shí)間.工序w能否進(jìn)行移動(dòng)則需要考慮機(jī)器的空閑時(shí)間,其中工序w的機(jī)器空閑時(shí)間從JP[w]的最早完工時(shí)間開始到JS[w]的最遲開工時(shí)間,即[CE(JP[w]),SL(JS[w])].若JP[w]不存在時(shí),則令CE(JP[w])=0.若JS[w]不存在時(shí),則令SL(JS[w])=makespan.工序的移動(dòng)有同機(jī)器的工序移動(dòng)和跨機(jī)器的工序移動(dòng),同機(jī)器的工序移動(dòng)是指僅改變工序w在原加工機(jī)器上的加工次序,跨機(jī)器的工序移動(dòng)是指對(duì)工序w時(shí)進(jìn)行加工順序和加工機(jī)器的改變.

圖2 面向機(jī)器空閑時(shí)間的鄰域結(jié)構(gòu)Fig.2 Neighborhood structure for machine idle time

1) 同機(jī)器的工序移動(dòng).當(dāng)工序w進(jìn)行前移或后移操作時(shí),則要求該工序的當(dāng)前加工機(jī)器Mk在范圍[CE(JP[w]),SL(JS[w])]內(nèi)存在兩相鄰工序或工序與機(jī)器空閑時(shí)間端點(diǎn)之間有空閑時(shí)間.若工序w移動(dòng)到工序x之前時(shí),則要求工序x的開工時(shí)間與CE(JP[w])的差值大于零.若工序w移動(dòng)到工序x和工序y之間時(shí),則要求工序x與工序y之間存在空閑時(shí)間.若工序w移動(dòng)到工序z之后時(shí),則要求工序z的結(jié)束時(shí)間與SL(JS[w])]的差值小于零.如圖2 所示,細(xì)實(shí)線表示工序w進(jìn)行前移操作,虛線表示工序w進(jìn)行后移操作.

2)跨機(jī)器的工序移動(dòng).當(dāng)工序w進(jìn)行跨機(jī)器移動(dòng)時(shí),則要求工序w在可選機(jī)器集中至少存在一臺(tái)機(jī)器Mk′,滿足在范圍[CE(JP[w]),SL(JS[w])]內(nèi)存在連續(xù)空閑時(shí)間T0大于或等于工序w在該機(jī)器上的加工時(shí)間Pw,即T0≥Pw.工序w進(jìn)行跨機(jī)器移動(dòng)時(shí)的具體操作如圖2 中雙點(diǎn)畫線所示.

3.3.3 精英存儲(chǔ)策略

利用變鄰域局部搜索算法對(duì)種群Ut進(jìn)行局部搜索后得種群Gt.為防止在迭代過程中丟失最優(yōu)解,建立了種群精英記憶庫(kù)且容量為N,將種群Gt與當(dāng)前精英記憶庫(kù)進(jìn)行合并(初始精英記憶庫(kù)為初始種群),去掉重復(fù)染色體后(保持個(gè)體前后順序不變)利用Pareto 非支配原則對(duì)記憶庫(kù)個(gè)體進(jìn)行分層,并選取非支配層個(gè)體F1存入精英記憶庫(kù).其中精英記憶庫(kù)的當(dāng)前容量為N0=min{|F1|,N},若非支配層個(gè)體數(shù)大于N,則截取F1中的前N 個(gè)個(gè)體進(jìn)入記憶庫(kù).

4 NSGA-III-AD算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題

4.1 種群初始化

在進(jìn)行種群個(gè)體初始化時(shí),首先介紹了染色體的編碼與解碼方式,然后利用混合初始化方法對(duì)個(gè)體進(jìn)行初始化,以提高初始調(diào)度解的質(zhì)量.

4.1.1 編碼與解碼

車間調(diào)度實(shí)例采用實(shí)際加工的工序進(jìn)行編碼,以避免虛工序的產(chǎn)生.工序鏈中的基因采用工件號(hào)進(jìn)行編碼,工件號(hào)出現(xiàn)的次數(shù)即為工件的工序數(shù),即第j 次出現(xiàn)的工件號(hào)i,表示工件Ji的第j 道工序Oi,j.機(jī)器鏈中的基因是工序的加工機(jī)器在當(dāng)前工序可選機(jī)器集中的序號(hào),而不是機(jī)器代號(hào),以減少個(gè)體在后續(xù)操作中無效解的產(chǎn)生.其中工序鏈基因與機(jī)器鏈基因一一對(duì)應(yīng),工序編碼的具體執(zhí)行過程如表1 所示.

表1 FJSP 實(shí)例Table 1 FJSP example

以表1 為例,FJSP 的染色體編碼如圖3 所示,圖4 為對(duì)圖3 所示的染色體進(jìn)行解碼后所得甘特圖.

圖3 FJSP 的染色體編碼Fig.3 Chromosome encoding of FJSP

圖4 調(diào)度甘特圖Fig.4 Gantt chart of scheduling

圖3 中工序鏈的編碼為[2 2 1 2 1],其中第一個(gè)“2”表示工件J2的第一道工序,第二個(gè)“2”表示工件J2的第二道工序,以此類推,工序順序?yàn)镺2,1→O2,2→O1,1→O2,3→O1,2.其中工序O1,1的可選機(jī)器集為Jm={M1,M4,M5},當(dāng)選擇機(jī)器M4加工該工序時(shí),由于該機(jī)器在當(dāng)前可選機(jī)器集Jm中的序號(hào)為“2”,因此,在機(jī)器鏈中與工序O1,1相對(duì)應(yīng)的機(jī)器基因?yàn)椤?”.

進(jìn)行染色體解碼時(shí),從左至右依次將每道工序安排至對(duì)應(yīng)的加工設(shè)備上,直到所有工序都安排完為止.若工件Ji的第j 道工序Oi,j在機(jī)器Mk上加工,則工序Oi,j的最早開工時(shí)間為STij=max{ETi(j-1)k′,MIk,Ri}.

4.1.2 混合初始化方法

種群初始化在FJSP 中扮演重要角色,初始解的質(zhì)量對(duì)算法的求解速度和質(zhì)量都有較大的影響,且機(jī)器選擇比工序排序更加重要.在此,利用混合初始化方法對(duì)加工機(jī)器進(jìn)行選擇,包括全局選擇(GS)、局部選擇(LS)和隨機(jī)選擇(RS)[12].GS 旨在選擇當(dāng)前工序機(jī)器集中總荷載最小的機(jī)器,主要考慮設(shè)備之間荷載的均衡性,以提高設(shè)備利用率.LS 則是在當(dāng)前工序機(jī)器集中選擇臨時(shí)荷載最小的機(jī)器.而RS 則是對(duì)加工機(jī)器進(jìn)行隨機(jī)選擇,使調(diào)度解盡量均勻離散的分布在目標(biāo)空間中,以保持種群個(gè)體的多樣性.在NSGA-III-AD 中的工序鏈隨機(jī)生成,機(jī)器鏈則利用比例GLR=(0.6,0.3,0.1)進(jìn)行初始化[31].

4.2 基于近似支配的選擇操作

在多目標(biāo)車間調(diào)度問題中,選擇操作主要從三個(gè)方面進(jìn)行闡述.一方面是選擇種群個(gè)體進(jìn)行遺傳操作,在NSGA-III-AD 中,利用均勻分布的思想選擇個(gè)體進(jìn)行交叉和變異操作,盡量使每個(gè)個(gè)體都能被選中.另一方面是對(duì)個(gè)體完成交叉或變異操作后所獲的個(gè)體集進(jìn)行近似非支配排序,選取非支配層個(gè)體作為個(gè)體進(jìn)行遺傳操作后的局部最優(yōu)輸出.最后運(yùn)用近似支配原則和小生境技術(shù),從完成交叉、變異及局部搜索后的個(gè)體集合中選取N個(gè)個(gè)體作為子代種群.

4.3 基于變鄰域的遺傳操作

遺傳操作包含交叉操作和變異操作,二者都是通過對(duì)染色體產(chǎn)生小的干擾,從而達(dá)到對(duì)解空間搜索的目的.進(jìn)行個(gè)體交叉操作時(shí),工序排序部分采用均勻交叉(UX)和基于工件優(yōu)先順序的交叉(IPOX)策略,對(duì)機(jī)器選擇部分則利用兩點(diǎn)交叉策略.對(duì)染色體進(jìn)行變異操作時(shí),工序鏈選擇基本鄰域搜索變異策略[12],機(jī)器鏈則采用輪盤賭變異策略.

4.4 算法步驟

NSGA-III-AD 算法求解多目標(biāo)柔性作業(yè)車間調(diào)度問題的具體步驟如下:

步驟1完成種群規(guī)模N,交叉概率Pc,變異概率Pm,最大迭代次數(shù)MAXGEN 等參數(shù)的設(shè)置,利用混合初始化方法進(jìn)行個(gè)體初始化,并生成初始精英記憶庫(kù).

步驟2依據(jù)設(shè)置的參數(shù),計(jì)算參考點(diǎn)總數(shù)H,并生成均勻分布的參考點(diǎn)集合Zr.

步驟3判斷是否滿足終止條件,若滿足則輸出最優(yōu)解集,否則轉(zhuǎn)至步驟4.

步驟4父代種群完成交叉和變異操作后,合并父代和子代種群得Ut,對(duì)種群Ut進(jìn)行變鄰域搜索后得種群Gt,計(jì)算Gt中個(gè)體的關(guān)聯(lián)參考點(diǎn)、垂直距離、投影距離、歐幾里得距離及小生境數(shù)等,利用近似支配原則和小生境技術(shù)生成子代種群Qt.

步驟5將Gt與當(dāng)前精英記憶庫(kù)合并,去掉重復(fù)染色體后選擇Pareto 非支配層個(gè)體進(jìn)入精英記憶庫(kù).

步驟6返回步驟3.

5 計(jì)算結(jié)果與對(duì)比分析

為評(píng)估和比較NSGA-III-AD 算法的性能.在本節(jié)中,首先構(gòu)建了非支配解集的評(píng)價(jià)指標(biāo).其次利用四個(gè)Kacem 實(shí)例[32]和兩個(gè)BRdata 實(shí)例[9,10]進(jìn)行測(cè)試,驗(yàn)證了提出算法的整體性能.最后利用六個(gè)優(yōu)化目標(biāo)的生產(chǎn)實(shí)例進(jìn)行詳細(xì)分析,經(jīng)過參數(shù)優(yōu)化后,不僅驗(yàn)證了近似支配、變鄰域搜索和精英存儲(chǔ)策略在算法中存在的必要性,而且通過與不同優(yōu)化算法對(duì)比,證明了提出算法的高效性.

上述NSGA-III-AD 算法通過MATLAB R2017b 編程實(shí)現(xiàn).設(shè)置種群規(guī)模N=252,交叉概率Pc=0.9,變異概率Pm=0.05,最大迭代次數(shù)MAXGEN=40.程序運(yùn)行環(huán)境為Intel(R)Core(TM)i3-4170 處理器,主頻3.70 GHz,運(yùn)行內(nèi)存為4G 的個(gè)人計(jì)算機(jī).

5.1 非支配解集的評(píng)價(jià)指標(biāo)

為對(duì)非支配解集中的個(gè)體進(jìn)行全面有效的評(píng)估,結(jié)合文獻(xiàn)中的評(píng)價(jià)方法,提出解集的收斂性、多樣性、分布性和綜合性評(píng)價(jià)指標(biāo).對(duì)多個(gè)解集進(jìn)行綜合評(píng)價(jià)時(shí),先去掉每個(gè)解集內(nèi)的重復(fù)個(gè)體,然后合并最優(yōu)解集并對(duì)合并后的解集進(jìn)行歸一化處理,以消除量綱和不同目標(biāo)函數(shù)值范圍的影響.其中任意個(gè)體對(duì)第z個(gè)目標(biāo)值的歸一化方法為=(fz -fmin)/(fmax-fmin),若集合中的第z個(gè)目標(biāo)值都相同,則=1,其中fmax和fmin分別為合并后集合中第z個(gè)目標(biāo)的最大值和最小值,歸一化完成后個(gè)體X的目標(biāo)向量記為.

1)收斂性指標(biāo)(CM)

由于在實(shí)際車間調(diào)度問題中對(duì)Pareto 前端未知.因此,利用個(gè)體歸一化目標(biāo)值在關(guān)聯(lián)參考線上的投影距離,定義種群個(gè)體的收斂性,即

其中dr1(X)表示個(gè)體X的歸一化目標(biāo)值在第r條參考線上的投影距離,Zr={λ1,λ2,...,λH}為參考點(diǎn)集合,|A|為非支配解集A的個(gè)體數(shù).若CM 值越小,則種群個(gè)體的收斂性越好.

2)多樣性指標(biāo)(DM)

將個(gè)體關(guān)聯(lián)到參考點(diǎn)上,然后計(jì)算個(gè)體對(duì)每個(gè)參考點(diǎn)的貢獻(xiàn)度CD,若參考點(diǎn)r的小生境數(shù)為ρr,則與之關(guān)聯(lián)個(gè)體X對(duì)參考點(diǎn)r的貢獻(xiàn)度為CD(X,r)=1/ρr,若個(gè)體與該參考點(diǎn)不關(guān)聯(lián),則個(gè)體對(duì)該參考點(diǎn)的貢獻(xiàn)度為零.為此,解集A的多樣性指標(biāo)值定義為

其中CD(X,r)為個(gè)體X對(duì)參考點(diǎn)r的貢獻(xiàn)度,|A|為解集A的個(gè)體數(shù),Zr為參考點(diǎn)集合.若DM 值越大,則種群個(gè)體的多樣性性越好.

3)分布性指標(biāo)(SM)

分布性指標(biāo)是用來評(píng)價(jià)解集中的個(gè)體是否在目標(biāo)空間上分布均勻.因此,定義解集A的分布性指標(biāo)值為[3]

其中d(X)=min{‖X-X′ ‖,X /=X′,X′ ∈A}表示個(gè)體X與相鄰個(gè)體X′歸一化目標(biāo)值的歐幾里得距離,表示所有相鄰個(gè)體歸一化目標(biāo)值的平均歐幾里得距離.若SM 值越小,則說明解集中的個(gè)體越均勻的分布在目標(biāo)空間中.

4)超體積指標(biāo)(HVM)

定義解集A的參考點(diǎn)為R=[R1,R2,...,Rg]T=[1.21,1.21,...,1.21]T.關(guān)于參考點(diǎn)R的超體積是指被解集A中的歸一化目標(biāo)向量所支配且以點(diǎn)R為邊界的空間體積[?],即

其中Volume(A)表示解集A的勒貝格測(cè)度,表示被f′(X)支配而不被參考點(diǎn)R支配的所有個(gè)體歸一化目標(biāo)值圍成的的體積.

超體積指標(biāo)能夠在某種程度上綜合反映解集的收斂性、多樣性和分布性,超體積越大表示算法所獲的非支配解集越優(yōu).對(duì)最優(yōu)解集進(jìn)行綜合評(píng)價(jià)時(shí),優(yōu)先考慮超體積指標(biāo)和收斂性指標(biāo),然后再考慮多樣性和分布性指標(biāo).

5.2 三個(gè)目標(biāo)的測(cè)試結(jié)果與對(duì)比分析

為檢測(cè)NSGA-III-AD 算法的性能,先用四個(gè)Kacem 實(shí)例和兩個(gè)BRdata 實(shí)例進(jìn)行測(cè)試,優(yōu)化目標(biāo)分別為,最大完工時(shí)間f1、機(jī)器總負(fù)荷f4和瓶頸機(jī)器負(fù)荷f5最小.并將Kacem 實(shí)例的測(cè)試結(jié)果與EDA[4]、P-DABC[5]和MOGA[12]中的最優(yōu)解集進(jìn)行對(duì)比,測(cè)試結(jié)果如表2 所示.

表2 四個(gè)Kacem 算例的結(jié)果對(duì)比Table 2 Comparison of results of four Kacem examples

此外,將BRdata 算例的測(cè)試結(jié)果與hDPSO[7]、BEG-NSGA-II[8]、DABC[9]和PSO+RRHC[10]進(jìn)行對(duì)比,如表3所示,且最優(yōu)解集的各指標(biāo)評(píng)價(jià)值如表4 所示.

由表2 可知,NSGA-III-AD 算法在4×5問題上,較其它三種優(yōu)化算法能獲得更多的非支配解.在8×8和10×10 問題上的運(yùn)行結(jié)果與MOGA 算法相同,且優(yōu)于EDA 和P-DABC 算法.在15×10 問題上,除優(yōu)于P-DABC 算法外,與其它算法的非支配解集相同.由表3 和表4 可知,NSGA-III -AD 和DABC 算法在Mk01 問題上所獲解集的多樣性雖劣于BEG-NSGA-II 和PSO+RRHC 算法,但在超體積、收斂性和分布性指標(biāo)上都優(yōu)于其它三種算法.在Mk05 問題上,提出的算法在分布性指標(biāo)上優(yōu)于其它算法,在超體積、收斂性和多樣性指標(biāo)上都排名第二.通過實(shí)例測(cè)試,驗(yàn)證了NSGA-III-AD 算法求解多目標(biāo)FJSP 的有效性.

表3 兩個(gè)Mk 算例的結(jié)果對(duì)比Table 3 Comparison of results of two Mk examples

表4 兩個(gè)Mk 實(shí)例的非支配解集的指標(biāo)值Table 4 Index value of the non-dominated solution set of two Mk instance

5.3 六個(gè)目標(biāo)的測(cè)試結(jié)果與對(duì)比分析

為進(jìn)一步分析 NSGA-III -AD 算法的性能,對(duì)文獻(xiàn)[11]中的10×8 生產(chǎn)實(shí)例進(jìn)行分析.首先利用正交實(shí)驗(yàn)確定最佳或近似最佳的參數(shù)組合,其次對(duì)算法中的主要?jiǎng)?chuàng)新操作進(jìn)行有效性分析,最后通過與其它多目標(biāo)優(yōu)化算法進(jìn)行對(duì)比,進(jìn)一步驗(yàn)證了提出算法的有效性.所有算例和非支配解集詳見https://pan.baidu.com/s/1YNedwpfDuJxqGKEvSFuLww 提取碼:cu3f.

5.3.1 參數(shù)優(yōu)化

為分析參數(shù)設(shè)置對(duì)NSGA-III-AD 算法的影響,在保證其他參數(shù)不變的情況下,提取算法中較重要的種群規(guī)模、交叉概率和變異概率三個(gè)參數(shù),每個(gè)參數(shù)取三個(gè)不同的水平,利用正交實(shí)驗(yàn)規(guī)則,生成9 種不同的參數(shù)組合.運(yùn)行上述10×8 實(shí)例,得不同參數(shù)組合下非支配解集的各指標(biāo)評(píng)價(jià)值如表5 所示.

表5 不同參數(shù)組合下非支配解集的指標(biāo)值Table 5 Index value of non-dominated solution set under different parameter combinations

首先,從超體積指標(biāo)進(jìn)行分析,在類別為7,8 和9 的參數(shù)組合中,整體性能明顯優(yōu)于其它組合.其次,從收斂性指標(biāo)上來看,類別7 較類別8 和9 更收斂,且三者在多樣性指標(biāo)和分布性指標(biāo)上的差異較小.綜上所述,選擇類別為7 的參數(shù)組合進(jìn)行算例結(jié)果的優(yōu)化,同時(shí)也證明了初始參數(shù)設(shè)置的合理性.

通過Kacem 和BRdata 實(shí)例的測(cè)試,證明了NSGA-III-AD 算法的整體性能.為進(jìn)一步分析近似支配、變鄰域搜索及精英存儲(chǔ)策略在提出算法中發(fā)揮的作用,于是在NSGA-III-AD 的基礎(chǔ)上進(jìn)行局部修改,提出了三種算法:1) NSGA-III-PARETO,利用Pareto 非支配原則取代近似支配原則.2) NSGA-III-AD-VNS,不包含面向空閑時(shí)間的變鄰域搜索策略.3) NSGA-III-AD-ESS,不包含面向迭代過程的精英存儲(chǔ)策略.三種算法運(yùn)行上述10×8 的調(diào)度實(shí)例,所獲最優(yōu)解集的各指標(biāo)評(píng)價(jià)值如表6 所示.

表6 不同算法下的最優(yōu)解集的各指標(biāo)值Table 6 Index values of optimal solution sets under different algorithms

5.3.2 近似支配、變鄰域搜索及精英保持策略的有效性分析

由表6 可知,四種算法在超體積指標(biāo)上無明顯差異,但從收斂性指標(biāo)上來看,NSGA-III-AD 算法明顯優(yōu)于其它三種算法.從多樣性指標(biāo)上來看,除NSGA-III-PARETO 算法外,提出的算法與其他兩種算法近似相等.但利用Pareto 進(jìn)行非支配排序時(shí),在收斂性和分布性指標(biāo)上都最差.將上述算法與NSGA-III-AD 算法進(jìn)行兩兩對(duì)比可知,提出的近似支配原則、變鄰域局部搜索和精英存儲(chǔ)策略在NSGA-III-AD 算法中發(fā)揮積極作用.

5.3.3 算法對(duì)比

上述分析證明了NSGA-III-AD 算法及其創(chuàng)新操作的有效性.在本節(jié)中,將提出的算法與NSGA-II[11],NSGA-III[20],NSGA-III/A-ENS[26],NSGA-III-RPCDP[27]和θ-DEA[28]算法進(jìn)行對(duì)比,運(yùn)行算例仍為10×8 的生產(chǎn)實(shí)例,并利用上述四個(gè)指標(biāo)對(duì)四種算法所獲的非支配解集進(jìn)行同時(shí)評(píng)價(jià),評(píng)價(jià)結(jié)果如表7 所示.

表7 六種不同算法下的最優(yōu)解集的各指標(biāo)值Table 7 Index values of optimal solution sets under six different algorithms

由表7 可知,NSGA-III-AD 算法的整體性能(超體積)明顯優(yōu)于其它五種算法,θ-DEA 算法在整體性能最差.其中NSGA-III/A-ENS 算法的收斂性最好,但NSGA-III 和NSGA-III-RPCDP 算法的收斂性明顯劣與其它算法.提出的算法與改進(jìn)NSGA-II 算法在四個(gè)指標(biāo)上各有優(yōu)劣,但提出算法所獲非支配解的個(gè)體數(shù)接近是NSGA-II 的四倍.利用綜合加權(quán)法[11]評(píng)選最優(yōu)的調(diào)度方案,并提取合并后解集中綜合評(píng)價(jià)得分最高的前40 個(gè)調(diào)度解并按照綜合評(píng)分降序排列,如表8 所示.權(quán)重向量

表8 部分最優(yōu)非支配解集及評(píng)價(jià)得分_________________________Table 8 Partial optimal non-dominated solution set and evaluation score

評(píng)價(jià)結(jié)果顯示,NSGA-III/A-ENS 和NSGA-II 所獲Pareto 解集評(píng)價(jià)得分最高的分別是方案36(序號(hào)4:D36=0.908 8)和方案17(序號(hào)7:D17=0.906 3).本文算法求得的非支配解集中共有3 個(gè)調(diào)度方案同時(shí)優(yōu)于上述兩個(gè)方案,其中評(píng)價(jià)得分最高的是方案27(序號(hào)1:D27=0.911 0),其對(duì)應(yīng)的調(diào)度甘特圖如圖5 所示.

圖5 最滿意方案27 對(duì)應(yīng)的調(diào)度解Fig.5 Scheduling solution corresponding to scheme 27

評(píng)價(jià)得分在0.895 6 及以上的調(diào)度方案中,NSGA-III /A-ENS 中有4 個(gè),文獻(xiàn)[11]中有10 個(gè),提出的算法中有26 個(gè).評(píng)價(jià)得分(S) 與調(diào)度解個(gè)體數(shù)(Number)的具體分布情況如圖6 所示,其中Numberl=,Nl為算法l所獲的非支配解個(gè)體數(shù),S ∈[0,1]為評(píng)價(jià)得分的下界閾值.

圖6 綜合評(píng)價(jià)得分與個(gè)體數(shù)的分布曲線Fig.6 Distribution curve of comprehensive evaluation scores and individual numbers

由于在特定權(quán)重下的綜合評(píng)價(jià)無法全面的體現(xiàn)企業(yè)各部門期望的調(diào)度方案.為評(píng)價(jià)NSGA-III-AD 的性能,提出通過隨機(jī)模擬40 000～1 000 000 名不同決策者對(duì)上述六個(gè)目標(biāo)的權(quán)重向量,并利用綜合加權(quán)法對(duì)合并后的解集進(jìn)行綜合評(píng)價(jià),最后比較滿意解在上述六種算法中出現(xiàn)的總次數(shù).若最高綜合評(píng)價(jià)得分出現(xiàn)在多種算法中,則對(duì)應(yīng)算法中的最優(yōu)解次數(shù)均增加1.通過25 次的仿真模擬,滿意解在各算法中出現(xiàn)的總次數(shù)如圖7 所示.

圖7 滿意調(diào)度方案在六種算法中出現(xiàn)的次數(shù)Fig.7 The number of times the satisfactory scheduling scheme appears in six algorithms

由圖7 可知,隨著模擬權(quán)重?cái)?shù)量的不斷增多,滿意解在NSGA-III-AD 中出現(xiàn)的總次數(shù)也越來越多,且與其它五種算法的差異也越來越明顯,即提出的算法能找到更多的滿意解.綜上所述,NSGA-III-AD 算法能盡可能的找到趨近于超曲面前端的解,在實(shí)際生產(chǎn)過程中也將具有更大的應(yīng)用價(jià)值.

6 結(jié)束語(yǔ)

本文在標(biāo)準(zhǔn)NSGA-III 算法的基礎(chǔ)上,結(jié)合多目標(biāo)柔性作業(yè)車間調(diào)度問題的特點(diǎn),提出了基于參考點(diǎn)近似支配的NSGA-III-AD 算法.首先,分析了標(biāo)準(zhǔn)NSGA-III 算法在求解多目標(biāo)優(yōu)化問題時(shí)存在的不足.為此,定義了種群個(gè)體的近似支配原則,并提出了面向空閑時(shí)間的變鄰域局部搜索算法和精英存儲(chǔ)策略.其次,對(duì)NSGA-III-AD 算法求解多目標(biāo)FJSP 的種群初始化方法、近似支配的選擇操作、變鄰域的遺傳操作和算法流程進(jìn)行了詳細(xì)闡述.然后,利用三個(gè)優(yōu)化目標(biāo)的基準(zhǔn)實(shí)例對(duì)提出算法的整體性能進(jìn)行了評(píng)估,驗(yàn)證了提出算法的有效性.最后,利用六個(gè)優(yōu)化目標(biāo)的生產(chǎn)實(shí)例,對(duì)算法中的參數(shù)設(shè)置和創(chuàng)新操作進(jìn)行了分析,并與其它多目標(biāo)優(yōu)化算法進(jìn)行了對(duì)比,從局部和整體兩方面驗(yàn)證了提出算法的有效性和可行性.但本文提出的算法仍有許多有待改進(jìn)之處,其中支配策略是多目標(biāo)優(yōu)化問題的核心之一,提出有效的支配原則是促使種群進(jìn)化的前提,也是目前研究的熱點(diǎn).此外,在今后的研究過程中不斷尋求NSGA-III 算法的最佳性能,可將多種智能優(yōu)化算法進(jìn)行融合,以提高算法的搜索能力和適用域,并將其應(yīng)用于生產(chǎn)實(shí)際.