考慮動(dòng)態(tài)分合的可重構(gòu)設(shè)施布局方法研究

丁祥海，諸天亮，姚文鵬

(1.杭州電子科技大學(xué) 工業(yè)工程與管理研究所，浙江 杭州 310018;2.中國(guó)移動(dòng)通信集團(tuán)衢州分公司，浙江 衢州 324000)

可重構(gòu)設(shè)施布局(Reconfigurable Facilities Layout，RFL)是一種下一生產(chǎn)周期生產(chǎn)信息(產(chǎn)品種類、工藝路線等)已知，考慮當(dāng)前車間設(shè)施布局，以某一個(gè)(或多個(gè))績(jī)效為目標(biāo)的布局方法[1]，在多品種變批量的市場(chǎng)中，獲得了廣泛應(yīng)用[2-5]。但是RFL通常不考慮設(shè)施拆分布置的情況。當(dāng)車間加工的物料有多種，工藝路線互不相同時(shí)，它會(huì)導(dǎo)致工藝路線存在迂回，造成浪費(fèi)從而提高了成本。分布式布局(Distributed Facilities Layout，DFL)雖然考慮了同類設(shè)施分開(kāi)布置，但是基于多個(gè)生產(chǎn)周期預(yù)測(cè)數(shù)據(jù)，沒(méi)有考慮當(dāng)前車間布局情況[6]。市場(chǎng)需求是動(dòng)態(tài)變化的，預(yù)測(cè)與實(shí)際需求之間往往存在較大偏差，這既會(huì)影響DFL方法的效果，又會(huì)催生物料流動(dòng)態(tài)分配難題[7]。本文為了解決RFL的浪費(fèi)問(wèn)題和DFL的單周期效果差問(wèn)題，考慮同類設(shè)施分合情況，提出一種兼具RFL單周期優(yōu)勢(shì)和DFL分布優(yōu)勢(shì)的布局方法，將此方法命名為動(dòng)態(tài)分合可重構(gòu)設(shè)施布局(Dynamic Combination Reconfigurable Facilities Layout，DC-RFL)方法。目前，分別研究RFL和DEL的文獻(xiàn)較多，但研究DC-RFL的文獻(xiàn)較罕見(jiàn)。

一、動(dòng)態(tài)分合可重構(gòu)設(shè)施布局問(wèn)題

(一)問(wèn)題描述和假設(shè)

DC-RFL考慮了同類設(shè)施的分合情況，在兼具RFL和DFL各自優(yōu)勢(shì)的情況下，解決了可能出現(xiàn)的工藝路線迂回導(dǎo)致的浪費(fèi)問(wèn)題、多周期預(yù)測(cè)導(dǎo)致的單周期效果差問(wèn)題。該方法擴(kuò)大了問(wèn)題的規(guī)模，而且會(huì)引起物料分配的動(dòng)態(tài)性，是一個(gè)比RFL和DFL更難的問(wèn)題。

1.布局方案的描述和假設(shè)

為了能夠具體、可視化地描述設(shè)施的位置和面積信息，這里采用空間填充曲線(Space filling curve)的方法。它將車間視為一塊網(wǎng)格圖形，圖形面積即車間面積，并將圖形分為若干面積相等的網(wǎng)格，網(wǎng)格按照空間填充曲線的規(guī)則連續(xù)編號(hào)，將設(shè)施以網(wǎng)格為最小單位擺放。假設(shè)車間的入料口和出料口唯一，有M種設(shè)施需要進(jìn)行布局；Mmi表示第m類第i臺(tái)設(shè)施(m=0，1，……，M+1)。當(dāng)m=0時(shí)表示入料口，m=M+1時(shí)表示出料口，入料口和出料口位置固定，i≥1。各種類單臺(tái)設(shè)施所需面積和生產(chǎn)能力已知且不變，布局方案可用設(shè)施起始網(wǎng)格編碼表示。

2.設(shè)施分合的描述和假設(shè)

