基于單點(diǎn)變異算法的單元分組問(wèn)題的研究

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

(1.浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023;2.浙江工業(yè)大學(xué) 浙江省技術(shù)創(chuàng)新與企業(yè)國(guó)際化研究中心，浙江 杭州 310023)

?

基于單點(diǎn)變異算法的單元分組問(wèn)題的研究

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

(1.浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院，浙江 杭州 310023;2.浙江工業(yè)大學(xué) 浙江省技術(shù)創(chuàng)新與企業(yè)國(guó)際化研究中心，浙江 杭州 310023)

摘要：針對(duì)單元制造中單元構(gòu)建問(wèn)題所涉及到的單元分組數(shù)問(wèn)題，結(jié)合零件—設(shè)備關(guān)聯(lián)矩陣的特點(diǎn)，提出一種劃分單元數(shù)的新穎算法.以直接聚類算法(DCA)的計(jì)算結(jié)果為基礎(chǔ)，根據(jù)4種不同的擴(kuò)張路徑形成決策序列.對(duì)決策序列進(jìn)行單點(diǎn)變異，利用單元成組效率評(píng)價(jià)指標(biāo)對(duì)決策序列進(jìn)行評(píng)價(jià).算例結(jié)果表明：對(duì)于復(fù)雜的初始關(guān)聯(lián)矩陣,所提算法可以提高單元?jiǎng)澐值某山M效率，得到較滿意的結(jié)果.

關(guān)鍵詞：?jiǎn)卧圃煜到y(tǒng)；直接聚類算法；單元分組數(shù)；單元構(gòu)建

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

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

1單元構(gòu)建問(wèn)題描述與直接聚類算法(DCA)

1.1問(wèn)題描述

單元構(gòu)建主要是通過(guò)對(duì)零件進(jìn)行工藝分析，將所加工零件和機(jī)器設(shè)備進(jìn)行分組，從而形成特定的零件簇和設(shè)備組，構(gòu)成一個(gè)獨(dú)立的制造單元.在形成制造單元的過(guò)程中，某些零件需要進(jìn)行跨單元加工，這導(dǎo)致生產(chǎn)單元不能獨(dú)立進(jìn)行管理.因此，合理進(jìn)行單元?jiǎng)澐譁p少跨單元件的數(shù)量成為單元構(gòu)建問(wèn)題最重要的目標(biāo)函數(shù)之一.而單元分組數(shù)作為單元構(gòu)建問(wèn)題的重要參數(shù)之一，如何進(jìn)行優(yōu)化以獲取最優(yōu)單元分組數(shù)至今尚沒(méi)有一致性的方法.

1.2直接聚類算法(DCA)

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

表1　零件—設(shè)備關(guān)聯(lián)矩陣

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

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

步驟2列移動(dòng).將第一行有元素“1”的各列移到矩陣的左邊，對(duì)剩余各行重復(fù)上述過(guò)程，直到不能再移動(dòng).

步驟3行移動(dòng).將第一列有元素“1”的各行向上移動(dòng)，盡可能組成由“1”組成的集中塊.對(duì)剩余各列重復(fù)上述過(guò)程.

表2　行和列調(diào)整后的矩陣

在表2所形成的對(duì)角矩陣塊的基礎(chǔ)上，制造企業(yè)可以根據(jù)自身實(shí)際情況自由組合，將設(shè)備和零件進(jìn)行不同劃分，從而形成多種目標(biāo)效果不同的制造單元，如圖1所示.

圖1　三種不同的單元?jiǎng)澐址绞紽ig.1　Three different ways of cell division

24種擴(kuò)張路徑與評(píng)價(jià)指標(biāo)

2.14種擴(kuò)張路徑

通過(guò)對(duì)圖1中不同的單元?jiǎng)澐址绞降姆治?，結(jié)合矩陣自身的特點(diǎn)，可以將矩陣中的每一個(gè)坐標(biāo)點(diǎn)看作是一個(gè)決策點(diǎn)，每個(gè)決策點(diǎn)可以有4種選擇路徑，分別是不擴(kuò)張、向右擴(kuò)張、向下擴(kuò)張和向斜下擴(kuò)張.不同制造單元的劃分主要由這4種不同的擴(kuò)張路徑形成.針對(duì)這4種路徑，可以采用0～3之間的整數(shù)進(jìn)行表示，如圖2所示.

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

根據(jù)圖2中4種不同的擴(kuò)張路徑，隨機(jī)產(chǎn)生0～3之間的隨機(jī)數(shù).根據(jù)該隨機(jī)數(shù)將不同的設(shè)備和零件進(jìn)行分組，形成制造單元.一個(gè)制造單元中含有元素“1”的個(gè)數(shù)越多，該單元的成組效率越高，說(shuō)明在該單元中可以加工更多的零件，從而能夠提高設(shè)備的利用率.筆者采用單元密度來(lái)評(píng)價(jià)在形成制造單元前后，單元中元素“1”在整個(gè)單元中所占比例的變化率.單元密度可表示為

(1)

式中：N1為制造單元中元素“1”的數(shù)量；c為當(dāng)前的制造單元；N0為制造單元中元素“0”的數(shù)量.

