考慮能耗和完工時(shí)間的柔性流水車間調(diào)度方法

牟 云，閻春平，劉藝繁，孫 雷

（重慶大學(xué) 機(jī)械工程學(xué)院，重慶 400030）

0 引言

柔性流水車間調(diào)度問(wèn)題(Flexible Flow-shop Scheduling Problem,FFSP)，又稱為混合流水車間調(diào)度問(wèn)題，由Salvador在1973年第一次提出[1]，F(xiàn)FSP問(wèn)題可以看作是經(jīng)典流水調(diào)度問(wèn)題和并行機(jī)調(diào)度問(wèn)題的結(jié)合，廣泛存在于機(jī)械、物流等領(lǐng)域[2]。按并行機(jī)種類的不同，柔性流水車間調(diào)度問(wèn)題可以分為相同并行機(jī)、均勻并行機(jī)和不相關(guān)并行機(jī)三類[3]。

FFSP被提出后的四十多年里，國(guó)內(nèi)外許多學(xué)者都對(duì)該問(wèn)題進(jìn)行了研究。主要通過(guò)采用不同的算法和不同的優(yōu)化目標(biāo)進(jìn)行求解。目前，對(duì)于FFSP問(wèn)題的求解算法主要分為三類：1) 精確算法；2）啟發(fā)式算法；3）元啟發(fā)式算法，目前應(yīng)用最為廣泛[4]。例如，王圣堯等使用分布估計(jì)算法求解FFSP問(wèn)題，通過(guò)基于種群的概率分布模型采樣來(lái)產(chǎn)生新種群，并通過(guò)案例驗(yàn)證了該算法求解結(jié)果優(yōu)于傳統(tǒng)遺傳算法、人工免疫系統(tǒng)算法[5]。任彩樂等通過(guò)改進(jìn)候鳥優(yōu)化算法求解FFSP問(wèn)題，研究了基于隨機(jī)迭代排列解碼方法的候鳥優(yōu)化算法，通過(guò)大量案例驗(yàn)證[3]。Cui等采用改進(jìn)的人工蜂群算法求解FFSP問(wèn)題，結(jié)合差分算法和變領(lǐng)域算法以產(chǎn)生新的雇傭蜂和觀察蜂，并驗(yàn)證了算法的有效性[6]。在優(yōu)化目標(biāo)方面，大量學(xué)者以最小最大完成時(shí)間為目標(biāo)對(duì)FFSP問(wèn)題求解。例如，宋存利提出改進(jìn)的貪婪遺傳算法求解以完工時(shí)間為目標(biāo)的不相關(guān)行機(jī)FFSP問(wèn)題[7]。Komaki等使用人工免疫系統(tǒng)算法求解以完工時(shí)間為目標(biāo)的兩階段FFSP問(wèn)題[8]。Deng等提出了一種混合離散群搜索算法求解以最小作業(yè)時(shí)間為目標(biāo)的FFSP問(wèn)題[9]。杜利珍等采用基于權(quán)重編碼的果蠅優(yōu)化算法求解不相關(guān)并行機(jī)FFSP問(wèn)題[10]。隨著能源、環(huán)境問(wèn)題的日益嚴(yán)峻，結(jié)合能耗的多目標(biāo)調(diào)度研究也日趨增加。例如，姜天華以能耗成本和完工時(shí)間成本的加權(quán)和為優(yōu)化目標(biāo)，使用灰狼優(yōu)化算法求解[11]。Zeng等考慮了制造過(guò)程中材料的浪費(fèi)，采用非支配排序遺傳算法求解最小化制造時(shí)間和材料浪費(fèi)的多目標(biāo)FFSP問(wèn)題[12]。Sven等構(gòu)建了總加工時(shí)間、總能耗和峰值負(fù)載的多目標(biāo)調(diào)度模型，提出了多階段迭代局部搜索算法進(jìn)行求解[13]。黃海松等構(gòu)建了以時(shí)間、成本、能耗及質(zhì)量為目標(biāo)的調(diào)度模型，采用離散花朵授粉算法進(jìn)行求解[14]。李聰波等定義了機(jī)床加工過(guò)程中的廣義能耗，構(gòu)建了面向廣義能耗的調(diào)度模型，采用了模擬退火算法進(jìn)行求解[15]。

