解瀟晗，朱曉春*，周 琦，周志成，梁 偉

(1.南京工程學(xué)院 江蘇省先進(jìn)數(shù)控技術(shù)重點實驗室，江蘇 南京 210000；2.國網(wǎng)江蘇省電力公司 電力科學(xué)研究院，江蘇 南京 210000)

0 引 言

通過車間調(diào)度有效降低能源消耗，是企業(yè)實現(xiàn)可持續(xù)發(fā)展的必然要求[1]。傳統(tǒng)作業(yè)車間調(diào)度往往以完工時間最短、成本最低等為優(yōu)化目標(biāo)。何斌等[2]針對最小化最大完工時間為優(yōu)化目標(biāo)的作業(yè)車間調(diào)度問題,提出了一種基于動態(tài)交叉與變異概率的改進(jìn)遺傳算法，顯著提高了算法尋優(yōu)能力和收斂速度。

近年來，面向能耗優(yōu)化的多目標(biāo)柔性作業(yè)車間調(diào)度問題(MOFJSP)的研究尤為重要。LIU等[3]提出了一種非支配排序遺傳算法，解決了以最小化電能消耗為優(yōu)化目標(biāo)的生產(chǎn)調(diào)度問題；MANSOURI等[4]明確了將能耗作為車間調(diào)度的指標(biāo)之一，建立了多目標(biāo)混合整數(shù)線性優(yōu)化模型，提出了啟發(fā)式算法，在完工時間和能源消耗之間進(jìn)行了快速權(quán)衡分析；MOUZON等人[5]針對單臺CNC機(jī)床上調(diào)度作業(yè)的問題，以減少能耗和總完成時間為目標(biāo)，開發(fā)了多種算法和多目標(biāo)數(shù)學(xué)規(guī)劃模型，該研究表明，機(jī)床在需要加工工件時啟動，節(jié)省的能源占總能耗的比例高達(dá)80%。

本文針對制造作業(yè)車間，構(gòu)建以能源消耗和完工時間為優(yōu)化目標(biāo)的調(diào)度模型，提出改進(jìn)遺傳算法，采用多層編碼策略，在能耗和完工時間最優(yōu)情況下，有效解決柔性車間作業(yè)調(diào)度問題。

1 低能耗柔性作業(yè)車間調(diào)度問題

1.1 問題描述

MOFJSP問題可以描述為：設(shè)有M臺機(jī)床可加工J個工件。第j個工件的第n道工序表示為Ojn，每個工件的工序數(shù)為一道或多道，且已確定順序，每道工序可由一臺或多臺機(jī)床加工完成。機(jī)床m∈M加工工件j∈J產(chǎn)生相應(yīng)的加工時間和能耗。相鄰兩個加工任務(wù)之間，機(jī)床可以保持空轉(zhuǎn)或關(guān)閉狀態(tài)。頻繁開啟或關(guān)閉機(jī)器會消耗額外能量，且會縮短機(jī)床使用壽命，而機(jī)床處于空轉(zhuǎn)狀態(tài)時，只會消耗少量能量，故應(yīng)在一段時間內(nèi)保持機(jī)床處于空轉(zhuǎn)狀態(tài)。

本文研究的主要調(diào)度目標(biāo)為最小化能源消耗，需要滿足一定的約束條件，并確定工件的加工順序以及相應(yīng)的加工設(shè)備，最終使得調(diào)度性能指標(biāo)整體處于最優(yōu)。

約束條件如下：

(1)工件的各道工序只能在一臺機(jī)床上進(jìn)行加工；

(2)工件在加工過程中不能中斷；

(3)同一時刻，每臺機(jī)床僅可以加工一個工件，每個工件僅可以在一臺機(jī)床上加工；

(4)機(jī)床可以存在停止或空載運(yùn)行狀態(tài)；

(5)同一工件的工序之間的操作優(yōu)先級不會改變；

(6)不考慮工件加工前準(zhǔn)備時間，所有工件和機(jī)床在t=0時刻均已準(zhǔn)備就緒。

1.2 相關(guān)符號定義

車間的能耗模型可限制制造系統(tǒng)內(nèi)的總能耗，同時最大限度地縮短最大完工時間。

相關(guān)的符號定義如表1所示。

表1 符號定義

1.3 模型建立

(1)

(2)

式中：δ—負(fù)載功耗系數(shù)。

故有：

(3)

維持機(jī)床正常運(yùn)行的基本能耗Eb可表示為：

(4)

將式(3～4)代入式(1)可得：

(5)

當(dāng)機(jī)床處于空轉(zhuǎn)運(yùn)行模式時，裝載或卸載工件、定位、夾緊以及更換刀具，將消耗大量能量Eu(即空載能耗)。Eu可表示為：

