基于單點變異算法的單元分組問題的研究

韓　毅,王德志,林華珍,顧　冰

(1.浙江工業大學 經貿管理學院，浙江 杭州 310023;2.浙江工業大學 浙江省技術創新與企業國際化研究中心，浙江 杭州 310023)

?

基于單點變異算法的單元分組問題的研究

韓毅1,2,王德志1,林華珍1,顧冰1

(1.浙江工業大學 經貿管理學院，浙江 杭州 310023;2.浙江工業大學 浙江省技術創新與企業國際化研究中心，浙江 杭州 310023)

摘要：針對單元制造中單元構建問題所涉及到的單元分組數問題，結合零件—設備關聯矩陣的特點，提出一種劃分單元數的新穎算法.以直接聚類算法(DCA)的計算結果為基礎，根據4種不同的擴張路徑形成決策序列.對決策序列進行單點變異，利用單元成組效率評價指標對決策序列進行評價.算例結果表明：對于復雜的初始關聯矩陣,所提算法可以提高單元劃分的成組效率，得到較滿意的結果.

關鍵詞：單元制造系統；直接聚類算法；單元分組數；單元構建

當前，國家發布了《中國制造2025》行動綱領，全面部署推進實施制造強國戰略，力圖打造一批具有國際競爭力的制造業，從而把我國建設成為引領世界制造業發展的制造強國.單元生產是根據加工零件的工藝路線的相似性形成零件簇，從而利用機器設備對零件簇進行生產加工的一種先進生產方式，具有訂單響應時間短、成品庫存少和生產成本低等多方面的優點[1]，從80年代成功運用之后，就受到國內外學者和企業界越來越多的關注與重視.Wang等[2]通過采用分散搜索算法解決了多目標動態單元構建問題；金晶等[3]等以物流量最少和機床負荷均衡為目標，采用遺傳算法驗證了模型的有效性；針對單元制造中異常零件最少與設備利用率最高的問題，Jamal等[4]根據問題的規模，提出了2種不同的解決方案；余世根等[5]利用遺傳算法對多目標情況下具有固定約束條件的制造車間的布局問題進行研究；而馬玉敏等[6]通過對傳統遺傳算法進行改進，提高了算法求解同一問題的效率.范佳靜等[7]等考慮了總搬運成本及機器設備的維修和折舊成本為目標，利用改進的遺傳算法對數學模型進行求解.Rafiei等[8]和Niakan等[9]討論了操作者在單元生產中的作用，以此實現企業利益和社會責任的平衡.

但是以上研究中，針對單元制造中單元構建問題所涉及到的單元分組數，大多數情況都是學者根據經驗判斷事先給定.單獨針對單元分組數的相關研究文獻還比較少.Zahir等[10]根據加工費用和零件搬運距離為目標，以獲得最佳單元數；陳形豐等[11]研究了在多品種少批量下的離散型制造企業車間布局分布問題；王建維[12]利用4個經典的聚類有效性函數作為綜合性能指標，選擇最佳單元分組數，從而避免單一指標做出誤判的情形.張傳忠等[13]等通過對直接聚類算法進行改進，直接對零件—設備關聯矩陣進行操作，從而確定單元分組數.針對單元分組數問題，將在直接聚類算法求解結果的基礎上，根據矩陣自身的特點提出4種不同的擴張路徑，從而形成不同的決策序列，對每一種決策序列進行變異和評價，從而確定最佳單元分組數.

1單元構建問題描述與直接聚類算法(DCA)

1.1問題描述

單元構建主要是通過對零件進行工藝分析，將所加工零件和機器設備進行分組，從而形成特定的零件簇和設備組，構成一個獨立的制造單元.在形成制造單元的過程中，某些零件需要進行跨單元加工，這導致生產單元不能獨立進行管理.因此，合理進行單元劃分減少跨單元件的數量成為單元構建問題最重要的目標函數之一.而單元分組數作為單元構建問題的重要參數之一，如何進行優化以獲取最優單元分組數至今尚沒有一致性的方法.

1.2直接聚類算法(DCA)