不同的調(diào)度順序?qū)е略O(shè)備的等待時(shí)間差異較大，設(shè)備的選擇對(duì)加工能耗也有所影響。考慮到制造加工過(guò)程中設(shè)備切削能耗、設(shè)備切削前后的空載能耗和設(shè)備待機(jī)等待能耗等設(shè)備加工相關(guān)能耗受調(diào)度順序影響較大，因此，本文構(gòu)建一個(gè)考慮設(shè)備加工相關(guān)能耗和完工時(shí)間的多目標(biāo)柔性流水車間調(diào)度模型（Multi-objective Flexible Flow-shop Scheduling Model，MOFFSM），采用結(jié)合局部搜索的多種群遺傳算法（Local Search-based Multi-population Genetic Algorithm，LS-MGA）進(jìn)行求解。通過(guò)算例對(duì)本文算法進(jìn)行測(cè)試，驗(yàn)證了改進(jìn)的多種群遺傳算法能夠有效解決多目標(biāo)柔性流水車間調(diào)度問(wèn)題。

1 多目標(biāo)柔性流水車間調(diào)度模型

1.1 參數(shù)定義

為便于模型建立，定義相關(guān)模型參數(shù)如表1所示。

表1 MOFFSM模型相關(guān)參數(shù)表

1.2 考慮加工相關(guān)能耗和完工時(shí)間的多目標(biāo)柔性流水車間調(diào)度模型

不相關(guān)并行機(jī)柔性流水車間工序流程模型如圖1所示。柔性流水車間調(diào)度問(wèn)題的基本描述如下：有n個(gè)待加工工件，每個(gè)工件需要經(jīng)過(guò)p道工序加工，每道工序有Mj臺(tái)加工設(shè)備可供選擇。

圖1 不相關(guān)并行機(jī)柔性流水車間工序流程模型

柔性流水車間的能耗包括直接能耗和間接能耗[16]。其中直接能耗是指與工件加工過(guò)程中直接相關(guān)的能耗，包括設(shè)備加工能耗、更換刀夾具的能耗、設(shè)備空閑等待能耗等[17]；間接能耗是指工件加工過(guò)程中必不可少的輔助設(shè)備所消耗的能耗,如工件搬運(yùn)能耗、車間照明能耗等。對(duì)于不同的調(diào)度結(jié)果，間接能耗和部分直接能耗的變化并不大，為更直觀的分析不同調(diào)度結(jié)果對(duì)工件加工能耗和完工時(shí)間的影響，本文只考慮因調(diào)度順序差異而變化較大的加工能耗Ep和設(shè)備空閑等待能耗Ew。

為能耗分析更具針對(duì)性，本文僅考慮由設(shè)備切削能耗Ec、設(shè)備切削前后的空載能耗Enl和附加載荷損耗能耗Ea組成的加工能耗，總加工能耗計(jì)算公式如下：

設(shè)備的總輸入功率Pink與空載功率Pnlk、切削功率Pck、附加載荷損耗功率Pa之間存在如下表達(dá)式[18]：

其中a0、a1為系數(shù)，當(dāng)主軸轉(zhuǎn)速穩(wěn)定時(shí)，設(shè)備的輸入功率和空載功率的變化比較小，可視為恒定值[19]。結(jié)合式(2)可知，主軸轉(zhuǎn)速穩(wěn)定時(shí)設(shè)備的空載功率Pwk和切削功率Pck可視為恒定值，式(3)可表示為：

總加工能耗計(jì)算公式：

設(shè)備的等待時(shí)間由所有設(shè)備的工作時(shí)間與所有工件的加工時(shí)間之差表示：

總待機(jī)能耗計(jì)算公式：

設(shè)備的待機(jī)功率已知且可以視為恒定值，式(7)可表示為：

