面向可重構混流生產線的設施布局與生產調度并行優化方法

房殿軍，黃哲昱

（同濟大學 中德學院，上海 201804）

1 引言

隨著“工業4.0”與“中國制造2025”等以智能制造為核心的制造業發展計劃相繼提出，高度靈活的大規模定制化生產模式成為制造業未來的愿景。為使生產企業具有靈活的市場響應能力，可重構制造系統（Reconfigurable Manufacturing System,RMS）得到了越來越廣泛的應用。RMS是指為響應市場不規則需求的突然變化，具有能通過快速改變結構和軟硬件組元來調整系統的生產能力和功能而設計的制造系統[1]。布局問題是RMS 研究的主要內容和關鍵技術之一，為RMS 的每個重構周期進行合理的設施布局來調整對企業的生產成本是至關重要的。

混合流水線生產（又稱為混流生產）是一種常見的生產線組織形式。其通過調整生產組織的方法，在一條流水線上進行多品種搭配，有序地生產多種產品。混流生產解決了傳統車間生產（Job-shop）和單件流生產（One-piece-flow）中生產效率與生產柔性的矛盾，可以獲得更多的產品變化，更短的產品生命周期，更低的產品成本和更高的產能。其特征是在某些工序上存在并行設備[2]。在實際生產中，由于同工序中的并行設備存在新舊差異或型號不一致，導致其生產能力存在差距，因此調度計劃通常會給不同設備分配不同的加工件上線量。

生產調度和設施布局是可重構制造系統研究的兩大方向。目前對混流生產調度的大多數研究，通常僅考慮準備時間和加工時間等參數，而忽略了物流運輸時間。可重構制造系統設施布局的研究則普遍集中于針對解決特定問題的算法改進，通常以設備間精確物流量作為已知量進行計算求解，忽略了實際生產中，由于并行設備之間產能不一致所導致的實際物流量與前期計劃存在差異的問題。以上缺陷會對解決方案在可重構混流生產線中的實用性產生影響。

本文針對采用設施多行排列的布局，且并行設備對同一工件加工時間不相等的可重構混流生產線設施布局問題，提出了一種利用遺傳算法求解最優布局和蟻群算法求解最優調度方案相結合的方法。首先根據可重構制造系統的特點對傳統生產線規劃流程進行改進，然后對多行布局和混流生產分別進行數學建模，并且引入路徑系數減少逆向物流。接著通過數據傳遞和結束條件設置實現遺傳算法與蟻群算法相互迭代求解。最后使用此方法對實際案例進行優化計算，結果表明了該方法具有一定有效性和實用性。

2 規劃流程改進

企業在按傳統規劃流程進行設施布局規劃時，由于在該階段尚未進行調度計算，因此無法獲得設施規劃所需要的并行設備之間的精確物料搬運量。如果忽略并行設備之間的差異性，顯然不可能得到最優結果。所以本文提出的優化流程是將區域內設施規劃的工作轉移到操作層中，與生產調度并行進行。通過布局規劃算法與生產調度算法相互迭代來解決問題，從而形成一種解決可重構混流生產設施布局的優化方法，如圖1所示。

圖1 改進的規劃流程

3 問題建模

3.1 混流生產調度數學模型

生產調度的功能是依次對混流生產線每一道工序上的任務進行分配。首先將生產計劃提交的當前工序任務集合劃分為多個子任務，然后根據每個子任務的不同，以工件前往下一道工序的運輸時長TTij、加工隊列等待時間BTij以及設備加工時間STij的總和最小為目標，合理進行任務和機器的映射。這個問題可以模型化描述為：按照一定的策略，將m個子任務分配到 n 個加工設備上（n＜m），用表示所有待執行子任務的集合，表示加工設備的集合，限制每一個子任務和加工設備的映射關系。如式（1）所示，以矩陣TMmap表示該映射關系：

其中TmMn表示子任務和加工設備之間的對應關系。目標函數為：

3.2 多行排列布局模型

布局遵循以下原則：以矩形表示車間和設施的形狀，且矩形尺寸都已知；設施橫向排列，且與車間矩形的長度方向平行；設備間橫向和縱向間距已知。以車間矩形左下頂點為原點，沿矩形長度方向向右為x 軸，沿矩形寬度方向向上為y 軸建立坐標系。以設施矩形幾何中心表示該設施的位置坐標。設施之間的距離由幾何中心之間的最短折線距離來表示

圖2 多行布局位置參數示意圖

目標函數為最小化物料搬運成本，見式（3），其中fij為物流量，Cdij為帶路徑系數的距離成本。

