基于模糊時間并具有成組約束的車間排序算法

黃錦鈿，陳慶新，毛 寧

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

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

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

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

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

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

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

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

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

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

1 模糊時間

1.1 模糊處理

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

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

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

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

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

1.2 排序方法的選用

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

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

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

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

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

2.1 遺傳算法概述

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

圖1 遺傳算法流程圖

2.2 編碼設(shè)計

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

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

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

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

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

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

2.4 初始種群設(shè)計

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

2.5 選擇算子

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

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

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

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

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

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

2.6 交叉算子

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

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

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

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

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

例子：假設(shè)有2個父代Pl和P2，隨機選擇Pl和P2最右邊的子調(diào)度作為維持的子調(diào)度，交叉運算執(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ù)染色體編碼的特點，本文采用隨機互換兩個基因位置的變異方式，隨機交換的基因可以是工件號和工件號，也可以是工件號和“0”的不同組合，所以存在下面4種變異形式：

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

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

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

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

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

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

3）如果兩個基因都是“0”，則把兩個加工小組上的加工任務(wù)對調(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）如果一個基因是“0”，另一個基因是工件，則工件的加工順序和工件對加工小組的分配都發(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)用實例

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

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

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

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

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

在上述給定條件下，應(yīng)用本文的遺傳算法求解，設(shè)置運行環(huán)境為初始種群染色體數(shù)為20個，交叉率為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]，各機床的計劃負(fù)荷甘特圖如下圖2所示。

圖2 前工序各機床的甘特圖

圖3 后各機床的甘特圖

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

4 結(jié)束語

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

[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].計算機集成制造系統(tǒng),2009,15(3):587-543.