王成福，曹 剛，宋李俊*

(1重慶理工大學(xué) 管理學(xué)院，重慶 400054；2 重慶理工大學(xué) 機械工程學(xué)院，重慶 400054)

0 引言

制造業(yè)極大促進(jìn)了全球經(jīng)濟增長，同時也消耗了大量能源。據(jù)相關(guān)統(tǒng)計數(shù)據(jù)，制造業(yè)約占全球一次能源使用量的33%，占全球CO2排放量的38%[1]。因此如何在經(jīng)濟穩(wěn)定可持續(xù)發(fā)展的同時降低能源消耗，是我國制造業(yè)亟須解決的問題。

工藝規(guī)劃與車間調(diào)度是制造系統(tǒng)的兩個關(guān)鍵內(nèi)容，國內(nèi)外學(xué)者在這兩方面進(jìn)行了深入研究。然而傳統(tǒng)的生產(chǎn)制造系統(tǒng)中，工藝規(guī)劃與車間調(diào)度兩個模塊通常是獨立、串行進(jìn)行的，其面向節(jié)能的獨立優(yōu)化均得不到全局最優(yōu)的結(jié)果[2]。

考慮到工藝規(guī)劃和車間調(diào)度兩者分開優(yōu)化車間能耗的局限性，從工藝規(guī)劃與車間調(diào)度集成（Integration of process planning and scheduling，IPPS）的角度優(yōu)化車間節(jié)能開始逐漸得到關(guān)注[2-6]，研究表明[4]兩者綜合考慮可以更好提高車間生產(chǎn)效率和降低能源消耗。目前對IPPS問題的研究大多假設(shè)機器的轉(zhuǎn)速是固定的，而實際生產(chǎn)中，加工使用的機床有不同的加工檔位可以選擇，不同檔位對應(yīng)不同的加工功率和時間，在不影響生產(chǎn)進(jìn)度的前提下，通過調(diào)整機床轉(zhuǎn)速可以達(dá)到節(jié)能的目的[7]。因此，研究考慮機床多轉(zhuǎn)速的綠色I(xiàn)PPS問題，具有重要的理論和實際意義。

綜上所述，本文以作業(yè)車間為對象，研究考慮機器多轉(zhuǎn)速的IPPS節(jié)能問題。首先，以達(dá)到車間總能耗和完工時間最小的目標(biāo)，構(gòu)建了一個集成機床、工藝路線、機器加工速度選擇和工件加工順序的優(yōu)化模型；在此基礎(chǔ)上，提出了一種改進(jìn)的灰狼優(yōu)化算法對該模型進(jìn)行求解，最后用一個實例對模型和算法進(jìn)行了驗證。

1 面向節(jié)能的IPPS優(yōu)化模型

1.1 問題描述

面向節(jié)能的IPPS問題描述如下：給定n個工件{1,2,...,n}在m臺機器{1,2,...,m}上進(jìn)行加工；每個工件i共有Si道工序{1,2,...,Si}，工件i可由工序集Ji中的若干工序加工完成，形成多條工藝路線；工件i的第j道工序Qi,j可選擇在mi,j個加工機器{1,2,...,mi,j}上加工；每臺機器有l(wèi)個檔位，機器每個檔位對應(yīng)的轉(zhuǎn)速、加工功率、空載功率及加工時間不同，每道工序可以在可選機器的所有檔位上加工；機器轉(zhuǎn)速越高，加工時間越短，加工功率越大，加工能耗（時間與功率的乘積）越高[8]。調(diào)度優(yōu)化的目標(biāo)是在滿足約束的條件下，給每個工件選擇最適合的加工工序，進(jìn)而選擇合適的工藝路線，以及每道工序的加工機器和檔位和在加工機器上的加工次序，同時使車間總能耗和完工時間最小。

本文采用AND/OR網(wǎng)絡(luò)圖表示工件的柔性工藝路線，如圖1所示，工件1的工序2和工序3可以二者選其一進(jìn)行加工，故工件1有2條可選工藝路線，分別為1-2-4和1-3-4兩種組合。而工件2的工序2、3都需要加工，但沒有先后順序，故工件2只有一條工藝路線。本研究對工藝規(guī)劃的優(yōu)化中不考慮對加工特征方法、加工資源和切削參數(shù)的優(yōu)化，僅對工藝路線進(jìn)行選擇優(yōu)化。

圖1 工件1與工件2的工藝路線網(wǎng)絡(luò)圖

1.2 參數(shù)定義

表1 參數(shù)定義表

