臧維娜， 高國生

（石家莊鐵道大學(xué) 機(jī)械工程學(xué)院，河北 石家莊 050043）

0 引言

綠色制造是一個綜合考慮環(huán)境影響和資源消耗的現(xiàn)代制造模式，旨在減少制造業(yè)對環(huán)境的負(fù)面影響，提高其資源利用率［1］。近些年來，隨著科技發(fā)展，制造業(yè)生產(chǎn)過程也發(fā)生了明顯變化，最主要的特征即為生產(chǎn)規(guī)模大型化與生產(chǎn)過程連續(xù)化。在實(shí)施綠色制造的過程中，車間是最基本的生產(chǎn)單元，車間調(diào)度可以利用現(xiàn)有的資源（加工能力），滿足被加工任務(wù)所需的各種約束（加工次序、所需機(jī)器等），使所有的任務(wù)能盡量按時完成（性能指標(biāo)最?。?］。柔性作業(yè)車間調(diào)度問題（Flexible Job－shop Scheduling Problem，F(xiàn)JSP）是生產(chǎn)系統(tǒng)中的核心問題之一，是對經(jīng)典作業(yè)調(diào)度的一種擴(kuò)展，在實(shí)際生產(chǎn)中，它允許每個工序在多個備選機(jī)器上加工，提高了加工靈活性，也增加了問題的復(fù)雜度，是更為復(fù)雜的NP－Hard問題。從實(shí)際生產(chǎn)角度來說，好的調(diào)度方案更符合生產(chǎn)需求，更適合生產(chǎn)的動態(tài)特性，從綠色制造角度來說，好的調(diào)度方案能減少資源消耗和環(huán)境污染，因此面向綠色制造的柔性車間調(diào)度研究具有重要的理論和實(shí)際應(yīng)用價值。

目前，求解FJSP的常用算法有粒子群算法、蟻群算法、禁忌搜索和遺傳算法等［3－7］。遺傳算法具有魯棒性好、計(jì)算性能穩(wěn)定、通用性強(qiáng)等特點(diǎn)，在求解組合優(yōu)化領(lǐng)域的非確定多項(xiàng)式問題上顯示出較好的搜索能力，在車間調(diào)度問題中得到了很好的應(yīng)用［8］。然而普通遺傳算法存在消耗時間長、局部搜索能力較差且易早熟收斂等不足，為了克服上述缺陷，國內(nèi)外學(xué)者們分別從算法編碼、種群初始化、遺傳操作、算法邏輯設(shè)計(jì)以及與其他算法融合等方面對算法進(jìn)行改進(jìn)。本文主要從種群初始化和遺傳操作上對算法進(jìn)行改進(jìn)，并對優(yōu)化目標(biāo)進(jìn)行了改善，彌補(bǔ)了遺傳算法的不足，更適應(yīng)面向綠色制造的柔性車間調(diào)度優(yōu)化。

1 面向綠色制造的柔性作業(yè)車間調(diào)度模型

1.1 問題描述

面向綠色制造的柔性作業(yè)車間調(diào)度研究n個工件｛J1，J2，…，Jn｝在m 臺機(jī)床｛W1，W2，…，Wm｝上加工，每個工件有一道或者多道工序，工件的工序順序確定，每道工序的加工機(jī)床有多臺可供選擇，工序的加工時間、能源消耗以及對環(huán)境的污染程度都會因加工機(jī)床的不同而不同，調(diào)度的最終目標(biāo)是給每道工序選擇最優(yōu)加工機(jī)床，確定每臺機(jī)床的工序加工順序和時間，使所期望的加工性能指標(biāo)最優(yōu)。此外，在加工過程中還需滿足以下約束條件：

（1）同一臺機(jī)床，同一個時間，只能加工一個工件；

（2）同一個工件，同一個時刻，只能在一臺機(jī)床上加工；

（3）每一個工序一旦開始加工便不能中斷；

（4）工件間無優(yōu)先級限制，所有工件的加工準(zhǔn)備時間為零；

