李道國，徐益標(biāo)

（1.杭州電子科技大學(xué) 信息工程學(xué)院；2.杭州電子科技大學(xué) 管理學(xué)院，浙江 杭州 310018）

基于多周期多品種多目標(biāo)的生產(chǎn)分布式布局遺傳算法研究

李道國1，徐益標(biāo)2

（1.杭州電子科技大學(xué) 信息工程學(xué)院；2.杭州電子科技大學(xué) 管理學(xué)院，浙江 杭州 310018）

市場需求逐漸從小品種、大批量向多品種、變批量轉(zhuǎn)變，現(xiàn)有的工藝原則布局以及成組原則布局的柔性不夠，不能適應(yīng)多變的生產(chǎn)需求，針對不足，文章提出以各種機器能力之間距離最小的分布式布局模型和以物料搬運成本最小為目標(biāo)的分布式布局模型，并結(jié)合兩者的特點，對兩個目標(biāo)函數(shù)進(jìn)行標(biāo)準(zhǔn)化處理，構(gòu)建了一個滿足多周期、多變生產(chǎn)需求的多目標(biāo)分布式布局模型。設(shè)計了相應(yīng)的遺傳算法，通過一個示例驗證了模型及算法的可行性。

遺傳算法；分布式布局；多目標(biāo)優(yōu)化

一、引言

現(xiàn)在制造業(yè)市場需求變化快，產(chǎn)品種類多樣化、生命周期短，制造企業(yè)的生產(chǎn)方式逐漸從少品種、大批量向多品種、變批量轉(zhuǎn)變。在這種情況下，傳統(tǒng)適合大批量、多品種的車間布局形式比如：工藝原則布局、產(chǎn)品原則布局等，不能很好的應(yīng)對不斷變化的生產(chǎn)需求[1]。

分布式布局如圖1（b），是由Montreuil等人于1991年提出[2]，通過將原本集群的具有相同功能的機器，戰(zhàn)略性的分布于整個生產(chǎn)車間，從而縮短了不同功能的機器之間的距離，有利于快速高效的構(gòu)造新的制造單元，降低物料處理成本，從而應(yīng)對不斷變化的生產(chǎn)需求。Benjafaar等人研究表明這種分解與分配確實能大大提高在多變生產(chǎn)環(huán)境下車間作業(yè)的工作效率[3]。分布式布局如圖1所示。

圖1 布局對比圖

目前國內(nèi)對于分布式布局的研究不是很多，對于車間分布式布局的研究主要集中在國外。montreuil等人研究了基于機器的分布式布局[4]，baykasoglu提出了基于設(shè)備加工能力的分布式布局[5]，并通過模擬仿真對基于能力的分布式布局方式進(jìn)行驗證，證明了其可行性[6]。但是大部分分布式布局一般都是基于已知的產(chǎn)品種類、工藝以及產(chǎn)量從而確定布局。但是現(xiàn)實情況是未來的需求難以預(yù)測[7]，只考慮當(dāng)前周期的需求則需要不斷重構(gòu)布局以適應(yīng)下一周期的生產(chǎn)需求[8]。本文針對現(xiàn)有研究的不足，以最小化搬運距離以及成本為目標(biāo)，提出了一種基于設(shè)備加工能力的分布式布局的方案，適應(yīng)多個周期不同的生產(chǎn)需求，并與傳統(tǒng)的分布式布局以及每期重構(gòu)布。

二、問題描述及模型構(gòu)建

基于加工能力的分布式布局是將m臺機器分布于車間中，所有機器總計擁有r種加工能力，每一種機器都擁有若干種加工能力，在布局過程中不單單需要考慮機器在車間內(nèi)的分布，而且需要考慮各種加工能力如何分布，產(chǎn)品如何選擇適合的機器來加工，對此本文考慮，以各個不存在加工能力Rj的位置到存在加工能力Rj的距離最小為目標(biāo)，以適應(yīng)多變的生產(chǎn)需求[9]，同時考慮當(dāng)前周期的生產(chǎn)需求，以物流成本最小為目標(biāo)，構(gòu)建一個多目標(biāo)模型，使得多個周期總物流費用最小。

本文研究的問題是各個機器在車間內(nèi)的分布，一般只考慮機器相對位置距離和物料搬運費用，根據(jù)問題本文做出如下假設(shè)：①車間整體空間形狀規(guī)則，為矩形空間，開始點為左上角，結(jié)束點為右下角。②機器設(shè)備的形狀，大小尺寸等進(jìn)行簡化，均考慮成大小相同的矩形。③機器分布于車間，車間規(guī)劃為如圖2所示的樣子，每個機器占據(jù)一個固定的區(qū)域位置。④為了簡化模型，不考慮物料在每一塊區(qū)域內(nèi)部的運輸問題。⑤不考慮物料流通路徑，各個相鄰位置之間的距離設(shè)定為1。