在DC-RFL中，同一類設(shè)施的拆分有多種情況，如3臺(tái)鉆床可能的拆分方式：(鉆1鉆2鉆3)、(鉆1，鉆2鉆3)等。為了簡(jiǎn)化問(wèn)題，引入設(shè)施相鄰和生產(chǎn)區(qū)域的概念。若設(shè)施A的最大網(wǎng)格編碼為k，設(shè)施B的最小網(wǎng)格編碼為k+1，則設(shè)施A和B相鄰。相鄰的同類設(shè)施組成一個(gè)生產(chǎn)區(qū)域。進(jìn)行如下規(guī)定：①同類型生產(chǎn)區(qū)域由相鄰變?yōu)椴幌噜彿Q為分離；由不相鄰變?yōu)橄噜彿Q為合并。分離后的兩個(gè)生產(chǎn)區(qū)域，單獨(dú)布局，合并后的兩個(gè)生產(chǎn)區(qū)域，作為整體參與布局；為進(jìn)一步簡(jiǎn)化問(wèn)題，假設(shè)同類設(shè)施的面積需求和生產(chǎn)能力相同。②某類設(shè)施的可拆分?jǐn)?shù)等于該類設(shè)施的數(shù)量，M種設(shè)施的可拆分?jǐn)?shù)可以用一個(gè)M維的向量來(lái)表達(dá)?；谝陨霞僭O(shè)，可以減少設(shè)施的拆分方式，如上述鉆床的情況，可以只需考慮(鉆1,鉆2,鉆3)一種拆分方式，其它方式可以在布局過(guò)程中，通過(guò)不同的合并方式獲得。

3.物料分配的描述和假定

(二)模型構(gòu)建

把物料加工過(guò)程簡(jiǎn)化為一個(gè)物流系統(tǒng)[8-9]，以物料小車運(yùn)送物料的過(guò)程為對(duì)象，不考慮各生產(chǎn)區(qū)域的等待、加工和搬運(yùn)等細(xì)節(jié)情況，從三個(gè)方面重點(diǎn)考慮生產(chǎn)區(qū)域的能力約束：一是總量約束，即各類設(shè)施總負(fù)荷不能超過(guò)該類設(shè)施總生產(chǎn)能力；二是拆分?jǐn)?shù)約束，考慮到設(shè)施總生產(chǎn)能力和實(shí)際負(fù)荷大小，對(duì)布局方案的多樣性做出限制；三是物料小車運(yùn)輸路徑約束，小車運(yùn)輸路徑是根據(jù)下一生產(chǎn)區(qū)域剩余生產(chǎn)能力來(lái)判斷選擇的。在此基礎(chǔ)上，以物流成本和重構(gòu)成本最低為優(yōu)化目標(biāo),建立DC-RFL模型如下：

(1)

(2)

(3)

(4)

式(1)是總成本費(fèi)用的目標(biāo)函數(shù)，前項(xiàng)是物流成本，后項(xiàng)是重構(gòu)成本；式(2)是對(duì)滿載量的約束，表示任一生產(chǎn)區(qū)域，其生產(chǎn)能力至少滿足小車一次滿載量負(fù)荷；式(3)是對(duì)周期加工任務(wù)的約束；式(4)考慮可能存在SPAj生產(chǎn)能力未充分利用時(shí)加工物料總數(shù)和設(shè)施拆分?jǐn)?shù)的共同約束，rem為取余函數(shù)。

下面給出一個(gè)小規(guī)模算例，說(shuō)明上述模型參數(shù)定義和約束設(shè)置等的可行性和有效性。設(shè)車間內(nèi)網(wǎng)格按照空間填充曲線規(guī)則的排列順序及坐標(biāo)，入料口是編碼為1的網(wǎng)格，坐標(biāo)為(0,0)，出料口是編碼為64的網(wǎng)格，坐標(biāo)為(5,8)。設(shè)車間內(nèi)有3類生產(chǎn)設(shè)施M1至M3，所占車間網(wǎng)格數(shù)分別為30、12、20，初始網(wǎng)格數(shù)編號(hào)分別為1-30、31-42、43-62。下一個(gè)周期的物料加工種類為a1、a2，a1的工藝流程是in→M1→M3→M2→out，加工數(shù)量為500，a2的工藝流程是in→M2→M1→out，加工數(shù)量為500。in到M1、M2、M3、out的單位成本系數(shù)分別為0.15、0.17、0.14、0.12;M1到M2、M3、out的單位成本系數(shù)分別為0.13、0.13、0.15;M2到M1、M3、out的單位成本系數(shù)分別為0.16、0.17、0.13;M3到M1、M2、out的單位成本系數(shù)分別為0.12、0.14、0.15。設(shè)施重構(gòu)成本C=[15,15,30]；設(shè)施拆分?jǐn)?shù)矩陣m=[2,1,1]；各類設(shè)施的總生產(chǎn)能力Cb=[2 000,3 500,2 500]；物料小車的滿載量Fl=50。經(jīng)計(jì)算得12種布局，其中初始布局方案為M1→M2→M3，RFL方案為M2→M1→M3，DC-RFL方案為M11→M3→M2→M12，成本費(fèi)用分別為2 490.77元、2 281.55元、2 029.26元，可以發(fā)現(xiàn)DC-RFL的總成本費(fèi)用更優(yōu)。

