周正一

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

關鍵詞：單元制造?單元構建??遺傳算法?成組效率

1.引言

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

因此，在利于遺傳算法在進行單元構建時，三個問題需要被考慮進來：（1）找到所求問題中最合適的分組數;（2）保證分組數多的染色體不會因為合法性要求高而成為劣勢群體。（3）不同的分組數染色體進行遺傳操作時，既要在一定程度上進行交流又要保持一定的獨立性。為此，本文引用粗粒度并行遺傳算法，使同一分組數的染色體在同一子種群中，各子種群在獨立進化的同時，保持一定程度的交流。

2.單元構建的基本概念和問題描述

2-1（a）?初始關聯矩陣???????????2-1（b）?對角矩陣

圖2-1?單元構建實例

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

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