目標(biāo)能耗計(jì)算公式:

空載功率Pwk、輸入功率Pink可通過(guò)功率傳感器直接測(cè)得。

完工時(shí)間取最遲完工設(shè)備時(shí)間，完工時(shí)間目標(biāo)函數(shù)如式(11)所示。

根據(jù)式(9)、式(11)建立考慮工件加工相關(guān)能耗和完工時(shí)間的多目標(biāo)柔性流水車間調(diào)度模型，目標(biāo)函數(shù)：

存在以下約束條件：

其中：式(13)表示至少有一道工序的加工設(shè)備數(shù)大于1；式(14)表示各個(gè)工序可選擇設(shè)備數(shù)之和等于總設(shè)備數(shù)；式(15)表示任一工件每次加工時(shí)只能選擇一臺(tái)設(shè)備；式(16)表示每個(gè)工件必須按工藝順序經(jīng)過(guò)p道工序加工；式(17)表示各個(gè)工件每道工序的加工結(jié)束時(shí)間為加工開始時(shí)間與該道工序的加工時(shí)間之和；式(18)表示每臺(tái)設(shè)備在0時(shí)刻均可使用，設(shè)備開始第一次加工時(shí)啟動(dòng)。

2 結(jié)合局部搜索的多種群遺傳算法

2.1 LS-MGA算法介紹

遺傳算法（Genetic Algorithm，GA）是一種元啟發(fā)式算法[20]。遺傳算法是基于生物進(jìn)化現(xiàn)象衍生的，包括遺傳過(guò)程中的基因交叉、變異、選擇淘汰等現(xiàn)象。遺傳算法在調(diào)度優(yōu)化問(wèn)題中應(yīng)用較多。但種群中出現(xiàn)適應(yīng)值比較高的染色體時(shí)，該染色體會(huì)在種群中迅速擴(kuò)散，導(dǎo)致算法過(guò)早收斂到局部解。而且遺傳算法的結(jié)果與染色體數(shù)目、交叉率、變異率等參數(shù)的設(shè)定有較大關(guān)系。基于上述分析，本文提出了結(jié)合局部搜索的多種群遺傳算法（LSMGA）。算法流程如圖2所示。

圖2 結(jié)合局部搜索的多種群遺傳算法流程圖

LS-MGA具體操作步驟如下：

步驟1：初始化相關(guān)參數(shù)：種群數(shù)MP，每個(gè)種群染色體數(shù)Psize，交叉概率Pc，變異概率Pv，最大迭代次數(shù)MaxGen，代溝Gap等，迭代計(jì)算標(biāo)志Gen=0。

步驟2：初始化各種群，生成MP*Psize條染色體編碼。

步驟3：若滿足條件Gen>MaxGen，則輸出Pareto解集；不滿足則計(jì)算各種群中染色體的多目標(biāo)評(píng)價(jià)函數(shù)值。

步驟4：采用輪盤賭選擇法從每個(gè)種群中篩選評(píng)價(jià)值較高的Psize*Gap條染色體。

步驟5：對(duì)步驟4篩選出的染色體進(jìn)行交叉操作，交叉概率Pc，本文采用了3種交叉算子。

步驟6：步驟5交叉后的染色體進(jìn)行變異操作，變異概率Pv。

步驟7：將本種群的評(píng)價(jià)值最高染色體插入鄰近種群。

步驟8：選取經(jīng)步驟4～步驟7操作前后評(píng)價(jià)值較高的Psize條染色體作為子代染色體。

步驟9：將各種群中的評(píng)價(jià)值最高染色體存入精英種群BPGen。

步驟10：對(duì)精英種群中的染色體進(jìn)行局部搜索，使用循環(huán)交換、循環(huán)插入、循環(huán)逆序三種鄰域搜索算子，并與局部搜索前的染色體的評(píng)價(jià)函數(shù)值進(jìn)行比較。

步驟11：若局部搜索后的染色體優(yōu)于原染色體，將精英種群中對(duì)應(yīng)的染色體以及對(duì)應(yīng)種群的最劣染色體替換。

