李文韜，陶 澤，陳曉菲

(沈陽理工大學 機械工程學院,沈陽 110159)

流水車間(Flow-shop)調(diào)度問題是車間調(diào)度問題中的一個具有代表性的經(jīng)典問題，在實際問題中應(yīng)用廣泛[1]，具有很大的研究價值，一直是理論界和工程領(lǐng)域的熱點問題。Flow-shop調(diào)度問題是以實際流水線車間的生產(chǎn)調(diào)度為依托而簡化的一個模型，其工藝約束相對來說比較簡單。合理的車間調(diào)度可以減少生產(chǎn)周期，對現(xiàn)有的資源進行最優(yōu)分配，從而更好的完成生產(chǎn)任務(wù)，提高生產(chǎn)效率。針對一系列復(fù)雜的優(yōu)化問題，遺傳算法提供了通用的解決方法，基于其魯棒性強的特點，遺傳算法在醫(yī)學領(lǐng)域、各種工業(yè)領(lǐng)域、甚至在服務(wù)領(lǐng)域都得到了應(yīng)用，隨著近年來的快速發(fā)展，已經(jīng)成為求解全局優(yōu)化問題的有力工具。

隨著工業(yè)技術(shù)的迅猛發(fā)展，對車間調(diào)度問題也提出了更高的要求，對單一目標的追求已經(jīng)遠遠不能滿足實際的生產(chǎn)需要，需要對兩個甚至多個目標進行優(yōu)化。對于調(diào)度問題，Paolucci M等提出了基于仿真決策支持系統(tǒng)進行調(diào)度[2]；吳云高對關(guān)于兩臺機器的Flow-shop優(yōu)化問題開展研究，建立了混合整數(shù)規(guī)劃的模型，采用了分支定界算法對問題進行求解[3]。但是，由于這些方法具有周期長、解質(zhì)量差等缺點往往不太適用于工程問題。相比而言，遺傳算法具有并行性的特點，在搜索空間中可以同時對多個解進行評估，可以對影響目標進行綜合考慮，因此，現(xiàn)階段遺傳算法是解決這類優(yōu)化問題的重要方法和手段。本文運用遺傳算法和小生境技術(shù)，對雙目標Flow-shop調(diào)度問題進行探究，以生產(chǎn)周期和平均流時間[4]為目標模擬加工車間，通過系統(tǒng)仿真得出雙目標Flow-shop調(diào)度問題的結(jié)果。

1 Flow-shop調(diào)度問題的描述

Flow-shop調(diào)度問題是研究流水線上工件在不同功能的機器上的加工過程，其中每個等待加工的工件都具有同樣的順序并且在每臺機器上只能加工一次。因此，F(xiàn)low-shop也稱為同序作業(yè)調(diào)度問題。Flow-shop可以描述為：n個工件、m臺機器進行流水作業(yè)加工，其加工順序是恒定的，在一段時間內(nèi)每個工件只能被一臺機器加工，工件所需的各個時間均已知。Flow-shop最后需綜合所有調(diào)度指標使之達到最優(yōu)。

2 基于遺傳算法和小生境技術(shù)相結(jié)合的調(diào)度算法

遺傳算法是一種隨機、并行的優(yōu)化算法，是以種群開始[5]，種群則是由基因通過編碼而成的染色體組成。初始化種群后，逐代產(chǎn)出越來越好的染色體。每代都需要通過適應(yīng)度的大小進行選擇，之后進行遺傳算子的交叉與變異，產(chǎn)生新的集合即新的種群，重復(fù)以上過程直至達到某種指標可以收斂為止。但是由于遺傳算法一般是優(yōu)先選擇更高級別染色體進行復(fù)制，往往收斂于局部最優(yōu)解，降低了遺傳算法的全局搜索能力，無法保證解的多樣性，需要引進小生境技術(shù)，來保證解的多樣性，對解決多目標調(diào)度問題具有明顯的優(yōu)越性[6]。將小生境技術(shù)與遺傳算法相結(jié)合，對多目標優(yōu)化問題進行求解，可能獲得最優(yōu)解。對于同級別的染色體，通過小生境技術(shù)可以選出更好的個體進行復(fù)制。改進后的的遺傳算法流程圖如圖1所示。