(6)

在實際加工過程中，機(jī)床通常處于4種狀態(tài)：啟動、空載、加工和停止?fàn)顟B(tài)[7]。

文獻(xiàn)[8]給出了一般機(jī)床加工過程中的功率分布曲線，如圖1所示。

圖1 機(jī)床功率曲線

當(dāng)機(jī)床處于不同狀態(tài)時，其能源消耗值不同。根據(jù)式(5～6)，車間制造系統(tǒng)的總能耗為：

Etotal=Es+Eu+Ep

(7)

本課題研究的車間調(diào)度模型的優(yōu)化目標(biāo)為總能耗(f1)以及總完工時間(f2)。其具體數(shù)學(xué)模型如下：

(8)

受到的約束為：

Tmax≥Cjm,j∈J,m∈M

(9)

(10)

(11)

Cjm≤Sjk,m,k∈M,m≠k,j∈J

(12)

Cjm≤S(j+1)m,j∈J,m∈M

(13)

其中，約束(9)定義最大完工時間等于最后一個工件的完成時間；約束(10)表示每個工件的每道工序只能分配給一臺機(jī)床；約束(11)表示工件j在機(jī)床m上的完工時間Cjm，由工件j在機(jī)床m上的起始時間Sjm和加工時間Tjm組成；約束(12)給出了工件j的加工工序之間的優(yōu)先約束，即工件在當(dāng)前階段完成某道工序之后，才能在下一個生產(chǎn)階段處理下一道工序；約束(13)確保一臺機(jī)器只有在完成當(dāng)前工件后，才能處理下一個工件。

(14)

式中：α—能耗權(quán)值。

決策者根據(jù)對各目標(biāo)的偏好，對α進(jìn)行取值，通過將不同的標(biāo)準(zhǔn)值標(biāo)準(zhǔn)化為可比較的單位，以相同的比例評估所有目標(biāo)。因此，歸一化賦權(quán)值優(yōu)化目標(biāo)函數(shù)為：

(15)

(16)

2 多層編碼遺傳算法

遺傳算法(GA)是一種隨機(jī)搜索算法，使用現(xiàn)有信息指導(dǎo)搜索過程，通過估計染色體的適應(yīng)度執(zhí)行選擇、交叉、變異等其他遺傳操作[12-13]，收斂到最佳或令人滿意的解。

染色體表示問題中潛在的最優(yōu)解。在解決較復(fù)雜問題時，單一的染色體無法準(zhǔn)確表達(dá)問題的解。本文對MOFJSP環(huán)境下的遺傳算法進(jìn)行改進(jìn)，采用多層編碼策略，將個體的編碼分為多層，每層的編碼表示不同的含義，使多層編碼相互作用，求解整個問題的解，實現(xiàn)用單一的染色體表達(dá)復(fù)雜問題的解的目的。

2.1 編碼策略

本文提出的編碼方式為整數(shù)編碼，工件加工工序編碼如表2所示。

表2 工件加工工序編碼(片段)

該染色體的編碼主要分為兩層，第一層為工件工序的加工順序；第二層為每道工序?qū)?yīng)的加工機(jī)床。

第一層中，使用相同的數(shù)字來表示相同的工件，并且根據(jù)它們在編碼中出現(xiàn)的順序，來確定工件工序，如第1次出現(xiàn)“1”，表示第1個工件的第1道工序“1-1”，第2次出現(xiàn)“1”，表示第1個工件的第2道工序“1-2”，以此類推；

第二層表示各道工序所選擇的加工機(jī)床的編碼，如表2中的機(jī)床編碼1、3、3、2、3、1分別表示前面“1-1”工序在機(jī)床1上加工、“3-1”工序在機(jī)床3上加工。

2.2 適應(yīng)度函數(shù)

遺傳算法中，個體適應(yīng)程度越高，在下一代被選中的概率越高。通常，適應(yīng)度與目標(biāo)函數(shù)有關(guān)。在本文中，上述目標(biāo)函數(shù)—即方程(15)，為適應(yīng)度函數(shù)。

2.3 遺傳算法步驟

在GA操作階段，隨機(jī)產(chǎn)生初始種群，使用基本的遺傳操作產(chǎn)生新個體。這3個操作詳細(xì)描述如下：

(1)選擇操作?；趥€體的適應(yīng)性，操作者為交叉和變異操作選擇的個體適應(yīng)度通常不是最高的。本文采用輪盤賭法，選擇適應(yīng)性較好的個體，個體被選中的概率與其適應(yīng)度大小成正比[14]；

