可重構低熵智能車間布局建模與優化

陳 勇,林 罕,郎一丁,卓德城,張文珠,易文超,裴 植

(1.浙江工業大學 機械工程學院,浙江 杭州 310023;2.寧波富佳實業股份有限公司,浙江 寧波 315000)

隨著國際化的推進,企業之間的競爭愈演愈烈,訂單的波動日益加劇,客戶個性化需求逐漸增強。因此,在生產計劃和設備工藝等領域,企業的生產過程向多樣性和多變動性發展,對車間布局柔性、魯棒性和低熵化等需求日趨增長。同時,隨著工業4.0以及新興技術的不斷發展,傳統車間逐漸轉變為面向未來的智能車間[1]。針對這類智能車間,提出一種可重構低熵智能車間布局,企業可以在不增加車間生產面積的前提下滿足更多的生產需求,在提高生產效率的同時,能夠縮短企業生產周期、增加生產效益。

現有關于可重構低熵智能車間布局建模的研究較少,研究者們大多針對不確定性和多目標車間布局建模進行研究。丁穗庭等[2]詳細定義了可重構度和重構成本的概念,在求解目標函數時,成功建立可重構車間背景下的多目標函數求解模型,并使用啟發式算法對可重構車間模型進行求解。陳思楊[3]在研究某類注塑車間的單元布局時,根據單元搭建和單元系統布局的工藝特點分別進行建模計算,以提高作業效率,同時考慮生產計劃變化帶來的車間布局變化。龐嘉良等[4]在研究U型生產單元過程中,在目標函數模型約束中考慮了多個約束(時間約束、空間約束和預算約束),而在求解過程中,通過模擬退火算法和蟻群算法相結合的方式,設計了混合蟻群算法求解布局方案。王東奇等[5]和曹現剛等[6]分析了遺傳算法和模擬退火算法在可重構單元布局研究中的優缺點,將兩種算法結合起來,提出了遺傳模擬退火算法,保留了遺傳算法的全局搜索能力。丁祥海[7]在研究多目標可重構設施布局方法時,引入了空間曲線來表示設備的位置,在求解可重構布局的過程中,對全局極值進行了優化,改變了個體極值選取以及帕累托解集的策略,并對粒子群優化算法進行了改進。上述研究大多將車間布局作為一個整體進行考慮,忽略了單元內布局與單元間布局的聯系。而筆者采用分層的思想,對兩者分別展開研究與規劃,針對智能車間布局模型多變量、多約束和非線性的特點,基于精英策略和元胞概念[8-10],設計雙層遺傳元胞算法,以此提高求解智能車間布局的效率,并提出可重構低熵智能車間布局模型。

1 可重構低熵智能車間布局模型

1.1 可重構低熵智能車間布局模型構建

在建立布局模型時,為了減少單個廠房布局模式的復雜性,在創建可重構車間布局[11]模型時,將其區分為單元間的布置模式與單元內的布置模式兩個部分。在建立單元間的布置模式時,把單元視作最小的構成元素[12]。在建立單元內的布置模式時,把設備視作最小的構成元素?？芍貥嫷挽刂悄苘囬g分層布局模型的構建過程如圖1所示。

圖1 可重構低熵智能車間分層布局模型構建過程Fig.1 Construction process of reconfigurable low entropy intelligent workshop hierarchical layout model

1.2 可重構低熵智能車間單元間布局模型構建

1.2.1 問題描述與假設

考慮到模型的真實性和求解模型的難度等因素,提出了以下假設:1) 車間為矩形,不考慮車間高度(假設車間高度能夠容納最高設備);2) 各單元均為矩形,尺寸已提前設定;3) 各單元與車間四周相互平行;4) 單元間的物流路徑與X軸和Y軸平行;5) 車間布局已經存在。

基于上述假設,把簡單單元布置的問題簡化為連續式布置的問題,并且滿足上述約束條件時其幾何模型如圖2所示。圖2中:L表示廠房長度;H表示廠房寬度;Xi表示單元i的橫坐標;Yi表示單元i的縱坐標;Lj表示單元j的長度;Hj表示單元j的寬度;L0表示單元與車間邊界X向的最小間距;H0表示單元與車間邊界Y向的最小間距。

圖2 單元間布局幾何模型Fig.2 Geometric model of cell layout

1.2.2 面向低熵的多目標函數設計

1) 單元間物料搬運成本C1

(1)

(2)

2) 單元間單元重構成本C2

(3)

(4)

3) 單元間時間損失成本C3

(5)

(6)

4) 車間面積利用率S

