面向不確定性的再制造車間設(shè)施動(dòng)態(tài)布局方法

李聰波，馬輝杰，李玲玲，杜彥斌，穆安勇

（1.重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400030；2.重慶工商大學(xué) 制造裝備機(jī)構(gòu)設(shè)計(jì)與控制重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400067；3.重慶機(jī)床（集團(tuán)）有限責(zé)任公司，重慶 400055）

0 引言

進(jìn)入21世紀(jì)以來，資源和環(huán)境問題日益嚴(yán)峻，隨著相關(guān)法律法規(guī)的出臺(tái)和企業(yè)環(huán)保責(zé)任意識(shí)的增強(qiáng)，再制造越來越受到重視。再制造是將廢舊產(chǎn)品制造成為“如新產(chǎn)品一樣好”的再循環(huán)過程［1］。由于其蘊(yùn)含巨大的經(jīng)濟(jì)和環(huán)保效益，越來越多的制造企業(yè)開始涉足廢舊產(chǎn)品的再制造工程，如柯達(dá)、寶馬、惠普、施樂公司等均對(duì)其壽命終期產(chǎn)品實(shí)施再制造工程并獲得了巨大利潤(rùn)［2］。再制造作為一種實(shí)現(xiàn)可持續(xù)發(fā)展的有效手段，在世界各國(guó)得到了積極的推廣和應(yīng)用。

然而，再制造系統(tǒng)存在眾多不確定性因素［3］，如廢舊產(chǎn)品回收的數(shù)量和時(shí)間的不確定性、廢舊產(chǎn)品質(zhì)量狀況不確定性導(dǎo)致的再制造工藝路線和工藝時(shí)間的不確定性等，大大增加了再制造車間設(shè)施優(yōu)化布局的難度與復(fù)雜性。在實(shí)際再制造工藝過程中，廢舊零部件在回收時(shí)間和數(shù)量、再制造工藝路線和工藝時(shí)間上的不確定性，導(dǎo)致各再制造工藝單元承擔(dān)的任務(wù)量具有隨機(jī)性，進(jìn)而導(dǎo)致各再制造工藝單元的生產(chǎn)設(shè)備臺(tái)數(shù)、各個(gè)再制造工藝單元之間的物流運(yùn)輸量具有高度不確定性。因此，如何綜合考慮再制造系統(tǒng)的眾多不確定性因素，以最大化提升再制造車間的物流效率為目標(biāo)，開展再制造車間的設(shè)施優(yōu)化布局，是一個(gè)亟需解決的問題。

車間設(shè)施布局是生產(chǎn)制造企業(yè)設(shè)施規(guī)劃的一個(gè)重要問題。通過對(duì)車間中的機(jī)器設(shè)備、倉(cāng)庫(kù)等物流要素進(jìn)行合理布置，可有效提高物料處理效率、減少在制品停留時(shí)間、減少生產(chǎn)提前期［4］。目前關(guān)于生產(chǎn)車間設(shè)施布局的研究主要分為靜態(tài)布局和動(dòng)態(tài)布局。靜態(tài)布局主要考慮生產(chǎn)車間布局相關(guān)輸入信息（如各工藝間的物流運(yùn)輸量、產(chǎn)品的市場(chǎng)需求等）的不變性。例如：Chan等研究了一個(gè)生產(chǎn)多類型產(chǎn)品的制造車間布局問題，通過對(duì)所有機(jī)器設(shè)備進(jìn)行集群和分群式優(yōu)化布局，最大程度地減少了產(chǎn)品在各設(shè)備群?jiǎn)卧獌?nèi)部的物流運(yùn)輸成本［5］；Chaieb等考慮多種物流運(yùn)輸設(shè)備、加工工藝順序柔性等因素，研究了一個(gè)圓周型雙向設(shè)施優(yōu)化布局問題［6］。然而，由于實(shí)際制造系統(tǒng)往往存在一些變動(dòng)，眾多學(xué)者更傾向于研究基于多個(gè)時(shí)段的車間動(dòng)態(tài)布局方法。例如：Dharmalingam 等考慮市場(chǎng)需求不確定性，研究了一個(gè)批量生產(chǎn)的自動(dòng)化車間設(shè)施動(dòng)態(tài)布局方法；假設(shè)每個(gè)工藝單元的大小固定，且每個(gè)工藝單元只能容納一定數(shù)量的機(jī)器設(shè)備；通過優(yōu)化確定各機(jī)器設(shè)備在各工藝單元中的位置，最大程度地減少工藝單元內(nèi)部的物流運(yùn)輸距離［7］。Baykasoglu 等假設(shè)車間各工藝單元的尺寸大小相同，綜合考慮物流成本和工藝單元重布置成本，建立了車間動(dòng)態(tài)布局優(yōu)化模型［8］。Mackendall等考慮工藝單元大小的不一致性、工藝單元的朝向隨機(jī)性等特征，研究了一個(gè)開放式的車間優(yōu)化布局問題［9］。Kia等綜合考慮工藝路線可選性、機(jī)器設(shè)備的生產(chǎn)能力約束、工藝單元大小一致性等特征，研究了一種分批量式生產(chǎn)制造車間的多目標(biāo)優(yōu)化布局方法［10］。

