黃錦鈿，陳慶新，毛 寧

HUANG Jin-dian1, CHEN Qing-xin2, MAO Ning2

（1.揭陽職業(yè)技術(shù)學(xué)院，揭陽 522000；2.廣東工業(yè)大學(xué)，廣州 510006）

0 引言

單元成組加工是現(xiàn)代制造企業(yè)應(yīng)用廣泛的一種生產(chǎn)作業(yè)方式，該生產(chǎn)方式是將加工工藝相似的工件放到一組，并根據(jù)工件的工藝要求為所需要的設(shè)備分組，運(yùn)用單元成組加工有利于保證工件加工質(zhì)量和提高生產(chǎn)效率。文獻(xiàn)[1]認(rèn)為模具型腔的加工受到EDM車間工藝條件的限制，加工型腔所用的電極必須被成組安排到同一臺(tái)設(shè)備，從而研究了后工序帶有成組特征的模具電極調(diào)度策略，并在不同的加工條件下提出相應(yīng)的調(diào)度算法。文獻(xiàn)[2]在假定工件具有精確的加工時(shí)間和到達(dá)時(shí)間前提下，提出了一種前工序具有成組約束的兩階段柔性同序加工車間排序算法。在企業(yè)的實(shí)際生產(chǎn)中，往往存在大量的不確定因素，如機(jī)器故障、操作工人的熟練程度、環(huán)境參數(shù)等的影響，很少能獲得精確的加工時(shí)間和到達(dá)時(shí)間。因此，本文將在文獻(xiàn)[2]已有研究的基礎(chǔ)上，借助模糊數(shù)學(xué)理論[3,4]，將工件的加工時(shí)間和到達(dá)時(shí)間作模糊數(shù)考慮，在前工序帶成組加工約束的兩階段柔性同序加工車間中，基于遺傳算法提出一種新的啟發(fā)式算法，調(diào)度目標(biāo)是為所有工件指定加工設(shè)備并確定加工順序，使所有工件經(jīng)過這兩道工序的最大完成時(shí)間最短?，F(xiàn)結(jié)合模具企業(yè)生產(chǎn)的實(shí)際情況，將問題進(jìn)一步具體化，并提出以下假設(shè)。

假設(shè)1：各部件到達(dá)車間的時(shí)間已知但不確定，不同部件到達(dá)車間的時(shí)間不一定相同，同一部件中的工件到達(dá)車間的時(shí)間相同；

假設(shè)2：每個(gè)部件包括多個(gè)工件，且數(shù)量確定已知；

假設(shè)3：每個(gè)工件都必須經(jīng)過兩道工序的加工，而且加工順序不能改變；

假設(shè)4：允許工件在工序之間等待，兩道工序之間具有無限的緩存能力；

假設(shè)5：每道工序?qū)?yīng)的工作中心都由若干個(gè)工作小組組成，每個(gè)工作小組中有若干臺(tái)設(shè)備，各工作小組的設(shè)備數(shù)量不等且確定已知，相同工作小組中的設(shè)備工作效率相同，不同工作小組中的設(shè)備工作效率不同；

假設(shè)6：工件在各工序各工作小組需要的加工時(shí)間已知但不確定，相同部件中的工件加工要求相同，不同部件中的工件加工要求不同；

假設(shè)7：一臺(tái)設(shè)備在同一時(shí)刻只能加工一個(gè)工件；

假設(shè)8：工件一旦在設(shè)備上開始加工，不允許中途停下來，插入其他的工件；

假設(shè)9：在前工序，同一部件中的工件必須被安排在同一工作小組加工。

1 模糊時(shí)間

1.1 模糊處理

模糊數(shù)是模糊集的一種特殊形式。模糊數(shù)一般采用分段直線的方法來表示，最常用的就是三角形模糊數(shù)和梯形模糊數(shù)，其對(duì)應(yīng)的隸屬度函數(shù)就是三角形和梯形。本文中工件的到達(dá)時(shí)間采用三角模糊數(shù) 來表示，其隸屬度函數(shù)公式如(1)所示：