二、模型求解

(一)算法設(shè)計(jì)

染色體編碼。染色體即為設(shè)施拆分編碼，例染色體i的編碼(1 0 1 0 1 )，表示5類設(shè)施M1至M5中M1、M3和M5拆分。染色體的基因數(shù)量即為設(shè)施的種類數(shù)。染色體基因全為“0”對(duì)應(yīng)RFL情形；染色體基因全為“1”對(duì)應(yīng)單周期的DFL。每個(gè)染色體對(duì)應(yīng)一個(gè)布局方案及其目標(biāo)函數(shù)值，這個(gè)布局方案和目標(biāo)函數(shù)值是通過(guò)粒子群算法獲得的。

粒子更新。個(gè)體最佳位置由Lkhg確定，是第g次迭代的最佳布局；全局最佳位置由Lkh確定，它是染色體h決定的粒子群迭代過(guò)程中的最佳方案。粒子更新迭代公式如下[9]。

(5)

為了防止陷入局部收斂，引用遺傳算法的變異概念，在每次粒子更新時(shí)隨機(jī)產(chǎn)生因數(shù)Kr(0a，(a為一個(gè)設(shè)定數(shù)，0

粒子解碼。通過(guò)式(5)獲得的粒子位置值需要和空間填充網(wǎng)格編碼對(duì)應(yīng)，這個(gè)過(guò)程稱為解碼。對(duì)新產(chǎn)生的粒子中各個(gè)體位置值的大小進(jìn)行排序，位置值最小個(gè)體對(duì)應(yīng)的生產(chǎn)區(qū)域放置在空間填充曲線的入口端，然后根據(jù)順序和各生產(chǎn)區(qū)域面積數(shù)確定各生產(chǎn)區(qū)域起始網(wǎng)格編號(hào)。例如，粒子A(x1,x2,x3,x4,x5,x6,x7,x8)對(duì)應(yīng)的位置值為(0.55，0.32，0.94，0.41，0.55，0.73，0.29，0.77)，根據(jù)大小可得排序向量B=(4,2,8,3,5,6,1,7)。向量B中數(shù)值為1的元素對(duì)應(yīng)向量A中的元素x7，表示x7排在空間填充曲線最前端，故元素x7的起始網(wǎng)格編碼為“1”；向量B中數(shù)值為2的元素對(duì)應(yīng)A中的元素x2，故元素x2應(yīng)緊鄰在x7后面，其起始網(wǎng)格編碼為x2的起始網(wǎng)格編碼值加上x(chóng)2所需的網(wǎng)格數(shù)減去1；其余類推。

(二)遺傳-粒子群混合算法流程設(shè)計(jì)

之所以采用遺傳-粒子群混合算法而不單獨(dú)只用其中一種算法來(lái)實(shí)現(xiàn)重構(gòu)布局的計(jì)算主要有兩個(gè)原因：其一是上文提到的為了實(shí)現(xiàn)在設(shè)施拆分信息編碼不變時(shí)能夠改變?cè)O(shè)施布局信息編碼的目的；其二是若采用單一算法，則會(huì)對(duì)各類設(shè)施全部拆分后進(jìn)行重構(gòu)，而混合算法則會(huì)優(yōu)先確定設(shè)施是否需要拆分。遺傳-粒子群混合算法具體步驟如下：

1.設(shè)置好相關(guān)參數(shù)，輸入車間初始布局和下一周期的產(chǎn)品需求等數(shù)據(jù)；

2.利用遺傳算法進(jìn)行運(yùn)算，確定設(shè)施的拆分編碼，即拆分方案；

4.判斷是否滿足粒子群算法終止條件，滿足則轉(zhuǎn)到下一步，否則重復(fù)步驟3；

5.保存該拆分編碼對(duì)應(yīng)的最優(yōu)設(shè)施布局方案；

6.判斷是否滿足遺傳算法終止條件，滿足則算法結(jié)束，選取最滿意的拆分編碼及其對(duì)應(yīng)的設(shè)施布局方案，否則重復(fù)步驟2，并且為了避免最優(yōu)解的遺漏，同時(shí)保存每代種群中具有最優(yōu)目標(biāo)值的拆分編碼及其對(duì)應(yīng)的設(shè)施布局方案。

步驟1中輸入數(shù)據(jù)包括基礎(chǔ)數(shù)據(jù)、物流數(shù)據(jù)和程序運(yùn)行數(shù)據(jù)三類?；A(chǔ)數(shù)據(jù)包括各類設(shè)施面積大小、初始布局方案、費(fèi)用值(包括重構(gòu)成本、運(yùn)輸成本)等；物流數(shù)據(jù)包括下一周期的物料種類、物料量、物料加工工藝流程等需求數(shù)據(jù)；程序運(yùn)行數(shù)據(jù)包括種群規(guī)模、最大迭代次數(shù)、最大進(jìn)化代數(shù)、Kr值等。

三、算例分析

(一)基本數(shù)據(jù)

算例采用MatlabR2018a編碼實(shí)現(xiàn)。在單周期情況下，分別就DC-RFL、RFL和DFL進(jìn)行對(duì)比分析，從而驗(yàn)證所提出方法的優(yōu)越性。

圖1 車間網(wǎng)格編碼及坐標(biāo)

A車間設(shè)施布局以網(wǎng)格編碼及坐標(biāo)的形式表示如圖1，車間內(nèi)僅有一個(gè)入料口和一個(gè)出料口，坐標(biāo)分別為(0,0)和(16,30)。A車間有7種加工設(shè)施M1至M7，所占車間網(wǎng)格數(shù)分別為96、96、60、96、60、96、96，初始網(wǎng)格數(shù)編號(hào)從1-564按照M1至M7的順序依次排列，例如M1為1-96、M2為97-192。M1-M7的可拆分?jǐn)?shù)分別為2、4、3、5、2、3、2；重構(gòu)成本分別為100、100、150、100、200、100、150；生產(chǎn)能力分別為2 000、3 500、2 500、2 000、3 000、2 500、2 500。物料小車滿載量Fl=50。下一周期有5種加工物料b1至b5，加工數(shù)量分別為500、600、450、500、550，工藝路徑為b1：in→M1→M2→M5→M6→M3→M2→M4→out；b2：in→M4→M5→M3→M7→M6→M2→M3→M7→out；b3：in→M2→M5→M6→M7→out；b4：in→M2→M7→M5→M1→out；b5：in→M3→M6→M5→M2→M1→out。物料成本系數(shù)cij如表1。