1.3 假設(shè)條件

1）所有機器、工件在時刻均準(zhǔn)備就緒，處于待機狀態(tài)。

2）任一工序某一時刻只能在一臺機器上加工且不能中斷。

3）任一機器某一時刻只能加工一道工序且不能中斷。

4）每道工序在可選機器上的各個檔位都可加工。

5）不同工件的工序之間相互獨立，沒有先后約束。

6）不考慮同一工件不同工序以及同一機器上不同工件間的轉(zhuǎn)換、運輸時間。

2 車間能耗計算模型

車間總能耗主要分為機器能耗和公共能耗，機器能耗根據(jù)機器加工過程所處的狀態(tài)（如圖2所示），又可細(xì)分為開/關(guān)機能耗、加工能耗、空載能耗和待機能耗[4]。本文不考慮開/關(guān)機能耗，雖然當(dāng)機器待機時間過長時，可以通過關(guān)閉機床進(jìn)行節(jié)能，但在實際加工過程中，機器使用前需要熱機以保證工件加工質(zhì)量，且頻繁開關(guān)機，增加人工操作，因此本文假設(shè)機器無加工任務(wù)時保持待機狀態(tài)[9]。下面對各部分能耗進(jìn)行分析計算：

圖2 機器功率變化圖

1）加工能耗

加工能耗是指機器加工工件的能量損耗[10]，總加工能耗Ew可用式(1)表示為：

2）空載能耗

空載能耗是指機器由于上一個加工任務(wù)和下一個加工任務(wù)間出現(xiàn)閑置的能量損耗。而機器的空載功率會因為選擇加工檔位l的不同而變化，因此要由上一加工任務(wù)的加工檔位來確定空載功率大小[7]。因此，分別計算每一加工檔位下的空載能耗，累加得到機器k的空載能耗Eidle,k，用式(2)表示為：

進(jìn)一步，可以求得總空載能耗Eidle用式(3)表示為：

3）待機能耗

待機能耗主要指機器在通電但非工作的狀態(tài)下，用于維持待機狀態(tài)的能量損耗[7]。一般而言，待機狀態(tài)下機器的待機功率為定值，則總待機能耗Efk用式(4)表示為：

4）公共能耗

公共能耗是指維持作業(yè)車間運轉(zhuǎn)但不直接參與作業(yè)車間加工所的能量損耗，如作業(yè)車間中照明、通風(fēng)、空調(diào)等公共設(shè)備的能耗。實際生產(chǎn)中，這部分能耗較為穩(wěn)定，公共能耗EP可用式(5)表示為：

3 集成優(yōu)化模型

調(diào)度優(yōu)化的目標(biāo)函數(shù)是完工時間Cmax和車間總能耗Etatal：

在上述調(diào)度模型中，式(6)是總的優(yōu)化目標(biāo)，包括完工時間Cmax和作業(yè)車間能耗Etatal，完工時間通過式(7)計算，決策變量是Xij、Yi,j,k,l和；能耗Etatal通過式(8)計算，決策變量是Ew、Eidle、Efk和EP。式(9)、式(10)表示同一機器上，同一時刻只能加工一道工序；式(13)、式(14)表示同一工件的不同工序不能同時加工；式(12)、式(16)確保工序次序約束正確；式(17)確保每個工件只能選擇一條加工路線；式(18)表示一道工序只能選擇一臺機器加工；式(11)、式(15)表示變量的取值范圍。

4 調(diào)度優(yōu)化模型求解方法

4.1 基本灰狼優(yōu)化算法

灰狼優(yōu)化算法（Grey Wolf Optimization Algorithm,GWO）是由Mirjalili等[11]于2014年提出的一種群智能優(yōu)化算法。算法迭代過程中，種群個體按照適應(yīng)度值大小由高到低被劃分為頭狼α、下屬狼β、普通狼σ和底層狼ω。α、β和σ是決策層個體，負(fù)責(zé)確定獵物位置，并引導(dǎo)ω更新位置，通過靠近、包圍、攻擊等行為完成捕食。該算法特點是求解快、收斂精度高，且其原理簡單、參數(shù)少、易實現(xiàn)，已被成功用于解決多種優(yōu)化問題[12-15]。但灰狼優(yōu)化算法多用于求解連續(xù)優(yōu)化問題，對作業(yè)車間調(diào)度這類復(fù)雜的離散組合優(yōu)化問題研究較少，因此本文將其應(yīng)用于柔性作業(yè)車間調(diào)度問題，并對算法做了改進(jìn)，以提高其求解復(fù)雜調(diào)度優(yōu)化問題的性能。受篇幅限制，基本GWO算法的步驟可參考文獻(xiàn)[11]。

