一種求解多品種小批量單元?jiǎng)澐值牟脊萨B算法

何 星 ，張利平 ，唐秋華 ，張子凱

（1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081；2.武漢科技大學(xué)機(jī)械傳動與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081；3.生產(chǎn)系統(tǒng)工程研究所，武漢科技大學(xué)，湖北 武漢 430081）

1 引言

目前市場需求正發(fā)生重大轉(zhuǎn)變，個(gè)性化產(chǎn)品定制已是大勢所趨，傳統(tǒng)流水線式生產(chǎn)已經(jīng)不能滿足多品種、小批量的定制要求，制造企業(yè)也正面臨巨大挑戰(zhàn)[1]。與此同時(shí)，制造單元的優(yōu)勢得到肯定，將制造單元與企業(yè)緊密結(jié)合，制定出合理的制造單元，從而使企業(yè)獲得更大的生產(chǎn)效益。

制造單元內(nèi)采用傳送帶運(yùn)輸物料，單元間則使用AGV 小車。采用這種制造單元的方式可以在很大程度上縮減物料運(yùn)輸時(shí)間，防止運(yùn)輸過程中AGV 小車混亂[2]。在單元內(nèi)加工設(shè)備一般呈L 或U 型分布，方便一個(gè)員工同時(shí)操控多臺加工設(shè)備，減少人力成本[3]。制造單元的高柔性、高效率和低投入等特點(diǎn)為為制造企業(yè)適應(yīng)新的市場環(huán)境保駕護(hù)航[4]。

現(xiàn)階段在制造單元?jiǎng)澐謫栴}上的研究主要集中在兩個(gè)方面，一個(gè)是數(shù)學(xué)規(guī)劃方面，另一個(gè)是智能計(jì)算方面。文獻(xiàn)[5]采用改進(jìn)的聚類-遺傳算法聯(lián)合仿真建模分析的方法進(jìn)行研究；文獻(xiàn)[6]采用離散仿真和分支定界相結(jié)合的方法對AGV 調(diào)度系統(tǒng)進(jìn)行研究。然而，隨著智能制造的日益普及，產(chǎn)品類型增多、批量減少，快速精準(zhǔn)的制造單元?jiǎng)澐值南嚓P(guān)研究還不夠充分，需要進(jìn)一步深入研究。

布谷鳥算法在2009 年被劍橋大學(xué)的文獻(xiàn)[7]提出，是一種源于布谷鳥育雛方式的進(jìn)化算法。現(xiàn)階段，已在一些生產(chǎn)調(diào)度問題中應(yīng)用該算法，并取得了不錯(cuò)的結(jié)果，因此，結(jié)合布谷鳥算法的簡單、高效和靈活性，針對多品種小批量環(huán)境下的制造單元?jiǎng)澐謫栴}，采用動態(tài)發(fā)現(xiàn)概率和初始化規(guī)則篩選機(jī)制的改進(jìn)布谷鳥算法，綜合考慮制造單元?jiǎng)澐謫栴}的路徑優(yōu)化與均衡性，實(shí)現(xiàn)了制造單元?jiǎng)澐值目焖倬珳?zhǔn)。

2 問題描述及數(shù)學(xué)建模

研究制造單元系統(tǒng)，如圖1 所示。原料堆放區(qū)的零件按照加工順序運(yùn)用AGV 小車送到相應(yīng)的制造單元加工，制造單元內(nèi)運(yùn)輸采用環(huán)形傳送帶，當(dāng)傳送帶上容量達(dá)到飽和時(shí)則將待加工零件放在緩沖區(qū)儲存。當(dāng)零件某制造單元中完成相應(yīng)工序后，其緊后工序在其它制造單元，則制造單元間采用AGV 小車運(yùn)輸，以此類推，直到所有零件加工完成后運(yùn)到指定區(qū)域。

圖1 車間布局Fig.1 Workshop Layout

該問題可以描述如下：車間有P 種類型產(chǎn)品i=1，2，…，P，每種零件加工工藝路徑不同，零件i 有Ni道工序，車間的M 臺加工機(jī)器按照某種特定指標(biāo)被劃分成C 個(gè)制造單元，制造單元間采用AGV 小車進(jìn)行運(yùn)輸，單元內(nèi)采用環(huán)形傳送帶運(yùn)輸，以所有零件加工過程的跨單元總次數(shù)最小為目標(biāo)，以期獲得最佳的制造單元?jiǎng)澐址绞剑瑥亩ＷC零件加工過程中運(yùn)輸時(shí)間最小化及設(shè)備利用率最大化，減少零件在設(shè)備間的無效移動，提高生產(chǎn)效率。鑒于車間制造單元系統(tǒng)的復(fù)雜性，作如下假設(shè)：

