楊 艷，趙維強(qiáng)，陶惠絹，錢 惠，曹進(jìn)露，趙丹萍，朱靜云

(江蘇陽光集團(tuán)有限公司，江蘇 江陰 214426)

1 引言

流水生產(chǎn)線是一種先進(jìn)的生產(chǎn)組織形式，有利于機(jī)器設(shè)備和人力的充分利用。流水線不暢通，就會發(fā)生誤工情況，導(dǎo)致生產(chǎn)效率降低，生產(chǎn)受阻。在服裝生產(chǎn)過程中，縫紉車間流水線的平衡是其關(guān)鍵環(huán)節(jié)，如何合理地組織縫紉生產(chǎn)，解決好流水線的平衡問題，是提高服裝生產(chǎn)效率的關(guān)鍵。

很多研究表明，尋找流水線平衡問題的最優(yōu)解是非常困難的，最有工程意義的求解算法是放棄尋找最優(yōu)解的目標(biāo)，轉(zhuǎn)而試圖在合理的、有限的時間內(nèi)尋找到一個近似于最優(yōu)、有用的解。近年來這方面已經(jīng)取得了不少研究成果，特別是模糊邏輯(FL)、遺傳算法(GA)、神經(jīng)網(wǎng)絡(luò)(NN)、蟻群算法(ACO)、粒子群算法(PSO)等求解方法，為解決較大規(guī)模的優(yōu)化問題提供了比較可行的方法，其中遺傳算法在解決流水線平衡問題方面具有較好的效果。本文將遺傳算法應(yīng)用到男西褲生產(chǎn)流水線中，解決并行制造中的流水線平衡問題，以實(shí)現(xiàn)對流水線人員的合理安排，并對流水線的工藝進(jìn)行仿真設(shè)計(jì)。

2 遺傳算法

Srinivas M.等人[1]提出一種遺傳算法(Adaptive General Algorithm，AGA)，能夠使交叉概率Pc和變異概率Pm隨群體的自適應(yīng)自動改變。當(dāng)種群各個體的適應(yīng)度趨于一致或者趨于局部最優(yōu)時，使Pc和Pm增加，以跳出局部最優(yōu)；當(dāng)群體適應(yīng)度比較分散時，使Pc和Pm減少，以利于優(yōu)良個體的生存。同時，對于適應(yīng)度高于群體平均適應(yīng)值的個體，選擇較少的Pc和Pm值，使得該優(yōu)良解得以保護(hù)；低于平均適應(yīng)值的個體，選擇較大的Pc和Pm值，增加新個體產(chǎn)生的速度。因此，遺傳算法能夠提供相對某個解最佳的交叉概率Pc和變異概率Pm。

與其他算法相比，遺傳算法的交叉概率與變異概率不是一個固定值，而是按群體的適應(yīng)度進(jìn)行自適應(yīng)調(diào)整。遺傳算法的交叉概率Pc和變異概率Pm如式(1)、式(2)所示。

(1)

(2)

在上式中，fmax是每代群體中個體的最大適應(yīng)度值；favg是每代群體的平均適應(yīng)度值；f′是被選擇交叉的兩個個體中較大的適應(yīng)度值；f是被選擇變異個體的適應(yīng)度值。只要設(shè)定k1、k2、k3、k4取(0，1)區(qū)間的值，就可以實(shí)現(xiàn)自適應(yīng)調(diào)整。

從上式中可以看出，當(dāng)適應(yīng)度值越接近于最大適應(yīng)度值時，Pc和Pm的值就越?。划?dāng)?shù)扔谧畲筮m應(yīng)度值時，Pc和Pm的值為零。這種調(diào)整Pc和Pm的方法對于群體處于進(jìn)化后期時比較合適，因?yàn)樵谶M(jìn)化后期，群體中每個個體基本上表現(xiàn)出較優(yōu)的性能，這時不宜對個體進(jìn)行較大的變化以免破壞了個體的優(yōu)良性能結(jié)構(gòu)，但是這種調(diào)整方式對于處于進(jìn)化初期階段的群體效率較低，使進(jìn)化走向局部最優(yōu)解的可能性增加。

實(shí)行遺傳算法的主要問題包括：問題的編碼、適應(yīng)度函數(shù)的構(gòu)造、初始種群的選取、選擇策略、交叉變異算子的選取、交叉變異概率的確定、算法終止條件[2]。

3 問題描述