（一）以距離最短為目標(biāo)的布局模型

由于每個周期內(nèi)產(chǎn)品的種類、批量和加工工藝都會發(fā)生變化，不能預(yù)測之后幾個周期的產(chǎn)品需求。所以本文考慮產(chǎn)品生產(chǎn)過程中無論下一工序需要何種加工能力，該加工能力都能在其附近。

圖2 車間設(shè)備布圖

圖3 加工能力1的分布圖

表1 機器加工能力表

表1是機器與加工能力的對應(yīng)表，圖2是車間布局圖，左上角位置的數(shù)字表示位置編號，中間的數(shù)字表示機器編號。圖3表示加工能力1在車間中的分布情況，1表示該位置存在該種加工能力，0表示不存在該種加工能力 ，由圖可知加工能力 1分布于位置 1、2、9、10、11，加工能力不存在的位置為 3、4、5、6、7、8、12。各個不存在能力 1的位置到存在能力1的位置的最小距離即1+1+1+1+1+1+1=7。因此模型的目標(biāo)函數(shù)設(shè)定為：

其中各個符號的意義如下：re_map[i，j]表示加工能力j是否存在于位置i，如果存在則等于1，不存在則等于 0，dik表示位置i到位置k的距離，Sj表示存在加工能力j的位置的集合。

（二）以成本為目標(biāo)函數(shù)的布局模型

以距離為目標(biāo)的布局模型，可以適應(yīng)多變的生產(chǎn)需求，在每個周期的生產(chǎn)過程中都不會產(chǎn)生較高的物流費用，但也不是每個周期中最優(yōu)的布局，因此以當(dāng)前周期的物流成本最小也是本文所考慮的目標(biāo)之一，模型如下：

其中Ωij表示加工能力j是否存在于位置i，如果存在則等于1，不存在則等于0；dik表示位置i到位置k的距離；fijktl表示產(chǎn)品l的加工工藝中是否有從加工能力j到加工能力t的過程，并且該過程是否選擇設(shè)備i以及設(shè)備k，如果是則為該過程的物流量，不是則為0；cl表示產(chǎn)品l的單位物流成本；rj表示表示擁有加工能力j的機器的數(shù)量；L表示表示產(chǎn)品種類數(shù)。

約束（5）和（6）保證了每個機器只能被分配在一個位置上并且每個位置也只能被一個機器占據(jù)，一旦位置數(shù)超過子部門的個數(shù)在保證最優(yōu)的情況下將利用零物流量和零重新布置費用的虛擬部門來解決兩者間數(shù)量上的差異。約束（7）保證產(chǎn)品l在具有加工能力j，t的機器i，k之間的物流量和其總的物流量相等。

（三）標(biāo)準(zhǔn)化處理

因為本文構(gòu)建的目標(biāo)函數(shù)有兩個，屬于多目標(biāo)優(yōu)化問題，求解多目標(biāo)優(yōu)化其實就是求解帕累托最優(yōu)解的問題，根據(jù)實際情況求出一個令人滿意的解，由于兩個目標(biāo)函數(shù)具有不同的量綱，所以需要對其進(jìn)行標(biāo)準(zhǔn)化處理[10]，采用min-max標(biāo)準(zhǔn)化處理，也稱為離差標(biāo)準(zhǔn)化，是對原始數(shù)據(jù)的線性變換，使結(jié)果值映射到[0-1]之間。轉(zhuǎn)換函數(shù)如下：

最終目標(biāo)函數(shù)模型為：

三、模型求解

本文選擇使用遺傳算法來對分布式布局問題進(jìn)行求解，通過合理的參數(shù)設(shè)置更好的求得滿意的解?；静襟E如下：

步驟1：初始化種群，采用隨機生成的方式生成初始種群。

步驟2：染色體編碼，編碼是遺傳算法成功的首要問題，排序問題一般使用符號編碼，對機器進(jìn)行編號，表示如下：[M1，M2，M5，M4，M3]。M1 在 1 位置，M2在 2位置，M5在 3位置，M4在 4 位置，M3在5位置。

步驟3：選擇，本文采用順序選擇的方法，其將選擇概率固定化。首先按適應(yīng)值大小對個體進(jìn)行排序，接著定義最好的個體的選擇概率為q，排序后的第j個個體的選擇概率為：

其中NP為種群個數(shù)，對于最小化問題來說，最好的個體也就是適應(yīng)值最小的個體，目標(biāo)函數(shù)可以直接作為適應(yīng)值進(jìn)行計算，保證了優(yōu)秀個體的選擇概率。

步驟4：染色體交叉，采用部分交叉策略，由于在交叉過程中會產(chǎn)生非法編碼，所以需要化解沖突，具體如圖4所示，染色體A，B交叉之后，染色體A中3，2，0發(fā)生重復(fù)，染色體B中 5，6，7重復(fù)，因此需要將染色體A中未交叉部分中的重復(fù)的基因進(jìn)行替換，分別為3換成7，2換成6，0換成5。