（1）加工零件的種類、工序及每道工序加工時(shí)間已知；

（2）緩沖區(qū)和堆放區(qū)容量無限；

（3）AGV 小車的數(shù)量已知且按照零件加工工序進(jìn)行配送；

（4）每輛AGV 小車每次只運(yùn)送一種零件且不發(fā)生沖突。

式中：i— 第 i 個(gè)加工零件，i=1，2，…，P；n— 零件 i 的第 n 道工序，n=1，2，…，Ni；j— 第 j 臺機(jī)器，j=1，2，…，M；k— 第 k 個(gè)制造單元，k=1，2，…，C；Rij—（0～1）變量，若零件 i 需要在機(jī)器 j上加工則為 1，反之為 0；Xinj—（0～1）變量，若零件 i 的第 n道工序在機(jī)器 j 上加工則為 1，反之為 0；Yjk—（0～1）變量，若機(jī)器j 被分配到單元k 內(nèi)則為1，反之為0；Z—所有零件加工過程跨單元運(yùn)輸總次數(shù)。

目標(biāo)函數(shù)：所有零件加工過程的跨單元總次數(shù)最小，其公式，如式（1）所示。

約束條件：

其中式（1）表示為目標(biāo)函數(shù)，即所有零件加工過程的跨單元總次數(shù)最小；式（2）表示任一機(jī)器有且僅能被劃分到一個(gè)制造單元內(nèi)；式（3）表示對于任意零件至少在一臺機(jī)器上加工；式（4）表示對于制造單元?jiǎng)澐值膫€(gè)數(shù)必須不少于3 個(gè)；式（5）表示保證制造單元內(nèi)加工機(jī)器數(shù)量平衡，使所有制造單元內(nèi)機(jī)器數(shù)量相差不超過2 臺。

3 改進(jìn)布谷鳥算法

布谷鳥在繁衍過程中方式獨(dú)特，它只下蛋而不孵蛋，通過將蛋下在別的鳥巢中，讓宿主以為是自己的鳥蛋，從而代替布谷鳥來孵化，但這種行為有一定的風(fēng)險(xiǎn)，宿主有一定的概率發(fā)現(xiàn)布谷鳥蛋，如果被發(fā)現(xiàn)，該蛋將被宿主推下鳥巢，或者宿主重新選址建巢[8]。布谷鳥算法的提出源于布谷鳥的特殊巢寄繁育方式，并且該算法已經(jīng)應(yīng)用于解決組合優(yōu)化問題，且具有較好的性能[9]。制造單元?jiǎng)澐謫栴}正是屬于組合優(yōu)化問題，以標(biāo)準(zhǔn)布谷鳥算法為基礎(chǔ)，并對其進(jìn)行改善，提升算法的性能，其偽代碼，如圖2 所示。

圖2 布谷鳥偽代碼Fig.2 Cuckoo Pseudo Code

3.1 編碼與解碼

針對加工機(jī)器與所在制造單元之間的對應(yīng)關(guān)系，每個(gè)鳥巢對應(yīng)一種制造單元?jiǎng)澐址桨福B巢中的每一個(gè)數(shù)字則表示單元的編號，數(shù)字在鳥巢中所處位置表示加工機(jī)器的排列順序，由數(shù)字串所組成的鳥巢則表示各臺機(jī)器所在單元的的劃分方案。以16臺機(jī)器為例，每一方格所在的位置表示加工機(jī)器（1，2，3，…，16）的排列順序，每一個(gè)方格中數(shù)值表示制造單元的編號，數(shù)字‘1，2，3’分別表示制造單元1，制造單元2 和制造單元3，則每個(gè)位置的加工機(jī)器被劃分到對應(yīng)的制造單元內(nèi)，如圖3 所示。例如，第1 個(gè)方格數(shù)字是2，表示機(jī)器1 被劃分到制造單元2 中；第2 個(gè)方格數(shù)字是3，表示機(jī)器2 被劃分到制造單元3 中，以此類推。上述編碼與解碼，將零件、機(jī)器和制造單元緊密聯(lián)系在一起，能簡單方便表征零件所需機(jī)器及機(jī)器所在制造單元。

圖3 鳥巢編碼Fig.3 Nest Code

3.2 初始化鳥巢

