齊曉寧，汪永超，賈 婧，張魁偉

(四川大學(xué)制造科學(xué)與工程學(xué)院，成都 610065）

0 引言

綠色制造是現(xiàn)代制造業(yè)的熱點之一，它綜合考慮了資源效率和環(huán)境影響因素，旨在減少制造過程的資源消耗和環(huán)境污染，實現(xiàn)企業(yè)經(jīng)濟(jì)效益和社會效益的協(xié)調(diào)優(yōu)化。機(jī)械加工系統(tǒng)是典型的制造系統(tǒng)，它在將加工資源轉(zhuǎn)變?yōu)楫a(chǎn)品或半成品的同時，也產(chǎn)生了大量的資源消耗和環(huán)境影響問題，國內(nèi)外針對機(jī)械加工系統(tǒng)的綠色制造展開了大量的研究工作，但大多數(shù)集中在工藝以及產(chǎn)品的設(shè)計方面。然而在實際生產(chǎn)中，加工任務(wù)調(diào)度方案的不同，不僅影響制造系統(tǒng)的生產(chǎn)進(jìn)度、效率、質(zhì)量、成本等同時也會對加工過程中的資源消耗和環(huán)境排放等產(chǎn)生影響［1-2］。車間的合理調(diào)度能在保證產(chǎn)品加工質(zhì)量、時間的同時，最大限度的減少機(jī)械加工系統(tǒng)生產(chǎn)過程中的資源消耗和環(huán)境污染，因此其研究具有重要的理論意義和工程價值。由于車間調(diào)度本身就是一個非常難解的組合問題且面向綠色制造的車間調(diào)度考慮因素眾多［3-4］，傳統(tǒng)的優(yōu)化算法不能保證最優(yōu)結(jié)果，因此采用遺傳算法求解該優(yōu)化問題。

