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

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

0 引言

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

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

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

1.1 問(wèn)題描述

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

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

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

(3）每臺(tái)機(jī)床同一時(shí)刻最多只能有一個(gè)工件在加工;

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

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

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

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

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

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

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

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

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

(2）資源消耗R

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

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

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

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

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

1.2.3 約束條件

(1）由上可知變量X={xij}為一個(gè)0－1矩陣，應(yīng)該滿(mǎn)足 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)度問(wèn)題編碼

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

2.2 適應(yīng)度

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

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

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

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

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

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

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

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

2.3 選擇操作

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

2.4 交叉操作

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

2.5 變異操作

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

2.6 算法流程圖

遺傳算法的步驟如下:

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

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

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

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

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

圖1 算法流程圖

3 實(shí)例分析

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

表1 加工時(shí)間矩陣表(min）

表2 能耗矩陣表(kwh）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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