步驟12：若種群中評(píng)價(jià)值最高染色體數(shù)占種群總?cè)旧w數(shù)的比例超過(guò)50%，將評(píng)價(jià)值最高的染色體替換為隨機(jī)生成的新染色體。

步驟13：記錄精英種群BPGen的Pareto解集，記為PSGen，Gen=Gen+1，進(jìn)入步驟3。

2.2 編碼方案

每一條染色體編碼對(duì)應(yīng)調(diào)度問(wèn)題的一個(gè)解，編碼的方式會(huì)影響最終解的質(zhì)量。本文按工序分段編碼，將工件加工序號(hào)和加工設(shè)備序號(hào)分開。例如，有6個(gè)待加工工件，每個(gè)工件均需經(jīng)過(guò)3道工序加工，每道工序?qū)?yīng)有{3，2，3}臺(tái)加工設(shè)備可供選擇，對(duì)該調(diào)調(diào)度問(wèn)題進(jìn)行編碼，第一道工序編碼示例如圖3所示。

圖3 示例調(diào)度問(wèn)題第一道工序編碼示例

每道工序的編碼分為工件加工序號(hào)和加工設(shè)備序號(hào)，工件加工序號(hào)長(zhǎng)度為6，加工設(shè)備序號(hào)長(zhǎng)度為6，3到工序編碼總長(zhǎng)度為36。第一道工序6個(gè)加工零件按“5-1-4-2-3-6”的順序依次加工，即5號(hào)工件最先加工，1號(hào)工件次之，6號(hào)工件最后加工。“3-1-1-3-2-2”表示6個(gè)工件對(duì)應(yīng)該工序階段的設(shè)備序號(hào)，第一個(gè)加工工件（即5號(hào)工件）的第一道工序選擇3號(hào)設(shè)備，第二個(gè)加工工件（即1號(hào)工件）的第一道工序選擇1號(hào)設(shè)備，以此類推。根據(jù)零件編號(hào)、設(shè)備序號(hào)及加工時(shí)間即可計(jì)算相應(yīng)的切削能耗、等待能耗等數(shù)據(jù)。

2.3 種群初始化

種群的初始化影響最終果的質(zhì)量和收斂速度。種群的初始化涉及工件加工順排序和設(shè)備選擇兩方面。為在保證種群多樣性的同時(shí)兼顧初始種群的質(zhì)量，隨機(jī)生成各種群第一道工序的加工順序，后續(xù)工序的加工順序按“先完工先加工”的規(guī)則排序，即前序工作先完工先加工，若有多個(gè)工件同時(shí)完工，隨機(jī)生成同時(shí)完工工件的加工順序。設(shè)備選擇采取兩種方式：①輪盤賭選擇：根據(jù)設(shè)備的加工時(shí)間為各設(shè)備分配選擇概率，加工時(shí)間長(zhǎng)的選擇概率低，按輪盤賭選擇法選擇各工件的加工設(shè)備；②隨機(jī)選擇：隨機(jī)選擇各工件的加工設(shè)備。通過(guò)隨機(jī)選擇的方式確定使用哪種設(shè)備選擇方式。

2.4 交叉算子

交叉操作可以有效提高種群編碼的多樣性，普通遺傳算法通過(guò)交叉兩條染色體產(chǎn)生新的編碼。考慮到交叉概率對(duì)求解結(jié)果的影響較大，本文對(duì)各個(gè)種群分配不同的交叉概率。同時(shí)，本文使用三種交叉算子對(duì)個(gè)體的編碼進(jìn)行交叉，每次交叉操作時(shí)通過(guò)隨機(jī)選擇的方式確定使用哪種交叉算子。

1）單點(diǎn)自交叉算子

單點(diǎn)自交叉是在一條染色體上進(jìn)行交叉操作，交叉后產(chǎn)生一條新染色體，具體步驟如下：

步驟1：在染色體編碼的加工序號(hào)段隨機(jī)選擇交叉點(diǎn)。