（5）不同工件的工序間無先后約束，同一工件的工序間有先后約束。

1.2 調(diào)度目標(biāo)

綠色制造需要綜合考慮制造過程中的時間、質(zhì)量、成本、資源消耗以及環(huán)境污染5個方面的影響，因此面向綠色制造的作業(yè)車間調(diào)度理應(yīng)以這5項(xiàng)最優(yōu)為目標(biāo)。但在實(shí)際生產(chǎn)中，由于調(diào)度問題的復(fù)雜性，再加上5大目標(biāo)間的相互聯(lián)系，很難達(dá)到全面的最優(yōu)，在此假設(shè)可選加工機(jī)床均能保證工件的加工質(zhì)量，且忽略加工過程中所產(chǎn)生的生產(chǎn)成本差異，以時間、資源消耗和環(huán)境污染為調(diào)度目標(biāo)。

1.2.1 時間t

多數(shù)文獻(xiàn)都將最大完工時間最小作為作業(yè)車間調(diào)度的優(yōu)化目標(biāo)，但是在實(shí)際生產(chǎn)中，加工時間并非越短越好，最理想的狀態(tài)應(yīng)該是工件在其交貨期內(nèi)完成，提前完成會給企業(yè)增加倉儲費(fèi)用，延后完成會降低客戶滿意度，并且受到合同懲罰，因此調(diào)度的目標(biāo)應(yīng)是盡量使工件在交貨期所在的時間段內(nèi)完工。

1.2.2 資源消耗和環(huán)境影響

制造過程是將原材料加工成產(chǎn)品的過程，在這個過程中，必會造成資源價值和屬性的改變，也就是說加工過程中必然會產(chǎn)生資源消耗和環(huán)境影響。文獻(xiàn)［9］已用實(shí)例證明，同一工件會因加工機(jī)床不同而消耗不同資源。受調(diào)度方案所影響的資源消耗主要表現(xiàn)在電能消耗上，其他的物料消耗，包括原材料、切削液等主要在前期加工設(shè)計(jì)階段決定，因此將電能消耗量定義為資源屬性值；生產(chǎn)過程中會產(chǎn)生廢氣、廢液、噪聲等對環(huán)境造成影響，加工安全性也會對勞動者的身心健康造成危害，因此將這幾方面的綜合影響量定義為環(huán)境屬性值。綜上可知，面向綠色制造的作業(yè)車間調(diào)度問題應(yīng)將這兩方面的影響考慮其中，優(yōu)化目標(biāo)是將這兩方面的影響盡量降到最低，兩方面的數(shù)值進(jìn)行量綱統(tǒng)一后，將其和稱為可持續(xù)性指標(biāo)值，則優(yōu)化目標(biāo)就變?yōu)榭沙掷m(xù)性指標(biāo)值最高。

根據(jù)上述內(nèi)容，為該調(diào)度模型定義變量如下：i代表工件序號，i＝1，2，…，n；k代表機(jī)床序號，k＝1，2，…，m；j代表工件的工序號；第i個工件的第j道工序可選機(jī)床集合為Mij，集合中元素的個數(shù)為mij；hi表示工件i的工序總數(shù)；tijk表示工件i的第j道工序在機(jī)床k上的加工時間，Ti表示加工完工件i的時間，ri，ei分別表示加工工件i的資源屬性值和環(huán)境屬性值（均為量綱統(tǒng)一后的數(shù)值），wr，we為其權(quán)重，REi表示可持續(xù)性指標(biāo)值（如式（1）所示）；stij，enij分別表示工序i的第j道工序的起始和結(jié)束時間；［Si，Li］表示工件i的交貨期，si，li分別為提前完工和延后完工的單位時間懲罰系數(shù)。