基于矩陣的簇聚法是解決制造單元劃分問題中最常用的方法之一.該方法主要利用表1所示的零件—設備關聯矩陣，矩陣中元素“1”表明零件需要相應設備的加工，否則為空格.將零件作為行、設備作為列填入到矩陣中，通過對該初始矩陣按照一定的規則進行行列置換，最終將相似零件和對應加工機器設備聚集在一起，形成一組具有較高密度“1”的對角塊矩陣.其中每一個子矩陣就代表一個制造單元.Chan等[14]提出的直接聚類算法就是將行列交錯移位，在矩陣的左上角形成簇聚組.

表1　零件—設備關聯矩陣

直接聚類算法根據對初始矩陣的零件行和設備列進行置換，最終形成由元素“1”組成的集中塊，如表2所示.其具體算法步驟如下：

步驟1對行、列進行排序.將初始矩陣的每行、每列的元素“1”相加.其中以行總和遞減的方式從上到下排列，各列以列總和遞增的方式從左到右排列.如果行或列總和相同，再以零件號或設備號遞減方式排列.

步驟2列移動.將第一行有元素“1”的各列移到矩陣的左邊，對剩余各行重復上述過程，直到不能再移動.

步驟3行移動.將第一列有元素“1”的各行向上移動，盡可能組成由“1”組成的集中塊.對剩余各列重復上述過程.

表2　行和列調整后的矩陣

在表2所形成的對角矩陣塊的基礎上，制造企業可以根據自身實際情況自由組合，將設備和零件進行不同劃分，從而形成多種目標效果不同的制造單元，如圖1所示.

圖1　三種不同的單元劃分方式Fig.1　Three different ways of cell division

24種擴張路徑與評價指標

2.14種擴張路徑

通過對圖1中不同的單元劃分方式的分析，結合矩陣自身的特點，可以將矩陣中的每一個坐標點看作是一個決策點，每個決策點可以有4種選擇路徑，分別是不擴張、向右擴張、向下擴張和向斜下擴張.不同制造單元的劃分主要由這4種不同的擴張路徑形成.針對這4種路徑，可以采用0～3之間的整數進行表示，如圖2所示.

圖2　4種不同的擴張路徑 Fig.2　Four different expansion path

根據圖2中4種不同的擴張路徑，隨機產生0～3之間的隨機數.根據該隨機數將不同的設備和零件進行分組，形成制造單元.一個制造單元中含有元素“1”的個數越多，該單元的成組效率越高，說明在該單元中可以加工更多的零件，從而能夠提高設備的利用率.筆者采用單元密度來評價在形成制造單元前后，單元中元素“1”在整個單元中所占比例的變化率.單元密度可表示為

(1)

式中：N1為制造單元中元素“1”的數量；c為當前的制造單元；N0為制造單元中元素“0”的數量.

2.2評價指標

目前，評價指標主要是使用設備—零件關聯矩陣中的異常零件(該零件未分配到單元中，需要跨單元加工)和每個制造單元中元素“0”所占的比率對單元成組的效率進行評價.采用Kumar和Chandrasekharan提出的單元分組效率指標作為目標函數.該評價指標對制造單元中元素“0”的數量的變化非常敏感.目標函數表示為

(2)

式中：e為設備—零件關聯矩陣中元素“1”的總數量；e1為制造單元外的元素“1”(異常零件)的數量；e0為制造單元中元素“0”的數量；ψ為異常零件與矩陣中元素“1”的總數量的比率；φ為制造單元中元素“0”的數量與矩陣中元素“1”的總數量的比率.

3基于DCA的單點變異算法步驟

隨著問題規模的擴大，很難根據已有的知識給出準確的單元分組數.因此，筆者提出來一種新穎的啟發式算法，它能夠有效的進行單元劃分，從而使異常零件的數量最少.其具體的算法步驟如下：

步驟1根據DCA算法的求解結果，以矩陣的左上角第一個點為起始點，并且將該點作為決策點，記錄該點的坐標.

步驟2根據4種不同的選擇策略，在每一個決策點隨機產生0～3之間的隨機數，然后進行判斷.

1) 如果隨機數為0，則形成一個單元，記錄該單元的坐標，同時將決策點的橫縱坐標各移動1個單位，若移動后的坐標沒有越界，則將其作為新的決策點.否則執行步驟3.

