李文韜，陶 澤，陳曉菲

(沈陽理工大學(xué) 機(jī)械工程學(xué)院，沈陽 110159)

科技高度發(fā)展的今天，單一的目標(biāo)已經(jīng)不能滿足企業(yè)生產(chǎn)的需要。在實(shí)際生產(chǎn)問題中有很多是屬于雙目標(biāo)的優(yōu)化問題，其理論與方法也一直是研究討論重點(diǎn)，因此研究雙目標(biāo)問題有重要意義[1]?；旌狭魉囬g調(diào)度問題(HFSP)作為一般流水車間調(diào)度問題的推廣，是一種更加復(fù)雜的問題，其主要特征為加工過程中某些工序存在并行機(jī)器調(diào)度，因此需要解決工件在各并行機(jī)器的分配。

對(duì)調(diào)度問題，相關(guān)學(xué)者已提出運(yùn)籌學(xué)方法、啟發(fā)式方法、神經(jīng)網(wǎng)絡(luò)方法等對(duì)問題進(jìn)行求解。但這些方法具有周期長、解質(zhì)量差等缺點(diǎn)，不太適用于工程問題。相比而言，小生境遺傳算法可兼顧遺傳算法良好的全局搜索能力及小生境技術(shù)維持種群多樣性的優(yōu)點(diǎn)[2]。相關(guān)學(xué)者已經(jīng)成功的利用遺傳算法解決調(diào)度問題。Davis[3]把遺傳算法的思想運(yùn)用到車間調(diào)度問題中，成功的取得了車間調(diào)度問題的最優(yōu)近似解；張思源等[4]設(shè)計(jì)混合遺傳算法，解決置換車間和非置換車間兩種情況下的流水車間調(diào)度問題。本文以生產(chǎn)周期和生產(chǎn)費(fèi)用為目標(biāo)，運(yùn)用小生境遺傳算法，利用軟件進(jìn)行仿真優(yōu)化，得出調(diào)度甘特圖，并給出最優(yōu)方案。

1 雙目標(biāo)混合流水車間調(diào)度問題的描述

對(duì)于流水車間，企業(yè)往往需要在雙目標(biāo)約束下進(jìn)行加工生產(chǎn)，若調(diào)度能同時(shí)滿足目標(biāo)條件，則生產(chǎn)就能達(dá)到較高水平。本文研究以生產(chǎn)周期-生產(chǎn)費(fèi)用為雙目標(biāo)的流水車間調(diào)度問題，所建立的數(shù)學(xué)模型如下。

最小化生產(chǎn)周期

(1)

最小化生產(chǎn)費(fèi)用

(2)

式中：f1為生產(chǎn)周期；f2為生產(chǎn)費(fèi)用；Lik為工件i在機(jī)器k上的加工時(shí)間；Ci為工件i的生產(chǎn)成本；n為工件總數(shù)；i為加工零件；k為加工機(jī)器。

HFSP是由一般流水車間調(diào)度問題推廣出來的，在現(xiàn)實(shí)生產(chǎn)過程中普遍存在。HFSP描述如下：n個(gè)工件在m臺(tái)機(jī)器上進(jìn)行流水作業(yè)加工(m>n)，每個(gè)階段至少存在一臺(tái)機(jī)器，且至少有一個(gè)階段存在并行機(jī)器，要求相同工序的并行機(jī)器加工性能相同；已知各工件的加工時(shí)間，最終求得工件的加工順序及并行機(jī)器的分配情況[5]。建立的數(shù)學(xué)模型如下。

(3)

(4)

(5)

Mj≥1

(6)

(7)

Cij≤Bir,r=j+1

(8)

式中：n為待加工的工件數(shù)；Xip為0～1變量(若工件i被安排在第p個(gè)位置上則取值為1，否則取值為0)；Mj為工序j的并行機(jī)器數(shù)量；Yijk為0～1變量(若工件i的第j道工序被安排在第k臺(tái)機(jī)器上則取值為1，否則取值為0)；m為工件所需的工序數(shù)；Cij為工件i在工序j上的加工完成時(shí)間；Bir為工件i在工序r上的開始加工時(shí)間。式(3)和式(4)表示每個(gè)位置被分配一個(gè)工件，且每個(gè)工件只能有一個(gè)優(yōu)先級(jí)順序；式(5)表示每階段的任務(wù)只能由一臺(tái)機(jī)器加工；式(6)和式(7)表示所有工序中至少存在一個(gè)工序有并行機(jī)器；式(8)表示只有當(dāng)前工序完成后才能進(jìn)入下一道工序。

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