在模具企業(yè)的實(shí)際生產(chǎn)中，有經(jīng)驗(yàn)的調(diào)度員在估計(jì)某一工件的加工時(shí)間時(shí)，一般認(rèn)為工件的加工時(shí)間在某一個(gè)時(shí)間區(qū)間段內(nèi)都是合理的，如果低于這個(gè)時(shí)間段的下界或高于它的上界時(shí)，隨著偏離的距離越遠(yuǎn)則其合理性就越低，即滿意度越低。因此，工件的加工時(shí)間采用梯形模糊數(shù)來表示，其隸屬度函數(shù)如式(2)所示：

在模糊調(diào)度問題中，模糊數(shù)的求和及取大操作是關(guān)鍵，求和操作用于計(jì)算工件的模糊完工時(shí)間，取大操作用于確定工件工序的開工時(shí)間。由于本文中工件的到達(dá)時(shí)間和加工時(shí)間分別采用三角模糊數(shù)和梯形模糊數(shù)，因此在求和計(jì)算工件模糊完成時(shí)間時(shí)存在兩種模糊數(shù)間的三種不同運(yùn)算，根據(jù)模糊數(shù)擴(kuò)張?jiān)?，模糊?shù)的求和運(yùn)算作如下三個(gè)定義。

和計(jì)算工件的完成時(shí)間一樣，在確定工件的開工時(shí)間時(shí)同樣存在三種不同的取大運(yùn)算，根據(jù)模糊取大操作的原理作如下三個(gè)定義。

定義6：如果三角模糊數(shù)和梯形模糊數(shù)作取大運(yùn)算，設(shè)則將三角模糊數(shù)表示為梯形模糊數(shù)的特殊形式，即三角模糊數(shù)表示為 ，因此

1.2 排序方法的選用

模糊數(shù)的比較是模糊優(yōu)化的一個(gè)關(guān)鍵問題，要使得兩個(gè)模糊數(shù)之間的比較有意義必須在相同模糊度的情況下進(jìn)行，雖然很多學(xué)者都在研究模糊數(shù)的比較方法，提出了各種比較指標(biāo)。但是，迄今為止還沒有一個(gè)方法被公認(rèn)為是最好的，所有的方法在復(fù)雜的情況下都或多或少地缺乏分辨力，甚至與人們的直覺相抵觸。實(shí)際應(yīng)用中，具體采用哪種方法則主要取決于問題的本身和決策者的態(tài)度。由于本文研究的調(diào)度問題比較復(fù)雜，且在實(shí)際生產(chǎn)中調(diào)度人員的估計(jì)方法也是采用取均值的方式，所以本文采用均勻分布的Lee-Li法，把相關(guān)的模糊數(shù)轉(zhuǎn)化為精確值來處理。

將模糊集 的均值和標(biāo)準(zhǔn)偏差分別記為m()和σ()，借助模糊事件概率測(cè)度的概念，均勻分布的Lee-Li法用下式計(jì)算均值和標(biāo)準(zhǔn)偏差：

在模糊均值和模糊偏差的基礎(chǔ)上，Lee-Li進(jìn)一步定義了模糊集綜合評(píng)判排序指標(biāo)如下：

這里的β是由決策者選定的權(quán)值，它反映了均值與偏差在決策者心目中的相對(duì)重要程度,通過式(5)我們可以把模糊數(shù)轉(zhuǎn)化為精確值，以此為基礎(chǔ)得到目標(biāo)函數(shù)值。

2 基于遺傳算法的求解過程

2.1 遺傳算法概述

遺傳算法自從1975 年由Holland 提出至今已被廣泛的應(yīng)用到組合優(yōu)化、機(jī)器學(xué)習(xí)、模式識(shí)別以及人工神經(jīng)元網(wǎng)絡(luò)等方面[5,6]。遺傳算法基本流程描述如圖1所示：

圖1 遺傳算法流程圖

2.2 編碼設(shè)計(jì)

