基于改進模擬植物生長算法的多層可重構設施布局方法

丁祥海

杭州電子科技大學，杭州，310018

?

基于改進模擬植物生長算法的多層可重構設施布局方法

丁祥海

杭州電子科技大學，杭州，310018

在對模擬植物生長算法進行改進的基礎上，建立了一種多層可重構設施布局方法。該方法引入了空間填充曲線來表征布局方案，可以實現任意兩個設施之間的互換，確保設施不被分割；考慮了柔性面積需求、設施形狀約束系數、電梯能力約束等因素，使獲得的方案更加接近實際情況；建立了以物流成本和重構成本為績效評價目標的多層可重構設施布局模型；對模擬植物生長算法進行了改進，在此基礎上設計了多層可重構設施布局尋優(yōu)改善算法，該算法具有設置參數簡單、全局尋優(yōu)、搜索速度較快等特點。最后用算例說明了該方法的有效性。

多層可重構設施布局；改進模擬植物生長算法；電梯能力約束；設施形狀約束系數

0　引言

為了應對因城市化發(fā)展導致土地價格越來越高的現狀，大量工廠向垂直方向拓展，多層設施布局問題(multi-floor facility layout problem,MFFLP)成為設施布局問題的重要方面[1-3]。在城市生產環(huán)境中生產的產品一般是小型化的，其生產設施逐漸輕型化，可移動性增加，重構成本大幅降低；而城市生產越來越面向顧客，定制化、多品種、小批量是其主要的生產方式[4-6]。在重構成本較低和生產數據不確定(包括產品品種和生產數量)程度高的情況下，適合采用可重構設施布局(reconfigurable facilities layout，RFL)。因此，多層可重構設施布局問題(multi-floors reconfigurable facilities layout problem，MF-RFLP)在城市生產環(huán)境中具有廣泛的應用需求，它使得這類企業(yè)的設施布局由較長期的決策變成短期的對市場需求的一種反應[7-8]。Johnson[1]基于CRAFT研究了多層設施布局問題，但沒有考慮電梯的能力，且只有相鄰的設施或者面積相等的設施才能實現互換，設施有可能被分割在不同的樓層； Bozer等[9]解決了不同面積設施互換問題和設施被分割問題，但未考慮設施的重構成本和電梯的能力；Mafsuzaki等[10]考慮了電梯能力，但其目的是解決在生產數據確定情況下電梯的數量和位置的決策問題，而多層可重構設施布局往往是電梯能力和位置已知情況下的垂直物流分配問題；Bernardi等[3]建立的多層設施布局問題模型需要設置大量的參數和約束條件，而且其尋優(yōu)過程是局部的。多層設施布局問題是NP困難的，大量啟發(fā)式算法應用于多層設施布局問題，如模擬退火法[11-12]、遺傳算法[13-14]、禁忌搜索[15]、蛙跳算法[16]、粒子群算法[17]等，其他學者也應用模糊邏輯[18]和專家系統(tǒng)[19]等方法來求解設施布局問題。這些算法通過建立隨機性、正反饋性等機制確保以較大概率收斂到全局的最優(yōu)，但是需要設定一些直接影響收斂性和計算速度的參數，這些參數目前沒有通用的選取法則，針對具體問題需要反復摸索。本文分析了可重構設施布局的流程，引入空間填充曲線，并基于空間曲線對多層設施布局問題進行表達，實現任意設施的兩兩互換；并基于物流和重構成本建立了可重構設施布局的目標函數，基于設施形狀約束和電梯能力建立了問題的約束條件；引入形態(tài)素因子，對模擬植物生長算法進行改善，提高了算法的尋優(yōu)速度，并在此基礎上設計了多層可重構設施布局的算法；最后，通過一個算例說明了模型的有效性。

1　多層可重構設施布局模型

1.1問題描述

可重構設施布局是指已知下一生產周期的數據(產品品種和數量)情況下，在現有布局的基礎上，尋找一種生產績效最佳的布局方案。其過程一般包括產生可選布局方案、評估方案的績效和選擇并實施方案(圖1a)。多層可重構設施布局問題需要同時考慮水平和垂直物流(圖1b)，是一個比單層可重構設施布局更復雜的問題。本文進行以下設定。

(1)車間劃分為面積相等的網格，引入空間填充曲線，保證車間每個網格的連續(xù)性和遍歷性[9]。每一層設定一條空間填充曲線，每層的空間填充曲線可以不同，但每層的單個網格面積相等。

(2)網格分配從空間填充曲線的入口端開始，設施之間不留任何網格，沒有用完的網格數余留在空間填充曲線的出口端。

