基于多周期多品種多目標的生產分布式布局遺傳算法研究

李道國，徐益標

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

基于多周期多品種多目標的生產分布式布局遺傳算法研究

李道國1，徐益標2

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

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

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

一、引言

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

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

圖1 布局對比圖

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

二、問題描述及模型構建

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

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

（一）以距離最短為目標的布局模型

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

圖2 車間設備布圖

圖3 加工能力1的分布圖

表1 機器加工能力表

表1是機器與加工能力的對應表，圖2是車間布局圖，左上角位置的數字表示位置編號，中間的數字表示機器編號。圖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。因此模型的目標函數設定為：

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

（二）以成本為目標函數的布局模型

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

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

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

（三）標準化處理

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

最終目標函數模型為：

三、模型求解

本文選擇使用遺傳算法來對分布式布局問題進行求解，通過合理的參數設置更好的求得滿意的解。基本步驟如下：

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

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

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

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

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

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

圖4 交叉過程示意圖

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

四、實例分析

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

表2 生產信息表

表3 機器能力對應表

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

表4 不同方法的比較

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

五、結束語

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

[1]鎖小紅，劉戰(zhàn)強，2007.制造系統(tǒng)設備布局的建模理論與求解方法[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，Florida，USA，pp.1-13.

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

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

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

F273

A

1004-2768（2017）11-0115-04

2017-09-05

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

M 校對：R）