由于再制造工藝過程的眾多不確定性，使得再制造車間的設(shè)施布局比傳統(tǒng)的制造車間布局問題更為復(fù)雜。如各再制造工藝單元的生產(chǎn)能力需求不確定性，導(dǎo)致再制造生產(chǎn)設(shè)備數(shù)量隨機(jī)變動(dòng)，進(jìn)而導(dǎo)致再制造工藝單元的尺寸大小也各不相同；此外，廢舊零部件再制造工藝路線的隨機(jī)性，導(dǎo)致各再制造工藝單元間的廢舊零部件物流運(yùn)輸量也具有不確定性。因此，亟需開展再制造車間的設(shè)施動(dòng)態(tài)布局方法研究。

本文將綜合考慮廢舊產(chǎn)品回收時(shí)間和數(shù)量不確定性、再制造工藝路線隨機(jī)性、再制造工藝的生產(chǎn)能力需求不確定性等因素，開展再制造車間設(shè)施優(yōu)化布局研究。首先對(duì)再制造工藝過程的不確定性進(jìn)行描述，在此基礎(chǔ)上對(duì)再制造車間的不確定性物流要素進(jìn)行分析，建立再制造車間設(shè)施動(dòng)態(tài)布局模型，并提出一種基于模擬退火（Simulated Annealing，SA）算法的再制造車間設(shè)施布局優(yōu)化求解方法。

1 再制造車間布局不確定性描述

再制造布局問題的相關(guān)參數(shù)描述如下：

i，j為工藝作業(yè)單元序號(hào)（i，j=1，2，…，Z），Z表示再制造車間的工藝單元總數(shù)，i=1表示拆解工藝單元，i=2表示清洗工藝單元，i=3表示檢測(cè)工藝單元，i=16表示再裝配工藝單元，i=4，5，…，Z-1表示各再制造修復(fù)工藝單元；

k為廢舊零部件的類型，k=1，2，…，K；

r為再制造工藝路線編號(hào)，r=1，2，…，R；

f為再制造車間的行，f=1，2，…，F(xiàn)，F(xiàn)為再制造車間的總行數(shù)；

h為再制造車間每一行中定位區(qū)域的序號(hào)，h=1，2，…，H，H表示再制造車間每一行中的定位區(qū)域總數(shù)；

t為再制造布局時(shí)期的序號(hào)，t=1，2，…，T，T表示布局時(shí)期總數(shù)；

Mli為第i個(gè)工藝作業(yè)單元中的單臺(tái)設(shè)備長(zhǎng)度，Mwi為第i個(gè)工藝作業(yè)單元中的單臺(tái)設(shè)備寬度，Mli≥Mwi；

Sl為再制造車間的長(zhǎng)度，Sw為再制造車間的寬度，Sl≥Sw；

ε為車間主干道的寬度；

δi為第i個(gè)再制造工藝單元的重布置成本；

θ為單位物流運(yùn)輸成本；

Δt為第t個(gè)布局時(shí)期的總物流成本；

Ct為第t個(gè)布局時(shí)期的工藝單元重布置成本的預(yù)算；

βit為一個(gè)二進(jìn)制變量，若第i個(gè)再制造工藝單元中的設(shè)備豎向排列則βit=1，如果橫向排列則βit=0；

πihft為一個(gè)二進(jìn)制變量，若在第t個(gè)布局時(shí)期內(nèi)第h行第f列的定位區(qū)域被第i個(gè)再制造工藝單元占用為第一個(gè)定位區(qū)域，則πihft=1，否則πihft=0；

（xit，yit）為第t個(gè)布局時(shí)期的第i個(gè)再制造工藝單元的重心坐標(biāo)。

1.1 再制造工藝過程不確定性

廢舊產(chǎn)品的使用壽命因其在服役環(huán)境、使用情況、自身物理性質(zhì)等方面的差異而各不相同，從而導(dǎo)致回收進(jìn)入再制造系統(tǒng)的廢舊產(chǎn)品的數(shù)量和時(shí)間具有高度不確定性。眾多學(xué)者在處理廢舊產(chǎn)品回收不確定性時(shí)，認(rèn)為廢舊產(chǎn)品的回收滿足泊松過程［11-13］。

廢舊零部件質(zhì)量狀況的差異性導(dǎo)致再制造工藝路線和工藝時(shí)間具有高度不確定性。廢舊零部件進(jìn)入再制造系統(tǒng)后，首先經(jīng)過拆解工藝得到多個(gè)廢舊零部件，經(jīng)過清洗和損傷檢測(cè)工藝后，再根據(jù)其損傷狀況分為直接重用、可再制造和材料回收三類?？稍僦圃斓牧悴考枰?jīng)過一系列再制造修復(fù)工藝才能達(dá)到新產(chǎn)品的標(biāo)準(zhǔn)。由于廢舊零部件在其類型、物理特性、損傷形式和損傷程度等方面的差異，導(dǎo)致其再制造工藝路線具有不確定性。如某廢舊機(jī)床的關(guān)鍵零部件（主軸、導(dǎo)軌、蝸輪副、絲杠和齒輪等），根據(jù)其損傷狀況的不同采取的再制造修復(fù)工藝也各不相同，具體如圖1所示。

由于廢舊零部件到達(dá)時(shí)間和數(shù)量的不確定性以及再制造工藝路線和工藝時(shí)間的不確定性，導(dǎo)致各個(gè)再制造工藝單元承擔(dān)的任務(wù)量也存在不確定性，進(jìn)而導(dǎo)致各個(gè)再制造工藝單元對(duì)生產(chǎn)能力的需求不確定，為完成再制造生產(chǎn)任務(wù)所需配備的設(shè)備數(shù)量隨機(jī)變化。

1.2 再制造工藝過程不確定性建模

（1）廢舊產(chǎn)品的到達(dá)