(6)設施不能被分割。分配給一個設施的所有網格必須在同一條空間填充曲線上，且所有的網格號是連續(xù)的。這個設定保證了設施不會被分割開。設一個設施占有Ai個網格，其網格編號依次為(a，a+1，…，i，j，…，b)，則應滿足:j=i+1,b-a+1=Ai(a,b=0,1,…,N；N為所在樓層可分配的空間曲線的最大網格編號)。

(7)拆卸、搬運和安裝是產生設施重構費用的主要動因。在多層可重構設施布局中，搬運既包括垂直方向的運動，又包括水平方向的運動。在整個設施重構費用中，水平方向運動產生的費用所占比重小，因此，本文設定設施在同層樓重構時，其重構費為一定值，與重構前后的位置無關；設施在不同樓層之間重構時，其重構費用只與重構前后的樓層相關，與所在樓層的具體位置無關。

(a)可重構設施布局過程

(b)可重構設施布局問題中的物流圖1　多層設施可重構布局

1.2模型的構建

可重構設施布局的績效不僅包括物流成本和重構成本，而且包括在制品庫存、周期時間、生產提前期等績效指標。目前關于布局與在制品庫存、周期時間和生產提前期等績效指標的內在聯系的研究尚不充分[7]。本文方法只考慮重構成本和物流成本，取兩者的和為目標函數，即

(2)

設施之間、設施與電梯之間的水平距離可以由網格編號與網格座標方便求得，不再贅述。

2　基于改進模擬植物生長算法的MF-RFLP求解算法

2.1模擬植物生長算法及其可能存在的問題

模擬植物生長算法(PGSA)是李彤等[20-21]提出的基于植物向光性機理的智能優(yōu)化算法，最初用于解決非線性整數規(guī)劃問題，由于其對參數的確定極為簡單和寬松，同時具備全局尋優(yōu)性質，故在電網規(guī)劃[22]、設施選址[23]、地下物流[24]等工程技術領域獲得應用，并取得了較好的效果。本文用其解決MF-RFLP，是一種新的嘗試。

PGSA的核心問題包括兩個方面，一是形態(tài)素濃度的計算方法，二是生長點的選擇。已經擴展但沒有長出新節(jié)點的葉節(jié)點，其形態(tài)素為0，其他葉節(jié)點的形態(tài)素計算公式為

(3)

其中，pi為節(jié)點Si的形態(tài)素濃度，f(Si)為節(jié)點Si的目標函數值，f(S0)為起始節(jié)點S0的目標函數值。生長節(jié)點的選擇是通過構建pi在[0,1]的狀態(tài)區(qū)間，利用計算機產生隨機數，依據隨機數所在的區(qū)間來進行的。當解空間中節(jié)點數量比較多時，收斂速度慢是模擬植物生長算法存在的主要問題。

2.2模擬植物生長算法的改進

2.3設施互換準則和算法

2.3.1設施互換準則

準則1任意設施兩兩互換是產生新節(jié)點的基本方法。既要考慮面積相等設施之間的互換和相鄰設施之間的互換，又要考慮面積不相等的不相鄰的設施之間的互換。

準則2面積不相等的不相鄰的設施互換時可能產生設施重構的傳導效應，每個波及到需要重構的設施只需滿足該設施的最小需求面積。

準則3當發(fā)生設施重構波導效應有多個重構方案時，選擇重構費用最小的方案。

2.3.2同層設施互換算法

圖2　同層設施互換

(1)如果Ai=Aj，則平穩(wěn)互換，Aj→Ai,Ai→Aj。其他設施不需移動。

2.3.3不同層設施互換算法

圖3　不同樓層的設施互換

(1)如果s(g)=s(h) ，設施在同一樓層，設施互換可以進行。

(2)如果s(g)≠s(h) ，設施不在同一樓層，則需要考慮兩個設施的面積：

①如果Az(i)=Az(j)，則可以平穩(wěn)互換；

當設施互換可以進行，但需要移動其他設施時情況比較復雜，下面做進一步分析。

2.4設施形狀約束系數算法

2.5改進模擬植物生長的MF-RFLP算法

在模擬植物生長算法中，按照形態(tài)素濃度是否為零可以將節(jié)點分為兩類：一類是已擴展的節(jié)點，這類節(jié)點形態(tài)素為0；另一類是尚未擴展的節(jié)點，這類節(jié)點形態(tài)素大于或等于0。因此，建立Open表和Closed表，Open表用來儲存尚未擴展的葉節(jié)點，Closed表儲存已經擴展的節(jié)點，包括根節(jié)點、枝節(jié)點和不能產生新的合格節(jié)點的葉節(jié)點(圖4)。