遺傳算法(Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的隨機(jī)搜索算法，它最初由美國Michigan大學(xué)J.Holland教授于1975年首先提出來的，能同時使用多個搜索點的搜索信息，在各調(diào)度方案間進(jìn)行交叉和變異操作，搜索范圍廣、不易陷入局部最優(yōu)解同時具有原理和操作簡單、通用性強、并行性等優(yōu)點被廣泛應(yīng)用于優(yōu)化計算方面［5］。本文通過選擇合理的編碼方法、算子、適應(yīng)度值的計算和相關(guān)參數(shù)的設(shè)置，用遺傳算法來解決面向綠色制造的車間的優(yōu)化調(diào)度問題，并應(yīng)用于實例。

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

1.1 問題描述

面向綠色制造的車間調(diào)度主要是研究n個工件在m臺機(jī)床上的加工，各工件在各個機(jī)床上的加工時間和消耗的電能已知，要求確定各工件在機(jī)床上的安排順序，使得工件的綠色度最高。假設(shè)加工過程滿足以下約束條件:

(1）機(jī)械加工系統(tǒng)中的m臺機(jī)床的加工性能基本相同;

(2）有n個需加工工件，每個工件在每臺機(jī)床上僅需加工一次;

(3）每臺機(jī)床同一時刻最多只能有一個工件在加工;

(4）每個工件同一時刻最多只能在一臺機(jī)床上進(jìn)行加工;

(5）每一個操作一旦開始就不能中斷，必須等到該工件加工完畢才能在該機(jī)床上加工其它工件;

(6）不同零件之間沒有優(yōu)先權(quán)上的限制，且所有工件的加工準(zhǔn)備時間為0。

1.2 面向綠色制造的車間優(yōu)化調(diào)度數(shù)學(xué)模型

綠色制造是要綜合考慮制造過程中的時間、質(zhì)量、成本、資源消耗和環(huán)境污染五個方面的影響，因此面向綠色制造的機(jī)床調(diào)度優(yōu)化理想中應(yīng)該以時間最小、質(zhì)量最好、成本最低、資源消耗最少、環(huán)境影響最小為目標(biāo)。但在實際生產(chǎn)中由于調(diào)度問題本來就是一個NP難題，由于零件的質(zhì)量通常只需要能達(dá)到零件的圖紙規(guī)定的質(zhì)量要求即可，不必追求質(zhì)量最好而環(huán)境影響很難用具體的數(shù)值表示，在實際中，可依據(jù)工人的加工經(jīng)驗判斷某個工件在某臺機(jī)床上加工是否滿足工藝質(zhì)量要求，是否會違反環(huán)境法規(guī)和工廠自行的一些環(huán)境條例，若質(zhì)量不合格或違反環(huán)境法規(guī)則應(yīng)避免安排該工件在該機(jī)床上加工，因此在該模型中，將質(zhì)量和環(huán)境影響作為約束條件，以時間和資源消耗為目標(biāo)。

1.2.1 調(diào)度方案變量體系

由上述問題的描述可知，該調(diào)度問題即為確定n個工件在m臺機(jī)床上的加工安排，某一時刻工件在機(jī)床上的狀態(tài)分為兩種，工件i在機(jī)床j上加工和不在其上加工。因此采用0－1整數(shù)變量矩陣對調(diào)度方案變量 X={xij|i=1，2，…，n;j=1，2，…，m}進(jìn)行描述，即當(dāng)工件i安排在機(jī)床j上加工時，xij=1，否則xij=0。其中i=1，2，…，n，j=1，2，…，m用n × m矩陣 X={xij}，(i=1，2，…，n;j=1，2，…，m）表示調(diào)度方案變量。

1.2.2 調(diào)度目標(biāo)函數(shù)

(1）時間T

實際生產(chǎn)中，時間標(biāo)準(zhǔn)為最大完工時間Makespan(從工件開始加工到最后一個工件加工結(jié)束所經(jīng)歷的時間）。其計算公式為:

式中:tij——工件i在機(jī)床j上加工時所需要的加工時間和輔助時間。

(2）資源消耗R

機(jī)械加工過程中的資源消耗主要有物料消耗和電能消耗，物料消耗主要是指原材料、切削液等主要是由工藝參數(shù)選擇、切削液選擇及設(shè)計參數(shù)等決定的。合理的調(diào)度最直觀的是能合理的使用電能，加工過程中的電能消耗如下:

式中:eij——工件i在機(jī)床j上加工時產(chǎn)生的能量消耗。

(3）質(zhì)量環(huán)境影響

由于質(zhì)量、環(huán)境影響的模糊復(fù)雜性，在該模型中我們將二者作為一個約束考慮。引入一個0－1變量qeij對質(zhì)量、環(huán)境影響進(jìn)行約束。當(dāng)工件i安排在機(jī)床j上加工滿足質(zhì)量要求且不會有嚴(yán)重環(huán)境污染時，qeij=1，否則qeij=0。則將其納入到時間和資源消耗函數(shù)總來，得到:

即目標(biāo)函數(shù)為:

1.2.3 約束條件

(1）由上可知變量X={xij}為一個0－1矩陣，應(yīng)該滿足 xij=0，1(i=1，2，…，n;j=1，2，…，m）;

(3）qeij=0，1(i=1，2，…，n;j=1，2，…，m）。

2 遺傳算法求解模型

2.1 調(diào)度問題編碼

這里采用二進(jìn)制編碼，因其編碼和解碼操作簡單，且交叉和變異操作等便于實現(xiàn)。一種調(diào)度方案對應(yīng)一個染色體，染色體由n個基因段連接而成。假如工件工件i安排在機(jī)床j上加工，則將十進(jìn)制數(shù)j對應(yīng)的二進(jìn)制數(shù)作為工件i對應(yīng)的基因段。每個基因段有固定的長度l，取j的最大值對應(yīng)的二進(jìn)制數(shù)的長度作為l，若基因段長度不夠則在其前面補充相應(yīng)位數(shù)的0。

2.2 適應(yīng)度

對于多目標(biāo)調(diào)度問題，利用線性加權(quán)和公式把多個目標(biāo)函數(shù)值映射為染色體的適應(yīng)度，由于事先很難知道權(quán)重系數(shù)的具體值而且T(X）、R(X）均為求極小值，因此綜合適應(yīng)度為:

但是在這之前要先對調(diào)度方案的各個指標(biāo)值進(jìn)行無量綱標(biāo)準(zhǔn)化處理，處理公式如下:

式中:Tmax(X），Tmin(X）——調(diào)度產(chǎn)生的完工時間最大值和完工時間最小值;

Rmax(X）、Rmin(X）——調(diào)度產(chǎn)生的電能消耗最大值和電能消耗最小值。

由公式(7）、(8）可看出，在進(jìn)行多目標(biāo)調(diào)度求解之前，要先用遺傳算法算出 Tmax(X）、Tmin(X）和Rmax(X）、Rmin(X），由于完工時間和電能消耗均要求越小越好，因此采用變權(quán)重的方法確定權(quán)重系數(shù)。

式中:N——每代的種群個數(shù);

i——整數(shù)集合［1，N］的一個隨機(jī)數(shù)。

這樣在每一代計算中就增加了選權(quán)重的過程，由于w1、w2是隨機(jī)選取的，這樣遺傳算法的搜索方向也是隨機(jī)的。這樣就能產(chǎn)生足夠大的群體得到更多的非劣解，避免陷入局部最優(yōu)解。

2.3 選擇操作

選擇是用來確定重組或交叉?zhèn)€體，其基于排序選擇。選擇的第一步是計算適應(yīng)度值并將其按由大到小排序，按一定的淘汰比例將適應(yīng)度值小的個體淘汰掉，并采用“精英策略”補充同樣數(shù)目的上代較優(yōu)秀個體［6］。個體適應(yīng)度值的大小決定了其子孫遺留的可能性，若有M個個體，某個個體i的適應(yīng)度值為fi，則它被選擇的概率為:

2.4 交叉操作

交叉操作可以將父代的良好基因通過信息互換而產(chǎn)生更好的子代，此處采用單點交叉法。它是隨機(jī)地從遺傳種群中選取兩個個體C1和C2作為父代，并隨機(jī)在C1上選取一個基因位x1，在C2上選取同樣的基因位，將C1、C2上該基因位后的基因段互換，產(chǎn)生兩個新的子代個體。

2.5 變異操作

變異是產(chǎn)生新個體的一種方法，通過變異操作可以改善遺傳算法的局部搜索能力和維持種群的多樣性，避免陷入“早熟”，較低的變異概率可以防止群體中重要的單一基因丟失，但降低了遺傳算法開辟新搜索空間的能力;較高的變異概率將使遺傳操作趨于純粹的隨機(jī)搜索，降低了算法的收斂速度和穩(wěn)定性，因此要選擇合適的變異概率［7-8］。這里采用交換變異即在父染色體中隨機(jī)選取兩個變異位置然后將其上基因互換。

2.6 算法流程圖

遺傳算法的步驟如下:

(1）隨即產(chǎn)生初始種群，并按照一定的編碼方法對種群進(jìn)行編碼，得到初始化種群;

(2）由變權(quán)重方法得到權(quán)重系數(shù)，計算個體的適應(yīng)度;

(3）判斷是否滿足終止條件，若滿足則輸出最佳個體及代表的最優(yōu)解同時計算結(jié)束，如不滿足轉(zhuǎn)下一步;

(4）根據(jù)適應(yīng)度選擇的大小選擇再生個體;

(5）按照一定的交叉、變異概率和方法生成新的個體和種群，并返回第(2）步。

圖1 算法流程圖

3 實例分析

在此以一個齒輪加工車間的生產(chǎn)加工為例進(jìn)行分析，該車間要對一批齒輪零件進(jìn)行滾齒加工，包括6中不同的齒輪，有5臺滾齒機(jī)可用于調(diào)度，取編號Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ其中6種不同齒輪在各臺機(jī)器上的加工時間和電能消耗分別如表1和表2所示。

表1 加工時間矩陣表(min）

表2 能耗矩陣表(kwh）

6種加工任務(wù)受質(zhì)量環(huán)境約束如表3所示，其中×表示由于質(zhì)量不合格或有嚴(yán)重環(huán)境）污染不能安排該工件在該機(jī)床上加工(如不可安排加工任務(wù)4在機(jī)床Ⅱ上加工）。

表3 加工任務(wù)質(zhì)量環(huán)境約束

采用上述遺傳算法對該實例進(jìn)行仿真計算，這里種群規(guī)模取20，最大迭代次數(shù)選取40，交叉概率取0.9，變異概率為0.5，則優(yōu)化結(jié)果如下，對應(yīng)的綜合調(diào)度模型解為:

此時對應(yīng)的能耗值為23.12kWh，最小加工時間為26.77min。

4 結(jié)束語

(1）將綠色制造的思想納入到傳統(tǒng)的車間調(diào)度中，綜合考慮時間、質(zhì)量、成本、資源消耗和環(huán)境影響因素建立了面向綠色制造的車間調(diào)度數(shù)學(xué)模型。該模型中采用0-1變量思想將質(zhì)量和環(huán)境影響作為約束，以時間和電能消耗為優(yōu)化目標(biāo)。

(2）針對面向綠色制造的車間調(diào)度問題，采用遺傳算法進(jìn)行求解，在算法中采用二進(jìn)制編碼，簡化了解碼和交叉、變異操作;采用變權(quán)重的方法獲得合適的權(quán)重系數(shù)，從而得到更多的非劣解。最后經(jīng)過實例分析證明了該算法的可行性。

［1］何彥，劉飛，曹華軍，等.面向綠色制造的機(jī)械加工系統(tǒng)任務(wù)優(yōu)化調(diào)度模型［J］.機(jī)械工程學(xué)報，2007，43(4）:27-33.

［2］莊新村，盧宇灝，李從心.基于遺傳算法的車間調(diào)度問題［J］. 計算機(jī)工程，2006，32(1）:193-194.

［3］夏筱筠，李鑫，常曉芳.企業(yè)車間生產(chǎn)調(diào)度MES系統(tǒng)的設(shè)計與研究［J］.組合機(jī)床與自動化加工技術(shù)，2010(8）:109-112.

［4］張家興，夏筱筠，蔣煥軍.自適應(yīng)蟻群算法在Job Shop調(diào)度問題中的研究［J］.組合機(jī)床與自動化加工技術(shù)，2010(9）:99-103.

［5］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，1999.

［6］孫志峻，朱劍英，潘全科.基于遺傳算法的多資源作業(yè)車間智能動態(tài)優(yōu)化調(diào)度［J］.機(jī)械工程學(xué)報，2002，38(4）:120-125.

［7］劉晶晶，翟正軍.基于改進(jìn)的遺傳算法的任務(wù)分配與調(diào)度［J］. 微電子學(xué)與計算機(jī)，2006，23(6）:216-219.

［8］何霆.生產(chǎn)車間調(diào)度問題研究［J］.機(jī)械工程學(xué)報，2000，36(5）:97-102.