根據(jù)上述編碼與解碼，隨機(jī)初始化鳥巢將大概率產(chǎn)生無效鳥巢，該鳥巢無法滿足上述數(shù)學(xué)規(guī)劃模型。例如：111111111122-3312，該鳥巢中制造單元1 的數(shù)量明顯多余其他制造單元，這意味著制造單元內(nèi)的設(shè)備數(shù)量出現(xiàn)嚴(yán)重的不均衡，不符合上述模型的目標(biāo)期望。這類鳥巢被認(rèn)為是無效的。如果初始化過程產(chǎn)生大量該類鳥巢，將會影響最優(yōu)解的尋優(yōu)速度，在后續(xù)鳥巢更新過程中也將耗費(fèi)大量計(jì)算成本用于無效鳥巢的更新，這將對整個(gè)最優(yōu)解質(zhì)量產(chǎn)生不良的影響。因此，采用一種初始化鳥巢篩選機(jī)制，將無效鳥巢過濾掉，使所有初始化的鳥巢都是有效解，提高算法收斂速度。篩選步驟如下：

Step1：隨機(jī)生成鳥巢；

Step2：計(jì)算每個(gè)鳥巢中單元?jiǎng)澐謹(jǐn)?shù)量及每個(gè)單元對應(yīng)的機(jī)器數(shù)量，比較機(jī)器數(shù)量最多和最少兩單元機(jī)器差值；

Step3：判斷 Step2 中的差值是否滿足式（5），若滿足，則該鳥巢被保留，進(jìn)入Step4；反之，重新隨機(jī)產(chǎn)生鳥巢替代原鳥巢，返回Step2；

Step4：當(dāng)鳥巢數(shù)量沒達(dá)到上限N 時(shí)，則返回Step1；當(dāng)鳥巢數(shù)量達(dá)到上限N 時(shí)，結(jié)束。

3.3 鳥巢評估

每個(gè)鳥巢表示制造單元的劃分方法，計(jì)算出所有零件按該單元?jiǎng)澐址椒ㄍ旯ず蟮陌徇\(yùn)總次數(shù)Ni，在每種制造單元?jiǎng)澐址椒ㄖ辛慵枰话徇\(yùn)次數(shù)在總次數(shù)中的比例fi，取倒數(shù)Fi，最后計(jì)算每一個(gè)在整體中所占的權(quán)重wi，公式如下：

通過上述公式可得到權(quán)重wi，即為每個(gè)鳥巢的評估質(zhì)量。將所有鳥巢的評估質(zhì)量進(jìn)行對比，找出質(zhì)量最好的解并保留。

3.4 動態(tài)發(fā)現(xiàn)概率

發(fā)現(xiàn)概率是宿主發(fā)現(xiàn)布谷鳥蛋的概率，一旦被發(fā)現(xiàn)，該巢將直接被舍棄，重新建立新巢。在標(biāo)準(zhǔn)布谷鳥算法中，發(fā)現(xiàn)概率都是固定的，這將導(dǎo)致算法出現(xiàn)早熟等現(xiàn)象。為了提高算法的全局搜索能力，以及算法更新過程中跳出局部最優(yōu)，采用一種基于指數(shù)函數(shù)的動態(tài)發(fā)現(xiàn)概率方法，該方法引入指數(shù)函數(shù)，如式（9）所示。

其中影響發(fā)現(xiàn)概率的因素有兩個(gè)：

（1）迭代次數(shù)v，隨著迭代次數(shù)的增加，發(fā)現(xiàn)概率隨之減小

（2）適應(yīng)度變化權(quán)重w1，通過比較當(dāng)前鳥巢與前一代鳥巢的適應(yīng)度值，求解兩代鳥巢適應(yīng)度的差值，并對每個(gè)鳥巢的差值求和，如式（10）所示。其中f1為當(dāng)代種群鳥巢的適應(yīng)度值，f2為上代鳥巢適應(yīng)度值。

隨著迭代次數(shù)的增大，發(fā)現(xiàn)概率也會隨之變化，若發(fā)現(xiàn)概率的變化使下代鳥巢適應(yīng)度變壞，則會通過適應(yīng)度權(quán)重調(diào)整發(fā)現(xiàn)概率，以此來保證合適的發(fā)現(xiàn)概率，能有效的跳出局部搜索，防止在迭代過程中陷入局部最優(yōu)解。

3.5 鳥巢更新