以男西褲的縫制工藝為研究對象，它由40道大工序按照一定的順序組成，若將其交給40名員工Pi(i=1，2，…，40)去完成，每人完成一個大工序，因這40個人的技能水平不同，他們完成不同工序所花時間也不同。因此關(guān)鍵在于分配這40道工序到不同的人，并使整個加工時間變到最短。

已知完成各道工序的標(biāo)準(zhǔn)時間給定，令ST(i)表示完成第i道工序100次的標(biāo)準(zhǔn)時間，ST=[41 30 25 42 30 65 28 46 57 58 86 41 37 19 28 30 29 47 64 54 33 20 34 52 47 63 44 36 65 56 38 34 55 57 65 58 36 38 68 67]。工序的生產(chǎn)順序如圖1所示。

圖1 男西褲的縫制工序順序圖

其中fi(i∈N，1≤i≤40)表示第i道工序；員工i完成工序j所花的時間，由式(3)確定。

Ti·j=k·STj(k∈R)

(3)

這個問題可以歸為組合優(yōu)化中的旅行商問題(TSP)一類，屬于NP-Hard組合優(yōu)化問題。解決這類問題的方法有很多，如窮舉法、貪心法、動態(tài)規(guī)劃方法、分枝定界法等，但是這些方法的目標(biāo)函數(shù)都被定義為線性的。而本問題由于生產(chǎn)工藝的并行性，其目標(biāo)函數(shù)是非線性的，同時隨著問題規(guī)模的增加，這些精確的數(shù)學(xué)方法已無法解決此類問題。

已有研究結(jié)果表明，遺傳算法對求解生產(chǎn)流水線問題具有較好的效果。本文將該算法應(yīng)用于男西褲流水線，通過優(yōu)化，自動給出比較合適的交叉概率和變異概率，從而顯著提高搜索效率。

4 基于遺傳算法的男西褲流水線分析

4.1 編碼

本文選用一種基于順序表達(dá)的實(shí)數(shù)編碼方式。染色體的長度等于縫制工序數(shù)，全部員工的上崗順序編碼為一組自然數(shù)編碼的字符串，即染色體；染色體的基因取1～40之間的自然數(shù)，分別代表員工1～員工40。例如1，2，3，4……40。

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

適配值函數(shù)為：

其f(m)表示完成40道工序?qū)嶋H所用去的時間。

f1=T1+T2+T3+T4+T7+T8+T9+T10+T11+T12+T40

f2=T5+T6+T7+T8+T9+T10+T30

f3=T11+T12+T13+T16+T17+T20+T29+T30+T31+T32+T33+T34+T35+T36+T37+T38+T39+T40

f4=T14+T15+T16+T17+T20+T29+T30+T31+T32+T33+T34+T40

f5=T18+T19+T20+T29+T30+T31+T32+T33+T40

f6=T20+T28+T29+T34+T35+T36+T37+T40

f7=T21+T22+T23+T26+T27+T30+T31+T32+T33+T34+T35+T40

f8=T24+T25+T26+T27+T3

4.3 初始種群的選取

初始化種群：初始化種群是將優(yōu)化問題的一組初始可行解，即全部員工的上崗順序編碼為一組自然數(shù)編碼的字符串，即染色體；染色體的基因取1～40之間的自然數(shù)，分別代表員工1～員工40。初始種群中的染色體隨機(jī)產(chǎn)生。

把上一步生產(chǎn)的染色體種群按照評價函數(shù)進(jìn)行排序，采用傳統(tǒng)的輪盤賭的方式選擇產(chǎn)生父代染色體。個體被選中的概率與其在群體中的相對適應(yīng)度成反比。

4.4 復(fù)制算子

從群體中選擇優(yōu)勝個體淘汰劣質(zhì)個體的操作為選擇算子。本文采用精英原則的輪盤賭選擇機(jī)制，即經(jīng)交叉后的子代需與父代進(jìn)行比較，只有當(dāng)子代的適應(yīng)值大于父代的適應(yīng)值時，才用子代代替父代，否則保留父代。

4.5 交叉 變異算子的選取

在男西褲流水線的平衡問題中，由于染色體上每位基因表述的是完成該工序的員工號，所以交叉、變異的概率大小更直接地體現(xiàn)為參與交叉、變異的基因位數(shù)的多少。參與交叉、變異的基因位數(shù)多，則該工序的操作員工順序改變大；參與交叉、變異的基因位數(shù)少，則該工序的操作員工順序改變不明顯。所以如果不考慮參與交叉、變異的基因位數(shù)，則所謂的交叉、變異概率顯得毫無意義。因此，把交叉、變異概率理解為參與交叉、變異基因位數(shù)的多少。