根據(jù)本文調(diào)度問題的特點(diǎn)，相同部件中的工件在前工序中必須被安排到同一個(gè)加工小組加工，因此在編碼時(shí)將相同部件中的所有工件看成一個(gè)整體，同時(shí)將前工序中同一個(gè)加工小組中的機(jī)床看成一個(gè)整體。

編碼時(shí)，用自然數(shù)序列代表所有可能的部件加工順序，而不同加工小組上的部件則用‘0’隔開。對(duì)于n個(gè)部件、前階段有M個(gè)工作小組的問題，一個(gè)合法的染色體應(yīng)包括n個(gè)部件符號(hào)，（M-1）個(gè)間隔符號(hào)‘0’，總長(zhǎng)度為（n+M-1）個(gè)基因?，F(xiàn)假設(shè)有7個(gè)部件、前工序有3個(gè)工作小組的情況，則染色體的基因編碼表示應(yīng)為：[1 6 3 0 7 4 0 2 5]。則各小組上對(duì)應(yīng)的部件加工順序?yàn)椋篗1：1→6→3；M2：7→4；M3：2→5。

從染色體的編碼信息中可以確定部件在前工序中的加工小組和加工順序，然后對(duì)比部件的到達(dá)時(shí)間和機(jī)床的空閑時(shí)間，進(jìn)一步確定工件對(duì)應(yīng)的機(jī)床和加工順序。這種編碼方式有利于保證滿足工件成組加工的約束，而且有利于提高搜索效率。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)

本文調(diào)度的目標(biāo)函數(shù)值是最短的最大完成時(shí)間f(S)。按先到達(dá)先加工的原則確定工件的加工順序，所有工件通過兩道工序的最大完成時(shí)間為Cmax，現(xiàn)通過下面公式將目標(biāo)函數(shù)值轉(zhuǎn)化為適應(yīng)度函數(shù)值F(S)：

通過式（6）計(jì)算轉(zhuǎn)換，使得目標(biāo)函數(shù)值較小的染色體有較高的適應(yīng)度，而且各染色體將以適當(dāng)?shù)母怕蔬z傳到下一代。

2.4 初始種群設(shè)計(jì)

為了使初始種群盡可能多樣化并且提高尋優(yōu)效率，本文采用兩種方式產(chǎn)生初始種群。第一種方式是采用完全隨機(jī)方法產(chǎn)生初始種群，例如有n個(gè)待排產(chǎn)的部件，前工序中有M個(gè)加工小組，則首先產(chǎn)生由自然數(shù)1到n組成的隨機(jī)序列，然后將M-1個(gè)0隨機(jī)插入到序列中，這樣就得到一個(gè)長(zhǎng)度為n+M-1的染色體，反復(fù)做上述操作，可以得到若干個(gè)隨機(jī)初始染色體；第二種方式是采用確定方式產(chǎn)生優(yōu)良初始染色體，采用先到達(dá)先加工的原則可以得到一個(gè)適應(yīng)度較高的初始染色體。將這兩種方式產(chǎn)生的染色體結(jié)合到一起作為初始種群，這樣不僅增加了種群的多樣性，而且提高了種群的進(jìn)化進(jìn)程。

2.5 選擇算子

選擇過程是為了從當(dāng)前的群體中選出優(yōu)良的個(gè)體，使他們有機(jī)會(huì)作為父代將其優(yōu)良的個(gè)體信息傳遞給下一代，本文采用確定式采樣選擇方法來選擇優(yōu)良的個(gè)體。具體操作步驟如下：

1）計(jì)算群體中各個(gè)個(gè)體在下一代群體中的期望生存數(shù)目Ni：

式中，Nind為種群個(gè)_體數(shù)_量，i = 1,2,3,…,Nind。

2）用Ni的整數(shù)部分確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目。其中表示取不大于x的最大的整數(shù)。此時(shí)可確定出下一代群體中的個(gè)個(gè)體。

3）按照Ni的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排序，順序取前Nind-個(gè)個(gè)體加入到下一代群體中。至此可完全確定出下一代群體中的Nind個(gè)個(gè)體。

這種選擇操作方法可保證適應(yīng)度較大的一些優(yōu)良個(gè)體一定能夠被保留在下一代群體中，并且操作也比較簡(jiǎn)單。