遺傳算法基本原理是把所求解的問題采用編碼的方式編成染色體，每個(gè)染色體代表被求問題的一個(gè)解。然后對(duì)種群中的每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，若不滿足算法的終止條件，則算法通過適應(yīng)度值的大小進(jìn)行降冪排列來評(píng)價(jià)個(gè)體的優(yōu)劣程度，挑選優(yōu)秀的個(gè)體構(gòu)成下一代種群，進(jìn)行選擇、交叉、變異操作，一代代不斷地進(jìn)行遺傳，直至結(jié)果達(dá)到算法收斂條件，獲得最優(yōu)的個(gè)體。由于遺傳算法一般是優(yōu)先選擇更高級(jí)別染色體進(jìn)行復(fù)制，往往收斂于局部最優(yōu)解，降低了遺傳算法的全局搜索能力，無法保證解的多樣性，為此引進(jìn)小生境技術(shù)解決多目標(biāo)調(diào)度問題，可獲得全局最優(yōu)解[6]。小生境技術(shù)的基本思想是將每一代個(gè)體劃分為若干類，在每類中選出適應(yīng)度值大的個(gè)體作為優(yōu)秀個(gè)體代表組成一個(gè)種群，再在種群內(nèi)部及不同種類之間通過遺傳操作產(chǎn)生子代種群，采用預(yù)選擇機(jī)制完成選擇操作。對(duì)于同級(jí)別的染色體，通過小生境技術(shù)可選出更好的個(gè)體進(jìn)行復(fù)制。改進(jìn)后的遺傳算法流程圖如圖1所示。

圖1 算法流程圖

3 雙目標(biāo)混合流水車間調(diào)度的算法實(shí)現(xiàn)

3.1 編碼與解碼

本文對(duì)HFSP采用的是矩陣編碼，這種方法的優(yōu)點(diǎn)是能很好的解決工序之間的約束關(guān)系，使得染色體與可行調(diào)度能一一對(duì)應(yīng)，在遺傳操作中也不會(huì)產(chǎn)生非法解。

(9)

矩陣中的元素ast都是區(qū)間(1，Ms+1)里的一個(gè)實(shí)數(shù)。對(duì)矩陣中的元素進(jìn)行取整，當(dāng)出現(xiàn)取值相同時(shí)，說明至少兩個(gè)工件在同一機(jī)器上進(jìn)行同一工序的加工。此時(shí)分兩種情況進(jìn)行考慮：(1)所取的工序?yàn)榈谝坏罆r(shí)，加工順序可以按照a1t的升序進(jìn)行加工；(2)所取工序?yàn)榈诙阑蛑蟮墓ば?，根?jù)前一道工序的完成時(shí)間再確定其加工順序，前一道工序先完成的先加工，若加工完成時(shí)間相同，按照ast的升序進(jìn)行排序加工。

矩陣編碼完成后，可以確定染色體。每條染色體皆由s段構(gòu)成，每段由t個(gè)基因構(gòu)成。段與段之間用標(biāo)識(shí)符斷開，標(biāo)識(shí)符用“0”表示，代表不同工序，因此染色體的長度為s(t+1)-1。染色體表示形式為

[a11,a12,…,a1t,0,a21,a22,…,a2t,0,…,as1,as2,…,ast]

3.2 產(chǎn)生初始種群

運(yùn)用小生境遺傳算法進(jìn)行運(yùn)算時(shí)，初始種群的產(chǎn)生特別重要。若產(chǎn)生的初始種群適應(yīng)度值較低，則不利于初始小生境環(huán)境的產(chǎn)生，影響全局的搜索效率；相反，若產(chǎn)生的初始種群適應(yīng)度值較高，則算法會(huì)快速的進(jìn)行搜索，找到局部的最優(yōu)解[7]。本文中，初始種群的產(chǎn)生方式為隨機(jī)產(chǎn)生，其染色體的表現(xiàn)形式與編碼的方式相同。

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