圖4　改進的模擬植物生長算法模型

基于模擬植物生長算法的車間設施布局改善具體流程如下。

(1)基礎數據輸入。①車間網格數據，包括網格編號、網格坐標、網格面積等；②設施基本數據，包括設施的最小面積、最大面積、形狀約束值、重構費用等；③物流數據，包括設施之間的物流量、單位物流費用等；④現有布局方案，包括設施的順序，以及每個設施占有的面積(網格數)等；⑤算法參數設置，參數包括最大擴展次數，形態(tài)素因子β等。

(2)計算原始布局的費用f(S0)，建立樹根，令max=f(S0)。

(3)設施互換(圖4)。將合格的節(jié)點存入Open表，將不合格的節(jié)點舍棄；選擇形態(tài)素值高的節(jié)點存入Open表；在剩余節(jié)點中隨機抽取部分節(jié)點存入Open表；將已擴展節(jié)點從Open表中移到Closed表中。節(jié)點是否合格的判定方法如下：①節(jié)點為新節(jié)點；②節(jié)點滿足形狀約束；③節(jié)點費用小于父節(jié)點費用；④方案垂直物流需求滿足電梯能力約束。

(4)判斷。若Open表不為空且擴展次數小于預定值，則計算形態(tài)素，產生隨機數，選定待擴展節(jié)點，執(zhí)行步驟(3)；若Open表為空或者擴展次數等于預定值，輸出最小費用方案，停止計算。

以上所有算法用MATLAB 7.10編程實現。

3　算例及分析

為了對提出的方法進行比較，本文提供兩個算例。第一個算例比較了模擬植物生長算法改進前后的效果，第二個算例比較了I-PGSA、CRAFT和MULTIPLE三種方法的優(yōu)劣。

3.1模擬植物生長算法改進前后的效果比較

設某小型電動工具裝配企業(yè)車間分布在一個兩層樓的建筑物內，第一層的有效面積為64個網格，第二層樓的有效面積為56個網格，樓層高度為5 m。其空間填充曲線、相應的網格編號及其坐標如圖5所示。有3個電梯，1號和2號電梯的能力為100箱/天，3號電梯的能力為120箱/天，電梯位置如圖6所示，生產周期為10天。所有設施的形狀系數設定為1.2，最小面積見表1，其物流數據見表2。為方便計算，水平物流的費用為1元/箱米、垂直物流為5元/箱米。原始方案的目標函數值為167 710元。設定同一層樓的重構費用為600元、不同層重構費用為1300元，擴展的次數為300。應用PGSA運算了3次，獲得最小目標值為125 146元，對應的布局方案如圖7所示；應用I-PGSA運算了3次，獲得最小目標值為100 120元的改善方案如圖8所示。結果表明I-PGSA比PGSA具有更快的收斂速度。

圖5　空間填充曲線及其編號與坐標

圖6　設施的初始布局

(網格個數)

表2　設施之間的物流量

圖7　PGSA擴展300次的布局方案

圖8　改善模擬植物生長算法擴展300次的布局方案

3.2與CRAFT和MULTIPLE方法的比較分析

CRAFT和MULTIPLE是兩種主要的布局方法，許多軟件都是基于這兩種方法開發(fā)的。本文采用文獻[9]中的數據和空間填充曲線，應用所建立的方法進行求解，并與CRAFT和MULTIPLE方法進行比較。因為設施O的位置不能改變，本文令設施O的重構成本為一個較大的值(100 000元)，形狀約束系數為1，其他設施形狀約束系數定為1.25，擴展次數為10。所得結果見表3。本文方法對應的布局方案如圖9所示。

表3　三種方法運算結果

圖9　改善后的布局方案

CRAFT方法只考慮了面積相等的設施或者相鄰設施的互換，而且設施有可能被分割在不同的樓層，故其運算速度較快，所需時間少。MULTIPLE方法考慮了面積不相等設施之間的互換，比CRAFT方法考慮了更多的方案，但在處理設施重構波動效應時，沒有遵循重構成本最低原則，而是采用近似平均分配網格的方法，這樣提高了整個方案的重構成本，這是其獲得的目標值大于本文所提方案獲得的目標值的主要原因。另外，MULTIPLE方法沒有考慮電梯的能力。本文方法既考慮了面積不相等設施之間的互換，同時考慮了電梯的約束，雖然運行時間稍多于CRAFT方法和MULTIPLE方法的運行時間，但是獲得的布局方案目標值明顯優(yōu)于另外兩種方法獲得的布局方案目標值。

4　結論