2.6 交叉算子

交叉運(yùn)算是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體，它在遺傳算法中起著關(guān)鍵作用。在交叉運(yùn)算之前必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)，本文采用隨機(jī)配對(duì)的配對(duì)策_(dá)略，即將_群體中的Nind個(gè)個(gè)體以隨機(jī)的方式組成 對(duì)配對(duì)個(gè)體組，交叉操作是在這些配對(duì)個(gè)體組中的兩個(gè)個(gè)體之間進(jìn)行的。本文每個(gè)染色體編碼包含前工序中各個(gè)加工小組的調(diào)度信息，我們將每個(gè)加工小組對(duì)應(yīng)的調(diào)度稱為子調(diào)度。本文采用子調(diào)度維持交叉算子，即在兩個(gè)父代染色體作交叉運(yùn)算時(shí)，在兩個(gè)父代染色體中的各取一個(gè)子調(diào)度復(fù)制到后代中，然后用另一個(gè)父代染色體剩余的編碼按順序來完成該后代的構(gòu)造。交叉過程具體描述如下：

1）從一個(gè)父代染色體中找到字符“0”所在的位置，建立一個(gè)空白后代染色體，并將父代染色體中的字符“0”復(fù)制到后代染色體相應(yīng)的位置；

2）從該父代染色體中隨機(jī)取出一個(gè)子調(diào)度，并將其填入所建后代染色體中的相應(yīng)位置；

3）在另一個(gè)父代染色體中，將與步驟2)所取出的子調(diào)度相同的基因標(biāo)記為“-1”；

4）從左到右掃描另一個(gè)父代染色體不為“0”和“-1”的基因，依次將其填入到后代染色體的其余位置。

例子：假設(shè)有2個(gè)父代Pl和P2，隨機(jī)選擇Pl和P2最右邊的子調(diào)度作為維持的子調(diào)度，交叉運(yùn)算執(zhí)行過程如下所示：

父代Pl：1 2 3 0 4 5 6 0 7 8 9

父代P2：2 5 8 1 0 3 4 0 6 7 9

中間執(zhí)行過程：

父代Pl：1 2 3 0 4 5 -1 0 -1 8 -1

父代P2：2 5 -1 1 0 3 4 0 6 -1 -1

后代Cl：××× 0××× 0 7 8 9

后代C2：××××0×× 0 6 7 9

結(jié)果：

后代C1： 2 5 1 0 3 4 6 0 7 8 9

后代C2： 1 2 3 4 0 5 8 0 6 7 9

從上例可以看出，染色體的某一基因片段保持不變，其余基因順序?qū)⒈徽{(diào)整，部件在前工序的加工小組分配和加工順序也將被調(diào)整。

2.7 變異算子

根據(jù)染色體編碼的特點(diǎn)，本文采用隨機(jī)互換兩個(gè)基因位置的變異方式，隨機(jī)交換的基因可以是工件號(hào)和工件號(hào)，也可以是工件號(hào)和“0”的不同組合，所以存在下面4種變異形式：

1）如果兩個(gè)基因都是工件，可能出現(xiàn)兩種情況。一種情況是兩個(gè)工件在同一加工小組上加工，這時(shí)實(shí)質(zhì)是改變工件的加工順序，如下所示：

變異前：1 3 4 0 5 6 0 7 8 9

變異后：1 4 3 0 5 6 0 7 8 9

2）另一種情況是兩個(gè)工件在不同的加工小組上加工。這時(shí)變異改變?nèi)旧w的工件順序和工件對(duì)加工小組的分配，如下所示：

變異前：1 2 3 4 0 5 6 0 7 8 9

變異后：1 2 7 4 0 5 6 0 3 8 9

3）如果兩個(gè)基因都是“0”，則把兩個(gè)加工小組上的加工任務(wù)對(duì)調(diào)，工件的加工順序不變，如下所示：

變異前：1 2 3 4 0 5 6 0 7 8 9

變異后：5 6 0 1 2 3 4 0 7 8 9