步驟2：將交叉點(diǎn)及其后面的工序整體移到該工序段最前端。

步驟3：根據(jù)交叉后的工序重新選擇設(shè)備。

例如，一條染色體的加工序號(hào)為“123654789”，在第4個(gè)點(diǎn)進(jìn)行自交叉，交叉后為“654789123”。

2）多點(diǎn)自交叉算子

多點(diǎn)自交叉是在一條染色體上選擇多個(gè)點(diǎn)進(jìn)行交叉操作，交叉后產(chǎn)生一條新染色體，具體步驟如下：

步驟1：在染色體的每一個(gè)加工序號(hào)段隨機(jī)生成交叉位置。

步驟2：將每個(gè)工序段的交叉點(diǎn)及其后面的工序整體移到該工序段最前端。

步驟3：根據(jù)交叉后的工序重新選擇設(shè)備。

例如，一條包含兩個(gè)工序的染色體加工序號(hào)為“123654789|865791324”，兩個(gè)工序的自交叉點(diǎn)位4和5，交叉后為“654789123|913248657”。

3）多點(diǎn)互交叉算子

多點(diǎn)互交叉是在兩條染色體上選取多個(gè)位置進(jìn)行交叉，交叉后產(chǎn)生兩條新染色體，具體步驟如下：

步驟1：在染色體的每一個(gè)加工序號(hào)段隨機(jī)生成交叉位置。

步驟2：每個(gè)交叉點(diǎn)將對(duì)應(yīng)工序段的加工序號(hào)分成兩部分，交換兩條染色體交換對(duì)應(yīng)工序段的后半部分。

步驟3：交叉后的染色體中存在缺失或重復(fù)的基因，根據(jù)交叉前基因映射關(guān)系修改問(wèn)題基因。

步驟4：根據(jù)交叉后的工序重新選擇設(shè)備。

例如，6個(gè)工件3到工序的加工序號(hào)多點(diǎn)交叉示意圖如圖4所示。

圖4 多點(diǎn)交叉示意圖

2.5 變異算子

本文對(duì)各個(gè)種群分配不同的變異概率，變異操作通過(guò)交換兩個(gè)基因的位置實(shí)現(xiàn)，具體步驟如下：

步驟1：在染色體的每個(gè)加工序號(hào)段隨機(jī)生成兩個(gè)變異位置。

步驟2：交換每個(gè)加工序號(hào)段內(nèi)兩個(gè)變異位置的基因。

步驟3：根據(jù)變異后的加工序號(hào)重新選擇加工設(shè)備。

例如，一個(gè)染色體的加工序號(hào)“123654789”，變異位置為2和7，變異后的加工序號(hào)為“173654289”。

2.6 多目標(biāo)評(píng)價(jià)函數(shù)

考慮能耗和完工時(shí)間的調(diào)度優(yōu)化問(wèn)題在評(píng)價(jià)個(gè)體適應(yīng)度時(shí)，需同時(shí)考慮能耗目標(biāo)函數(shù)和完工時(shí)間目標(biāo)函數(shù)，本文采用適應(yīng)性權(quán)重法分配各目標(biāo)的權(quán)重。初始化種群后計(jì)算各種群目標(biāo)能耗最大值Emax、目標(biāo)能耗最小值Emin、完工時(shí)間最大值Tmax、完工時(shí)間最小值Tmin，適應(yīng)性多目標(biāo)評(píng)價(jià)函數(shù)如式(19)所示。

保留每代多目標(biāo)評(píng)價(jià)函數(shù)值最高的染色體編碼，并錄入解集。使用式(20)計(jì)算各非支配解的適應(yīng)度評(píng)價(jià)值[20]，式(21)計(jì)算各支配解的適應(yīng)度評(píng)價(jià)值。

