周正一

摘要：對(duì)于具有多品種、多批次、小批量等特點(diǎn)的中小型離散制造業(yè)來說，為了追求高柔性、高質(zhì)量、短交貨期和低成本的目的，建立單元制造系統(tǒng)勢(shì)在必行。本文針對(duì)單元制造系統(tǒng)中最為關(guān)鍵的單元構(gòu)建問題進(jìn)行研究，分析了利用傳統(tǒng)遺傳算法在解決單元構(gòu)件問題時(shí)可能存在的缺陷，提出了一種新算法的單元構(gòu)建算法，并結(jié)合實(shí)例證明了方法的可行性和有效性。

關(guān)鍵詞：?jiǎn)卧圃?單元構(gòu)建??遺傳算法?成組效率

1.引言

在利用遺傳算法解決單元構(gòu)建問題（Cell?formation?problem，?CFP）時(shí)，一般將分組數(shù)直接作為一個(gè)優(yōu)化的變量通過遺傳算子進(jìn)行優(yōu)化，但這里面存在以下三個(gè)問題：（1）對(duì)于分組數(shù)多得染色體，其合法性呈下降趨勢(shì)，這使得分組數(shù)多的染色體成為劣勢(shì)群體，并面臨較高的淘汰風(fēng)險(xiǎn)。（2）對(duì)于同一問題，當(dāng)分組數(shù)不同時(shí)，目標(biāo)函數(shù)的收斂性不同，對(duì)于不同的問題，最優(yōu)分組數(shù)也不同。（3）由于上述兩個(gè)問題的存在，使得在一個(gè)種群中，將分組數(shù)直接作為變量進(jìn)行優(yōu)化時(shí)，由于單元數(shù)少的染色體存活的概率較大，使得算法一般會(huì)陷入局部最優(yōu)解，即出現(xiàn)局部收斂的現(xiàn)象。

因此，在利于遺傳算法在進(jìn)行單元構(gòu)建時(shí)，三個(gè)問題需要被考慮進(jìn)來：（1）找到所求問題中最合適的分組數(shù);（2）保證分組數(shù)多的染色體不會(huì)因?yàn)楹戏ㄐ砸蟾叨蔀榱觿?shì)群體。（3）不同的分組數(shù)染色體進(jìn)行遺傳操作時(shí)，既要在一定程度上進(jìn)行交流又要保持一定的獨(dú)立性。為此，本文引用粗粒度并行遺傳算法，使同一分組數(shù)的染色體在同一子種群中，各子種群在獨(dú)立進(jìn)化的同時(shí)，保持一定程度的交流。

2.單元構(gòu)建的基本概念和問題描述

2-1（a）?初始關(guān)聯(lián)矩陣???????????2-1（b）?對(duì)角矩陣

圖2-1?單元構(gòu)建實(shí)例

CFP問題的求解可描述為：對(duì)關(guān)聯(lián)矩陣進(jìn)行行變換和列變化，使之盡可能成為一個(gè)對(duì)角塊矩陣，在該對(duì)角矩陣中每一個(gè)“塊”便為一個(gè)單元，圖2-1（b）為圖2-1（a）的一個(gè)變換矩陣，通過變換處理后將車間劃分為3個(gè)單元。

CFP問題的優(yōu)化目標(biāo)為：最小化零件在單元間移動(dòng)所帶來的花費(fèi)，并最大化單元內(nèi)的設(shè)備利用率，即最小化對(duì)角塊中元素0與對(duì)角塊外元素1的數(shù)量。目標(biāo)函數(shù)為Kumar和Chandrasekharan提出了Grouping?efficac