距離成本受路徑方向影響，由路徑系數與折線段距離共同決定。

其中CX1和CX2分別為橫向順流與逆流成本系數，CY1和CY2分別為縱向順流與逆流成本系數。規定：從車間矩形的左上頂點開始，從左向右為橫向順流（即沿x軸正方向），從上向下為縱向順流（即沿y軸負方向）。

此外還需要設置車間邊界約束，即設施不能超越車間的長和寬。設施之間不能夠相互干 ，保證橫縱安全間距。

3.3 設施布局與混流生產調度問題模型的耦合分析

從上述的建模過程中發現，生產調度模型以時間TTij（可以通過距離dij與已知平均搬運速度直接計算得到）作為已知量，fij作為優化變量，而設施規劃模型以fij作為已知量，dij作為優化變量。從圖3中可以明顯地看出兩個模型在數據上具有耦合性。

圖3 模型數據的耦合關系

4 算法實現

本文針對論題提出了一個將設施布局算法與生產調度算法相互迭代運算的求解方法，其主要部分由初始解模塊、迭代控制模塊、設施規劃模塊和生產調度模塊四個模塊組成。每一個模塊的主要功能、執行流程及邏輯關聯如圖4所示。

（1）初始解模塊：該模塊為并行算法提供初始解。根據實際應用環境的不同提供合適的初始解產生方式。

（2）生產調度模塊：該模塊使用蟻群算法，根據初始布局或者設施布局模塊提供的布局進行調度求解，解算出調度方案中設備間物流搬運量的值，提供給設施布局模塊。

（3）設施布局模塊：該模塊使用遺傳算法，根據已知條件和生產調度模塊所提供的設備間物流搬運量優化值進行求解，對布局進行優化，將解算出的設備間物料搬運的距離提供給生產調度模塊。

（4）迭代控制模塊：作為主函數對生產調度模塊和設施布局模塊進行迭代調用，并且判斷迭代循環是否滿足終止條件。在結構上將生產調度模塊與設施布局模塊嵌套在迭代控制模塊之中。

圖4 并行迭代優化方法架構

4.1 初始解模塊

初始解是遺傳算法等優化算法執行的基礎，合理的初始解通常可以加快算法的收斂速度，避免陷入局部最優。在本算例中，初始解即為初始布局，本文提出了三種可行的生成方法：隨機生成、啟發式方法生成和利用原有布局。其中前兩者既可以用于一個全新的規劃，又可以用于對現有設施進行改進，而后者只能用于現有布局的改進。

4.2 生產調度模塊參數設置

生產調度模塊使用蟻群算法，以工件為多代理，對每一個工件以最小工序通過時間為目標進行自主調度。

（1）路徑選擇概率。路徑選擇的概率公式如下所示：

其中ηij表示子任務i 選擇加工設備j 時的啟發因子，它的值定義為表示第i個任務在第j個機器上的運輸時長、加工隊列等待時間以及設備加工時間的和，即Tij=TTij+BTij+STij。τij表示任務 i選擇機器j 的信息素。α為信息素啟發系數。β表示期望啟發系數。allowk表示螞蟻可以選擇的下一個機位。

（2）局部信息素更新。依據如下的信息素矩陣公式（6）來完成更新。

其中，δ為局部信息素揮發程度，N為該工序并行設備數量。

4.3 設施布局模塊

設施布局模塊采用遺傳算法對布局方案進行求解。

（1）編碼策略。采用布局設備幾何中心的浮點數XY 坐標作為基因，由所有設備的坐標值，排列成一個染色體，來表示一個可能的布局方案：如（x1,y1,x2,y2,...,xn,yn）。

（2）適應度函數。將約束條件設計成罰函數，對約束條件采用搜索空間的限定法以適應遺傳算法的需要，定義適應度函數為：

其中，K是一個常數，λ是罰函數系數，根據實際情況選取。約束條件轉化F(x)函數，并對其值進行平方運算，保證其值為正。對目標函數取倒數，目的是將求解物流量Zmin最小值轉化為求解適應度函數f(x)的最大值，以符合遺傳算法形式多樣的需要。

（3）遺傳參數。遺傳算法中各個主要參數的取值范圍：群體大小N=20～200；交叉概率Pc=0.60～1.00；變異概率Pm=0.005～0.01。

（4）選擇運算。計算群體中每一個染色體位串的適應值，將群體中各染色體按照適應度函數值排序，利用輪盤賭選擇方式進行選擇運算。