眾多學(xué)者在處理廢舊產(chǎn)品到達(dá)時(shí)間和數(shù)量不確定性時(shí)，均假設(shè)廢舊產(chǎn)品的到達(dá)滿足泊松過程［11-13］。定義一個(gè)隨機(jī)二進(jìn)制變量Aet表示廢舊產(chǎn)品的到達(dá)不確定性。若第e個(gè)廢舊產(chǎn)品在時(shí)間段t內(nèi)到達(dá)再制造車間，則Aet=1，否則Aet=0。因此，在第t個(gè)時(shí)間段內(nèi)到達(dá)再制造車間的廢舊產(chǎn)品總數(shù)滿足。其中：u（x）表示時(shí)刻x到達(dá)再制造車間的廢舊產(chǎn)品數(shù)量，滿足u（x）～P（λ），λ表示平均到達(dá)數(shù)量；Bt和Dt分別表示第t個(gè)布局時(shí)期的開始時(shí)刻和結(jié)束時(shí)刻。

（2）廢舊零部件的可再制造性

定義一個(gè)隨機(jī)二進(jìn)制變量πek，若πek=1則表示第e個(gè)廢舊產(chǎn)品的第k類廢舊零部件可開展再制造加工；否則，該零部件為直接重用或材料回收。各廢舊零部件的可再制造性由一個(gè)隨機(jī)概率值確定。

（3）廢舊零部件的再制造工藝路線

廢舊零部件質(zhì)量狀況的不確定性導(dǎo)致其再制造工藝路線具有高度不確定性。因此，采用工藝概率這一指標(biāo)描述廢舊零部件再制造工藝路線的隨機(jī)特性［3］。令Pekr為一個(gè)隨機(jī)二進(jìn)制變量。若Pekr=1，則表示第e個(gè)廢舊產(chǎn)品的第k類零部件選擇了第r條工藝路線；否則Pekr=0。各廢舊零部件所選擇的工藝路線由一個(gè)隨機(jī)概率值確定。

（4）廢舊零部件的再制造工藝時(shí)間

廢舊零部件的再制造工藝時(shí)間因受其質(zhì)量狀況影響而存在較大波動(dòng)，眾多學(xué)者將廢舊零部件的再制造工藝時(shí)間作指數(shù)分布處理［11-14］。因此，定義ψki表示第k類零部件在第i個(gè)再制造工藝單元中的工藝時(shí)間，滿足ψki～Γ（1，ν）。其中：1／ν表示期望工藝時(shí)間，（1／ν）2表示方差。

1.3 再制造車間布局不確定性

再制造工藝過程的眾多不確定性因素，不僅影響各再制造工藝單元設(shè)備臺(tái)數(shù)的優(yōu)化配置，還會(huì)導(dǎo)致各再制造工藝單元間廢舊零部件物流運(yùn)輸路線和物流運(yùn)輸量的不確定性。具體建模分析如下：

（1）各再制造工藝單元的設(shè)備數(shù)量

在第t個(gè)布局時(shí)期中第i個(gè)再制造工藝單元所擁有的設(shè)備數(shù)量Nit，與在該時(shí)間段內(nèi)到達(dá)該工藝單元加工的零部件數(shù)量、再制造工藝時(shí)間（ψki）、單臺(tái)設(shè)備的加工容量（ci）和設(shè)備故障率（）有關(guān)：

式中：ci表示第i個(gè)再制造工藝單元的單臺(tái)設(shè)備加工容量（單位：h／d）表示再制造設(shè)備故障率；αir為一個(gè)二進(jìn)制變量，若第i個(gè)工藝作業(yè)單元存在于第r條再制造工藝路線中，則αir=1，否則αir=0。

（2）再制造車間的物流運(yùn)輸量

廢舊零部件在開展再制造加工過程中，需相應(yīng)地在各再制造工藝單元之間進(jìn)行物料搬運(yùn)，由此產(chǎn)生物流運(yùn)輸量。然而，由于廢舊產(chǎn)品的到達(dá)時(shí)間和數(shù)量、再制造工藝路線的不確定性，導(dǎo)致各再制造工藝單元間的廢舊零部件物流運(yùn)輸量也有高度的不確定性。再制造車間的廢舊零部件物流運(yùn)輸量

式中：Wt表示在第t個(gè)時(shí)期的廢舊零部件物流運(yùn)輸總量；Γijr為一個(gè)二進(jìn)制變量，Γijr=1 表示零件第r條再制造工藝路線中的第i個(gè)再制造工藝緊前于第j個(gè)再制造工藝，否則Γijr=0；mek表示從第e個(gè)廢舊產(chǎn)品上拆解下的第k類廢舊零部件的重量；dijt表示在第t個(gè)布局時(shí)期內(nèi)第i個(gè)再制造工藝單元與第j個(gè)再制造工藝單元之間的物流距離。

2 再制造車間設(shè)施優(yōu)化布局模型

2.1 再制造車間布局問題描述