4）如果一個(gè)基因是“0”，另一個(gè)基因是工件，則工件的加工順序和工件對(duì)加工小組的分配都發(fā)生改變，如下所示：

變異前：1 2 3 4 0 5 6 0 7 8 9

變異后：1 2 3 4 0 5 6 7 0 8 9

3 應(yīng)用實(shí)例

在某模具企業(yè)運(yùn)用本文所提的方法，對(duì)14個(gè)不同時(shí)到達(dá)車間的部件進(jìn)行排序，各部件包括的工件數(shù)量見表1。將各件的到達(dá)時(shí)間用三角模糊數(shù)表示，見表2。將各工件在設(shè)備上的加工時(shí)間用梯形模糊數(shù)表示，在前工序車間有大宇和威力兩個(gè)型號(hào)的數(shù)控機(jī)床，見表3和表4。

表1 各部件包括的工件數(shù)量（單位：個(gè)）

表2 各部件的到達(dá)時(shí)間（單位：小時(shí)）

表3 各部件Ji對(duì)應(yīng)的工件在前工序各設(shè)備的加工工時(shí)（單位：h）

表4 各部件Ji對(duì)應(yīng)的工件在后工序各設(shè)備的加工工時(shí)（單位：h）

在上述給定條件下，應(yīng)用本文的遺傳算法求解，設(shè)置運(yùn)行環(huán)境為初始種群染色體數(shù)為20個(gè)，交叉率為0.5，變異率為0.03，遺傳代數(shù)為12。通過eM-Plant仿真,發(fā)現(xiàn)最好的染色體出現(xiàn)在第9代，第10代，第11代，第12代。均為：[1 3 6 10 14 7 11 0 2 4 8 9 12 13 5]，各機(jī)床的計(jì)劃負(fù)荷甘特圖如下圖2所示。

圖2 前工序各機(jī)床的甘特圖

圖3 后各機(jī)床的甘特圖

運(yùn)用本文提出的遺傳算法所有工件通過兩道工序的時(shí)間是325小時(shí)。如果按先到達(dá)先加工的原則確定工件的加工順序，通過兩道工序的最大完成時(shí)間是369小時(shí)，單純按照J(rèn)ohnson法則確定工件的加工順序，最大完成時(shí)間將是415小時(shí)。從這些運(yùn)行結(jié)果對(duì)比可以看出，該遺傳算法的排序結(jié)果優(yōu)于其它算法，而且計(jì)算時(shí)間為半秒，適合應(yīng)用于車間現(xiàn)場(chǎng)。

4 結(jié)束語

本文研究了前階段帶有成組約束的兩階段柔性同序加工車間的排序問題，考慮了具有模糊加工時(shí)間和模糊到達(dá)時(shí)間的情況，分別用梯形模糊數(shù)和三角模糊數(shù)來表示加工時(shí)間和到達(dá)時(shí)間，采用均勻分布的Lee-Li法將模糊數(shù)轉(zhuǎn)化為精確值，通過遺傳算法優(yōu)化排序，應(yīng)用企業(yè)的實(shí)際算例仿真說明該算法的有效性和可行性。

[1] 孫吳勝.考慮后工序帶有成組特征的模具電極調(diào)度策略的研究[D].廣州:廣東工業(yè)大學(xué).2007.

[2] 黃錦鈿,陳慶新,毛寧.具有成組約束的柔性同序加工車間的排序算法[J].工業(yè)工程,2011,V14(2):112-117.

[3] Slowinski R,Hapke M.Scheduling under fuzziness[M].New York:Physica-Verlag.2000.

[4] J.Peng,B.Liu,Parallel machine scheduling models with fuzzy processing times[J],Information Sciences,166,49-66,2004.

[5] 盧永超,陳慶新,毛寧.基于遺傳禁忌搜索算法的模具電火花車間調(diào)度[J].工業(yè)工程,2008,11(5):80-85.

[6] 盧永超,陳慶新,毛寧.模具電火花加工車間的非同等并聯(lián)機(jī)混合遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2009,15(3):587-543.