4.4 迭代控制模塊

迭代控制模塊主要起到以下三個功能：

（1）功能模塊調用。迭代控制模塊在編程時作為主函數，對設施規劃模塊和混流生產調度模塊的子函數進行循環調用。

（2）功能模塊間數據傳遞。迭代控制模塊將矩陣Dist從設施規劃模塊傳遞到生產調度模塊，將矩陣Flow從生產調度模塊傳遞到設施規劃模塊。

（3）功能模塊迭代終止判斷。并行優化算法形式上是一種迭代計算方法，每進行一輪迭代都要進行算法終止判斷。可以采用以下兩種判斷形式：①迭代次數的判定。②適應度值收斂程度判斷，即當（a 為設定的收斂度常數）時則結束迭代。本文中的算例選用第一種判斷形式。

算法步驟如下：

Step2：定義當前設備間距離矩陣變量為Dist，對優化對象的原始布局設施間距離進行計算，并賦值給當前設備間距離矩陣變量為Dist；

Step3：定義當前設備間工件搬運數量矩陣變量為Flow；

Step4：設當前循環次數參數N=0，最大循環次數為ξ；

Step5：以Dist以及其他相關參數為已知條件，使用蟻群算法進行混流生產線調度計算，得到工件工序通過時間較短的工件調度方案；

Step6：根據Step5調度方案中的設備間工件搬運數量對Flow賦值；

Step7：以Flow以及其他相關參數為已知條件，以A 為初始解，使用遺傳算法進行求解，得到物流搬運成本較小的布局方案；

Step8：對Step7 中的優化布局方案進行編碼，并賦值給A；

Step9：計算Step7中得出的優化布局方案的設備間距，并賦值給Dist；

Step10：N=N+1；

Step11：若 N ≤ξ，則返回Step5；否則，結束求解。算法流程如圖5所示。

5 計算實例

某車間外形尺寸為72×30m2。內部有8個不同工序組成的加工站，編號為G1-G8，總共包含20臺加工設備，編號M1-M20。每個加工站各自包含一個或多個并行設備。具體加工編號、工序名稱、設備數量、設備編號、單機區域尺寸等數據見表1。

圖5 綜合迭代算法流程圖

表1 工序及相應設備尺寸表

本實驗使用原始布局作為優化過程的初始解。原始布局按照工序加工站順序排列，如圖6所示，設備之間的交通路徑設定為：干路寬度2m，支路寬度1m。加工設備到區域邊界的最小安全距離為1m。平均物料搬運速度為1m/s。

圖6 車間原始布局

該車間生產5種零件，其工序如圖7所示。

五種零件在各臺設備上的加工時間見表2，單位為分鐘。其中0 表示該工件沒有相應的加工工序。工件等待時間通過記錄仿真過程中各個工件在各個加工設備的前置Buffer中的滯留時間得到。

圖7 產品工序流程

表2 工件在設備上的加工時間

由于采用了橫向分行結構，導致縱向物流成本會明顯大于橫向物流成本，同時也要兼顧盡可能減少逆向物流，由此設置 (CX1,CX2,CY1,CY2)=(1,-3,3,-9)。使用并行優化算法運算10次后選取較優的兩個結果進行觀察，分別為76 458和76 461，兩個結果非常接近，而在第二個結果中，鉆、磨、去毛刺這三道工序的設備排列相對整體集中（如圖8所示），使這一區域的物流方向更加一致，有利于減少物流路徑交叉，從該角度出發可以選擇此方案作為最終的布局優化方案。目標函數值優化曲線如圖9所示,原始布局目標函數值為101 327，在前5 次迭代中結果迅速收斂，優化效果顯著。當迭代20次時，目標函數已經基本穩定。因此在不同的場合下，可以根據實際需求在最優逼近程度與求解速度之間做權衡，在獲得滿意解的前提下選擇合適的迭代次數。

圖8 最終布局優化方案

6 結語

本文采用混流生產調度與設施布局規劃相結合的方式，提出了一種對車間設施布局及生產調度方案進行相互迭代優化的方法，取代了傳統的設施布局與生產調度分離的規劃流程，并通過數學模型的建立及仿真，驗證了該方案的可行性，同時通過設置路徑系數減少了物流路徑出現逆向和交叉，降低了物流成本，具有一定的實用性。本文的研究成果在一定程度上彌補了可重構混流生產線使用傳統布局規劃方法時無法獲得并行設備準確物流量的缺陷，為可重構制造系統周期化重置提供了有效的解決辦法。

圖9 目標函數值優化曲線