房殿軍，黃哲昱

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

1 引言

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

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

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

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

2 規(guī)劃流程改進(jìn)

企業(yè)在按傳統(tǒng)規(guī)劃流程進(jìn)行設(shè)施布局規(guī)劃時(shí)，由于在該階段尚未進(jìn)行調(diào)度計(jì)算，因此無法獲得設(shè)施規(guī)劃所需要的并行設(shè)備之間的精確物料搬運(yùn)量。如果忽略并行設(shè)備之間的差異性，顯然不可能得到最優(yōu)結(jié)果。所以本文提出的優(yōu)化流程是將區(qū)域內(nèi)設(shè)施規(guī)劃的工作轉(zhuǎn)移到操作層中，與生產(chǎn)調(diào)度并行進(jìn)行。通過布局規(guī)劃算法與生產(chǎn)調(diào)度算法相互迭代來解決問題，從而形成一種解決可重構(gòu)混流生產(chǎn)設(shè)施布局的優(yōu)化方法，如圖1所示。

圖1 改進(jìn)的規(guī)劃流程

3 問題建模

3.1 混流生產(chǎn)調(diào)度數(shù)學(xué)模型

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

其中TmMn表示子任務(wù)和加工設(shè)備之間的對(duì)應(yīng)關(guān)系。目標(biāo)函數(shù)為：

3.2 多行排列布局模型

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

圖2 多行布局位置參數(shù)示意圖

目標(biāo)函數(shù)為最小化物料搬運(yùn)成本，見式（3），其中fij為物流量，Cdij為帶路徑系數(shù)的距離成本。

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

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

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

3.3 設(shè)施布局與混流生產(chǎn)調(diào)度問題模型的耦合分析

從上述的建模過程中發(fā)現(xiàn)，生產(chǎn)調(diào)度模型以時(shí)間TTij（可以通過距離dij與已知平均搬運(yùn)速度直接計(jì)算得到）作為已知量，fij作為優(yōu)化變量，而設(shè)施規(guī)劃模型以fij作為已知量，dij作為優(yōu)化變量。從圖3中可以明顯地看出兩個(gè)模型在數(shù)據(jù)上具有耦合性。

圖3 模型數(shù)據(jù)的耦合關(guān)系

4 算法實(shí)現(xiàn)

本文針對(duì)論題提出了一個(gè)將設(shè)施布局算法與生產(chǎn)調(diào)度算法相互迭代運(yùn)算的求解方法，其主要部分由初始解模塊、迭代控制模塊、設(shè)施規(guī)劃模塊和生產(chǎn)調(diào)度模塊四個(gè)模塊組成。每一個(gè)模塊的主要功能、執(zhí)行流程及邏輯關(guān)聯(lián)如圖4所示。

（1）初始解模塊：該模塊為并行算法提供初始解。根據(jù)實(shí)際應(yīng)用環(huán)境的不同提供合適的初始解產(chǎn)生方式。

（2）生產(chǎn)調(diào)度模塊：該模塊使用蟻群算法，根據(jù)初始布局或者設(shè)施布局模塊提供的布局進(jìn)行調(diào)度求解，解算出調(diào)度方案中設(shè)備間物流搬運(yùn)量的值，提供給設(shè)施布局模塊。

（3）設(shè)施布局模塊：該模塊使用遺傳算法，根據(jù)已知條件和生產(chǎn)調(diào)度模塊所提供的設(shè)備間物流搬運(yùn)量?jī)?yōu)化值進(jìn)行求解，對(duì)布局進(jìn)行優(yōu)化，將解算出的設(shè)備間物料搬運(yùn)的距離提供給生產(chǎn)調(diào)度模塊。

（4）迭代控制模塊：作為主函數(shù)對(duì)生產(chǎn)調(diào)度模塊和設(shè)施布局模塊進(jìn)行迭代調(diào)用，并且判斷迭代循環(huán)是否滿足終止條件。在結(jié)構(gòu)上將生產(chǎn)調(diào)度模塊與設(shè)施布局模塊嵌套在迭代控制模塊之中。

圖4 并行迭代優(yōu)化方法架構(gòu)

4.1 初始解模塊

初始解是遺傳算法等優(yōu)化算法執(zhí)行的基礎(chǔ)，合理的初始解通?？梢约涌焖惴ǖ氖諗克俣?，避免陷入局部最優(yōu)。在本算例中，初始解即為初始布局，本文提出了三種可行的生成方法：隨機(jī)生成、啟發(fā)式方法生成和利用原有布局。其中前兩者既可以用于一個(gè)全新的規(guī)劃，又可以用于對(duì)現(xiàn)有設(shè)施進(jìn)行改進(jìn)，而后者只能用于現(xiàn)有布局的改進(jìn)。

4.2 生產(chǎn)調(diào)度模塊參數(shù)設(shè)置

生產(chǎn)調(diào)度模塊使用蟻群算法，以工件為多代理，對(duì)每一個(gè)工件以最小工序通過時(shí)間為目標(biāo)進(jìn)行自主調(diào)度。

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

其中ηij表示子任務(wù)i 選擇加工設(shè)備j 時(shí)的啟發(fā)因子，它的值定義為表示第i個(gè)任務(wù)在第j個(gè)機(jī)器上的運(yùn)輸時(shí)長(zhǎng)、加工隊(duì)列等待時(shí)間以及設(shè)備加工時(shí)間的和，即Tij=TTij+BTij+STij。τij表示任務(wù) i選擇機(jī)器j 的信息素。α為信息素啟發(fā)系數(shù)。β表示期望啟發(fā)系數(shù)。allowk表示螞蟻可以選擇的下一個(gè)機(jī)位。

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