本文研究的再制造車間設(shè)施布局問題是基于多個(gè)時(shí)段（t=1，2，…，T）的車間設(shè)施動(dòng)態(tài)布局問題。該問題描述為：一個(gè)典型的再制造車間是一個(gè)近似矩陣，有固定的長(zhǎng)度和寬度；再制造車間中設(shè)計(jì)有若干條主干道，將再制造車間劃分為寬度相等的若干行；再制造車間的每一行中設(shè)計(jì)有一定數(shù)量且長(zhǎng)寬相等的定位區(qū)域，如圖2所示。再制造車間中配備有一系列再制造工藝單元（如拆解、清洗、損傷檢測(cè)、研磨、車削、電鍍鉻、激光熔覆、再裝配等）；每個(gè)再制造工藝單元擁有一定數(shù)量的再制造設(shè)備，以完成某一相應(yīng)類型的再制造修復(fù)工藝；每個(gè)再制造工藝單元根據(jù)其所擁有的設(shè)備總數(shù)量以及單臺(tái)設(shè)備需占用的面積大小，在再制造車間中占用一定數(shù)量的定位區(qū)域；被同一個(gè)工藝單元占用的定位區(qū)域必須兩兩相鄰，且不可跨行。

再制造車間布局的假設(shè)條件如下：

（1）廢舊機(jī)床倉(cāng)庫(kù)和再制造機(jī)床成品倉(cāng)庫(kù)分別定位于再制造車間的入口處和出口處。廢舊機(jī)床回收后首先進(jìn)入廢舊機(jī)床倉(cāng)庫(kù)，再制造完工后的再制造機(jī)床則進(jìn)入再制造機(jī)床成品倉(cāng)庫(kù)。

（2）廢舊產(chǎn)品的回收時(shí)間和數(shù)量不確定，其質(zhì)量狀況也不確定，即所選擇的再制造工藝路線是隨機(jī)的。

（3）在各個(gè)時(shí)間段內(nèi)，各再制造工藝單元承擔(dān)的再制造任務(wù)量不確定，導(dǎo)致再制造工藝單元對(duì)生產(chǎn)能力的需求也不確定，進(jìn)而導(dǎo)致各再制造工藝單元中的設(shè)備數(shù)量隨機(jī)變化。若在一個(gè)時(shí)間段內(nèi)某再制造工藝單元的設(shè)備數(shù)量Nit＜N（it-1），則多余的再制造設(shè)備將會(huì)被移出原先的定位區(qū)域；若Nit＞N（it-1），則新購(gòu)置的設(shè)備將會(huì)被放入該再制造工藝單元所占用的定位區(qū)域中。這兩種情況都會(huì)產(chǎn)生工藝單元重布置成本，主要用于設(shè)備移除、設(shè)備搬遷和設(shè)備安裝等。

（4）所有再制造設(shè)備被看作是近似矩形，其長(zhǎng)度和寬度已知。由于各再制造工藝單元因其所擁有的設(shè)備數(shù)量不同，導(dǎo)致尺寸變動(dòng)，每個(gè)再制造工藝單元根據(jù)尺寸大小占用相應(yīng)數(shù)量的定位區(qū)域。

（5）各再制造工藝單元中的設(shè)備縱向或橫向擺放。同一個(gè)再制造工藝單元中，所有設(shè)備的擺放形式必須相同。

（6）被定位于再制造車間中同一行的所有工藝單元，具有相同的縱坐標(biāo)。

（7）廢舊零部件在各再制造工藝單元內(nèi)部的物流量忽略不計(jì)。

2.2 決策變量

再制造車間動(dòng)態(tài)布局模型的決策變量為：各個(gè)布局時(shí)期中各再制造工藝單元的設(shè)備數(shù)量、各再制造工藝單元的尺寸長(zhǎng)度，以及各再制造工藝單元在再制造車間中的相對(duì)位置。

（1）各再制造工藝單元的設(shè)備數(shù)量

各再制造工藝單元的設(shè)備數(shù)量Nit，與時(shí)間段t內(nèi)到達(dá)該工藝單元加工的零部件數(shù)量、再制造工藝時(shí)間、單臺(tái)設(shè)備的加工容量（ci）、設(shè)備故障率（）有關(guān)，具體計(jì)算如式（1）所示。

（2）再制造工藝單元的尺寸

再制造工藝單元的長(zhǎng)度受其所擁有的設(shè)備數(shù)量Nit和設(shè)備擺放形式βit影響，具體如式（3）所示?；谠僦圃旃に噯卧某叽绱笮】梢源_定該工藝單元所需的定位區(qū)域的數(shù)量，如式（4）所示。

式中：ceil（n）為向右取整函數(shù)，即返回大于或等于n的最小整數(shù)；Sl／H表示單個(gè)布局區(qū)域的寬度。

（3）再制造工藝單元的重心坐標(biāo)

再制造工藝單元的重心坐標(biāo)表示了該工藝單元在再制造車間中的詳細(xì)位置坐標(biāo)，記為（xit，yit）。當(dāng)各再制造工藝單元在車間中占用確定的定位區(qū)域后，其重心坐標(biāo)可由式（5）計(jì)算?；诟髟僦圃旃に噯卧闹匦淖鴺?biāo)，可計(jì)算出任意兩個(gè)工藝單元間的物流距離，具體如下：

式中：πihft表示一個(gè)二進(jìn)制變量（決策變量），πihft=1表示第t個(gè)布局時(shí)期內(nèi)第h行第f列的定位區(qū)域被第i個(gè)再制造工藝單元占用，否則πihft=0；Xfh和Yfh分別表示再制造車間中第f行第h列定位區(qū)域的橫坐標(biāo)和縱坐標(biāo)，滿足：

2.3 目標(biāo)函數(shù)

再制造工藝過程的眾多不確定性，導(dǎo)致各再制造工藝單元中的設(shè)備數(shù)量、尺寸大小、物流量情況也不確定。本文以再制造車間的物流成本和工藝單元重布置成本最小為優(yōu)化目標(biāo)，具體分析如下：