(1)每層樓分別建立空間填充曲線，并按空間填充曲線確定的順序給設施分配面積，利用空間填充曲線的連續(xù)性，保證了設施不會被分割。

(2)考慮了不同面積的設施交換時可能產生的設施重構傳導效應，并通過引入設施的柔性面積需求，減小了這種效應的影響。

(3)對模擬植物生長算法進行了改進。通過建立解空間子集和引入形態(tài)素因子，加快了算法的收斂速度，同時保證了算法搜索的全局性。

(4)MF-RFLP是在土地成本增加、產品小型化和個性化、生產數據多變的城市生產環(huán)境下的一個生產運作管理問題。本文方法綜合考慮了物流成本和重構成本、形狀約束和電梯能力等方面，使得模型更加接近實際情況，所得方案具備更高的可行性。建立的MF-RFLP改進模擬植物生長算法具有參數簡單和較好的全局搜索能力。本文的不足在于在建立目標函數時，只考慮了物流成本和重構成本，沒有考慮面積使用成本，也沒有考慮在制品庫存、系統(tǒng)產出率、提前期等指標，今后將開展這些方面的研究。

[1]Johnson R V.Spacecraft for Multi-floor Layout Pla-nning[J]. Management Science,1982,28(2):407-417.

[2]Izadinia N,Eshghi K,Solmani M H.A Robust Mo-del for Multi-floor Layout Problem[J].Computers & Industrial Engineering,2014,78(12):127-134.

[3]Bernardi S,Anjos M F.A Two-stage Mathematical-programming Method for the Multi-floor Facility Layout Problem[J].Journal of the Operational Research Society,2013,64(3):352-364.

[4]封海波.上海都市型工業(yè)空間組織探討[J].城市研究,2014(6):129-133.

Feng Haibo.Discussion on Urban Industrial Space Organizations of Shanghai[J].City Study, 2014(6):129-133.

[5]王磊，付建榮.美國都市工業(yè)的空間分布及其對中國城市發(fā)展的啟示[J].經濟地理,2014,34(8)：81-88.

Wang Lei, Fu Jianrong.The Spatial Distribution of Urban Manufacturing Industries in the United States and Its Implications for Urban Development in China[J].Economic Geography, 2014,34(8)：81-88.

[6]Spath D,Lentes J.Urban Production to Advance the Competitiveness of Industrial Enterprises[C]// Challenges for Sustainable Operations.International Conference on Production Research.Iguassu Falls,2013:1-5.

[7]Meng G,Heragu S S,Zijm H.Reconfigurable Layout Problem[J].International Journal Production Research,2004,42(22):4709-472.

[8]金哲，宋執(zhí)環(huán)，楊將新.可重構制造系統(tǒng)工藝路線與系統(tǒng)布局設計研究[J].計算機集成制造系統(tǒng)，2007,13(1)：7-12.

Jin Zhe, Song Zhihuan, Yang Jiangxin. Process Route and Layout Design Method for Reconf-igurable Manufacturing Systems[J].Computer Integrated Manufacturing Systems,2007,13(1)：7-12.

[9]Bozer Y A,Meller R D,Erlebacher S J.An Improvement-type Layout Algorithm for Single and Multiple-floor Facilities[J].Management Science,1994,40(7):918-932.

[10]Matsuzaki K, Irohara T, Yoshimoto K.Heuristic Algorithm to Solve the Multi-floor Layout Problem with the Consideration of Elevator Utilization[J].Computers & Industrial Engineering,1999,36(2):487-502.

[12]Ghadikolaei Y K, Shahanaghi K, Ghadikolaei Y K, et al. Multi-floor Dynamic Facility Layout: A Simulated Annealing-based Solution[J]. International Journal of Operational Research, 2013, 16(4):375-389.

[13]Aiello G, Scalia G L, Enea M. A Non Dominated Ranking Multi Objective Genetic Algorithm and Electre Method for Unequal Area Facility Layout Problems[J].Expert Systems with Applications,2013, 40(12):4812-4819.

[14]Pourvaziri H, Naderi B, Pourvaziri H, et al. A Hybrid Multi-population Genetic Algorithm for the Dynamic Facility Layout Problem[J]. Applied Soft Computing, 2014, 24(24):457-469.

[15]Scholz D, Petrick A, Domschke W. STaTS: A Sl-icing Tree and Tabu Search Based Heuristic for the Unequal Area Facility Layout Problem[J]. European Journal of Operational Research, 2009, 197(1):166-178.

[16]劉瓊，許金輝，張超勇.基于改進蛙跳算法的魯棒性車間布局[J].計算機集成制造系統(tǒng),2014, 20(8):1879-1886.