2) 如果隨機數是1，將決策點的縱坐標向右移動一位，如果新坐標越界，則執行步驟3，否則判斷新坐標位置的值是否是元素“1”，如果是元素“1”，則將該坐標點對應的設備和零件劃入單元中，以該新坐標為新決策點；如果是元素“0”，判斷該列是否存在其他非零元素，并且執行5).

3) 如果隨機數是2，將決策點的橫坐標向下移動一位，如果新坐標越界，則執行步驟3，否則判斷新坐標位置的值是否是元素“1”，如果是元素“1”，則將該坐標點對應的設備和零件劃入單元中，以該新坐標為新決策點；如果是元素“0”，判斷該行是否存在其他非零元素，并且執行5).

4) 如果隨機數是3，將決策點的行列坐標各移動一位，如果新坐標越界，則執行步驟3，否則判斷新坐標位置的值是否是元素“1”，如果是元素“1”，則將該坐標點對應的設備和零件劃入單元中，以該新坐標為新決策點；如果是元素“0”，判斷該行或該列是否存在其他非零元素，執行5).

5) 若存在非零元素，則計算將該非零元素處對應的設備和零件劃入單元前后的單元密度，同時產生一個0～1之間的隨機數，如果劃入前的單元密度大于劃入后的單元密度，并且隨機數大于0.5，則將該非零元素處對應的設備和零件劃入單元，將決策序列隨機數變為0，形成新的制造單元.否則，不將該非零元素劃入單元中，決策點依舊是移動前的坐標值，然后執行步驟4.

步驟3將矩陣中剩余的行和列劃入該單元中，將決策序列隨機數變為0，從而形成一個新的制造單元.

步驟4對以上步驟不斷迭代，產生一組決策序列.該序列中的每個值代表決策點所產生的0～3之間的隨機值.

步驟5對產生的決策序列進行變異操作.在決策序列值的個數范圍內產生隨機數，該隨機數決定決策序列中發生變異的決策點，該點的變異操作會導致后續的隨機值發生變化.

步驟6比較變異前后目標函數值的大小，保留目標函數值較大的序列.在最終保留的決策序列中，選擇目標函數值最大的決策序列作為最終的單元劃分的依據.

4數值算例

為檢驗本算法的有效性，利用Matlab軟件隨機產生6種零件和10種設備組成大小為6×10的零件—設備關聯矩陣，如表3所示.通過采用筆者提出的算法對關聯矩陣進行求解，進而獲得單元構建中最佳的制造單元數量.

表3　零件—設備關聯矩陣

利用直接聚類算法(DCA)對零件—設備關聯矩陣進行變換，最終的變換結果如表4所示.

表4　行和列調整后的矩陣

由表4可知：根據DCA算法將相似零件與對應加工機器設備聚集在一起，最終形成由元素“1”組成的集中塊.針對該集中塊，采用筆者所提出的算法，產生10組不同的決策序列，如表5所示，而每一種決策序列都代表一種單元劃分方案.

表5　單元劃分的決策序列

通過對表5的決策序列進行分析，可以發現：在每一次隨機產生的決策序列中，所組成的序列規模都是不一致，這也帶來了單元分組數之間的差異性，從而對每一種決策序列進行評價的目標函數值優劣不一.這說明了不同的單元劃分策略關系到單元構建實施成功與否的關鍵.在第7組的決策序列中，通過對決策序列進行多點變異，最終得到比較滿意的目標函數值，而單元數量由原來的4個減少為2個.這不僅能提升單元內設備的利用率，而且可以減少企業布置生產單元的成本.

因此，針對表3隨機產生的零件—設備關聯矩陣，利用所提出的新穎算法，可以確定的決策序列是{1,1,2,3,1,0,2,0,0},產生3個生產單元，分別是單元1由零件{5,4,2}和設備{3,8,9,4,1}共同組成；單元2由零件{1,3}和設備{7}所組成；單元3由零件{6}和設備{2,5,6,10}共同組成.最終的目標函數值是0.540 5.該決策序列的最終決策路徑，如表6所示.

表6單元劃分的決策路徑

Table 6Decision path of unit partition

5結論