（1）物流成本

廢舊零部件在開展再制造加工的過程中，需相應(yīng)地在各再制造工藝單元之間進(jìn)行物料移動(dòng)，由此產(chǎn)生物流成本。某一布局時(shí)期內(nèi)的再制造車間物流運(yùn)輸總成本

式中θ表示單位物流運(yùn)輸成本。

（2）再制造工藝單元重布置成本

由于各個(gè)時(shí)段的車間布局方案可能各不相同，在當(dāng)前時(shí)段的布局方案下，需對(duì)再制造車間開展重新布局，即調(diào)整某些再制造工藝單元的相對(duì)位置，由此產(chǎn)生設(shè)備移除、設(shè)備搬遷和設(shè)備安裝等費(fèi)用。

重布置成本由決策變量“再制造工藝單元的重心坐標(biāo)（xit，yit）”決定，具體計(jì)算見式（9）和式（10）。也就是說若重布局方案中某一工藝單元的重心坐標(biāo)與前一時(shí)期的布局重心坐標(biāo)不一致，則說明工藝單元的位置發(fā)生了變動(dòng)，由此產(chǎn)生重布置成本。式中τit為一個(gè)二進(jìn)制變量。若在第t個(gè)布局時(shí)期中第i個(gè)再制造工藝單元的重心坐標(biāo)與第t-1個(gè)布局時(shí)期的重心坐標(biāo)不同，則τit=1，否則τit=0。

2.4 再制造車間動(dòng)態(tài)布局模型

本文以再制造車間的物流成本和工藝單元重布置成本最小為目標(biāo)，建立再制造車間設(shè)施動(dòng)態(tài)布局模型，如式（11）～式（14）所示。

式中：約束條件（12）保證任一時(shí)期的再制造工藝重布置成本不能超出該時(shí)期的預(yù)算；約束條件（13）確保了所有再制造工藝單元占用的定位區(qū)域總數(shù)不超過再制造車間中所設(shè)計(jì)的布局區(qū)域數(shù)量；約束條件（14）是再制造車間的物料流守恒約束，等式左邊表示從損傷檢測(cè)（i=3）進(jìn)入各個(gè)再制造工藝（i=4，5，…，Z-1）的廢舊零部件總量，等式右邊表示從各個(gè)再制造工藝單元完成加工后進(jìn)入再裝配工藝（i=Z）的廢舊零部件總量。

3 基于模擬退火算法的再制造設(shè)施布局優(yōu)化求解

SA 算法是一種基于Monte-Carlo迭代求解策略的隨機(jī)尋優(yōu)算法。它從某一較高初溫出發(fā)，伴隨溫度的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找全局最優(yōu)解，即能概率性地跳出局部最優(yōu)解，最終趨于全局最優(yōu)［15］。SA 算法因其獨(dú)特的優(yōu)化機(jī)制以及通用性和靈活性在各領(lǐng)域得到了廣泛應(yīng)用［16-17］。本文引入SA 算法開展再制造設(shè)施布局優(yōu)化求解。

SA 算法首先生成一個(gè)再制造布局初始解g0，然后采用某種機(jī)制生成一個(gè)相鄰解g′。如果相鄰解g′優(yōu)于初始解g0，則用g′替換g0；如果相鄰解g′并不優(yōu)于初始解g0，則以一定的概率AP接受相鄰解g′并替換g0。接受概率AP的計(jì)算方式如下：式中：Δ=f（g′）-f（g）；T表示溫度，是一個(gè)隨迭代次數(shù)不斷變化的參數(shù)；f（g）為優(yōu)化目標(biāo)函數(shù)。隨著每一次SA 算法迭代結(jié)束，溫度T的被冷卻率α減低，由此接受一個(gè)劣解的概率也隨之降低。當(dāng)算法滿足終止條件時(shí)，SA 算法停止運(yùn)算并輸出最優(yōu)結(jié)果。SA 算法是非常成熟的優(yōu)化算法，本文根據(jù)再制造設(shè)施布局問題的實(shí)際需要，對(duì)算法中的關(guān)鍵步驟作了改進(jìn)，具體如下：

（1）SA 中再制造布局方案解的形式

為了解決再制造設(shè)施布局問題中再制造工藝單元尺寸大小不一致的問題，本文設(shè)計(jì)了一個(gè)兩階段矩陣表示再制造設(shè)施布局方案。

第一個(gè)矩陣A=［atw］T×W是一個(gè)初始的再制造布局方案，定義了再制造工藝單元在再制造車間的第一行到最后一行從左到右的排列順序，其中：W=；atw是一個(gè)非負(fù)整數(shù)，atw＞0表示第t個(gè)布局時(shí)期內(nèi)排列在第w個(gè)次序的再制造工藝單元編號(hào)，atw=0表示排列在第w個(gè)次序的再制造工藝單元是一個(gè)虛擬的工藝單元，它僅僅會(huì)占用1個(gè)定位區(qū)域（即Nit=1，，Mwi=［SW-（F-1）ε］／F）。圖3a所示為4個(gè)再制造工藝單元在4個(gè)時(shí)期內(nèi)的排列次序。