步驟5：變異、變異是為了避免算法早熟，陷入局部最優(yōu)解，本文變異方法為隨機選擇染色體中的一個基因，并且隨機插入到染色體中的某一個位置。

圖4 交叉過程示意圖

步驟6：終止，算法合理的終止條件可以提升算法的性能，本文采用兩個終止條件，一是當(dāng)算法達(dá)到指定的迭代次數(shù)之后終止，二是當(dāng)算法結(jié)果在指定代數(shù)之后未曾優(yōu)化停止算法。

四、實例分析

車間現(xiàn)有24臺機器，整個車間的布局為4*6的結(jié)構(gòu)，已知本周期的需要生產(chǎn)的產(chǎn)品種類，相應(yīng)的工藝路線和各個產(chǎn)品的單位物流成本，如表2所示，以及各個機器設(shè)備所具備的加工能力如表3所示。假定之后四個周期的生產(chǎn)需求隨機生成，并且每個周期的重構(gòu)費用為500。

表2 生產(chǎn)信息表

表3 機器能力對應(yīng)表

為證明本文提出的分布式布局方法的正確性，將本文與傳統(tǒng)的分布式布局的方法（模型1）以及重構(gòu)的分布式（模型2）進(jìn)行比較。通過算法得到的結(jié)果如表4所示。從數(shù)據(jù)中可以得知，以根據(jù)功能之間總的距離最短為目標(biāo)的分布式布局方法與本文的多目標(biāo)方法相比，只是在第一周期的物流費用有明顯差距，其余4個周期的數(shù)據(jù)相差不大，總物流費用傳統(tǒng)分布式模型略高于本文模型。雖然重構(gòu)式布局每個周期的物料搬運成本均低于本文模型，但是每個周期都重構(gòu)而會產(chǎn)生大量的重構(gòu)費用，導(dǎo)致總費用遠(yuǎn)遠(yuǎn)大于本文模型。

表4 不同方法的比較

最終結(jié)果證明將模型1與模型2進(jìn)行合并，形成多目標(biāo)函數(shù)的合理性。模型保留了傳統(tǒng)分布式布局方法應(yīng)對多變的生產(chǎn)需求的能力，使每個周期的物流成本不會因需求的變動而大幅波動，也避免了重構(gòu)布局時產(chǎn)生的大量的重構(gòu)費用。

五、結(jié)束語

本文針對生產(chǎn)需求變化過快導(dǎo)致的生產(chǎn)車間布局不能及時響應(yīng)的問題，實現(xiàn)了以機器各能力之間距離最短以及物流成本最小化為目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問題的遺傳算法，希望為多品種、變批量的制造企業(yè)的車間布局提供一種解決方案。研究還有許多不足之處，例如只考慮了各個機器之間的相對位置關(guān)系，而忽略了具體車間以及機器的尺寸，以及未充分考慮機器設(shè)備之間的相互關(guān)系等，這都有待于進(jìn)一步研究。

[1]鎖小紅，劉戰(zhàn)強，2007.制造系統(tǒng)設(shè)備布局的建模理論與求解方法[J].計算機集成制造系統(tǒng)（10）：1941-1951.

[2]Montreuil B，Venkatadri U，Lefranc-ois P.Holographic layout of manufacturing systems.In：19th IIE systems integration conference，October（1991）.

[3]Benjafaar S.，Sheikhzadeh M.Design of flexible plant layouts.IIE Transactions，2000，32：309-322.

[4]Montreuil B.，Venkatadri U.，Lefrancois P.（1991）Holographic layout of manufacturing systems.In 19th IIE Systems Integration Conference，Orlando，F(xiàn)lorida，USA，pp.1-13.

[7]李聰波，馬輝杰，李玲玲，等，2015.面向不確定性的再制造車間設(shè)施動態(tài)布局方法[J].計算機集成制造系統(tǒng)（11）：2901-2011.

[8]陶俐言，聶清，王志鋒，等，2014.面向變批量生產(chǎn)的制造單元構(gòu)建方法[J].計算機集成制造系統(tǒng)（10）：2411-2418.

[10]余世根，魯建廈，2010.基于GA的固定約束條件下多目標(biāo)車間設(shè)備布局問題研究[J].浙江工業(yè)大學(xué)學(xué)報（4）：401-405.

F273

A

1004-2768（2017）11-0115-04

2017-09-05

李道國（1965-），男，浙江杭州人，杭州電子科技大學(xué)信息工程學(xué)院教授，研究方向：電子商務(wù)、模式識別與人工智能；徐益標(biāo)（1992-），男，浙江紹興人，杭州電子科技大學(xué)管理學(xué)院碩士研究生，研究方向:生產(chǎn)計劃與控制。徐益標(biāo)為通訊作者。

M 校對：R）