為了節約土地成本,必須最大化車間面積利用率。車間面積利用率表示為

(7)

式中:Si表示每個單元的布置面積;Sl表示布局最終所占用的面積。

根據車間布局的熵理論,需要減少在制品的數量。平均在制品數量表示為

(8)

式中:R0p表示產品p在車間生產可達到的理論值;Rp表示產品p在車間生產的瓶頸值;Tp表示產品p在車間生產時的周期。

6) 柔 性V

單元間布局柔性是指增加新產品后單元間的適應性反映了車間布局的靈活性。柔性表示為

(9)

將上述6個目標函數綜合處理表示為

(10)

式中:C表示成本函數;A表示單元間布局的轉化柔性;Z表示給定的常值;u表示面積利用率轉化成本因子,即為該車間面積占用土地總成本。

目標隸屬度函數經過聯立形成連續遞減函數,結果如圖3所示。

圖3 目標隸屬度函數Fig.3 Objective membership function

目標隸屬度函數的表達式為

(11)

通過對模糊滿意度的歸一化處理,可以將基于低熵的單元間規劃的多目標函數轉換為單目標函數,即

(12)

1.2.3 約束條件

1) 邊界約束:車間內所有單元的布置必須不能超過車間邊界,即視為滿足

(13)

(14)

(15)

(16)

2) 間距約束:在優化車間布局時,需要保證每個單元之間有一定的距離供人員和搬運設備的移動,即視為滿足

Aij×Bij=0

(17)

(18)

(19)

式中:Lmin表示單元在x方向的最小間距;Hmin表示單元在y方向的最小間距。

3) 固定位置約束:由于一些特殊原因,有些單元只能安排在某個區域,或者有些單元不能安排在某個區域,具體如下:

設Sk為某一特定的范圍,特定范圍的表達式為

(20)

某一待布置的單元i的范圍pi的表達式為

(21)

由此可以推斷,某個單元只能布置在特定的位置的表達式為

Pi∈Sk

(22)

而某個單元不能布置在特殊位置的表達式為

Pi?Sk

(23)

4) 預算約束:在低熵智能車間重構過程中,單元間重構成本不能超過M0,具體表示為

C2+C3≤M0

(24)

1.3 可重構低熵智能車間單元內布局模型構建

集群內部的設備基本屬于同類型,設備的大小和形狀基本相同,單元和單元之間雖然沒有物流關系,但和外部單元之間存在比較頻繁的物流關系,通常和多個單元有物流關系。因此,結合二次分布布局模型,構建集群單元的低熵布局模型為

f=γ1[uic-u(c)]+γ2[uib-u(b)]

(25)

(26)

2 可重構低熵智能車間布局模型算法求解

2.1 基于雙層遺傳元胞算法的模型求解流程分析

雙層遺傳元胞算法以遺傳算法為核心,先將精英染色體種群更換為隨機產生的初始種群,再把這部分精英重新分配到元胞自動機中,使得個體遺傳操作僅能和相鄰結構個體進行,以達到保護種群多樣性、提高算法檢索能力的目的,同時避免算法“早熟”和“退化”的問題[13]。圖4展示了該算法的具體求解過程。

圖4 雙層遺傳元胞算法求解流程Fig.4 Solution flow of two-layer genetic cell algorithm

2.2 外層遺傳元胞算法設計

2.2.1 精英種群引入初始種群

首先,通過遺傳算法得到的最優結果即為精英染色體,再通過M次迭代生成M條精英染色體,并標記為精英染色體種群,更換其中部分隨機染色體并標記為初始種群。更換過程如圖5所示。

圖5 精英染色體種群替換部分隨機染色體示意圖Fig.5 Schematic diagram of elite chromosome population replacing some random chromosomes

2.2.2 編碼與解碼

由于可重構低熵智能車間存在復雜的物流關系,車間單元的定位和布局方向都會影響模型目標函數,因此單元布局定位采取了整數與浮點數混合編碼的方法。其中:要排列的活動單元序列號用整數部分位來表示,每個單元的坐標用浮點位表示;單元布局方向通過二進制編碼(0,1),0代表單元的長度平行于X,1代表單元的長度垂直于X。以5個活動單元的編碼為例,其染色體的表達如圖6所示。通過使用這種編碼方法,無須解碼即可直接獲得每個單元的具體位置。

圖6 染色體編碼方式Fig.6 Chromosome coding mode

2.2.3 適應度函數設計

遺傳算法在優化的過程中,由于目標函數的優化和適應度函數值的增長并不相同,目標函數需要不斷進行變換。筆者采用倒數構造法處理目標函數,其轉換公式為