非交貨期間完工都會對企業(yè)產(chǎn)生一定損失，因此需要進(jìn)行懲罰，時間懲罰值用Pi表示（如式（2）所示），因此，將作業(yè)車間調(diào)度在時間方面的調(diào)度目標(biāo)定為時間懲罰值最小，在資源消耗和環(huán)境影響方面的調(diào)度目標(biāo)定為可持續(xù)性指標(biāo)值最高，則總目標(biāo)F如式（3）所示，其中P′i為量綱統(tǒng)一后的值，Wp、Wre為兩分目標(biāo)權(quán)重。

2 改進(jìn)遺傳算法求解面向綠色制造的柔性作業(yè)車間調(diào)度

2.1 基因編碼

面向綠色制造的柔性作業(yè)車間調(diào)度問題，遺傳算法的編碼應(yīng)由兩部分組成，一部分是基于機(jī)床分配的編碼，一部分是基于工序的編碼。對于基于機(jī)床分配的編碼，染色體的基因數(shù)等于所有工件工序的總數(shù)，基因用機(jī)床編號表示，如染色體［3 5 1 4 3 2 6 1 2］，第一數(shù)字3表示為第一道工序選擇W3機(jī)床進(jìn)行加工。對于基于工序的編碼，染色體的基因數(shù)等于所有工件工序的總數(shù)，工序用工件序號表示，序號出現(xiàn)的次數(shù)即為該工件的工序號，如染色體［1 2 1 3 2 3 3 2 1］，數(shù)字1表示工件J1，3個數(shù)字1表示工件J1的3個工序。

2.2 種群初始化

在用遺傳算法求解調(diào)度問題時，好的初始解可以加快算法的求解速度和質(zhì)量，目前多數(shù)文獻(xiàn)采用隨機(jī)的初始化方法，初始解質(zhì)量低，導(dǎo)致迭代次數(shù)增加，運(yùn)算效率降低。Kacem等［10］提出了一種基于短用時策略與設(shè)備均衡策略的種群初始化方法，使種群質(zhì)量大幅度提高。但是該方法強(qiáng)烈依賴于工件的排序順序，并且這種單一的初始化方法也使得初始結(jié)果有一定的局限性，并不能保證算法的運(yùn)算質(zhì)量。Zhang等［11－12］提出了一種綜合機(jī)器全局搜索（Global search，GS）、局部搜索（Local search，LS）和隨機(jī)選擇這3種方式的初始化方法，3種方式產(chǎn)生的初始解按一定比例共同組成初始種群，進(jìn)一步提高了初始種群質(zhì)量。本文將以此方法為基礎(chǔ)，對此進(jìn)行改進(jìn)，以更適應(yīng)于面向綠色制造的柔性車間調(diào)度問題。

原始方法均以機(jī)床負(fù)荷和加工時間為性能指標(biāo)進(jìn)行初始化，由于所期望的完工時間是在交貨期內(nèi)，完工時間過短和過長都會對企業(yè)造成損失，再考慮到一個工件的完工時間受到自身和其他工件的調(diào)度安排影響，直接將其限定在一個區(qū)間范圍內(nèi)是極其復(fù)雜的，所以將初始解的性能指標(biāo)定為可持續(xù)性指標(biāo)值和機(jī)床負(fù)荷這兩方面上，兩個指標(biāo)隨機(jī)參與初始化過程。

以某工程機(jī)械零部件制造企業(yè)3個工件、5臺機(jī)床的作業(yè)調(diào)度進(jìn)行研究，加工數(shù)據(jù)如表1所示。

表1 加工數(shù)據(jù)

用nijk，cijk，sijk分別表示噪聲、拆卸回收性、安全性（均為量綱統(tǒng)一后的數(shù)值），wn，wc，ws分別表示其權(quán)重，則環(huán)境屬性值如式（4）所示。

各權(quán)重值應(yīng)根據(jù)企業(yè)實(shí)際加工標(biāo)準(zhǔn)來制定，在此將wn，wc，ws初步設(shè)為20%，50%，30%，式（1）中wr，we分別設(shè)為60%，40%。經(jīng)過計(jì)算，可以得到表1中各加工方法的可持續(xù)性指標(biāo)值，結(jié)果如表2所示。

表2 可持續(xù)性指標(biāo)值

