可重構(gòu)低熵智能車間布局建模與優(yōu)化

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

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

隨著國際化的推進(jìn),企業(yè)之間的競爭愈演愈烈,訂單的波動日益加劇,客戶個(gè)性化需求逐漸增強(qiáng)。因此,在生產(chǎn)計(jì)劃和設(shè)備工藝等領(lǐng)域,企業(yè)的生產(chǎn)過程向多樣性和多變動性發(fā)展,對車間布局柔性、魯棒性和低熵化等需求日趨增長。同時(shí),隨著工業(yè)4.0以及新興技術(shù)的不斷發(fā)展,傳統(tǒng)車間逐漸轉(zhuǎn)變?yōu)槊嫦蛭磥淼闹悄苘囬g[1]。針對這類智能車間,提出一種可重構(gòu)低熵智能車間布局,企業(yè)可以在不增加車間生產(chǎn)面積的前提下滿足更多的生產(chǎn)需求,在提高生產(chǎn)效率的同時(shí),能夠縮短企業(yè)生產(chǎn)周期、增加生產(chǎn)效益。

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

1 可重構(gòu)低熵智能車間布局模型

1.1 可重構(gòu)低熵智能車間布局模型構(gòu)建

在建立布局模型時(shí),為了減少單個(gè)廠房布局模式的復(fù)雜性,在創(chuàng)建可重構(gòu)車間布局[11]模型時(shí),將其區(qū)分為單元間的布置模式與單元內(nèi)的布置模式兩個(gè)部分。在建立單元間的布置模式時(shí),把單元視作最小的構(gòu)成元素[12]。在建立單元內(nèi)的布置模式時(shí),把設(shè)備視作最小的構(gòu)成元素?？芍貥?gòu)低熵智能車間分層布局模型的構(gòu)建過程如圖1所示。

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

1.2 可重構(gòu)低熵智能車間單元間布局模型構(gòu)建

1.2.1 問題描述與假設(shè)

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

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

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

1.2.2 面向低熵的多目標(biāo)函數(shù)設(shè)計(jì)

1) 單元間物料搬運(yùn)成本C1

(1)

(2)

2) 單元間單元重構(gòu)成本C2

(3)

(4)

3) 單元間時(shí)間損失成本C3

(5)

(6)

4) 車間面積利用率S

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

(7)

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

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

(8)

式中:R0p表示產(chǎn)品p在車間生產(chǎn)可達(dá)到的理論值;Rp表示產(chǎn)品p在車間生產(chǎn)的瓶頸值;Tp表示產(chǎn)品p在車間生產(chǎn)時(shí)的周期。

6) 柔 性V

單元間布局柔性是指增加新產(chǎn)品后單元間的適應(yīng)性反映了車間布局的靈活性。柔性表示為

(9)

將上述6個(gè)目標(biāo)函數(shù)綜合處理表示為

(10)

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

目標(biāo)隸屬度函數(shù)經(jīng)過聯(lián)立形成連續(xù)遞減函數(shù),結(jié)果如圖3所示。

圖3 目標(biāo)隸屬度函數(shù)Fig.3 Objective membership function

目標(biāo)隸屬度函數(shù)的表達(dá)式為

(11)

通過對模糊滿意度的歸一化處理,可以將基于低熵的單元間規(guī)劃的多目標(biāo)函數(shù)轉(zhuǎn)換為單目標(biāo)函數(shù),即

(12)

1.2.3 約束條件

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

(13)

(14)

(15)

(16)

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

Aij×Bij=0

(17)

(18)

(19)

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

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

設(shè)Sk為某一特定的范圍,特定范圍的表達(dá)式為

(20)

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

(21)

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

Pi∈Sk

(22)

而某個(gè)單元不能布置在特殊位置的表達(dá)式為

Pi?Sk

(23)

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

C2+C3≤M0

(24)

1.3 可重構(gòu)低熵智能車間單元內(nèi)布局模型構(gòu)建

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

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

(25)

(26)

2 可重構(gòu)低熵智能車間布局模型算法求解

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

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

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

2.2 外層遺傳元胞算法設(shè)計(jì)

2.2.1 精英種群引入初始種群

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

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

2.2.2 編碼與解碼

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

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

2.2.3 適應(yīng)度函數(shù)設(shè)計(jì)

遺傳算法在優(yōu)化的過程中,由于目標(biāo)函數(shù)的優(yōu)化和適應(yīng)度函數(shù)值的增長并不相同,目標(biāo)函數(shù)需要不斷進(jìn)行變換。筆者采用倒數(shù)構(gòu)造法處理目標(biāo)函數(shù),其轉(zhuǎn)換公式為

(27)

式中:fit(x)表示適應(yīng)度函數(shù);f表示目標(biāo)函數(shù)。

2.2.4 選 擇

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

(28)

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

2.2.5 交 叉

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

(29)

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

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

1) 單元編號序列的交叉:兩點(diǎn)交叉和修復(fù)程序PMX算子的結(jié)合如圖7所示。

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

(30)

(31)

(32)

(33)

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

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

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

2.2.6 變 異

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

(34)

式中:Pm表示變異概率;Pm max表示最大變異概率;Pm min表示最小變異概率;fit表示執(zhí)行變異操作的個(gè)體適應(yīng)度值;fitmax表示當(dāng)前種群最大適應(yīng)度值;fitavg表示當(dāng)前種群平均適應(yīng)度值;λ=9.9。

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

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

2.3 內(nèi)層遺傳元胞算法設(shè)計(jì)

2.3.1 染色體編碼與解碼

使用自然數(shù)編碼,把兩倍的設(shè)備數(shù)設(shè)置成模型的染色體長度。染色體編碼的前半部分表示設(shè)備和位置之間的一一對應(yīng)關(guān)系;染色體編碼的后半部分表示產(chǎn)品和設(shè)備之間的一一對應(yīng)關(guān)系。

2.3.2 獲得初始種群并設(shè)計(jì)適應(yīng)度函數(shù)

針對流水線布局優(yōu)化問題的特點(diǎn),設(shè)種群規(guī)模為50,hi表示單元i寬度,用目標(biāo)函數(shù)的倒數(shù)表示算法的適應(yīng)度函數(shù),即

(35)

2.3.3 選擇、交叉和變異算子設(shè)定

通過選擇得到適應(yīng)度,因?yàn)檫m應(yīng)度函數(shù)已知,可將蒙特卡羅法用于分配個(gè)體概率,如果個(gè)體i的適應(yīng)度為fr,則選擇的概率為

(36)

選擇方法仍然通過輪盤賭的方式?jīng)Q定。適應(yīng)度被轉(zhuǎn)化為選擇概率,輪盤被旋轉(zhuǎn),指針停留的最后位置代表被選擇的個(gè)體。

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

3 可重構(gòu)低熵智能車間布局算例驗(yàn)證分析

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

表1 不同算法結(jié)果對比

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

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

4 可重構(gòu)低熵智能車間布局實(shí)例分析

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

表2 單元劃分結(jié)果

圖11 車間3布局現(xiàn)狀Fig.11 Layout status of workshop Ⅲ

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

表3 C1單元設(shè)備坐標(biāo)表

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

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

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

表4 成本指標(biāo)對比

圖14 評價(jià)指標(biāo)對比a(uf(x))Fig.14 Comparison of evaluation indicators a(uf(x))

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

圖16 WIP指標(biāo)對比Fig.16 WIP index comparison

圖17 重構(gòu)成本和時(shí)間損失成本指標(biāo)對比Fig.17 Comparison of reconstruction cost and time loss cost

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

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

5 結(jié) 論

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