每次鳥巢更新均會保留當(dāng)前最優(yōu)解，且采用不同的更新方法更新所有當(dāng)前鳥巢。采用一種融合隨機(jī)鍵與局部搜索的鳥巢更新方法，該方法首先產(chǎn)生一組隨機(jī)數(shù)序列，將原編碼順序按隨機(jī)序列進(jìn)行重新排列，這樣可以防止無效解的產(chǎn)生，從而保證更新后解的有效性。

該方法對每個(gè)鳥巢中的相應(yīng)位置的數(shù)字進(jìn)行隨機(jī)調(diào)換，但不改變數(shù)字的個(gè)數(shù)。在該條編碼中，1 的個(gè)數(shù)為6，2 的個(gè)數(shù)為6，3的個(gè)數(shù)為4，在位置選擇上根據(jù)隨機(jī)概率調(diào)換相應(yīng)位置的數(shù)字，更新后數(shù)字1，2，3 的個(gè)數(shù)保持不變，如圖4 所示。

圖4 鳥巢更新Fig.4 Nest Update

這種鳥巢更新方法是一種有效局部搜索機(jī)制，可避免算法陷入局部最優(yōu)。與動態(tài)發(fā)現(xiàn)概率結(jié)合，可保證算法不會因步長太大跳出最優(yōu)解，也不會因步長太小而陷入局部最優(yōu)，從而實(shí)現(xiàn)全局最優(yōu)性與局部有效性。

4 實(shí)驗(yàn)與分析

為驗(yàn)證改進(jìn)布谷鳥算法方案設(shè)計(jì)的有效性與優(yōu)越性，首先，將改進(jìn)算法應(yīng)用到某汽車零配件加工車間中，其次，采用制造單元?jiǎng)澐值臉?biāo)準(zhǔn)案例測試集進(jìn)行算法的驗(yàn)證。改進(jìn)算法的參數(shù)設(shè)置如下：最大迭代次數(shù)Nmax=200，初始鳥巢群體規(guī)模M=100，運(yùn)用Matlab2016a 軟件進(jìn)行編程及迭代運(yùn)算。

4.1 某汽車零配件加工車間生產(chǎn)實(shí)例與結(jié)果分析

本案例源自某汽車零配件加工車間，該車間中共有加工機(jī)器16 臺，編號分別為M1～M16，加工零件類型30 種，編號分別為P1～P30，每個(gè)零件的加工順序及其所用機(jī)器，如表1 所示。

零件從物料區(qū)發(fā)送至第一道工序所在制造單元內(nèi)，再按順序分配到相應(yīng)的加工機(jī)器上，假設(shè)在傳統(tǒng)流水線中，加工機(jī)器間的搬運(yùn)時(shí)間一致且都為4s；在單元制造式生產(chǎn)中，零件在制造單元間的運(yùn)輸時(shí)間均為5s，在制造單元內(nèi)運(yùn)輸時(shí)間為3s。

表1 某汽車零配件加工車間數(shù)據(jù)Tab.1 Auto Parts Processing Workshop Data

針對上述實(shí)例，運(yùn)用改進(jìn)布谷鳥算法獲得最優(yōu)制造單元?jiǎng)澐址桨福倪M(jìn)布谷鳥算法的收斂曲線，如圖5 所示。

圖5 改進(jìn)布谷鳥算法收斂曲線Fig.5 Improved Cuckoo Algorithm Convergence Curve

當(dāng)?shù)?5 代時(shí)輸出最優(yōu)解，鳥巢編碼是［1 1 2 3 2 1 2 2 2 1 3 3 1 1 2 3］，即16 臺機(jī)器被劃分到3 個(gè)制造單元中，制造單元1 的機(jī)器為：M1、M2、M6、M10、M13、M14；制造單元 2 的機(jī)器為：M3、M5、M7、M8、M9、M15；制造單元 3 的機(jī)器為：M4、M11、M12、M16，其單元布局方案，如圖6 所示。綜上所述，所有零件加工過程的跨單元總次數(shù)為45 次，其中，制造單元1 與制造單元2 間AGV 小車搬運(yùn)次數(shù)為18 次，制造單元2 與制造單元3 間AGV 小車搬運(yùn)次數(shù)為9 次，制造單元1 與制造單元3 間搬運(yùn)次數(shù)18 次，所有制造單元的平均設(shè)備負(fù)荷均衡性為86.1%，加工完所有零件的搬運(yùn)時(shí)間是678s；傳統(tǒng)式流水線式生產(chǎn)的搬運(yùn)時(shí)間為1440s。

圖6 制造單元布局圖Fig.6 Manufacturing Unit Layout