其中，k∈[1,K]，K為非支配解的個(gè)數(shù)，N為支配解的個(gè)數(shù)，nk為非支配解k的支配解個(gè)數(shù)。N∈[1,N]，k0∈[1,K0]，K0為未支配該解的非支配解的個(gè)數(shù)，k1∈[1,K1]，K1為支配該解的非支配解的個(gè)數(shù)，適應(yīng)度計(jì)算示例如圖5所示。

圖5 適應(yīng)度計(jì)算示例

2.7 多策略鄰域搜索

針對(duì)遺傳算法容易陷入局部解這一問(wèn)題，對(duì)每個(gè)種群中評(píng)價(jià)函數(shù)值最高的染色體進(jìn)行局部搜索。對(duì)于調(diào)度問(wèn)題的局部搜索問(wèn)題，現(xiàn)有研究通常采用有限次的交換、插入、逆序等鄰域搜索策略[21]。本文針對(duì)每條染色體第一道工序的加工序號(hào)進(jìn)行局部搜索，采取循環(huán)交換、循環(huán)插入、循環(huán)逆序等三種鄰域搜索算子，以充分改善算法的局部搜索能力。后續(xù)工序按“先完工先加工”的規(guī)則重新排序，并根據(jù)新的加工順序重新選擇加工設(shè)備。通過(guò)隨機(jī)選擇的方式選擇上述三種鄰域搜索策略。

1）循環(huán)交換

循環(huán)交換第一道工序加工序號(hào)段上的兩個(gè)位置的編碼，直至完成所有交換操作。交換操作的偽代碼如表2所示（其中后續(xù)工序重排函數(shù)fRA，設(shè)備選擇函數(shù)fMC，評(píng)價(jià)函數(shù)fMO，下同）。

表2 交換操作偽代碼

2）循環(huán)插入

循環(huán)選擇第一道工序加工序號(hào)段上的兩個(gè)位置，將大位置編碼插入小位置前，直至完成所有位置的插入。循環(huán)插入算子的偽代碼如表3所示。

表3 插入操作偽代碼

3）循環(huán)逆序

循環(huán)選擇第一道工序加工序號(hào)段上的兩個(gè)位置，將兩個(gè)位置之間的加工序號(hào)編碼倒序，直至完成所有逆序操作。逆序操作的偽代碼如表4所示。

表4 逆序操作偽代碼

3 算例驗(yàn)證

為驗(yàn)證本文算法(LS-MGA)對(duì)于求解多目標(biāo)柔性流水車間調(diào)度優(yōu)化問(wèn)題的有效性，通過(guò)測(cè)試算例進(jìn)行驗(yàn)證。LS-MGA相關(guān)參數(shù)初始化：種群數(shù)10，種群大小60，各種群的交叉概率取0.7～0.9之間隨機(jī)數(shù)，各種群的變異概率取0.001～0.05之間隨機(jī)數(shù)，代溝0.9，迭代次數(shù)1000.使用MATLAB 2016進(jìn)行求解。

以某柔性加工車間內(nèi)6種零件的加工調(diào)度為例進(jìn)行驗(yàn)證。相關(guān)加工數(shù)據(jù)如表5、表6所示，其中Tc為切削時(shí)間（s），Pin為輸入功率（kW），Tnl為空載時(shí)間（s），Pnl為空載功率（kW），Pw為待機(jī)功率（kW））。

表5 加工時(shí)間數(shù)據(jù)表

表6 加工能耗數(shù)據(jù)表

使用LS-MGA、GA、LS-MGA_E、LS-MGA_T分別求解測(cè)試案例，其中：LS-MGA為本文算法，GA為考慮加工相關(guān)能耗和完工時(shí)間的遺傳算法、LS-MGA_E為本文算法以加工相關(guān)能耗為評(píng)價(jià)指標(biāo)、LS-MGA_T為本文算法以完工時(shí)間為評(píng)價(jià)指標(biāo)。對(duì)比分析各算法所求適應(yīng)度值最高解的最大完工時(shí)間T、最小目標(biāo)能耗E、評(píng)價(jià)指標(biāo)S，記錄LS-MGA和GA的Pareto解集平均值，記錄S-MGA_E、LS-MGA_T求解5次的平均值。將4組求解結(jié)果原始值繪制成散點(diǎn)圖，根據(jù)式(20)、式(21)對(duì)每種算法的求解結(jié)果進(jìn)行評(píng)價(jià)，為每種算法解集中解的評(píng)價(jià)值均值，圖6為求解結(jié)果散點(diǎn)圖，求解結(jié)果如表7所示。