Liu Qiong，Xu Jinhui，Zhang Chaoyong.Robust Layout of Floor Shop Based on Improved Shuffled Frog Leaping Algorithm[J].Computer Integrated Manufacturing Systems,2014,20(8):1879-1886.

[17]Samarghandi H,Taabayan P, Jahantigh F F.A Par-ticle Swarm Optimization for the Single Row Facility Layout Problem[J]. Cpmputer & Industrial Engineering ,2010,58(4):529-534.

[18]武志軍，寧汝新，王愛民.可重構制造系統(tǒng)布局規(guī)劃方案的灰色模糊綜合評價方法[J].中國機械工程，2007,18(19):2313-2318.

Wu Zhijun,Ning Ruxin,Wang Aimin.Grey Fuzzy Synthetically Evaluation Method for RMS Layout Planning[J].China Mechanical Engineering, 2007,18(19):2313-2318.

[19]García-Hernández L, Palomo-Romero J M, Salas-Morera L, et al. A Novel Hybrid Evolutionary Approach for Capturing Decision Maker Knowledge into the Unequal Area Facility Layout Problem[J].Expert Systems with Applications, 2015, 42(10):4697-4708.

[20]李彤, 王春峰, 王文波, 等.求解整數規(guī)劃的一種仿生類全局優(yōu)化算法[J].系統(tǒng)工程理論與實踐,2005,25(1):76-85.

Li Tong, Wang Chunfeng, Wang Wenbo, et al.A Global Optimization Bionics Algorithm for Solving Integer Programming-plant Growth Simulation Algorithm[J].System Engineering Theory and Practice,2005,25(1):76-85.

[21]李彤，王眾托. 模擬植物生長算法與知識創(chuàng)新的幾點思考[J].管理科學學報,2010,13(3):87-96.Li Tong, Wang Zhongtuo.Plant Growth Simulation Algorithm and the Thinking in Knowledge Innovation[J]. Journal of Management Sciences in China, 2010,13(3):87-96.

[22]王淳，程浩忠. 基于模擬植物生長算法的配電網重構[J].中國電機工程學報,2007,27(9)：50-55.

Wang Chun,Cheng Haozhong.Reconfiguration of Distribution Network Based on Plant Growth Simulation Algorithm[J]. Proceedings of the CSEE, 2007,27(9)：50-55.

[23]李彤，王眾托.模擬植物生長算法在設施選址問題中的應用[J].系統(tǒng)工程理論與實踐,2008,28(12)：107-115.

Li Tong, Wang Zhongtuo.Application of Plant Growth Simulation Algorithm on Solving Facility Location Problem[J]. System Engineering Theory and Practice, 2008,28(12)：107-115.

[24]李彤，王眾托. 大型城市地下物流網絡優(yōu)化布局的模擬植物生長算法[J].系統(tǒng)工程理論與實踐，2013,33(4)：971-980.

Li Tong, Wang Zhongtuo.Optimization Layout of underground Logistics Network in Big Cities with Plant Growth Simulation Algorithm[J]. System Engineering Theory and Practice, 2013,33(4)：971-980.

(編輯陳勇)

Multi-floor Reconfigurable Facility Layout Method Based on Improved Plant Growth Simulation Algorithm

Ding Xianghai

Hangzhou Dianzi University, Hangzhou, 310018

A method of multi-floor reconfigurable facility layout was presented based on improved plant growth simulation algorithm. According to the features of multi-floor reconfigurable facility layout problem, spacefilling curves were used to describe the facility locations, making it possible to exchange any two facilities. Flexible area requirements, shape constraints and elevator utilization were used to keep the layout solution’s feasibility. Considering the material handle costs and facility reconfigurable costs together, a performance evaluation model was constructed. Based on the improved plant growth simulation algorithm, the performance improvement algorithm was developed. At last, two examples were presented to show the accuracy and generalization of this method.

multi-floor reconfigurable facility layout；improved plant growth simulation algorithm；elevator capacity constraint；facility shape constraint coefficient

2015-10-09

浙江省自然科學基金資助項目(LY13G010007)；國家社會科學基金資助項目(15BGL100)；NSFC-浙江兩化融合聯合基金資助項目(U1509220)；浙江省人文社科基地重點項目(ZD05-2016ZB)；浙江省哲學社會科學重點研究基地浙江省信息化與經濟社會發(fā)展研究中心項目(15XXHJD11)

TH66DOI：10.3969/j.issn.1004-132X.2016.15.007

丁祥海，男，1971年生。杭州電子科技大學工業(yè)工程與管理研究所副教授、博士。主要研究方向為城市生產、裝配系統(tǒng)規(guī)劃等。