第二個(gè)矩陣E=［etw］T×W與矩陣A對(duì)應(yīng)，定義了在第t個(gè)時(shí)期內(nèi)排列在第w個(gè)次序的再制造工藝單元的設(shè)備擺放形式。其中etw是一個(gè)二進(jìn)制變量0或1。矩陣E需基于矩陣A和各再制造工藝單元的設(shè)備擺放形式βit來確定，具體如式（16）所示。當(dāng)atw＞0時(shí)，etw=1表示排列在第w個(gè)次序的再制造工藝單元的設(shè)備縱向擺放，etw=0表示設(shè)備橫向擺放；當(dāng)atw=0 時(shí)，表示虛擬單元中的設(shè)備縱向擺放，即etw=1。圖3b所示為與圖3a的矩陣A對(duì)應(yīng)的再制造工藝單元的設(shè)備排放形式。

基于矩陣E和式（3）可以確定各再制造工藝單元所需占用的布局區(qū)域數(shù)量ηit。在此基礎(chǔ)上，根據(jù)矩陣A可計(jì)算出詳細(xì)的再制造布局方案矩陣G=［gfht］F×H×T，具體算法流程如算法1。在矩陣G中，每一個(gè)元素gfht＞0表示在第t個(gè)時(shí)期中占用了再制造車間第f行第h列的定位區(qū)域的再制造工藝單元編號(hào)。如果gfht=0，則表示再制造車間第f行第h列的定位區(qū)域處于未被占用的狀態(tài)。圖3c所示為基于圖3a的矩陣A和圖3b的矩陣E計(jì)算得到的布局方案矩陣G。

算法1 計(jì)算布局方案矩陣G

算法1 按照矩陣A中各再制造工藝單元的排列順序，先后為每一個(gè)再制造工藝單元從左到右分配一個(gè)或若干個(gè)連續(xù)的定位區(qū)域。為了保證被同一個(gè)再制造工藝單元占用的定位區(qū)域沒有跨行，矩陣G必須滿足以下約束：

基于一個(gè)可行的布局方案矩陣G，通過式（18）計(jì)算得到各再制造工藝單元占用的第一個(gè)定位單元。在此基礎(chǔ)上，根據(jù)式（4）～式（11）可以求得再制造布局總成本。

（2）生成SA 算法初始解

初始解質(zhì)量的優(yōu)劣對(duì)SA 算法的性能影響較大［18］。初始解越差，SA 算法的收斂越慢，產(chǎn)生最優(yōu)解的質(zhì)量可能越差。本文生成再制造布局方案初始解的流程如下：

算法2 生成再制造布局初始解。

步驟1 創(chuàng)建兩個(gè)集合AS和IS。其中：AS=｛（Av，Ev），v=1，2，…，V｝表示再制造布局方案的可行解集合；IS=｛（Au，Eu）｝表示再制造布局方案的非可行解集合。初始化AS=?，IS=?。

步驟2 隨機(jī)產(chǎn)生一個(gè)二元組解（A＊，E＊）。如果（A＊，E＊）?IS且（A＊，E＊）?AS，則轉(zhuǎn)步驟3；否則，重復(fù)步驟2。

步驟3 基于步驟2中的二元組解（A＊，E＊）計(jì)算矩陣G。如果矩陣G滿足約束條件（17），則更新AS=AS∪（A＊，E＊）；否則更新IS=IS∪（A＊，E＊），重新返回步驟2。

步驟4 如果AS中可行解的數(shù)量大于V，則轉(zhuǎn)步驟5，否則返回步驟2。

步驟5 基于式（11），計(jì)算AS中所有可行解對(duì)應(yīng)的再制造布局總成本。選擇再制造布局總成本最小的二元組解（A＊，E＊）作為SA 算法的再制造布局初始解。

（3）生成SA 相鄰解

采用多間隔交換移動(dòng)方法（ζ間隔，ζ∈｛1，2，…，H-h｝）生成再制造布局方案相鄰解［17］，具體算法流程如下：

算法3 生成再制造布局相鄰解。

步驟1 任意選擇一種間隔方式（m間隔，m∈｛1，2，…，n-w｝），隨機(jī)選擇矩陣A中任意一行t和一列w的元素atw，將atw與at（w+m）相互調(diào)換，由此得到一個(gè)新矩陣A′；然后隨機(jī)選擇矩陣E中任意一個(gè)大于0的元素etw，更新etw=1-etw，得到一個(gè)新矩陣E′。由此產(chǎn)生一個(gè)新的布局方案相鄰解s′=（A′，E′）。

步驟2 基于步驟1生成的相鄰解s′計(jì)算矩陣G。若矩陣G滿足約束條件（17），則輸出s′；否則，重新開始步驟1。

（4）算法終止條件

文中SA 算法的終止條件為：①最大的迭代次數(shù)olmax已經(jīng)執(zhí)行完畢；②連續(xù)σmax次的算法迭代過程中，同一個(gè)再制造布局方案的最優(yōu)解沒有被更新。

基于SA 求解的再制造布局方案的算法流程如下：

算法4 求解最優(yōu)再制造布局方案。

步驟1 初始化SA 算法參數(shù)：溫度T，冷卻因子α，外部迭代次數(shù)ol=0，內(nèi)部迭代次數(shù)il=0，最大外部迭代次數(shù)olmax，最大內(nèi)部迭代次數(shù)ilmax，同一個(gè)解沒有被更新的最大迭代次數(shù)σmax。

步驟2 基于算法2生成一個(gè)再制造布局方案初始解s0，令s0l=s0。基于s0l計(jì)算再制造布局方案矩陣Gol和相應(yīng)的布局總成本f（Gol）。

步驟3 While（ol＜o(jì)lmaxandσ＜σmax）do：

步驟4 輸出sol，Gol和f（Gol）。結(jié)束算法。

4 案例應(yīng)用