利用直接聚類算法對零件—設備關聯矩陣進行排序，將該排序結果作為新算法的初始矩陣.根據矩陣本身的特點，利用4種不同的擴張策略得到10組不同的決策序列，對每一種決策序列采取單點變異，并利用成組效率評價指標對每一種決策序列進行評價，找出其中評價指標最大的決策序列作為最終單元劃分的策略.通過數值算例可以看出：對于復雜的初始關聯矩陣,所提算法可以提高單元劃分的成組效率，得到較滿意的結果.

參考文獻：

[1]王曉晴，唐家福，宮俊.基于分散搜索的多目標動態單元構建方法[J].管理科學學報，2009,12(5):44-52.

[2]WANG Xiaoqing, TANG Jiafu. Optimization of the multi-objective dynamic cell formation problem using a scatter search approach[J]. International journal of advanced manufacturing technology,2009,44(3):318-329.

[3]金晶,馮定忠，金壽松.基于負荷均衡和物流量控制的制造單元構建技術[J].輕工機械,2010,28(1):107-111.

[4]JAMAL A, LEILA H. Minimization of exceptional elements and voids in the cell formation problem using a multi-objective genetic algorithm[J]. Expert systems with applications,2011,38(8):9597-9602.

[5]余世根，魯建廈.基于GA的固定約束條件下多目標車間設備布局問題研究[J].浙江工業大學學報，2010,38(4):401-405.

[6]馬玉敏，陳炳森，張為民.基于多條工藝路線單元構建的遺傳算法[J].現代設計技術，2001,18(1):18-21.

[7]范佳靜,馮定忠.基于改進遺傳算法的制造單元設計研究[J].中國機械工程，2011，22(1):39-43.

[8]RAFIEI H,GHODSI R. A bi-objective mathematical model toward dynamic cell formation considering labor utilization[J].Applied mathematic modeling,2013,37(4):2308-2316.

[9]NIAKAN F, ARMAND B. A Multi-objective mathematical model considering ecomomic and social criteria in dynamic cell formation[J]. Advances in information and communication technology,2014,439:46-53.

[10]ZAHIR A, HAMDI A. A mathematical approach for the formation of manufacturing cells[J]. Computers & industrial engineering,2005,48(1):3-21.

[11]陳形豐，魯建廈，李英德,等.離散型制造企業車間布局緩沖區面積設置仿真決策研究[J].浙江工業大學學報，2010,38(3):246-256.

[12]王建維.制造單元構建的關鍵技術研究[D].大連：大連理工大學，2009.

[13]張傳忠，李祖庚.形成單元制造的組的直接聚類算法[J].成組技術,1985，4(3):35-44.

[14]CHAN H M, MILNER D A. Direct clustering algorithm for group formation in cellular manufacturing[J]. Journal of manufacturing systems,1982,1(1):65-74.

(責任編輯：陳石平)

Research on the cell partition problem based on single point mutation algorithm

HAN Yi1,2, WANG Dezhi1, LIN Huazhen1, GU Bing1

(1.College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China 2.Research Center for Technology Innovation and Enterprise Internationalization, Hangzhou 310023, China)

Abstract:Aiming at cell partition problem in the cellular manufacturing system, a novel algorithm, combining with the characteristics of the parts and equipment association matrix for partitioning cells is presented. During the process of cell formation，the result from the direct clustering algorithm(DCA) is adopted as an initial solution. A decision sequence is then reached according to four different expansion directions. Then, the single point mutation on the decision sequence is carried out，and the efficiency evaluation index of cell formation is used as the objective function to evaluate the algorithm. The results show that the proposed algorithm can improve the efficiency of cell partition and get better satisfactory results for those problems with complicated initial correlation matrix.

Keywords:cellular manufacturing system; direct clustering algorithm; cell number; cell formation

收稿日期：2015-10-08

基金項目：國家自然科學基金資助項目(71301147,71301148,71302051)；教育部人文社科基金資助項目(12YZCZH065)

作者簡介：韓 毅(1979—)，男，遼寧沈陽人，副教授，博士，研究方向為生產批量計劃與調度、智能優化算法與應用、供應鏈優化以及逆向物流等，E-mail:hanyi@zjut.edu.cn.

中圖分類號：TH163

文獻標志碼：A

文章編號：1006-4303(2016)02-0202-05