表1 物料運(yùn)輸成本系數(shù)cij

(二)計(jì)算結(jié)果及分析

1.計(jì)算結(jié)果

粒子群參數(shù)設(shè)置：種群規(guī)模為10，C1=C2=2，w=0.5，迭代次數(shù)1 000。遺傳算法參數(shù)設(shè)置：種群規(guī)模為10，進(jìn)化代數(shù)30，交叉概率為60%。應(yīng)用遺傳-粒子群混合算法運(yùn)行20次后，DC-RFL的最優(yōu)結(jié)果為21 195.03，對(duì)應(yīng)拆分碼為[1 1 0 1 1 1 1]，布局方案如表2，結(jié)果平均值為21 453.34。

表2 DC-RFL最優(yōu)結(jié)果的布局方案信息

2.比較分析

與RFL比較。拆分碼[0 0 0 0 0 0 0]對(duì)應(yīng)RFL。此時(shí)用單一的粒子群方法求解。應(yīng)用改進(jìn)粒子更新過(guò)程的PSO運(yùn)算20次，迭代1 000次，得到最優(yōu)解為28 239.84元，平均值為28 426.44元，得到最優(yōu)解的平均迭代次數(shù)為68次。應(yīng)用未改進(jìn)粒子更新過(guò)程的PSO運(yùn)算20次，迭代1 000次，得到最優(yōu)解為28 239.84元，解最大值為31 849.83元，平均值為29 944.33元。