2.2評(píng)價(jià)指標(biāo)

目前，評(píng)價(jià)指標(biāo)主要是使用設(shè)備—零件關(guān)聯(lián)矩陣中的異常零件(該零件未分配到單元中，需要跨單元加工)和每個(gè)制造單元中元素“0”所占的比率對(duì)單元成組的效率進(jìn)行評(píng)價(jià).采用Kumar和Chandrasekharan提出的單元分組效率指標(biāo)作為目標(biāo)函數(shù).該評(píng)價(jià)指標(biāo)對(duì)制造單元中元素“0”的數(shù)量的變化非常敏感.目標(biāo)函數(shù)表示為

(2)

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

3基于DCA的單點(diǎn)變異算法步驟

隨著問(wèn)題規(guī)模的擴(kuò)大，很難根據(jù)已有的知識(shí)給出準(zhǔn)確的單元分組數(shù).因此，筆者提出來(lái)一種新穎的啟發(fā)式算法，它能夠有效的進(jìn)行單元?jiǎng)澐?，從而使異常零件的?shù)量最少.其具體的算法步驟如下：

步驟1根據(jù)DCA算法的求解結(jié)果，以矩陣的左上角第一個(gè)點(diǎn)為起始點(diǎn)，并且將該點(diǎn)作為決策點(diǎn)，記錄該點(diǎn)的坐標(biāo).

步驟2根據(jù)4種不同的選擇策略，在每一個(gè)決策點(diǎn)隨機(jī)產(chǎn)生0～3之間的隨機(jī)數(shù)，然后進(jìn)行判斷.

1) 如果隨機(jī)數(shù)為0，則形成一個(gè)單元，記錄該單元的坐標(biāo)，同時(shí)將決策點(diǎn)的橫縱坐標(biāo)各移動(dòng)1個(gè)單位，若移動(dòng)后的坐標(biāo)沒(méi)有越界，則將其作為新的決策點(diǎn).否則執(zhí)行步驟3.

2) 如果隨機(jī)數(shù)是1，將決策點(diǎn)的縱坐標(biāo)向右移動(dòng)一位，如果新坐標(biāo)越界，則執(zhí)行步驟3，否則判斷新坐標(biāo)位置的值是否是元素“1”，如果是元素“1”，則將該坐標(biāo)點(diǎn)對(duì)應(yīng)的設(shè)備和零件劃入單元中，以該新坐標(biāo)為新決策點(diǎn)；如果是元素“0”，判斷該列是否存在其他非零元素，并且執(zhí)行5).

3) 如果隨機(jī)數(shù)是2，將決策點(diǎn)的橫坐標(biāo)向下移動(dòng)一位，如果新坐標(biāo)越界，則執(zhí)行步驟3，否則判斷新坐標(biāo)位置的值是否是元素“1”，如果是元素“1”，則將該坐標(biāo)點(diǎn)對(duì)應(yīng)的設(shè)備和零件劃入單元中，以該新坐標(biāo)為新決策點(diǎn)；如果是元素“0”，判斷該行是否存在其他非零元素，并且執(zhí)行5).

4) 如果隨機(jī)數(shù)是3，將決策點(diǎn)的行列坐標(biāo)各移動(dòng)一位，如果新坐標(biāo)越界，則執(zhí)行步驟3，否則判斷新坐標(biāo)位置的值是否是元素“1”，如果是元素“1”，則將該坐標(biāo)點(diǎn)對(duì)應(yīng)的設(shè)備和零件劃入單元中，以該新坐標(biāo)為新決策點(diǎn)；如果是元素“0”，判斷該行或該列是否存在其他非零元素，執(zhí)行5).

5) 若存在非零元素，則計(jì)算將該非零元素處對(duì)應(yīng)的設(shè)備和零件劃入單元前后的單元密度，同時(shí)產(chǎn)生一個(gè)0～1之間的隨機(jī)數(shù)，如果劃入前的單元密度大于劃入后的單元密度，并且隨機(jī)數(shù)大于0.5，則將該非零元素處對(duì)應(yīng)的設(shè)備和零件劃入單元，將決策序列隨機(jī)數(shù)變?yōu)?，形成新的制造單元.否則，不將該非零元素劃入單元中，決策點(diǎn)依舊是移動(dòng)前的坐標(biāo)值，然后執(zhí)行步驟4.

步驟3將矩陣中剩余的行和列劃入該單元中，將決策序列隨機(jī)數(shù)變?yōu)?，從而形成一個(gè)新的制造單元.

步驟4對(duì)以上步驟不斷迭代，產(chǎn)生一組決策序列.該序列中的每個(gè)值代表決策點(diǎn)所產(chǎn)生的0～3之間的隨機(jī)值.

步驟5對(duì)產(chǎn)生的決策序列進(jìn)行變異操作.在決策序列值的個(gè)數(shù)范圍內(nèi)產(chǎn)生隨機(jī)數(shù)，該隨機(jī)數(shù)決定決策序列中發(fā)生變異的決策點(diǎn)，該點(diǎn)的變異操作會(huì)導(dǎo)致后續(xù)的隨機(jī)值發(fā)生變化.

