[發明專利]一種車間多行布局的建模和求解方法

在審

• 申請號: 201810438932.2
• 申請日: 2018-05-09
• 公開（公告）號: CN108596403A
• 公開（公告）日: 2018-09-28
• 發明（設計）人: 付建林;唐健均;徐修立;陳振;李永剛;呂原鵬;張劍
• 申請（專利權）人: 西南交通大學;成都飛機工業（集團）有限責任公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G06N3/00
• 代理公司: 成都信博專利代理有限責任公司 51200
• 代理人: 張輝

本發明公開了一種車間多行布局的建模和求解方法，針對車間總體布局問題，考慮更多約束情況，建立符合實際布局情況的精確數學模型，并采用基于混合編碼技術的遺傳算法進行優化求解。首先基于多行布局的混合整數規劃模型，將通道、間距和橫豎放置等實際要素轉化為約束條件，構建精確數學模型；其次采用混合編碼技術，利用系統布置方法布局解嵌入改進遺傳算法的初始種群中，進行合理的參數設置和選擇合適的操作策略，避免算法陷入局部最優解，提高搜索能力和效率；最后經過迭代尋優后，獲取更加滿意的最優布局解。本發明通過構建精確模型和求解方法，可獲得更加理想和更符合工程實際的車間總體布局。

技術領域

本發明涉及車間布局建模和優化領域，特別是一種車間多行布局的建模和求解方法。

背景技術

車間布局問題是指在生產車間空間里，將車間設備、道路及其他設施等布局對象按照要求進行合理布置。制造系統企業生產產品中，通常情況80％到90％的時間處于物流搬運和等待，所以選擇合適的布局設計目標，按照相關約束條件和原則進行車間布局，可以減少搬運物流時間和總體物流量，提高物料流轉效率，使物流成本下降10％至30％，為此，一個良好的車間布局對于生產企業尤為重要。

在車間布局數學模型方面，大量的學者進行了研究，其中文獻[Kaku B K,Thompson G L.An Exact Algorithm for the General Quadratic Assignment Problem[J].European Journal of Operational Research,1986,23(3):382-390.]首次采用了混合整數模型(Mix Integer Programming，MIP)處理車間設施布局問題。車間布局問題在被簡化抽象出數學模型后，仍被證明屬于NP難問題，目前該問題通常采用啟發式算法以得到離散問題的近似解，在車間布局問題上也是如此。比如文獻[Haktanirlar Ulutas B,Kulturel-Konak S.An artificial immune system based algorithm to solve unequalarea facility layout problem[J].Expert Systems with Applications,2012,39(5):5384-5395.]基于人工免疫系統求解不等面積設施布局。

在建立車間布局數學模型時，通常對模型進行簡化以便尋優，過于簡化的模型近似度不高，往往致使數學模型與實際物理模型之間存在特別大的差異，例如，未考慮不等面積設施布局的橫縱向放置問題、區域間距和主干道等現場實際問題，這使得優化后獲得的近似解，在加入相應布局約束后，往往偏離最優解很遠。

發明內容

本發明所要解決的技術問題是提供一種車間多行布局的建模和求解方法，考慮更多約束，建立更符合生產實際的精確車間總體布局數學模型，同時基于遺傳算法，采用混合編碼技術，利用系統布置方法布局解嵌入改進遺傳算法的初始種群中，進行合理的參數設置和選擇合適的操作策略，提高搜索能力和效率，實現精確布局模型的求解。

為解決上述技術問題，本發明采用的技術方案是：

一種車間多行布局的建模和求解方法，包括以下步驟：

步驟1：基于多行布局的MIP模型的車間總體布局建模

采用三層式布局方法，第三層布局根據現場的多重約束和規則，構建優化函數并求解，其目標函數為：

式中：f_ij為功能區i至功能區j的搬運頻率，c_ij為功能區i至功能區j的單位搬運成本，α_i、β_i是功能區i矩心的x和y坐標，α_j、β_j是功能區j矩心的x和y坐標；

步驟2：采用基于混合編碼技術的遺傳算法求解，具體為：