對比傳統(tǒng)流水線式生產(chǎn)，制造單元式生產(chǎn)在搬運(yùn)時(shí)間（節(jié)省762s）、設(shè)備負(fù)荷均衡性均具有明顯的優(yōu)勢。這主要?dú)w結(jié)于傳統(tǒng)流水線式生產(chǎn)要求每種類型零件按照固定的路線依次經(jīng)過每臺機(jī)器，不具備柔性；然而，制造單元式生產(chǎn)盡可能將相似工藝的零件所需設(shè)備集中在一個(gè)制造單元，避免在多臺設(shè)備間進(jìn)行無效移動，具有較高的柔性，更適應(yīng)多品種小批量生產(chǎn)方式。

4.2 改進(jìn)布谷鳥算法的性能分析

表2 標(biāo)準(zhǔn)測試案例結(jié)果Tab.2 Standard Test Case Results

為了測試改進(jìn)布谷鳥算法的性能，采用文獻(xiàn)[10]的標(biāo)準(zhǔn)測試案例，分別與啟發(fā)式規(guī)則、遺傳算法、改進(jìn)布谷鳥算法進(jìn)行對比試驗(yàn)。其中，遺傳算法是不考慮篩選機(jī)制的標(biāo)準(zhǔn)遺傳算法，啟發(fā)式規(guī)則是指初始化鳥巢過程中的可行解篩選機(jī)制，在產(chǎn)生符合約束條件的解集中直接獲得最優(yōu)解。實(shí)驗(yàn)結(jié)果，如表2 所示。為了更好分析算法性能，將標(biāo)準(zhǔn)測試案例集劃分為小規(guī)模和大規(guī)模案例。

由表2 可知，10 組案例，每組案例3 種制造單元?jiǎng)澐址绞剑?0 組場景。問題規(guī)模按照零件類型大小分為小規(guī)模和大規(guī)模兩大類。在小規(guī)模15 組標(biāo)準(zhǔn)測試案例中，改進(jìn)布谷鳥算法均獲得了最優(yōu)解，且有6 組場景優(yōu)于另外兩種方法，6 組場景與遺傳算法結(jié)果相同。在大規(guī)模15 組標(biāo)準(zhǔn)測試案例中，改進(jìn)布谷鳥算法均獲得了最優(yōu)解，且其優(yōu)越性明顯優(yōu)于啟發(fā)式規(guī)則和改進(jìn)遺傳算法，其中有9 組場景的搬運(yùn)次數(shù)優(yōu)于另外兩種方法，4 組場景與遺傳算法結(jié)果相同。由此可見，隨著案例測試集的規(guī)模增加，改進(jìn)布谷鳥算法的優(yōu)勢愈加明顯，這表明改進(jìn)布谷鳥算法具有較好的尋優(yōu)能力，尤其在零件類型多樣的復(fù)雜環(huán)境下其優(yōu)勢更加突出。

5 結(jié)論

對標(biāo)準(zhǔn)布谷鳥算法進(jìn)行改進(jìn)，采用動態(tài)發(fā)現(xiàn)概率更新當(dāng)前解集，以及規(guī)則篩選機(jī)制保證解的可行性。采用某汽車零配件加工車間案例和30 組標(biāo)準(zhǔn)測試案例集對改進(jìn)的布谷鳥進(jìn)行驗(yàn)證，在車間案例中，對比傳統(tǒng)流水車間加工完20 種單件零件能有效節(jié)約搬運(yùn)時(shí)間762s，在30 組標(biāo)準(zhǔn)測試案例中，改進(jìn)布谷鳥算法有15 組場景優(yōu)于另外兩種算法，10 組場景與遺傳算法結(jié)果一致。通過實(shí)驗(yàn)證實(shí)了改進(jìn)的布谷鳥算法是一種有效的制造單元?jiǎng)澐址椒ǎ渚哂泻唵巍㈧`活和較強(qiáng)的尋優(yōu)能力，且隨著零件類型規(guī)模的增加，其優(yōu)勢愈加突出。

后續(xù)研究將進(jìn)一步改進(jìn)布谷鳥算法，有望與當(dāng)前智能制造有效結(jié)合，更有效的解決大規(guī)模制造單元?jiǎng)澐謫栴}；其次，生產(chǎn)過程中的不確定，包括零件類型的更改、設(shè)備故障等對制造單元?jiǎng)澐志鶗a(chǎn)生較大影響，后續(xù)研究將考慮這些不確定因素，提出更具有針對性的求解方法。