以某廢舊機(jī)床再制造車間設(shè)施布局為例，對(duì)所提模型和方法進(jìn)行驗(yàn)證。該機(jī)床再制造車間共配備16種再制造生產(chǎn)工藝。廢舊機(jī)床零部件在該車間中的再制造工藝流程如圖1所示。為了驗(yàn)證所提出的再制造車間動(dòng)態(tài)布局模型和方法的有效性，本文設(shè)計(jì)了兩個(gè)案例：①動(dòng)態(tài)布局，即每4個(gè)月對(duì)該再制造車間進(jìn)行重新布局，以一年為期，共開展3次車間優(yōu)化布局。②靜態(tài)布局，即以一年為期，對(duì)該再制造車間只開展一次優(yōu)化布局。在靜態(tài)布局方法中不產(chǎn)生工藝單元重布置成本，只產(chǎn)生物流成本。兩個(gè)案例均通過MATLAB 2009開展編程和仿真。再制造車間布局的其余參數(shù)如表1所示，再制造車間中廢舊機(jī)床和零部件的相關(guān)信息設(shè)置如下：

（1）廢舊機(jī)床零部件每天到達(dá)再制造車間的數(shù)量滿足泊松分布。其中，平均到達(dá)數(shù)量λ=U［10，15］×v，v∈｛1.0，1.1，1.2，1.3，1.4，1.5｝表示數(shù)量擴(kuò)張因子。

（2）每個(gè)廢舊機(jī)床五類關(guān)鍵零部件的可再制造概率πek=98%。每個(gè)可再制造的廢舊機(jī)床零部件隨機(jī)產(chǎn)生一種損傷形式，即每個(gè)廢舊零部件經(jīng)過各條再制造工藝路線的概率pekr是隨機(jī)產(chǎn)生的，pekr∈U［0，1］且。

（3）五類關(guān)鍵機(jī)床零部件的再制造流程如圖1所示。

（4）每種類型的廢舊機(jī)床零部件的平均工藝時(shí)間滿足指數(shù)分布，即ψki～Γ（1，ν），其中ν∈U［0.05，0.10］。

表1 再制造車間布局的相關(guān)參數(shù)

當(dāng)重布置成本為100時(shí)，通過開展24次獨(dú)立仿真，得到靜態(tài)布局方案和動(dòng)態(tài)布局方案的再制造布局總成本對(duì)比情況如圖4所示。其中，動(dòng)態(tài)布局方案下的再制造布局總成本比靜態(tài)布局方案平均減少23%。圖5和圖6所示分別為第8次獨(dú)立仿真得到的最優(yōu)動(dòng)態(tài)布局方案和靜態(tài)布局方案。

為了進(jìn)一步驗(yàn)證動(dòng)態(tài)布局方法的優(yōu)越性，在不同的平均達(dá)到數(shù)量下各開展10次獨(dú)立仿真，統(tǒng)計(jì)得到靜態(tài)布局和動(dòng)態(tài)布局的總成本數(shù)據(jù)均值，如表2所示。基于表2的數(shù)據(jù)，對(duì)動(dòng)態(tài)布局方案的總成本改善比率（φ1-φ2）／φ1 開展100（1-α）%的置信度區(qū)間估計(jì)。參數(shù)φ的100（1-α）%的置信度區(qū)間估計(jì)為

式中：n表示樣本容量表示樣本均值；S表示樣本標(biāo) 準(zhǔn)差）表示自由度為（n-1）的100（1-α）%置信度下的t分布分位數(shù)?；诒?的數(shù)據(jù)，計(jì)算得到動(dòng)態(tài)布局方法的總成本改善比率（φ1-φ2）／φ1 的95%置信度區(qū)間，如式（20）所示。（φ1-φ2）／φ1＞0，說明在95%的置信度區(qū)間估計(jì)下，動(dòng)態(tài)布局方法始終優(yōu)于靜態(tài)布局。

表2 不同平均到達(dá)數(shù)量下的靜態(tài)布局和動(dòng)態(tài)布局的總成本均值（重布置成本δ＝100）

在動(dòng)態(tài)布局方法中，通過對(duì)再制造工藝單元開展重新布局，即使增加了一部分工藝單元重布置成本，也可減少大部分物流成本。因此，為進(jìn)一步研究重布置成本的大小對(duì)再制造車間動(dòng)態(tài)布局的影響，分別對(duì)重布置成本在［100，1 900］區(qū)間變動(dòng)時(shí)開展多組獨(dú)立仿真。圖7 所示為重布置成本在［100，1 900］區(qū)間變動(dòng)時(shí)動(dòng)態(tài)布局與靜態(tài)布局的總成本對(duì)比情況。由圖7可以看出：當(dāng)重布置成本低于1 200時(shí)，通過對(duì)再制造工藝單元開展重新布局，可抵消大部分物流成本，使動(dòng)態(tài)布局總成本低于靜態(tài)布局；然而，隨著重布置成本的不斷提高，動(dòng)態(tài)布局的優(yōu)勢(shì)逐漸喪失，靜態(tài)布局能取得更低的成本。由此可以說明，對(duì)于一個(gè)制造車間，若其設(shè)施布局的柔性較高，則采用動(dòng)態(tài)布局方法優(yōu)于靜態(tài)布局；若該車間的設(shè)施不易移動(dòng)或移動(dòng)成本非常大，則采用靜態(tài)布局獲得的效果更好。

5 結(jié)束語