GS以深度優(yōu)先進(jìn)行搜索，兩性能指標(biāo)隨機(jī)選擇，可以選擇可持續(xù)性指標(biāo)值最大的工序所對應(yīng)的機(jī)床，或者選擇機(jī)床負(fù)荷最小的工序所對應(yīng)的機(jī)床，選擇完畢后更新未分配機(jī)床的其他工序所對應(yīng)的該機(jī)床的加工負(fù)荷，如此循環(huán)，當(dāng)所有工件工序的加工機(jī)床選擇完畢后，將各機(jī)床加工負(fù)荷歸零，進(jìn)行下一組循環(huán)。由于綠色性優(yōu)的機(jī)床可持續(xù)性指標(biāo)值普遍偏高，每次以可持續(xù)性作為性能指標(biāo)進(jìn)行機(jī)床選擇時，偏向于選擇此種機(jī)床，易造成這些機(jī)床的加工負(fù)荷大幅度偏高，因此應(yīng)避開選擇加工負(fù)荷最高的工序所對應(yīng)的機(jī)床。

具體操作過程如表3、表4所示，該示例以兩個指標(biāo)輪換著進(jìn)行機(jī)床選擇，先以可持續(xù)性為指標(biāo)為工序選擇機(jī)床，然后更新機(jī)床負(fù)荷（括號內(nèi)數(shù)字），再以加工負(fù)荷為指標(biāo)選擇機(jī)床，并更新機(jī)床負(fù)荷，如此循環(huán)直到選擇完畢。如表3所示，為第二個工件的第二道工序選擇完機(jī)床后，更新機(jī)床負(fù)荷，下一步該以可持續(xù)性為指標(biāo)進(jìn)行機(jī)床選擇，從表中可以看出，第3個工件的第三道工序選擇三號機(jī)床時指標(biāo)值最高，但選擇后會造成機(jī)床負(fù)荷最高，因此應(yīng)從其他可持續(xù)性指標(biāo)值中進(jìn)行選擇，最終結(jié)果如表4所示。

表3 GS－1

表4 GS－2

LS以廣度優(yōu)先進(jìn)行搜索，兩性能指標(biāo)隨機(jī)選擇，從第一個工件開始，一個工序選擇機(jī)床完畢后只更新本工件的其他工序所對應(yīng)的該機(jī)床的加工負(fù)荷，此工件所有工序選擇機(jī)床完畢后，機(jī)床加工負(fù)荷歸零，開始對下一個工件工序進(jìn)行機(jī)床選擇，如此循環(huán)，當(dāng)所有工件工序的加工機(jī)床選擇完畢后，將機(jī)床負(fù)荷歸零，進(jìn)行下一組循環(huán)，具體操作過程如表5所示。

表5 LS

初始化種群時仍需保留一定比例的隨機(jī)搜索個體，目的是為了擴(kuò)展搜索寬度，保持遺傳基因的多樣性。本文初始種群的60%采用全局搜索，30%采用局部搜索，10%采用隨機(jī)產(chǎn)生的方法，多次試驗(yàn)測試比較結(jié)果表明，該比例組合所生成的初始解質(zhì)量較優(yōu)［13］。

該方法是按指標(biāo)值的優(yōu)劣作為選擇順序先后的標(biāo)準(zhǔn)，不依賴于工件的排序順序，3種方法產(chǎn)生的種群共同組成初始種群，可有效保證種群質(zhì)量，提高算法效率。

2.3 適應(yīng)度函數(shù)與選擇操作