圖6 案例求解結(jié)果散點(diǎn)圖

表7 測(cè)試案例求解結(jié)果

從求解測(cè)試結(jié)果可以看出，與GA相比，本文算法完工時(shí)間和能耗求解結(jié)果均較好；LS-MGA_E、LS-MGA_T僅在單一目標(biāo)求解方面能有較好結(jié)果，LS-MGA_E加工相關(guān)能耗求解結(jié)果比LS-MGA少，但完工時(shí)間求解結(jié)果遠(yuǎn)高于LS-MGA的求解結(jié)果，LS-MGA_T完工時(shí)間求解結(jié)果比LS-MGA少，但能耗求解結(jié)果遠(yuǎn)高于LS-MGA 的求解結(jié)果。LS-MGA的求解結(jié)果適應(yīng)度評(píng)價(jià)值也高于其他幾種算法，由此說(shuō)明了本文算法是有效的。

使用本文算法求解該算例詳細(xì)過(guò)程：求解過(guò)程中最小完工時(shí)間和最小目標(biāo)能耗變化趨勢(shì)如圖7所示。

圖7 最小完工時(shí)間和最小目標(biāo)能耗變化趨勢(shì)

隨著迭代次數(shù)的增加，在種群間精英交流及局部搜索的作用下，種群的完工時(shí)間均值和目標(biāo)能耗均值均在逐漸降低。隨著群中精英個(gè)體所占比重不斷增加，種群完工時(shí)間和目標(biāo)能耗均值趨于平穩(wěn)。當(dāng)精英個(gè)體比重達(dá)到閾值，干擾精英個(gè)體，刺激種群變化避免求解過(guò)程陷入局部解，直至滿足循環(huán)結(jié)束條件。最終獲得解集如圖8所示，根據(jù)式(20)、式(21)計(jì)算各解適應(yīng)度值。

圖8 求解結(jié)果解集

選取適應(yīng)度值最高的解：最小完工時(shí)間224s，最小目標(biāo)能耗3271.9kW·s，其甘特圖如圖9所示。

圖9 適應(yīng)度值最高解的甘特圖

4 結(jié)語(yǔ)

本文使用結(jié)合局部搜索的改進(jìn)遺傳算法求解考慮制造生產(chǎn)過(guò)程中設(shè)備的加工相關(guān)能耗和完工時(shí)間的多目標(biāo)柔性流水車間調(diào)度問(wèn)題。得出如下結(jié)論：

1）通過(guò)對(duì)工件加工過(guò)程中的能耗分析，建立了考慮加工過(guò)程中的設(shè)備切削能耗、設(shè)備切削前后空切能耗、設(shè)備空閑等待能耗在內(nèi)的設(shè)備加工相關(guān)能耗和完工時(shí)間的多目標(biāo)調(diào)度模型。

2）分析了傳統(tǒng)遺傳算法的特點(diǎn)，采用了基于循環(huán)交換、循環(huán)插入、循環(huán)逆序鄰域搜索的多種群遺傳算法。通過(guò)種群間精英交流，種群內(nèi)精英保留、精英局部搜索等方法，提高了種群的多樣性和染色體的質(zhì)量，獲得了Pareto解集。

3）通過(guò)測(cè)試算例對(duì)本文算法進(jìn)行測(cè)試，驗(yàn)證了本文所提出算法有效性。

多目標(biāo)柔性流水車間調(diào)度問(wèn)題將緩沖區(qū)視為無(wú)限大，在未來(lái)的研究中，為更加契合實(shí)際工程問(wèn)題，將考慮緩沖區(qū)有限的多目標(biāo)車間調(diào)度問(wèn)題。