本文基于廢舊產(chǎn)品回收時(shí)間和數(shù)量不確定性、再制造工藝路線隨機(jī)性、再制造工藝的生產(chǎn)能力需求不確定性等問題，提出一種再制造車間設(shè)施動(dòng)態(tài)優(yōu)化布局方法。通過對(duì)再制造工藝過程的不確定性進(jìn)行描述，分析了再制造車間的不確定性物流要素，如再制造工藝單元尺寸大小不確定性、再制造工藝單元之間的物流量不確定性，并以再制造物流成本和工藝單元重布置成本最小為目標(biāo)，建立了再制造車間設(shè)施動(dòng)態(tài)布局模型，提出一種基于SA 算法的再制造車間設(shè)施布局優(yōu)化求解方法。最后以某廢舊機(jī)床再制造車間設(shè)施布局為例，運(yùn)用MATLAB 編程開展優(yōu)化布局，驗(yàn)證了所提模型與方法的有效性。

由于本文提出了一種再制造車間設(shè)施動(dòng)態(tài)布局模型和方法，下一步將研究基于魯棒性的再制造車間動(dòng)態(tài)布局方法，以提高布局方案對(duì)實(shí)際再制造系統(tǒng)動(dòng)態(tài)變化的適應(yīng)性。

［1］XU Binshi.Remanufacturing engineering and its development in China［J］.China Surface Engineering，2010，23（2）：1-6（in Chinese）.［徐濱士.中國(guó)再制造工程及其進(jìn)展［J］.中國(guó)表面工程，2010，23（2）：1-6.］

［2］ATASU A，SARVARY M，WASSENHOVE L N V.Remanufacturing as a marketing strategy［J］.Management Science，2008，54（10）：1731-1746.

［3］LI Chengchuan，LI Congbo，CAO Huajun，et al.Uncertain remanufacturing process routings model for used components based on GERT network［J］.Computer Integrated Manufacturing Systems，2012，18（2）：298-305（in Chinese）.［李成川，李聰波，曹華軍，等.基于GERT 圖的廢舊零部件不確定性再制造工藝路線模型［J］.計(jì)算機(jī)集成制造系統(tǒng)，2012，18（2）：298-305.］

［4］SAHIN R，ERTOGRAL K，TURKBEY O.A simulated annealing heuristic for the dynamic layout problem with budget control［J］.Computer and Industrial Engineering，2010，59（2）：308-313.

［5］CHAN F T S，LAU K W，CHAN P L Y，et al.Two-stage approach for machine-part grouping and cell layout problems［J］.Robotics and Computer Integrated Manufacturing，2006，22（3）：217-238.

［6］CHAIEB I，KORBAA O.Intra-cell machine layout associated with flexible production and transport systems［J］.Proceedings of the Institution of Mechanical Engineers，Part B：Journal of Engineering Manufacture，2003，217（7）：883-897.

［7］DHARMALINGAM P，KANTHAVEL K，SATHIYAMOORTHY R，et al.Optimization of cellular layout under dynamic demand environment by simulated annealing［J］.International Journal of Science Engineering Research，2012，3（10）：91-97.

［8］BAYKASOGLU A，DERELI T，SABUNCU I.An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems［J］.Omega-International Journal of Management System，2006，34（4）：385-396.

［9］MCKENDAL A R，HAKOBYAN A.Heuristics for the dynamic facility layout problem with unequal-area departments［J］.Europe Journal of Operational Research，2010，201（1）：171-182.

［10］KIA R，SHIRAZI H，JAVADIAN N，et al.A multi-objective model for designing agroup layout of a dynamic cellular manufacturing system［J］.International Journal of Industrial Engineering，2013，9（1）：1-14.

［11］GUIDE V D R，SRIVASTAVA R，KRAUS M E.Priority scheduling policies for repair shops［J］.International Journal of Production Research，2000，38（4）：929-950.

［12］CORUM A，VAYVAY O，BAYRAKTAR E.The impact of remanufacturing on total inventory cost and order variance［J］.Journal of Cleaner Production，2014，85：442-452.

［13］TEUNTER R H，F(xiàn)LAPPER S D P.Optimal core acquisition and remanufacturing policies under uncertain core quality fractions［J］.European Journal of Operational Research，2011，210（2）：241-248.

［14］LI Congbo，LI Lingling，CAO Huajun，et al.Fuzzy learning system for uncertain remanufacturing process time of used components［J］.Journal of Mechanical Engineering，2013，49（15）：137-146（in Chinese）.［李聰波，李玲玲，曹華軍，等.廢舊零部件不確定性再制造工藝時(shí)間的模糊學(xué)習(xí)系統(tǒng)［J］.機(jī)械工程學(xué)報(bào)，2013，49（15）：137-146.］

［15］MOUSAV S M，MOGHADDAM R T.A hybrid simulated annealing algorithm for location and routing scheduling problems with cross-docking in the supply chain［J］.Journal of Manufacturing Systems，2013，32（2）：335-347.

［16］ZHANG R.A simulated annealing-based heuristic algorithm for job shop scheduling to minimize lateness［J］.International Journal of Advanced Robotic Systems，2013，10（1）：1-9.

［17］MANAVIZADEH N，HOSSEINI N S，RABBANI M，et al.A simulated annealing algorithm for a mixed model assembly u-line balancing type-I problem considering human efficiency and Just-In-Time approach［J］.Computer Industrial Engineering，2013，64（2）：669-685.

［18］NASAB N G，AHARI S G，GHZANFARI M.A hybrid simulated annealing based heuristic for solving the locationrouting problem with fuzzy demands［J］.Scientia Iranica，2013，20（3）：919-930.