遺傳算法在進(jìn)行計(jì)算時(shí)只運(yùn)用適應(yīng)度函數(shù)進(jìn)行個(gè)體優(yōu)劣的評(píng)價(jià)[8]。對(duì)于雙目標(biāo)問題，所求目標(biāo)為全局的最小值，故可將目標(biāo)函數(shù)進(jìn)行一系列的轉(zhuǎn)換，最終確定適應(yīng)度函數(shù)為

(10)

式中Cmax(X)為算法計(jì)算過程中的最大值。

3.4 選擇操作

選擇操作是在現(xiàn)有群體中選擇出優(yōu)良的個(gè)體進(jìn)行下一代的遺傳[9]。當(dāng)選取優(yōu)先級(jí)別不相同的染色體時(shí)，采用比例選擇法進(jìn)行選取。當(dāng)優(yōu)先級(jí)別相同時(shí)，利用小生境技術(shù)進(jìn)行選取[10]，選擇的基本思想是通過計(jì)算小生境數(shù)選出更加優(yōu)秀的個(gè)體進(jìn)行遺傳，計(jì)算原理如下。

計(jì)算小生境的半徑

(11)

進(jìn)行統(tǒng)一綱量

(12)

計(jì)算每個(gè)個(gè)體之間的距離

(13)

計(jì)算小生境數(shù)

(14)

3.5 交叉操作

編碼方式為矩陣編碼，因此只需要滿足ast∈(1,Ms+1)這個(gè)條件，即可確保個(gè)體的合法性[11]。在本文中，采用兩個(gè)矩陣按行進(jìn)行交叉操作。舉例進(jìn)行具體說明。

設(shè)父代P1和P2的染色體編碼如下。

若按行進(jìn)行交叉操作，交叉點(diǎn)隨機(jī)選擇為2，則產(chǎn)生兩個(gè)新的染色體

3.6 變異操作

變異操作是將原染色體基因轉(zhuǎn)變成新染色體的過程[12]。本文采用的變異操作為逆轉(zhuǎn)方式，即隨機(jī)選取染色體中的一部分基因作為子串，然后將該子串進(jìn)行逆轉(zhuǎn)，以相反的順序排列后再重新放回原先的子串位置。

4 算例仿真

本次算例仿真是以生產(chǎn)周期和生產(chǎn)費(fèi)用為研究目標(biāo)，對(duì)雙目標(biāo)混合流水車間調(diào)度問題進(jìn)行最優(yōu)化處理。采用Delphi7.0軟件，運(yùn)用面向?qū)ο蟮募夹g(shù)進(jìn)行編程，運(yùn)行上述算法。在進(jìn)行優(yōu)化過程中，作出以下假設(shè)：工件的加工時(shí)間和加工順序確定，每個(gè)工件的各項(xiàng)加工參數(shù)不變。在假設(shè)的基礎(chǔ)上進(jìn)行加工，使工件依次進(jìn)入流水車間進(jìn)行生產(chǎn)，最終完成加工目標(biāo)。在本次仿真中，采用的工件數(shù)為8個(gè)，每個(gè)工件有6道工序，其中并行機(jī)器的設(shè)置為：第二道工序的并行機(jī)器為2臺(tái)，分別為機(jī)器M2、M3；第三道工序的并行機(jī)器為2臺(tái)，分別為機(jī)器M4、M5；第五道工序的并行機(jī)器為2臺(tái)，分別為機(jī)器M7、M8。把工件的非并行機(jī)器加工時(shí)間和并行機(jī)器的加工時(shí)間分別列在表1、表2中，表1為工件在非并行機(jī)器上的加工時(shí)間，表2為工件在并行機(jī)器上的加工時(shí)間。

表1 各工件在非并行機(jī)器上的加工時(shí)間 分鐘

表2 各工件在并行機(jī)器上的加工時(shí)間 分鐘