圖1 算法流程圖

3 Flow-shop調(diào)度問題的數(shù)學模型

在建立具體的數(shù)學模型前需要對該問題做一些約束：

(1)每個零件在流水線上的加工順序固定；

(2)每臺機器在某一時刻都只能同時加工一個工件；

(3)每個工件在每臺機器上都只能加工一次；

(4)工序的準備時間包含在加工時間中；

(5)每臺機器的加工時間給定；

(6)每個工件不能在多臺機器上同時加工。

對于一般流水車間調(diào)度問題，令c(ji,k)表示機器k加工完成零件ji的時間，tij為工件i在機器j上給定的加工時間，{j1,j2,…,jn}為工件的流水排序，則m臺機器加工n個工件所用的時間是

c(j1,1)=tj11

(1)

c(j1,k)=c(j1,k-1)+tj1k

(2)

c(ji,1)=c(ji-1,1)+tji1

(3)

c(ji,k)=max{c(ji-1,k),c(ji,k-1)}+tjik其中(i=2,3,…,n;k=2,3,…,m)

(4)

本文為雙目標Flow-shop調(diào)度問題，采用生產(chǎn)周期和平均流時間為目標約束，故目標函數(shù)為

F1=T=max(c1,c2,…,ck)

(5)

(6)

式中Fi為第i個工件的加工操作結(jié)束時間。

4 Flow-shop調(diào)度的算法實現(xiàn)

4.1 編碼與解碼

遺傳算法不能直接作用于調(diào)度問題的參數(shù)，而是需要通過編碼成特定結(jié)構(gòu)的染色體來解決具體問題。本文根據(jù)流水車間的現(xiàn)實情況將工件的順序編碼成染色體，并采用十進制進行編碼。例如：在流水車間里6個工件在6臺機器上加工，其加工順序為j1,j2,j5,j3,j6,j4，則可以編碼為{1,2,5,3,6,4}。

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

適應(yīng)度函數(shù)可以對染色體進行評價，染色體的適應(yīng)度值越高遺傳的概率越大，適應(yīng)度值越低遺傳概率就越小。而且，作為遺傳算法在搜索過程中的唯一評價依據(jù)[7]，設(shè)計適應(yīng)度函數(shù)的合理性顯得尤為重要。如果設(shè)計不當可能會出現(xiàn)一些超常個體來控制遺傳過程，導致早熟收斂，影響全局算法及優(yōu)化性能。所以，確定合適的適應(yīng)度函數(shù)是優(yōu)化過程中的重中之重。

4.3 選擇操作

選擇操作既從當前群體中以一定的方式選出優(yōu)異的個體為下一代進行繁殖。對于優(yōu)先級別不同的染色體，可以根據(jù)適應(yīng)度值的大小進行排列，之后按照每個適應(yīng)度值大小所占的比例進行分配。假設(shè)種群的大小為A，個體i的適應(yīng)值為fi，則i被選擇的概率pi為

(7)

對于級別相同的染色體，運用小生境技術(shù)進行選取。通過對小生境數(shù)的計算來選取更優(yōu)秀的個體進行復(fù)制，即選取小生境數(shù)相對較小的個體遺傳至下一代。其計算過程如下：

(8)

(9)

(3)個體間的距離

(10)

(11)

4.4 交叉操作

交叉操作是最重要的一項操作，在選擇操作之后，是將父代的兩個染色體的一段基因進行交叉，組成兩個新的染色體，其中都包含父代的優(yōu)異基因。例如：父代1：3 2 2 2 3 1 1 1 3；父代2：1 1 3 2 2 1 2 3 3；從父代1上選取一個或一段基因后，從父代2上消除對應(yīng)的基因，并將該選取基因加到子代上，重復(fù)該步驟至子代染色體包含所有基因。則子代1：3 2 1 1 2 1 2 3 3；子代2：1 1 3 2 2 2 1 3 3。