4.2 改進(jìn)灰狼優(yōu)化算法

針對機器多轉(zhuǎn)速的IPPS問題的特點和約束，本文算法提出一種四層編碼機制，設(shè)計一種由α、β和σ其中一個層級的灰狼來引導(dǎo)種群更新的種群個體更新方法，同時，引入遺傳算法的交叉操作，避免算法出現(xiàn)早熟收斂。此外，針對本文多目標(biāo)優(yōu)化的特點，也在基本GWO上進(jìn)行了一些改進(jìn)，算法流程如圖3所示。

圖3 改進(jìn)灰狼算法流程圖

4.2.1 編碼機制

本文提出一種基于工件加工順序、機器分配、速度選擇和工藝路線選擇的四層編碼方法，即每個解均包含四層編碼如圖4所示。該編碼方式中，前三層的編碼長度為加工任務(wù)的工序總數(shù)，第四層的編碼長度為可選擇的工藝總數(shù)。第一層和第二層采用實數(shù)編碼，各元素在[0,1]內(nèi)任意取值；第三層為整數(shù)編碼，各元素在[1,a]內(nèi)任意取值，a為每道工序的可選檔位機器數(shù)；第四層也為整數(shù)編碼，各元素在[1,b]內(nèi)任意取值，b為每個可選工藝的可選工序數(shù)。假設(shè)車間內(nèi)包含3個工件，其編碼方法見圖4，3個工件的工序數(shù)分別為6、5、4，其中工件1的工序3和4，工件2的工序4和5，工件3的工序2和3為可替換工藝，每臺機器有3個檔位可選擇，則前三層的編碼長度為15，第四層的編碼長度為3，第三層編碼表示工件i的第j道工序選擇l檔加工，第四層編碼[1,2,1]，其中1表示第1個可選擇工藝選擇可選工序的第一個，2表示第1個可選擇工藝選擇可選工序的第2個，以此類推。

圖4 四層編碼方式圖

由圖4可以看出，解碼時，第三層和第四層編碼可以直接確定各工序的速度選擇和工藝選擇，第一層和第二層編碼的各元素為連續(xù)值，而作業(yè)車間調(diào)度解為離散值，因此需要將其轉(zhuǎn)換為離散形式的調(diào)度解。

1）加工順序?qū)拥慕獯a具體步驟

步驟1：根據(jù)第四層的工藝選擇得到各個工件當(dāng)前待加工的工序集合，集合包含的工序個數(shù)記為l1；

步驟2：按照順序依次選擇待加工工序集合編碼的元素值x(h1)，按照式(19)進(jìn)行轉(zhuǎn)換，并選擇當(dāng)前待加工工序集合中的第u(h1)個工序進(jìn)行加工；

其中：x(h1)表示加工順序第h個編碼位置的元素值；u(h1)∈[1,l1]表示所選工序在當(dāng)前待加工工序集中的序號，即下一個需要加工的工序為當(dāng)前待加工工序中的第u(h1)個；

步驟3：剔除已安排加工的工序并更新待加工工序集合，然后重復(fù)上述步驟，直至所有工序安排完畢。

2）機器分配層的解碼具體步驟

步驟1：同樣根據(jù)第四層的工藝選擇得到加工工序集合，集合內(nèi)每個工序包含的可選機器個數(shù)記為l2；

步驟2：將每個工序?qū)?yīng)的機器分配層的元素值x(h2)，按照式(20)進(jìn)行轉(zhuǎn)換，由此獲得每個工序選擇可選機器集中加工該工序的機器編號；

其中：x(h1)表示加工順序第h個編碼位置的元素值；u(h1)∈[1,l1]表示所選工序在當(dāng)前待加工工序集中的序號，即下一個需要加工的工序為當(dāng)前待加工工序中的第u(h1)個。

4.2.2 種群初始化及Pareto前沿解

本文采用隨機初始化的方法獲得初始種群，按照4.2.1的編碼機制，每只狼即一個序列。

對于多目標(biāo)優(yōu)化問題，種群個體的優(yōu)劣不能由適應(yīng)度大小直接判斷，需通過Pareto排序?qū)⒎N群中的個體分成若干個非支配等級，首先找出當(dāng)前種群中的非支配最優(yōu)解，并賦值等級為1級，然后將這些解從種群中剔除，在剩下個體中尋找新的非支配解，并為其中個體的等級賦值為2級，依次類推，直至所有個體被分級，從而得到Pareto前沿解。