在遺傳算法中，適應(yīng)度的高低是評價種群中染色體優(yōu)劣的標(biāo)準(zhǔn)，適應(yīng)度越高，則說明個體越優(yōu)異，本文以式（3）作為適應(yīng)度函數(shù)值來進(jìn)行優(yōu)化選擇。選擇操作是從種群中選擇出優(yōu)良個體，淘汰劣質(zhì)個體，在此采用精英策略和GOLDBERG等［14］提出的錦標(biāo)賽法進(jìn)行選擇，精英策略就是將種群中適應(yīng)度高的個體直接復(fù)制到下一代中。錦標(biāo)賽法的目標(biāo)值就是適應(yīng)值，相對于多數(shù)文獻(xiàn)所應(yīng)用的輪賭法來講，免去了中間的轉(zhuǎn)換，其具體操作步驟是從種群中隨機(jī)選出3個個體，適應(yīng)度值最高的復(fù)制到交叉池中，如此循環(huán)，直到滿足所需數(shù)量。

2.4 交叉和變異

交叉操作是將兩父代染色體中的基因進(jìn)行交叉，以產(chǎn)生新的染色體，期望將優(yōu)良的基因進(jìn)行組合。將兩種染色體分別進(jìn)行交叉操作，基于機(jī)床分配的染色體采用兩點(diǎn)交叉法，基于工序編碼的染色體采用張超勇［15］提出的POX交叉算子。

基于機(jī)床分配的染色體的交叉操作流程為：選擇兩個父代染色體，再隨機(jī)選擇兩個交叉點(diǎn)，將兩父代染色體兩交叉點(diǎn)內(nèi)的基因進(jìn)行互換，形成新的子代染色體。

基于工序編碼的染色體的交叉操作流程為：將工件隨機(jī)分為兩個集合A1、A2，將父代染色體1／父代染色體2包含在A1中的工件復(fù)制給子代染色體1／子代染色體2，保留工件所在位置，將父代染色體2／父代染色體1包含在A2中的工件復(fù)制給子代染色體1／子代染色體2，保留工件順序。具體實(shí)現(xiàn)過程如圖1所示，其中A1＝｛J1，J3｝，A2＝｛J2，J4｝。

圖1 POX法交叉示例

變異操作是為了保持種群多樣性，避免早熟現(xiàn)象的產(chǎn)生，同時也可改善算法局部搜索能力。對機(jī)床染色體進(jìn)行變異時，在染色體中隨意選擇一個基因，為該工序在其可選加工機(jī)床集中隨意另選擇一臺機(jī)床，用其編號替代當(dāng)前基因；對工序染色體進(jìn)行變異時，在染色體中隨意選擇兩個基因，交換其位置。以上這兩種方式的變異操作均能保證新生解的可行性。

3 實(shí)例驗(yàn)證與結(jié)果分析

為了驗(yàn)證該算法的可行性與有效性，采用表1中的數(shù)據(jù)對3個工件5臺機(jī)床的加工問題進(jìn)行調(diào)度。利用MATLAB編寫程序代碼，令種群規(guī)模為40，迭代次數(shù)為30，交叉概率為0.7，變異概率為0.15。將提前完工和延后完工的單位時間懲罰系數(shù)均設(shè)為0.5，3個工件的交貨期分別為：［19，20］、［15，16］、［19，20］，Wp、Wre分別設(shè)為0.7和0.3。為了更好的對算法進(jìn)行驗(yàn)證，將該方法中初始種群的生成方法改為全部隨機(jī)生成來進(jìn)行比對，然后再去掉精英策略選擇法進(jìn)行對比，3種方法的運(yùn)算結(jié)果如圖2和表6所示，進(jìn)行比對的數(shù)值均為每次迭代后種群中的適應(yīng)度最高值。

表6 3種算法的運(yùn)算結(jié)果

從運(yùn)算結(jié)果可以看出，3種方法所得出的最優(yōu)值相同，最優(yōu)調(diào)度方案如圖3所示，圖中交叉線覆蓋的區(qū)域?yàn)闄C(jī)器空余時間，3個工件的完工時間分別為：19.5、16、19.5。改進(jìn)的遺傳算法產(chǎn)生的初始種群中的最優(yōu)值和最終結(jié)果的最優(yōu)值已非常接近，該方法迭代7次后便出現(xiàn)最優(yōu)解。初始種群若采用隨機(jī)方法生成，種群質(zhì)量差，迭代次數(shù)增加，精英策略可有效保留種群中的優(yōu)良個體，加快收斂效率。