其中，δ為局部信息素?fù)]發(fā)程度，N為該工序并行設(shè)備數(shù)量。

4.3 設(shè)施布局模塊

設(shè)施布局模塊采用遺傳算法對(duì)布局方案進(jìn)行求解。

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

（2）適應(yīng)度函數(shù)。將約束條件設(shè)計(jì)成罰函數(shù)，對(duì)約束條件采用搜索空間的限定法以適應(yīng)遺傳算法的需要，定義適應(yīng)度函數(shù)為：

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

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

（4）選擇運(yùn)算。計(jì)算群體中每一個(gè)染色體位串的適應(yīng)值，將群體中各染色體按照適應(yīng)度函數(shù)值排序，利用輪盤賭選擇方式進(jìn)行選擇運(yùn)算。

4.4 迭代控制模塊

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

（1）功能模塊調(diào)用。迭代控制模塊在編程時(shí)作為主函數(shù)，對(duì)設(shè)施規(guī)劃模塊和混流生產(chǎn)調(diào)度模塊的子函數(shù)進(jìn)行循環(huán)調(diào)用。

（2）功能模塊間數(shù)據(jù)傳遞。迭代控制模塊將矩陣Dist從設(shè)施規(guī)劃模塊傳遞到生產(chǎn)調(diào)度模塊，將矩陣Flow從生產(chǎn)調(diào)度模塊傳遞到設(shè)施規(guī)劃模塊。

（3）功能模塊迭代終止判斷。并行優(yōu)化算法形式上是一種迭代計(jì)算方法，每進(jìn)行一輪迭代都要進(jìn)行算法終止判斷。可以采用以下兩種判斷形式：①迭代次數(shù)的判定。②適應(yīng)度值收斂程度判斷，即當(dāng)（a 為設(shè)定的收斂度常數(shù)）時(shí)則結(jié)束迭代。本文中的算例選用第一種判斷形式。

算法步驟如下：

Step2：定義當(dāng)前設(shè)備間距離矩陣變量為Dist，對(duì)優(yōu)化對(duì)象的原始布局設(shè)施間距離進(jìn)行計(jì)算，并賦值給當(dāng)前設(shè)備間距離矩陣變量為Dist；

Step3：定義當(dāng)前設(shè)備間工件搬運(yùn)數(shù)量矩陣變量為Flow；

Step4：設(shè)當(dāng)前循環(huán)次數(shù)參數(shù)N=0，最大循環(huán)次數(shù)為ξ；

Step5：以Dist以及其他相關(guān)參數(shù)為已知條件，使用蟻群算法進(jìn)行混流生產(chǎn)線調(diào)度計(jì)算，得到工件工序通過時(shí)間較短的工件調(diào)度方案；

Step6：根據(jù)Step5調(diào)度方案中的設(shè)備間工件搬運(yùn)數(shù)量對(duì)Flow賦值；

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

Step8：對(duì)Step7 中的優(yōu)化布局方案進(jìn)行編碼，并賦值給A；

Step9：計(jì)算Step7中得出的優(yōu)化布局方案的設(shè)備間距，并賦值給Dist；

Step10：N=N+1；

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

5 計(jì)算實(shí)例

某車間外形尺寸為72×30m2。內(nèi)部有8個(gè)不同工序組成的加工站，編號(hào)為G1-G8，總共包含20臺(tái)加工設(shè)備，編號(hào)M1-M20。每個(gè)加工站各自包含一個(gè)或多個(gè)并行設(shè)備。具體加工編號(hào)、工序名稱、設(shè)備數(shù)量、設(shè)備編號(hào)、單機(jī)區(qū)域尺寸等數(shù)據(jù)見表1。

圖5 綜合迭代算法流程圖

表1 工序及相應(yīng)設(shè)備尺寸表

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

圖6 車間原始布局

該車間生產(chǎn)5種零件，其工序如圖7所示。

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

圖7 產(chǎn)品工序流程

表2 工件在設(shè)備上的加工時(shí)間

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

圖8 最終布局優(yōu)化方案

6 結(jié)語

本文采用混流生產(chǎn)調(diào)度與設(shè)施布局規(guī)劃相結(jié)合的方式，提出了一種對(duì)車間設(shè)施布局及生產(chǎn)調(diào)度方案進(jìn)行相互迭代優(yōu)化的方法，取代了傳統(tǒng)的設(shè)施布局與生產(chǎn)調(diào)度分離的規(guī)劃流程，并通過數(shù)學(xué)模型的建立及仿真，驗(yàn)證了該方案的可行性，同時(shí)通過設(shè)置路徑系數(shù)減少了物流路徑出現(xiàn)逆向和交叉，降低了物流成本，具有一定的實(shí)用性。本文的研究成果在一定程度上彌補(bǔ)了可重構(gòu)混流生產(chǎn)線使用傳統(tǒng)布局規(guī)劃方法時(shí)無法獲得并行設(shè)備準(zhǔn)確物流量的缺陷，為可重構(gòu)制造系統(tǒng)周期化重置提供了有效的解決辦法。

圖9 目標(biāo)函數(shù)值優(yōu)化曲線