4.2.3 建立社會等級

在基本灰狼優(yōu)化算法中，新個體由當(dāng)前個體根據(jù)決策層個體α，β和σ（初始種群中前三位）的信息而產(chǎn)生。僅通過非支配等級可能會出現(xiàn)兩個個體無法比較的情況，導(dǎo)致無法確定決策層個體。因此，本文采用基于非支配等級和擁擠距離的方法。對種群中個體排序遵循的原則：對于任意兩個個體，等級低的個體排在前面；若兩個個體等級相同，則比較二者的擁擠距離，擁擠距離大的個體排在前面[12]。排序完成后，選擇排名前三的個體，將其分別作為決策層個體α，β和σ。

4.2.4 外部檔案更新

外部檔案用于存放搜索過程中的Pareto前沿解，并基于Pareto支配關(guān)系對其進(jìn)行更新，更新方法如下：當(dāng)有一個新解，若外部檔案中任一解能支配它，則拒絕其加入；若其支配外部檔案中的部分解，將允許其加入外部檔案，并除去受支配解；若其與外部檔案中的所有解均為非支配關(guān)系，則新解直接加入外部檔案[12]。此外，若新產(chǎn)生的解與外部檔案中已有的解重復(fù)，則剔除。

4.2.5 種群個體更新方法

1）搜索算子

在基本灰狼優(yōu)化算法中，種群位置更新由決策層個體（α，β和σ）共同決定，但在解決復(fù)雜問題優(yōu)化時，理想解會更接近α，β或σ其中一個，導(dǎo)致由決策層個體（α，β和σ）共同決定的種群更新方法效果不是那么理想。因此，本文對搜索過程進(jìn)行改進(jìn)，生成子種群1，新種群由兩部分組成，新種群8%的灰狼則按照隨機生成的方法產(chǎn)生，剩余92%的灰狼按照以下步驟生成：

步驟1：按照[0.3,0.2,0.1]的比例選擇α，β和σ其中一只灰狼；

步驟2：對選中的灰狼，則選擇更新其中60%、40%、20%或10%的基因位，選擇的比例為[0.5 0.2 0.2 0.1]，更新方式為基本灰狼算法的更新方式，如式(21)、式(22)：

步驟3：按步驟1、2進(jìn)行更新，直到生成規(guī)定數(shù)量的新個體。

2）交叉算子

灰狼優(yōu)化算法進(jìn)化時，個體根據(jù)適應(yīng)度最優(yōu)的3個個體進(jìn)行個體位置更新，這使得算法容易陷入局部最優(yōu)。由于遺傳算法的全局搜索能力較強，在灰狼優(yōu)化算法中引入交叉算子，進(jìn)一步提升該算法的計算性能。交叉過程中，首先從[1,4]產(chǎn)生隨機整數(shù)x，再從[1,2,3,4]四層中隨機選出x層，對選出的編碼層進(jìn)行交叉操作。本文采用單點交叉、雙點交叉或多點交叉三種交叉方式，三種交叉方式的選擇比例為[0.3,0.9,0.5]，需要交叉的編碼層按照給定的比重選擇一種方式進(jìn)行交叉操作，生成子種群2。

5 應(yīng)用案例

本文選擇某柔性作業(yè)車間，對其一批包含5個工件的加工任務(wù)進(jìn)行試驗，以驗證本文建立的調(diào)度優(yōu)化模型的節(jié)能潛力及算法改進(jìn)的可行性。該任務(wù)5個工件的柔性工藝路線網(wǎng)用AND/OR圖表示，如圖5所示，車間工件能耗與車間信息表如表2所示，其中公共功率P0=40W。改進(jìn)的灰狼優(yōu)化算法參數(shù)設(shè)置如下：種群數(shù)量100，迭代次數(shù)500,交叉概率0.8。案例1為考慮工藝路線柔性、機器柔性、加工順序柔性和加工速度柔性的節(jié)能調(diào)度（優(yōu)化目標(biāo)為C、E）,案例2為案例1中不考慮機器加工速度柔性即都是以固定檔位加工的調(diào)度（優(yōu)化目標(biāo)為C、E）。

表2 工件能耗與時間信息表

圖5 零件柔性工藝路線圖

5.1 案例1的分析