(27)

式中:fit(x)表示適應度函數;f表示目標函數。

2.2.4 選 擇

輪盤賭方法用于從當前個體周圍的鄰居中選擇兩個個體。也就是說個體的適應度越高,被選擇的概率就越大,概率表達式為

(28)

式中:M表示種群的個體數;fiti表示個體的適應度。根據式(28),確定概率的步驟如下:1) 求出個體的適應度;2) 每個個體的遺傳概率由式(28)得出;3) 下一代個體通過輪盤賭法加以篩選。

2.2.5 交 叉

筆者使用非線性處理方法,使交叉概率隨種群中個體適應值不斷變化,種群更具多樣性[14]。交叉概率的計算式為

(29)

式中:Pc表示交叉概率;Pc max表示交叉概率的最大值;Pc min表示交叉概率的最小值;fitbig表示執行交叉操作的兩個個體相對應的適應度值中的較大值;fitmax表示當前種群中的最大適應度值;fitavg表示當前種群中的平均適應度值;λ=9.9。

在優化過程中,本研究主要涉及染色體部分,包括單元編號序列、單元坐標序列和單元布置方向序列,并使用不同的方式進行交叉。

1) 單元編號序列的交叉:兩點交叉和修復程序PMX算子的結合如圖7所示。

圖7 單元序列的交叉Fig.7 Crossover of unit sequences

(30)

(31)

(32)

(33)

式中:e表示0～1的小數;i=1,2,…,n,n為相鄰間距個數。

3) 布置方向序列的交叉:采用如圖8所示的兩點交叉的方式。

圖8 布置方向序列的交叉Fig.8 Intersection of arrangement direction sequence

2.2.6 變 異

為了增強算法的局部隨機檢索能力,維持種群的多樣性,筆者將引入變異算子的非線性處理方式,變異概率的計算式為

(34)

式中:Pm表示變異概率;Pm max表示最大變異概率;Pm min表示最小變異概率;fit表示執行變異操作的個體適應度值;fitmax表示當前種群最大適應度值;fitavg表示當前種群平均適應度值;λ=9.9。

在確保子代是有效解的前提下,筆者僅對單元編號序列與布置方向序列執行如圖9所示的基本位變化。

圖9 基本位變異法Fig.9 Basic position variation

2.3 內層遺傳元胞算法設計

2.3.1 染色體編碼與解碼

使用自然數編碼,把兩倍的設備數設置成模型的染色體長度。染色體編碼的前半部分表示設備和位置之間的一一對應關系;染色體編碼的后半部分表示產品和設備之間的一一對應關系。

2.3.2 獲得初始種群并設計適應度函數

針對流水線布局優化問題的特點,設種群規模為50,hi表示單元i寬度,用目標函數的倒數表示算法的適應度函數,即

(35)

2.3.3 選擇、交叉和變異算子設定

通過選擇得到適應度,因為適應度函數已知,可將蒙特卡羅法用于分配個體概率,如果個體i的適應度為fr,則選擇的概率為

(36)

選擇方法仍然通過輪盤賭的方式決定。適應度被轉化為選擇概率,輪盤被旋轉,指針停留的最后位置代表被選擇的個體。

因為約束條件復雜,所以選擇單點交叉的方式,為了避免種群的收斂過程單一,故選用低層次的變異概率。大量的實驗證明,交叉概率Pc=0.8,變異概率Pm=0.02是可以接受的。同時,根據實際應用,需要設定終止條件來停止算法進程,對流水線問題進行多次測試,最后選擇進化代數Gen=100來終止算法進程。

3 可重構低熵智能車間布局算例驗證分析

為了驗證筆者提出的雙層遺傳元胞算法的有效性,引用文獻中的算例對遺傳算法和PSO算法進行對比驗證。算法基本參數設置如下:種群數N=100,迭代數T=500,交叉概率Pc=0.7,變異概率Pm=0.01。筆者算法的仿真結果如圖10所示,算法對比結果如表1所示。

表1 不同算法結果對比

圖10 雙層遺傳元胞算法迭代過程Fig.10 Iterative process of two-layer genetic cell algorithm

由表1可知:使用雙層遺傳元胞算法、PSO算法和常規遺傳算法均可以在有效代數內得到最優結果。對比3種算法可知:筆者雙層遺傳元胞算法收斂速度比其他兩種算法更快,尋優時間為0.23 s,同樣最優適應度值更高,最后得到的物流搬運成本最低,從而證明了雙層遺傳元胞算法在可重構低熵智能車間布局中的有效性和優越性。

4 可重構低熵智能車間布局實例分析