4.5 變異操作

變異操作是指將原來染色體的一個基因轉(zhuǎn)變成其它基因，進而生成新的染色體，可以提高局部搜索能力，保持種群的多樣性，防止早熟現(xiàn)象的出現(xiàn)。變異操作按位進行，本文采用的變異方法是將染色體中原位上的基因用另一種基因進行同位置替換。

5 算例仿真

本次模擬針對雙目標Flow-shop調(diào)度問題，以生產(chǎn)周期最小和平均流時間最短為目標，采用Delphi7.0軟件進行編程并運行上述算法，是面向?qū)ο蟮木幊碳夹g(shù)。在工件加工時間以及加工順序確定、同時各個工件的各項加工參數(shù)不變的情況下，使待加工工件依次進入加工系統(tǒng)完成加工。在本次仿真實例中，以6×6的Flow-shop調(diào)度問題為例，相關(guān)參數(shù)為：工件種類jC={j1,j2,j3,j4,j5,j6}，機器種類MC={M1,M2,M3,M4,M5,M6}，其加工時間見表1所示。

表1 工件在機器上的加工時間

仿真過程中,取仿真次數(shù)為1、2、3、4、5、6、7、8次,交叉概率為0.8,變異概率為0.01[8]。

Delphi7.0軟件的仿真次數(shù)與對應(yīng)結(jié)果見表2所示。

表2 仿真次數(shù)與結(jié)果

經(jīng)過算法計算后，結(jié)合生產(chǎn)周期與平均流時間，得到遺傳產(chǎn)生后代的雙目標仿真結(jié)果。如圖2所示。

圖2 遺傳產(chǎn)生的后代

在雙目標的空間中，如果一個個體的橫縱坐標都比其它個體的橫縱坐標小，則定其級別為0；如果某個個體只有一個橫坐標或縱坐標小于之前的橫坐標或縱坐標，則定其級別為1，依次類推，直至所有個體的級別設(shè)置完畢。每一代中0級別為最高級別。從圖2中可以清楚的看到，P2的級別顯然高于其他個體，可以定其為0級，其平均流時間和生產(chǎn)周期時間都相對最少。因此，最終通過仿真得到的甘特圖如圖3所示。

圖3 雙目標調(diào)度甘特圖

通過甘特圖可以看出，其最優(yōu)的生產(chǎn)周期為46時間單位，同時可以清楚的反映出流水車間調(diào)度工件加工的順序是相同的。圖3與圖2相結(jié)合可得出其最優(yōu)平均流時間為37.3時間單位。

6 結(jié)論

分析了流水車間調(diào)度問題的特性，針對遺傳算法在解決雙目標Flow-shop調(diào)度問題的不足，提出了將小生境算法與遺傳算法相結(jié)合的方法。此方法可以保持解的多樣性并具有很高的收斂速度，既保證了生產(chǎn)周期最小，又保證了平均流時間最少。通過合理的參數(shù)設(shè)計建立仿真模型，最終得到的仿真結(jié)果證實該方法的可行性和有效性。

參考文獻：

[1] 王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學出版社,2002.

[2] Paolucci M,Sacile R,Boccalatte A.Allocating Crude Oil Supply to Port and Refinery Tanks:a Simulation-based Decision Support System[J].Decision Support System,2002,22(1):39-54.

[3] 吳云高.基于遺傳算法的車間調(diào)度方法及其應(yīng)用[D].杭州：浙江工業(yè)大學,2002.

[4] 陳振同.基于改進遺傳算法的車間調(diào)度問題研究與應(yīng)用[D].大連：大連理工大學,2007.

[5] 馬永杰.云文霞.遺傳算法研究進展[J].計算機應(yīng)用研究.2012,29(4)：150-152.

[6] 王小平.曹立明.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)[M].西安：西安交通大學出版社,2002.

[7] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].第一版.北京：國防工業(yè)出版社,1998:11-24.

[8] 仁慶道爾吉.車間作業(yè)調(diào)度及其遺傳算法[D].呼和浩特：內(nèi)蒙古大學,2006.