圖2 各算法收斂比較圖

圖3 最優(yōu)調(diào)度方案

4 結(jié)語

針對面向綠色制造的柔性作業(yè)車間調(diào)度問題，提出了一種改進(jìn)的遺傳算法來解決此問題。設(shè)定了新的調(diào)度目標(biāo)，綜合考慮了完工時間、環(huán)境影響、能量消耗對調(diào)度問題的影響，更加符合現(xiàn)代企業(yè)的生產(chǎn)需求。采用兩種編碼方式來描述調(diào)度方案，對初始種群做了調(diào)整，使種群個體更為優(yōu)質(zhì)，加快了算法的收斂效率。精英策略和錦標(biāo)賽法的聯(lián)合選擇機(jī)制，保障了下一代個體的質(zhì)量。兩種編碼采用不同方法進(jìn)行交叉和變異，保證了新生解的可行性，最后通過實(shí)例驗(yàn)證了該算法的可行性和有效性。但是，本文所需解決的調(diào)度問題相對簡單，迭代較小次數(shù)便能得出最優(yōu)解，后期還需對復(fù)雜問題進(jìn)行試驗(yàn)，測試該算法的計(jì)算效率、準(zhǔn)確性等問題。

［1］劉飛，曹華軍，張華.綠色制造的理論與技術(shù)［M］.北京：科學(xué)出版社，2005.

［2］陳偉.基于遺傳算法的綠色制造車間調(diào)度方法研究［D］.武漢：武漢科技大學(xué)，2005.

［3］李丹，高立群，馬佳，等.基于動態(tài)雙種群粒子群算法的柔性工作車間調(diào)度［J］.東北大學(xué)學(xué)報：自然科學(xué)版，2007，28（9）：1238－1242.

［4］GAO J，SUN L Y，GEN M.A hybrid genetic and variable neighborhood descent for flexible job shop scheduling prob－lems［J］.Computers ＆ Operations Research，2008，35：2892－2907.

［5］SAISI－MEHRABAD M，F(xiàn)ATTAHI P.Flexible job shop scheduling by tabu search algorithms［J］.The International Journal of Advance Manufacturing Technology，2007，32：563－570.

［6］張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（2）：

333－337.

［7］王云，馮毅雄，譚建榮，等.柔性作業(yè)車間分批調(diào)度多目標(biāo)優(yōu)化方法［J］.浙江大學(xué)學(xué)報：工學(xué)版，2011，45（4）：719－726.

［8］趙詩奎，方水良，顧新建.柔性車間調(diào)度的新型初始機(jī)制遺傳算法［J］.浙江大學(xué)學(xué)報：工學(xué)版，2013，47（6）：1022－1030.

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

［10］KACEM I，HAMMADI S，BORNE P.Approach by localization and multi－objective evolutionary optimization for flexible job－shop scheduling problems［J］.IEEE Transactions on Systems，Man and Cybernetics，Part C：Applications and Reviews，2002，32（1）：1－13.

［11］ZHANG G H，GAO L，SHI Y.An effective genetic algorithm for the flexible job－shop scheduling problem ［J］.Expert Systems with Applications，2011，38（4）：3563－3573.

［12］張國輝，高亮，李培根，等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題［J］.機(jī)械工程學(xué)報，2009，45（7）：145－151.

［13］蔣良宵.基于改進(jìn)遺傳算法的柔性作業(yè)車間調(diào)度問題［J］.現(xiàn)代計(jì)算機(jī)，2014，2：29－33.

［14］GOLDBERG D E，DEB K.A comparative analysis of selection schemes used in genetic algorithms［C］／／RAWLINS G，ed.Foundations of Genetic Algorithms.San Mateo：Morgan Kaufmann Publishers，1991：69－93.

［15］張超勇，饒運(yùn)清，劉向軍，等.基于POX交叉的遺傳算法求解Job－Shop調(diào)度問題［J］.中國機(jī)械工程，2004，15（23）：2149－2153.