ＣＭＳ環境下基于智能優化算法的單元間布局問題研究

摘 要：研究了單元制造系統（CMS）設計中單元間布局設計問題，從單元制造系統的實際出發，提出了一種基于割樹（Slicingtree）的單元間布局設計模型。該模型考慮了單元形狀約束、單元I/O點位置優化等諸因素對布局結果的影響。針對基于割樹的描述形式，采用遺傳算法求解，提出了一種新的割樹編碼方案，克服了以往編碼方案易產生非法子串、不能覆蓋整個解空間以及實現困難等缺點。計算結果表明，該算法是有效的、可行的。

關鍵詞：單元間布局；遺傳算法；單元制造系統；布局設計

中圖法分類號：TP391文獻標識碼：A

文章編號：1001-3695(2007)06-0072-03

0 引言

布局規劃合理與否對于單元制造系統（CMS）實施的成敗起著舉足輕重的作用［1］。一般而言，CMS的布局規劃包括以下三個步驟［2］：①單元構建（Cell Formation），即利用成組技術（GT）將待加工零件歸為若干零件族，將加工設備劃分為若干加工單元。②單元內布局（Intracell Layout），即為各個單元合理布置其內加工設備及工作站。③單元間布局（Intercell Layout），即在車間范圍內安排各單元的合理位置。

單元內布局形式通常比較固定，如單行、U型、環型等，一般用QAP模型描述。QAP問題的求解已經被證明是NPhard的。相對而言，單元間布局問題更為復雜，已成為近年來布局設計研究的一大熱點。

本文以單元間布局設計為研究對象，以最短化單元間物流搬運總路徑為優化目標，在前人研究工作的基礎之上，從單元制造系統的實際問題出發，提出了一種基于割樹（Slicingtree）的單元間布局模型，并設計了相應的遺傳算法（GA）進行求解。

1 問題描述

單元間布局設計通常在單元內設備布局完成之后進行［1］。不同于傳統的設施布局，此時各個單元的占地面積和形狀基本確定，最適合放置物料裝卸站點（I/O點）的邊也可以確定。合理的單元間布局設計必須考慮所有這些約束。在本文中，每個單元用一個矩形描述。該矩形除了具有一定的面積外，還限制其長寬比只能在一定范圍內變化，從而約束了單元的形狀。為了確定各單元在布局平面上的相對位置，采用割樹模型［3］描述如下：首先隨機地將待布置單元集A分成兩個子集B、C（B∪C=A，B∩C=）；然后隨機選取一種分割方式（水平或垂直）切割給定的布局平面，使切割后新產生的兩個矩形面積分別對應于單元集B的面積與單元集C的面積和。對所有新產生的單元子集重復這一過程直至所有單元子集中均僅含一個單元。最終所得的分割結果即描述了目標布局平面上各單元的位置和形狀信息，如圖1所示。由于分割結果可以等價地用一棵二叉樹加以表示，因而稱該表達方式為割樹。樹的葉節點為各單元編號；內節點或者為符號“H”（表示水平分割方式）或者為“V”（表示垂直分割方式）。割樹也可等價地描述為一個字符串。對于圖1 所示的例子，三種可行的字符串為

在單元制造系統中，由于單元之間的物流在各單元的I/O點之間進行，因而各單元I/O點位置的選取對最終搬運效率有很大的影響。本文假定每個單元僅有一個I/O點，其可能的位置為單元四條邊界的中點，則每個單元的I/O點位置可以用一個Bool變量對（u，v）描述如下：

2 算法描述

遺傳算法是一種基于生物自然選擇與遺傳機理的并行隨機搜索算法，在組合優化問題的求解中得到廣泛應用。遺傳算法的成功實施需要精心設計編碼、選擇、交叉、變異四個重要環節。為了對割樹進行編碼，文獻[3，6]采用基于逆序字符串的編碼方式，但這導致遺傳算子設計困難，算法只能搜索到解空間的真子集，從而可能使潛在的更優解被忽略。為了擴大搜索范圍，文獻[4]改用一種基于Gambler’s Ruin法則的編碼方案，但這種編碼方案無法避免遺傳操作產生非法子串。為解決此問題，文獻[5]提出一種同是基于Gambler’s Ruin法則的二維編碼方案，但該方案實現起來過于復雜。為了避免上述問題，本文提出一種基于順序字符串的編碼方案，并設計了相應的遺傳算子，允許搜索覆蓋整個問題解空間，且實現起來簡單易行。

2.1 編碼

一個染色體包含四個部分：前三部分可還原成等價于一棵割樹的順序字符串，后一部分則為各單元的I/O點位置變量對(u，v)。例如，對于圖1所示實例，染色體的前三部分為1234561001031245。第一部分123456為單元編號序列；第二部分10010中的1和0分別對應切割方式V和H；第三部分31245中的每個數字指示了順序字符串中括號對的確切位置。從一個給定的染色體編碼（前三個部分）還原出對應的順序字符串的過程如圖2所示。

由于各單元的I/O點位置變量對(u，v)為Bool型變量，其編碼較簡單，直接用一個長度為2N的二進制串即可描述。

2.2 交叉

根據上述染色體的結構特點，為保證交叉操作不產生非法子串，分別對染色體的不同部分采取不同交叉操作算子。染色體的第二部分與第四部分同為二進制串，故傳統的單點交叉算子即可適用。而第一、三部分均為自然數排列，其交叉操作設計為：從父串1中按相對適應值大小隨機選取一定數量的元素（基因），插入到子串的相同位置，子串中缺失的元素按其在父串2中出現的先后順序依次填充，如圖3所示。

2.3 變異

變異操作主要用于維持種群多樣性，避免算法早熟。對于染色體的第二、四部分，變異操作設計為隨機選取其中的某位并修改為其相反值（0變1，1變0）。第一和第三部分的變異操作設計為從父串中隨機選取兩個基因，改變其相互位置，并保持其余基因不變，如圖4所示。

2.4 懲罰函數

3 計算實例

為檢驗上述模型及求解方案的有效性，本文用C++語言在Pentium 1.7 GHz平臺上實現了該算法，并設計了單元數n=9、15、20、30等一系列數值實驗。由于篇幅所限，僅給出n=30的實驗結果。表1給出了必要的幾何數據，物流矩陣數據則來源于文獻[7]。算法參數選擇：種群數=300，進化代數=800，交叉率=0.6，變異率=0.15。圖5給出了算法運行得到的最優結果，運行時間39.7 s，目標函數值=24 974.4。實驗結果表明，本文所提出的模型及算法是有效的。

4 結束語

與以往文獻相比，本文編碼方案易于設計遺傳算子，并保證遺傳操作不產生非法子串，且使進化搜索可以覆蓋整個解空間。實驗結果表明，該模型及算法是有效的。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。