選取典型的實例,將模型算法應用到企業實際布局中,以證明算法的實用性。S公司智能車間同時實現了自動化處理、自動化搬運以及實時采集和反饋信息,其中有7個生產車間,公司以車間3為重構對象。車間3主要生產LG-2360、LCD-1.6和BD-1800。車間3長170 m,寬110 m,共14個功能單元。經計算,目前車間3物料搬運成本為2.247 8×107元,車間面積利用率為52.73%。車間3布局狀況如圖11所示。車間3的單元劃分采用成組技術,單元劃分結果如表2所示。

表2 單元劃分結果

圖11 車間3布局現狀Fig.11 Layout status of workshop Ⅲ

設置雙層遺傳元胞算法的參數如下:設種群規模N=200、精英種群M=50,設最大迭代數T=500。文檔大小K=100,反饋數目C=40,Pc max=0.8,Pc min=0.6,Pm max=0.04,Pm min=0.005。程序通過20次運算得出最優適應度函數值為2.463 3,對應的目標函數值為0.058 781。在確定各個單元的位置后,需確定各單元內部設備的布置位置,對設備較少的單元采用直觀判斷法,對設備較多的單元布局問題采用數學模型進行求解[15],最終選擇C1,C2,C3,C4,C5,C8進行建模分析。以C1為例子,建立二次模型并運用雙層遺傳元胞算法對單元內設備數量、設備尺寸和單元坐標進行求解,得到布局幾何模型與求解結果如圖12和表3所示。將所求得的單元間布局方案與單元內布局方案相結合,得到的車間最終布局如圖13所示。

表3 C1單元設備坐標表

圖12 C1單元布局幾何模型Fig.12 C1 unit layout geometric model

圖13 車間最終布局Fig.13 Final layout of workshop

為了驗證筆者提出的可重構低熵智能車間布局方法的有效性,將該方案與SLP布局方案和PSO布局方案進行比較。根據車間布局的低熵理論,低熵車間布局的指標主要包括物料搬運成本、重構成本、時間損失成本和車間面積利用率等,對比結果如圖14～17和表4所示。由圖17可知:筆者的布局方案通過減少物料搬運成本和設備成本,大大降低了重建成本和時間損失成本。相較于原布局,重構后的布局減少了在制品數量,使得單元內設備在生產過程中等待、停機和空轉等情況減少,設備運行更加合理,設備生產能力得到有效提升。與SLP方案和PSO方案相比,筆者方案有效提高了設備的綜合效率、布局靈活性和車間面積利用率。此外,優化后的布局響應企業生產過程中產品和批次的變化時具有很高的自我調節能力和適應性,產品加工的可選路徑較多,路徑工作效率較高,提高了低熵車間布局的抗干擾能力。可重構低熵智能車間布局建模方案具有重構時間短、響應速度快和訂單輸出完成率高等優點。

表4 成本指標對比

圖14 評價指標對比a(uf(x))Fig.14 Comparison of evaluation indicators a(uf(x))

圖15 評價指標對比b(1-uf(x))Fig.15 Comparison of evaluation indicators b(1-uf(x))

圖16 WIP指標對比Fig.16 WIP index comparison

圖17 重構成本和時間損失成本指標對比Fig.17 Comparison of reconstruction cost and time loss cost

由表4可知:SLP方案、PSO方案和筆者方案均在可重構成本M0以內,與SLP方案相比,筆者方案物料搬運成本和重構成本分別節約9.144%和42.008%;與PSO方案相比,筆者方案物料搬運成本和重構成本分別節省8.525%和22.567%。改造后的車間布局在物流上更加合理,從而降低了搬運成本,使管理更加順暢。

綜上所述,筆者提出的可重構低熵智能車間布局模型與雙層遺傳元胞算法是可行且有效的。將該模型和算法應用到實際車間布局過程中,可以有效地降低車間布局熵,提高布局的靈活性。

5 結 論

通過使用雙層遺傳元胞算法結合可重構低熵智能車間的布局概念,使得該車間模型同時具備了高柔性與高魯棒性,并且能夠在不改變車間現有面積的基礎上提升車間適應產品多樣性的能力,一定程度上解決了訂單多變性的問題。將這一理論應用到實際場景中,并與SLP方案以及PSO方案進行對比,結果表明:筆者所提算法與模型能夠更有效地實現車間低熵化,同時提高企業布局的柔性。然而筆者提出的單元內外分步建模的方法雖然降低了模型復雜度,但是提高了模型求解量。在今后的研究當中,可以考慮建立一個模型復雜程度和求解量低的多態性智能車間布局模型。