交叉長度=PC×NUM，變異長度=Pm×NUM

其中PC：交叉概率，Pm：變異概率，NUM：染色體長度。

交叉算子：將獲得的父代按適應(yīng)度值進(jìn)行排序，讓前半部分與后半部分分別進(jìn)行交叉，在兩個交叉的雙親中任意選取一個交叉位置，交叉長度= PC×NUM，再確定另一個交叉位置，由此確定交叉的基因段[3]。其后代在這段基因里的編碼按照另一雙親的順序排列，其余編碼的排列順序不變。因?yàn)殡p親都是可行解，則通過這樣的方法產(chǎn)生的后代也必然是可解行。變異算子：為了加快算法的收效效果，在父代上任意選取一個變異位置，變異長度=Pm×NUM，再確定另一個變異位置，由此確定變異的基因段，在變異的基因段，進(jìn)行隨機(jī)排序，得到新的染色體。

4.6 改進(jìn)的自適應(yīng)交叉 變異概率的確定

在遺傳算法中，個體的適應(yīng)度值越接近最大適應(yīng)度值，交叉概率與變異概率就越小；當(dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉概率與變異概率為零[4，5]。這種調(diào)整方法在群體處于進(jìn)化后期時是比較合適的，但在進(jìn)化初期對進(jìn)化是不利的，因?yàn)樵谶M(jìn)化初期群體中的較優(yōu)個體幾乎處于一種不發(fā)生變化的狀態(tài)，而此時的優(yōu)良個體不一定是優(yōu)化的全局最優(yōu)解，這增加了進(jìn)化走向局部最優(yōu)的可能性。

遺傳算法是將交叉概率PC和變異概率Pm分別改為式(4)、式(5)，使群體中最大適應(yīng)度值的個體的交叉概率和變異概率不為零，分別提高到Pc2和Pm2。

Pc=

(4)

Pm=

(5)

當(dāng)f′=fmax時，Pc=Pc2>0；當(dāng)f=fmax時，Pm=Pm2>0。為了保證每一代的最優(yōu)個體不被破壞，同時采用最優(yōu)保存策略，將其直接復(fù)制到下一代中。上式中，取Pc1=0.95，Pc2=0.6，Pm1=0.15，Pm2=0.001。

4.7 終止條件

令fmax[k]為第k代種群中最優(yōu)個體的適應(yīng)度值，favg[k]為第k代種群中所有個體適應(yīng)度值的平均值。分別定義第k(k≥10)代之前的前10代的種群最優(yōu)適應(yīng)度值的平均值和第k(k≥10)代之前的前10代的個體適應(yīng)度值的平均值。

(6)

(7)

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

5.1 實(shí)驗(yàn)

為了驗(yàn)證上述算法的有效性，用Minitab實(shí)現(xiàn)上述算法。在實(shí)際生產(chǎn)中，員工的熟練程度接近于標(biāo)準(zhǔn)時間的比較多，本文?。?/p>

(8)

其中x是均勻分布與[0，10]之間隨機(jī)數(shù)。通過上式設(shè)定的k使員工的實(shí)際操作時間處于標(biāo)準(zhǔn)時間的0.5倍～1.5倍的概率為70%，使員工的實(shí)際操作時間處于標(biāo)準(zhǔn)時間的0～0.5倍的概率為10%，使員工的實(shí)際操作時間大于標(biāo)準(zhǔn)時間的1.5倍的概率為20%。

5.2 結(jié)果分析

這里隨機(jī)選取員工完成各道工序的時間值，其中適應(yīng)度最高的個體如表1所示。

表1 遺傳算法分析表

運(yùn)用遺傳算法，得到的最好結(jié)果為19-38-15-11-37-30-33-13-6-39-14-23-35-20-5-3-34-21-29-32-22-1-31-26-16-27-36-2-40-24-10-17-25-9-4-8-18-28-12-7，與現(xiàn)有的手工分配相比，時間縮短的很多。

6 結(jié)語

文本利用遺傳算法解決了男西褲縫制流水線的平衡問題，不需過多的數(shù)學(xué)計(jì)算，且能夠在搜索過程中自動給定交叉概率和變異概率，顯著提高了收斂速度，且相對于其他方法而言，更容易得到最優(yōu)解，具有簡便高效的特點(diǎn)。