步驟6比較變異前后目標(biāo)函數(shù)值的大小，保留目標(biāo)函數(shù)值較大的序列.在最終保留的決策序列中，選擇目標(biāo)函數(shù)值最大的決策序列作為最終的單元?jiǎng)澐值囊罁?jù).

4數(shù)值算例

為檢驗(yàn)本算法的有效性，利用Matlab軟件隨機(jī)產(chǎn)生6種零件和10種設(shè)備組成大小為6×10的零件—設(shè)備關(guān)聯(lián)矩陣，如表3所示.通過(guò)采用筆者提出的算法對(duì)關(guān)聯(lián)矩陣進(jìn)行求解，進(jìn)而獲得單元構(gòu)建中最佳的制造單元數(shù)量.

表3　零件—設(shè)備關(guān)聯(lián)矩陣

利用直接聚類算法(DCA)對(duì)零件—設(shè)備關(guān)聯(lián)矩陣進(jìn)行變換，最終的變換結(jié)果如表4所示.

表4　行和列調(diào)整后的矩陣

由表4可知：根據(jù)DCA算法將相似零件與對(duì)應(yīng)加工機(jī)器設(shè)備聚集在一起，最終形成由元素“1”組成的集中塊.針對(duì)該集中塊，采用筆者所提出的算法，產(chǎn)生10組不同的決策序列，如表5所示，而每一種決策序列都代表一種單元?jiǎng)澐址桨?

表5　單元?jiǎng)澐值臎Q策序列

通過(guò)對(duì)表5的決策序列進(jìn)行分析，可以發(fā)現(xiàn)：在每一次隨機(jī)產(chǎn)生的決策序列中，所組成的序列規(guī)模都是不一致，這也帶來(lái)了單元分組數(shù)之間的差異性，從而對(duì)每一種決策序列進(jìn)行評(píng)價(jià)的目標(biāo)函數(shù)值優(yōu)劣不一.這說(shuō)明了不同的單元?jiǎng)澐植呗躁P(guān)系到單元構(gòu)建實(shí)施成功與否的關(guān)鍵.在第7組的決策序列中，通過(guò)對(duì)決策序列進(jìn)行多點(diǎn)變異，最終得到比較滿意的目標(biāo)函數(shù)值，而單元數(shù)量由原來(lái)的4個(gè)減少為2個(gè).這不僅能提升單元內(nèi)設(shè)備的利用率，而且可以減少企業(yè)布置生產(chǎn)單元的成本.

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

表6單元?jiǎng)澐值臎Q策路徑

Table 6Decision path of unit partition

5結(jié)論

利用直接聚類算法對(duì)零件—設(shè)備關(guān)聯(lián)矩陣進(jìn)行排序，將該排序結(jié)果作為新算法的初始矩陣.根據(jù)矩陣本身的特點(diǎn)，利用4種不同的擴(kuò)張策略得到10組不同的決策序列，對(duì)每一種決策序列采取單點(diǎn)變異，并利用成組效率評(píng)價(jià)指標(biāo)對(duì)每一種決策序列進(jìn)行評(píng)價(jià)，找出其中評(píng)價(jià)指標(biāo)最大的決策序列作為最終單元?jiǎng)澐值牟呗?通過(guò)數(shù)值算例可以看出：對(duì)于復(fù)雜的初始關(guān)聯(lián)矩陣,所提算法可以提高單元?jiǎng)澐值某山M效率，得到較滿意的結(jié)果.

參考文獻(xiàn)：

[1]王曉晴，唐家福，宮俊.基于分散搜索的多目標(biāo)動(dòng)態(tài)單元構(gòu)建方法[J].管理科學(xué)學(xué)報(bào)，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]金晶,馮定忠，金壽松.基于負(fù)荷均衡和物流量控制的制造單元構(gòu)建技術(shù)[J].輕工機(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的固定約束條件下多目標(biāo)車間設(shè)備布局問(wèn)題研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2010,38(4):401-405.

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

[7]范佳靜,馮定忠.基于改進(jìn)遺傳算法的制造單元設(shè)計(jì)研究[J].中國(guó)機(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]陳形豐，魯建廈，李英德,等.離散型制造企業(yè)車間布局緩沖區(qū)面積設(shè)置仿真決策研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2010,38(3):246-256.

[12]王建維.制造單元構(gòu)建的關(guān)鍵技術(shù)研究[D].大連：大連理工大學(xué)，2009.

[13]張傳忠，李祖庚.形成單元制造的組的直接聚類算法[J].成組技術(shù),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.

(責(zé)任編輯：陳石平)

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

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

作者簡(jiǎn)介：韓 毅(1979—)，男，遼寧沈陽(yáng)人，副教授，博士，研究方向?yàn)樯a(chǎn)批量計(jì)劃與調(diào)度、智能優(yōu)化算法與應(yīng)用、供應(yīng)鏈優(yōu)化以及逆向物流等，E-mail:hanyi@zjut.edu.cn.

中圖分類號(hào)：TH163

文獻(xiàn)標(biāo)志碼：A

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