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

在審

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

1.一種車間多行布局的建模和求解方法，其特征在于，包括以下步驟：

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

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

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

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

1)進行染色體編碼

基因編碼方式由功能區排列順序、間距、橫豎放置3部分構成，并采用混合的編碼結構，即功能區排序時采用整數編碼，間距采用實數編碼，橫豎放置采用二進制編碼技術；

2)產生初始種群

初始種群由系統布置方式獲取的部分布局方案，再加上隨機種群構成；

3)評價種群、進行選擇操作；

4)交叉操作

功能區排序層是整數編碼，采用部分映射交叉；間距層為實數編碼，采用算數交叉；功能區橫豎設置層是二進制編碼，采用兩點交叉；

5)變異操作

功能區橫豎設置基因段選擇基本位變異算子；功能區排序基因段則選擇逆轉變異算子，即在基因段上隨機產生2處位置，再將這2處位置上的基因值進行互換；間距使用的是實數編碼，首先根據變異概率找到變異點，在[W_min,W_max]區間隨機產生k個功能區間距值，并分別替換變異點的間距值，從而得到k個染色體，計算出這些染色體的適應度值，用適應度最高間距值來代替原有的間距值；

6)進化及終止

達到設定的最大進化迭代次數則終止迭代；

7)解碼輸出最優布局解。

2.如權利要求1所述的一種車間多行布局的建模和求解方法，其特征在于，在步驟1建立的車間總體布局精確數學模型中，約束條件為：

W_i^l≤Y_i″-Y_i′≤W_i^u，Y_i′，Y_i″≥0 (3)

(X_i″-X_i′)(Y_i″-Y_i′)＝A_i (4)

0≤X_i′≤X_i″≤B_x (5)

0≤Y_i′≤Y_i″≤B_y (6)

α_i＝0.5X_i′+0.5X_i″ α_i≥0 (7)

β_i＝0.5Y_i′+0.5Y_i″ β_i≥0 (8)

X_i″,X_i′≥T_j1 or X_i″,X_i′≤T_j2 (9)

L_i＝1 or 0 (14)

式中：為功能區i的長度上限和下限，W_i^u、W_i^l是功能區i的寬度上限和下限，X_i′、X_i″分別為功能區左右兩邊的x坐標，Y_i′、Y_i″功能區i上邊和底邊的y坐標，B_x、B_y指廠房沿x、y軸測量長度，A_i為功能區i的面積，α_i、β_i是功能區i矩心的x和y坐標，M為罰函數，T_j1、T_j2分別為豎向主干道x軸的左右坐標，決策變量表示功能區i嚴格限定在功能區j的右邊，否則決策變量功能區i嚴格限定在功能區j的上邊，否則S_ij為功能區之間的間距；為功能區之間的最小安全間距；決策變量L_i＝1表示功能區i豎直放置，L_i＝0則表示功能區i橫向放置；

約束式(2)和(3)分別用于保證每個功能區的長寬方向不會超過指定范圍，式(4)表達了每個功能區坐標點與面積之間的非線性約束關系，式(5)和式(6)限定每個功能區位于廠房內，式(7)和式(8)指定功能區矩心的x、y坐標，式(9)保證功能區布局避開豎向主干道；約束式(10)表明時，X_j″≤X_i′，即功能區i必須布置在相鄰關聯功能區j的右邊，式(11)是針對y方向的相鄰關聯功能區的約束，式(12)避免了在x、y方向上任意兩個功能區的干涉，式(13)保證最小功能區之間的間距，式(14)表示功能區能夠橫豎向放置。