運(yùn)用小生境遺傳算法解決問題，所設(shè)定的參數(shù)為：各個(gè)機(jī)器的初始加工時(shí)間均設(shè)為0，種群數(shù)目為100，交叉所占比率為0.8，變異所占比率為0.1，迭代次數(shù)為200。利用軟件計(jì)算最優(yōu)結(jié)果，進(jìn)行8次仿真運(yùn)算，仿真次數(shù)與對(duì)應(yīng)的生產(chǎn)周期見表3。

表3 仿真次數(shù)與生產(chǎn)周期

表3中計(jì)算的是混合流水車間中生產(chǎn)周期的最小值，通過表中的數(shù)據(jù)可以看出，生產(chǎn)周期皆在36～38分鐘，數(shù)據(jù)雖有起伏但變化不大，相對(duì)平穩(wěn)，符合算法的有效性和可行性。軟件通過小生境遺傳算法進(jìn)行計(jì)算，得出生產(chǎn)周期和生產(chǎn)費(fèi)用的最優(yōu)結(jié)果。各臺(tái)機(jī)器的生產(chǎn)費(fèi)用見表4。

表4 機(jī)器生產(chǎn)費(fèi)用

在雙目標(biāo)優(yōu)化過程中，通常所求的是目標(biāo)的最大值或最小值，本文所求的是生產(chǎn)周期最短和生產(chǎn)費(fèi)用最小。確定雙目標(biāo)的最優(yōu)解時(shí)，利用雙目標(biāo)空間定級(jí)圖可快速進(jìn)行研究、分析。在雙目標(biāo)最小化問題中，如果其空間中存在一個(gè)個(gè)體的橫坐標(biāo)和縱坐標(biāo)都比空間中其它個(gè)體小，那么可設(shè)定該因子為支配因子(在種群中，能支配其它任意個(gè)體的因子)，將其定為級(jí)別0；依次類推，如果在空間中一個(gè)個(gè)體只存在一個(gè)橫坐標(biāo)或縱坐標(biāo)大于之前的橫坐標(biāo)或縱坐標(biāo)，則其定為級(jí)別1，直至空間中所有的個(gè)體級(jí)別全部被定級(jí)完畢。

圖2是運(yùn)用小生境遺傳算法得到的后代示意圖。

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

通過示意圖2可以清楚的看到，P5點(diǎn)的個(gè)體在圖的最內(nèi)側(cè)，即其橫坐標(biāo)和縱坐標(biāo)都小于其它個(gè)體的橫縱坐標(biāo)，故可將P5點(diǎn)定級(jí)為0級(jí)。很顯然，其它個(gè)體的級(jí)別都大于P5點(diǎn)，生產(chǎn)周期和生產(chǎn)費(fèi)用也大于P5點(diǎn)，所以最終得出的最優(yōu)解是生產(chǎn)周期36分鐘，生產(chǎn)費(fèi)用為8750元。通過仿真得到的最優(yōu)甘特圖如圖3所示。

圖3 雙目標(biāo)混合流水車間調(diào)度甘特圖

從圖3上可以看出工件在并行機(jī)器上的分配情況，且工件的具體加工順序和加工時(shí)間均已確定。本文運(yùn)用小生境遺傳算法解決HFSP問題，充分縮短了加工時(shí)間，減少了生產(chǎn)費(fèi)用，提高了車間的生產(chǎn)效率。

5 結(jié)論

針對(duì)遺傳算法解決雙目標(biāo)混合流水車間調(diào)度問題的不足，提出了將小生境算法與遺傳算法結(jié)合的方法，既保持了種群的多樣性，又可提高全局的搜索能力和收斂速度，從而找出更多的最優(yōu)解以供選擇。解決了雙目標(biāo)混合流水車間調(diào)度的核心問題，即工件在每個(gè)機(jī)器上的分配問題、各機(jī)器工件上的加工順序問題以及平衡雙目標(biāo)之間的沖突而選取最優(yōu)結(jié)果問題。運(yùn)用此方法得到的是一組最優(yōu)解集而并非是單個(gè)的最優(yōu)解，是直接對(duì)兩個(gè)目標(biāo)進(jìn)行同時(shí)處理，結(jié)果更加切合實(shí)際。通過合理的參數(shù)設(shè)計(jì)建立仿真模型，仿真結(jié)果證明該方法的可行性和有效性。