(2)交叉操作。交叉算子模擬生物染色體之間的交配重組過程，通過對兩條配對染色體中的部分基因，按照一定得交叉概率和交叉方法，生成新的個體；交叉算子是遺傳算法的重要特征[15]。通常交叉概率為0.6～0.9。

本文采用整數(shù)交叉法，其操作流程如下：①從種群中隨機(jī)選取父代中的兩個染色體，并取出每個染色體的第一層編碼；②隨機(jī)選擇交叉位置進(jìn)行交叉；③比較交叉前后的個體，將冗余的基因調(diào)整為缺失的基因，同時調(diào)整第二層編碼，生成新的種群。

(3)變異操作。由于交叉操作不能產(chǎn)生具有新信息的解，為了能夠獲得具有最大適應(yīng)度的解，種群需要以指定變異概率執(zhí)行變異操。一般變異概率為0.001～0.1。

3 實驗結(jié)果與分析

該多層編碼遺傳算法在MATLAB R2016a環(huán)境中實現(xiàn)，在處理器為Inteli7 8700 3.2 GHz，內(nèi)存為16 GB的計算機(jī)上運(yùn)行。

改進(jìn)遺傳算法參數(shù)如表3所示。

表3 改進(jìn)遺傳算法參數(shù)

實驗數(shù)據(jù)來源于文獻(xiàn)[16]中的實際生產(chǎn)數(shù)據(jù)，其中，工件數(shù)量J=6，機(jī)器數(shù)量M=6。

加工能耗、加工時間、工序可選擇的機(jī)床等實例數(shù)據(jù)如表4所示。

表4 實例數(shù)據(jù)

由于能耗和完工時間之間的關(guān)系，能耗權(quán)值α由決策者的偏好決定。當(dāng)決策者想要最小化最大完工時間時，將能耗權(quán)值設(shè)置為α=0。在該條件下，采用本文算法，經(jīng)過15次仿真，得出的有效解集如表5所示。

表5 α=0時15組有效解集

由表5可知：完工時間和能耗之間存在著矛盾關(guān)系。當(dāng)完工時間達(dá)到最小值51時，對應(yīng)的能耗最小值為458.56；當(dāng)總能耗達(dá)到最優(yōu)值435.19時，完工時間增加到53。故較短的最大完工時間將消耗更多的能量，較高的能耗將縮短最大完工時間。

當(dāng)決策者想要最小化能量消耗時，將能耗權(quán)值設(shè)置為α=1，同樣仿真15次后，可得到最小能耗為331.86，相比最短完工時間對應(yīng)的能耗458.56，減少了約127。

雙目標(biāo)賦權(quán)值優(yōu)化結(jié)果如表6所示。

表6 雙目標(biāo)賦權(quán)值優(yōu)化結(jié)果

方案1的多層編碼遺傳算法收斂曲線如圖2所示。

圖2 收斂曲線

由圖2可知：在迭代次數(shù)為7時，已快速收斂到最優(yōu)解，優(yōu)勢個體大量遺傳，種群均值變化平緩且不斷趨于最優(yōu)解，搜索有效穩(wěn)定。

方案1時間最優(yōu)甘特圖如圖3所示。

圖3 時間最優(yōu)甘特圖

由圖3可知：各道工序均勻分布在6臺機(jī)床上，其中，平均加工能耗較大的機(jī)床也參與了工件的加工，導(dǎo)致加工能耗較高，達(dá)430.80。

方案2能耗最優(yōu)甘特圖如圖4所示。

圖4 能耗最優(yōu)甘特圖

由圖4可知：由于M2和M3平均加工能耗較低，各道工序集中在這兩臺機(jī)床上加工，加工能耗為304.80，比方案1減少126。

以“1-3”工序為例，可加工機(jī)床有M2、M5和M6。由表4可知：M2的加工能耗最小，故當(dāng)該工件到達(dá)第3道工序時，工件流向機(jī)床M2進(jìn)行加工。

4 結(jié)束語

本文探討了低能耗柔性作業(yè)車間調(diào)度問題，為了解決多目標(biāo)優(yōu)化問題，對加工工序較多、加工設(shè)備較多的柔性工藝路線生產(chǎn)問題提出了多層編碼方式；使用目標(biāo)加權(quán)法生成了有效解；針對MOFJSP，建立了調(diào)度模型；最后通過實例仿真，驗證了多層編碼遺傳算法能夠在解空間中識別出一組帕累托最優(yōu)解。

由于柔性作業(yè)車間層能耗源眾多，在今后的研究中，可以對車間能耗進(jìn)行更深入全面的分析。本研究下一步將針對柔性作業(yè)車間特點，將AGV小車運(yùn)輸能耗、車間照明設(shè)備等公共能耗納入研究對象中，以進(jìn)一步完善調(diào)度模型。