案例1考慮了工藝路線柔性、機器柔性、加工順序柔性和加工速度柔性的節(jié)能調(diào)度（優(yōu)化目標(biāo)為C、E），根據(jù)文章第2節(jié)的調(diào)度優(yōu)化模型和4.2節(jié)算法步驟求解該模型得到Pareto非支配解集如表3所示。為了分析不同工藝路線和生產(chǎn)調(diào)度方案下兩個目標(biāo)函數(shù)值的關(guān)系，圖6是對案例1求出的Pareto解集中目標(biāo)函數(shù)的走勢圖，可以看到，形成的Pareto邊界分布比較均勻，說明改進(jìn)的灰狼優(yōu)化算法很好地平衡了完工時間和能源消耗兩個目標(biāo)。由于多目標(biāo)優(yōu)化問題無法使每個目標(biāo)同時達(dá)到最優(yōu)，故選擇Pareto解集中完工時間最小和能源消耗最低的兩個解，得到對應(yīng)優(yōu)化方案的甘特圖如圖7和圖8所示。因此，本文提出的模型和求解方法能夠求解考慮工藝路線柔性、機器柔性、加工順序柔性和加工速度柔性的節(jié)能調(diào)度優(yōu)化問題，并能夠獲得多目標(biāo)的Pareto非支配解集。

圖6 Pareto解集中目標(biāo)函數(shù)走勢圖

圖7 完工時間最小對應(yīng)方案的甘特圖

圖8 能源消耗最小對應(yīng)方案的甘特圖

5.2 案例1與案例2的對比分析

案例1與案例2差別在于是否考慮了機器加工速度的柔性。案例2分別以檔位1、檔位2和檔位3其中一種檔位進(jìn)行加工，并用改進(jìn)的灰狼優(yōu)化算法求解得到Pareto解集，并得到案例1與案例2的Pareto解集分布圖如圖9所示。通過對比發(fā)現(xiàn)，考慮工藝路線柔性、機器柔性、加工順序柔性和加工速度柔性的綜合優(yōu)化，無論是加工過程中的完工時間還是能源消耗，得到的結(jié)果都要優(yōu)于不考慮加工速度柔性的調(diào)度結(jié)果。因此，本文提出的考慮工藝路線、加工機器、加工順序和加工速度同時優(yōu)化的節(jié)能調(diào)度模型能更好地實現(xiàn)高效節(jié)能的目標(biāo)。

圖9 固定轉(zhuǎn)速與多轉(zhuǎn)速的Pareto解結(jié)果對比

5.3 本文算法改進(jìn)分析

為證明本文所提的算法改進(jìn)有效，將用原始灰狼算法與本文提出的改進(jìn)灰狼優(yōu)化算法求解案例1得到的Pareto解集進(jìn)行對比分析，如圖10所示，改進(jìn)灰狼優(yōu)化算法求得的Pareto解支配了基本灰狼算法所求出的，說明改進(jìn)后效果要優(yōu)于改進(jìn)前。表4為灰狼優(yōu)化算法對案例1求解結(jié)果在數(shù)量和質(zhì)量的比較。其中：每個指標(biāo)左邊為基本灰狼算法的結(jié)果，右邊為改進(jìn)灰狼算法的結(jié)果。

表4 基本灰狼算法改進(jìn)前后在案例1中的結(jié)果對比

圖10 改進(jìn)灰狼優(yōu)化算法與原灰狼算法結(jié)果對比

6 結(jié)語

本文研究在面向節(jié)能的工藝規(guī)劃與車間調(diào)度集成問題的基礎(chǔ)上，考慮了制造過程中的機器加工速度柔性，建立了以車間總能耗、加工完工時間為優(yōu)化目標(biāo)的柔性作業(yè)車間節(jié)能調(diào)度模型。同時，提出了一種改進(jìn)的灰狼優(yōu)化算法對該模型進(jìn)行求解，并結(jié)合實際案例，經(jīng)過詳細(xì)分析，驗證了考慮機器加工速度柔性要比不考慮機器加工柔性的工藝規(guī)劃與車間調(diào)度問題節(jié)能效果更好，同時還證明了改進(jìn)后算法的可行性。

本文提出的節(jié)能調(diào)度模型，一定程度上降低了作業(yè)車間能耗，為企業(yè)實際應(yīng)用提供了方向和方法。然而本文研究的調(diào)度案例規(guī)模較小，缺乏所提節(jié)能調(diào)度模型對大規(guī)模調(diào)度問題的適用性研究和不同求解算法的對比研究，這將作為下一步的研究內(nèi)容。此外，在節(jié)能調(diào)度問題中考慮開/關(guān)機策略也是非常值得研究的。