與單周期DFL比較。拆分碼[1 1 1 1 1 1 1]對(duì)應(yīng)DFL(單周期)。這種情況運(yùn)算20次得到最優(yōu)解為22 554.4元，對(duì)應(yīng)布局方案如表3。考慮到DFL的所有可能布局方案涵蓋了DC-RFL的結(jié)果，其全部尋優(yōu)結(jié)果中也存在應(yīng)用DC-RFL后得到的較優(yōu)目標(biāo)值，再以更大迭代次數(shù)(考慮到運(yùn)算時(shí)間，迭代上限為10 000次)對(duì)DFL進(jìn)行多次尋優(yōu)，較優(yōu)解(目標(biāo)值為21 815.2元)僅出現(xiàn)一次，平均值為22 429.34元。

表3 單周期下DFL最優(yōu)結(jié)果的布局方案信息

結(jié)果表明：①在粒子更新時(shí)添加隨機(jī)因數(shù)Kr能有效避免粒子群算法陷入局部收斂；②DC-RFL能夠獲得比RFL更優(yōu)的布局方法；③DC-RFL比DFL(單周期)具有更快的搜索效率。

四、結(jié)論

針對(duì)傳統(tǒng)可重構(gòu)設(shè)施布局(RFL)的同類設(shè)施不拆分可能導(dǎo)致的工藝路線迂回浪費(fèi)問(wèn)題和分布式布局的多周期預(yù)測(cè)可能導(dǎo)致的單周期效果差問(wèn)題，本文提出了新的布局方法，即動(dòng)態(tài)分合可重構(gòu)設(shè)施布局(DC-RFL)，它兼具可重構(gòu)設(shè)施布局(RFL)的單周期最優(yōu)化優(yōu)勢(shì)和分布式布局(DFL)的選擇優(yōu)勢(shì)。DC-RFL最大的難題是如何分合設(shè)施，以及分合后物流在設(shè)施之間如何分配。引入空間填充曲線來(lái)表征車間中設(shè)施的擺放位置和形狀，較方便地將設(shè)施的分合問(wèn)題轉(zhuǎn)化為網(wǎng)格號(hào)是否相連的問(wèn)題；利用就近原則和設(shè)施的能力約束，有效解決了分合后設(shè)施之間的物流分配問(wèn)題。

本文構(gòu)建了動(dòng)態(tài)分合可重構(gòu)設(shè)施布局優(yōu)化模型，并提出了一種適用的遺傳-粒子群混合算法求解模型，該算法求解是一個(gè)兩步驟決策問(wèn)題，旨在以遺傳算法模塊搜尋到的設(shè)施拆分方案為基礎(chǔ)，通過(guò)粒子群算法模塊對(duì)各類拆分方案不斷尋優(yōu)得到最終結(jié)果。最后尋優(yōu)得到的結(jié)果與原始布局方案和RFL進(jìn)行對(duì)比，發(fā)現(xiàn)DC-RFL方法能以更短的搜索時(shí)間和更少的搜索次數(shù)得到一個(gè)總成本更低的布局方案，成本分別降低40.02%和24.94%。在如今多品種變批量的市場(chǎng)環(huán)境中，企業(yè)車間如何降低物流方面的成本投入是一個(gè)重要的管理問(wèn)題。本文方法綜合考慮了物流成本和重構(gòu)成本，貼近現(xiàn)實(shí)情況，極大提高了企業(yè)車間的管理效率，大大降低了設(shè)施布局方面的投入。

本文不足之處在于，只考慮同類設(shè)施之間的分合問(wèn)題，沒(méi)有考慮不同類型設(shè)施可能因?yàn)槲锪鞯木o密性，可以組合成單元參與布局的情況。另外，本文在目標(biāo)函數(shù)只涉及了成本費(fèi)用，沒(méi)有全方位考慮到在制品庫(kù)存、生產(chǎn)工序的交叉等因素。課題組將繼續(xù)從事這方面的研究。