基于擴展基本時段法的隨機回收率ELSPR

舒曼莉，徐克林，鄭永前

同濟大學 機械與能源工程學院，上海 201804

基于擴展基本時段法的隨機回收率ELSPR

舒曼莉，徐克林，鄭永前

同濟大學 機械與能源工程學院，上海 201804

1 引言

再制造中的豐厚利潤，讓許多制造企業紛紛進入再制造市場。再制造市場上的產品，一些再造品價值低于制造新品，比如汽車發動機、復印機等；另一些再造品，例如一次性相機、托盤、集裝箱等的再造品與制造新品有相同價值。合理調度產品生產順序和批量成為有效減少總生產成本的關鍵，即經濟批量調度問題，Hsu證明經濟批量調度問題是NP-Hard問題[1]。在考慮再造的經濟批量調度中，需同時調度制造和再造批量以滿足需求，并考慮兩種庫存成本，問題更復雜，求解可行域更小。針對再造品和制造新品有同等價值的情況，如何調度產品生產批量，包括制造批量和再造批量，從而減少總成本這一問題成為研究熱點。

經濟批量調度問題最初由Rogers提出，其研究調度產品生產順序和批量以使成本最低[2]。Davis提出混合整數規劃方法求解，可得最優解，但隨問題規模的擴大，求解時間激增[3]。Raza和Akgunduz基于批量變動法利用模擬退火方法求解，大幅度縮短求解時間，但隨問題規模擴大，所得解與最優解誤差增加[4]。Zanoni等采用基本時段法求解，其優化結果較之前研究更優，計算時間比文獻[3]大幅降低，但該算法不能保證所得解可行[5]。結合實際生產情況，Tang和Teunter首次研究考慮舊產品回收的經濟批量調度問題（Economic Lot Scheduling Problem with Returns，ELSPR），并提出復雜算法求解，結果表明其方法能有效減少成本[6]。文獻[7]在兩條生產線上分別進行制造和再造的情況，雖多啟用一條生產線，但總成本減少量足以抵消新開生產線的成本增加量。由于ESLPR的混合整數規劃求解方法過于復雜，基于公共周期法，Teunter提出啟發式算法求解，能有效降低部分總成本，但該方法僅對產品生產率小于50%的情況適用[8]。Feng基于公共周期法建模，假設產品的制造次數和再造次數之比為M/R，M和R不同為1，提出啟發式算法求解，其假設更接近實際，但所提算法過于復雜，難以推廣[9]。以上研究雖考慮問題時更結合實際，但求解方法仍不理想，或無法求得最優解，或所得解不可行。因此，目前的研究仍延續貼合實際的趨勢，找尋較優求解方法以快速求得最優并可行的解。

ELSPR求解方法有：公共周期法、基本時段法和批量變動法。公共周期法限定產品生產周期均相同，只要存在可行調度，該方法一定能得到可行解，簡單易行，但所得解通常較最優解誤差大。批量變動法假設產品可在一個周期內生產多次，但不易求解同時考慮制造和再造批次的ELSPR。除文獻[5]外，研究者均采用公共周期法，雖簡單易行，但優化效果差，故本文采用擴展基本時段法（Extended Basic Period Approach，EBP）。該方法放寬了對周期的限制，所得解優于公共周期法，但其難以保證收斂到可行解。不可行解出現的原因：一是超出能力限制，即基本時段內需生產產品超出設備生產能力；二是排序不當造成產品生產時間沖突，即同一時刻需設備生產兩個或以上產品。本文提出啟發式遺傳算法，避免由生產時間沖突造成的不可行解，對超出能力限制所得不可行解賦予懲罰函數，讓其受遺傳壓力被淘汰，在得到可行解的前提下將問題收斂到最優解。

針對現實企業的生產特點（由于生產能力的限制和降低庫存成本等原因，會售出部分舊產品以立刻獲取利潤），本文假設回收舊產品都可能存在一定的處置率，即立刻賣出舊產品獲取相應利潤。同時，為更符合實際，將舊產品回收率設為隨機，建立基于擴展基本時段法和隨機回收率的經濟批量調度模型，為避免擴展基本時段法造成的不可行解，提出啟發式遺傳算法，使得求解過程更為快速，并保證所得解可行。

2 基于EBP和隨機回收率的ELSPR

2.1 隨機回收率的ELSPR問題描述

考慮舊產品回收的經濟批量調度問題描述為：單一設備或者生產線可制造/再造N種產品，每種產品的制造/再造速度和需求速度Di已知；設備在任一時刻只能生產一個產品，轉換為制造/再造另一種產品時花費一定換模成本和時間；產品的制造/再造單位成本和生產型產品/舊產品庫存費率均已知；舊產品回收率βi隨機；舊產品的處置費用Vd已知，舊產品處置是賣出獲利，Vd小于零；假定計劃期連續、無限，如何調度舊產品再造率αi和產品制造/再造時刻，使得使得生產周期Ti內單位總成本最小。

圖1表示存在舊產品回收的混合生產系統結構。其中，舊產品庫存存放回收舊產品，生產型產品庫存存放制造新品和再造產品。其余假設如下：

（1）舊產品回收速度βi服從參數為λi的指數分布；

（3）產品在各自生產周期內只制造和再造各一次；

（4）再造產品和制造新品均能用于滿足需求；

（5）生產過程中不允許缺貨；

（6）舊產品有一定再造率αi，未再造舊產品被售出。

圖1 制造/再造混合系統結構圖

2.2 基于EBP和隨機回收率ELSPR的模型

擴展基本時段法假設每種產品有各自生產周期，產品i生產周期Ti是某基本時段B的2的冪次方倍（PoT策略，Power of Two），即Ti=kiB，ki為乘子。總生產周期Ttoatal即所有Ti的最小公倍數，Ttoatal=kmaxB。PoT策略使得求解過程更容易得到可行解，Maxwell和Singh證明使用PoT策略，求解結果誤差不超過6%[10]。

理想情況下，即生產型庫存為0時，系統開始制造/再造。此時，理想單位總成本IC包括換模成本Cs、生產（制造/再造）成本Cp、舊產品處置成本Cd、舊產品庫存成本Chr，以及生產型產品庫存成本Chs：

上述模型中，式（2）表示Ti內單位換膜成本，包括制造和再造換膜成本；式（3）表示Ti內單位生產成本，其中Diαiβi和Di(1-αiβi)分別表示產品i在Ti內單位再造和制造量；式（4）表示Ti內單位處置成本，βi(1-αi)Di表示Ti內單位處置舊產品量；式（5）表示Ti內舊產品單位庫存成本，αiβiDi和-αiβiDi分別表示(0～t1)，(t1～Ti)中產品庫存增長率，表示舊產品庫存量，如圖2中陰影部分所示，其中f(βi)為舊產品回收率βi服從分布函數；式（6）表示Ti內生

圖2 舊產品庫存量

圖3 生產型產品庫存量

實際生產中，存在非理想情況，即生產型庫存不為0時系統開始制造/再造，產生額外成本：

式（7）表示兩種非理性情況下的額外成本，如圖4、5所示，圖中陰影部分表示額外成本。式（8）、（9）中表 f(x)有：有：[z]+=max{z，0}， [z]-=max{-z，0}。示產品i的實際制造時間，Ti(1-βi)表示理想制造時間。對

圖4 f(-)＞T(1-βi)條件下額外成本

圖5 f(-)＜T(1-βi)條件下額外成本

故目標函數為：

式（11）、（12）為約束條件，保證調度滿足設備產能限制，即換模和生產時間之和不超過基本時段。

3 啟發式遺傳算法

遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論自然選擇和遺傳學機理生物進化過程的計算方法，是一種通過模擬自然進化過程搜索最優解的方法。Fujita首次運用遺傳算法求解ELSP，發現該問題適合用遺傳算法求解[11]。

實數編碼，基因串中分別包含基本時段B，舊產品再造率α，以及乘子k。規模為n的問題，染色體長為2n+1。BUB為該問題用公共周期法所得周期TC，BUB=TC，BLB為該問題用IS（Independent Solution）法求解時所得最小Ti，即BLB=Timin。α由定義可知α∈[0，1]。對乘子k，ki=2ai，ai=0，1， 2，…；=1；根據Hainan Sun[12]可知：

適應度函數，遺傳過程中不符合約束（11）、（12）的解賦予懲罰函數而不丟棄，增加種群多樣性，避免早熟。fitnessj=Fj+，Fj表示目標函數值，表示相應懲罰函數，t為遺傳代數。其中：

表示制造/再造過程中實際生產時間超過基本時段B的量，將解的不可行程度量化，不可行程度越高，懲罰函數就越大。初始種群，使用啟發式規則生成初始種群，避免因生產時間沖突造成的不可行解：

步驟1根據初始種群中的B以及ki，有Ti=kiB；

步驟3按-+Ti(1-αiβi)下降順序，排序所有再造批次，時間間隔

步驟4依次比較再造批次中相鄰批次，交換順序并比較目標函數F是否降低，若降低，則交換兩個批次；

步驟5計算末尾再造批次結束時間Tter以及總周期Ttoatal=kmaxB，總松弛時間為Tslack=Ttotal-Tter；

步驟6對滿足的產品的再造批次前加入松弛，直至滿足-=Ti(1-αiβi)或所有的松弛時間Tslack已分配完。

遺傳操作，在“選擇復制”中采用輪盤賭結合精英策略，選取父代中適應度函數最小的10%復制得到子代，余下90%子代采用輪盤賭方法在父代中選取。在“交叉”中采用均勻交叉，掩碼是隨機產生的二進制串。若掩碼為1，則子1基因點獲取父1的基因信息，子2獲取父2的；若掩碼為0，則子1獲取父2的基因信息，子2則獲取父1的，如圖6所示。“變異”為多點變異，染色體中每段均給予一定變異幾率，變異點隨機產生，該基因位上的數值由另一個隨機數代替，隨機數的產生服從初始種群產生規則。遺傳過程中，隨遺傳代數增加，逐漸降低交叉率，增大變異率，使子代穩定遺傳，同時由于變異率增加也保持了種群的多樣性。

圖6 均勻交叉操作范例

終止條件，達到一定代數，或相鄰若干代種群平均適應值無變化或變化小于閾值，則退出算法。

4 數值實驗

實驗數據源于文獻[6]，研究對象為一機械部件廠，實例包含5種產品，各產品相關參數如表1所示。通過HGA求解，所得結果如表2、3所示，其中“當前策略”為該機械部件廠當前采用的調度方法。

表2結果表明本文提出的模型對機械廠目前調度有所優化，成本比文獻[6]下降3.6%。成本降低集中在額外成本和庫存成本。由于目標函數包含產品制造/再造成本，該成本遠高于換模及庫存成本，且對舊產品再造率αi敏感性小，制造/再造成本變化幅度小，使總成本優化幅度減小。若總成本不包括制造/再造成本，單位總成本較文獻[6]所得結果下降18.7%。本文提出的ELSPR求解方法比文獻[6]有更好的優化效果。

若不考慮產品處置，即舊產品均可再造，此時制造/再造成本作為定值不包括在目標函數中。優化結果如表3所示，單位總成本比文獻[6]所得結果下降17%。雖然優化幅度不大，但建模時考慮舊產品再造率可進一步降低額外成本和庫存成本。在建模時考慮舊產品再造率，不僅符合生產實際，而且可以有效地降低成本。

從表1可看出，算例中研究對象生產率均較高，在80%左右。下面對生產率處于中低部分的對象進行研究，實驗數據從文獻[8]中獲得，如表4所示。分別用IS和文獻[6]方法及HGA進行求解。IS法求得的解若可行，則其為該問題最優解，但這幾乎不可能，尤其對生產率ρ＞0.25的問題[13]。故IS通常作為同類問題的下界。由于IS所得解通常不可行，故不考慮IS法額外成本AC。如表5為三種方法求解結果，由表5可知，在考慮舊產品回收率情況下，HGA所得解比文獻[6]下降9.8%。如表6為HGA求解產品調度情況，其中表示產品制造/再造的結束時間，可以看出HGA所得調度可行。在不同的產品生產率下，提出的HGA算法均能取得優于文獻[6]的解，并且能保證所得調度的可行性。

表1 求解模型所用參數

表2 文獻[6]和HGA求解結果比較

表3 舊產品均可再造情況下求解結果比較

表4 產品相關參數

表5 中低生產率下求解結果對比

表6 求解模型所得決策變量參數值

5 敏感性分析

對回收率參數λ進行敏感性分析，其余參數如表4所示，結果如圖7所示。分析發現，逐漸增大λ值，回收率β均值減小，成本大幅震蕩。λ在[0，10]時，成本震蕩幅度較大，隨著λ逐漸增大，處于[50，100]時，成本逐漸增大。由于生產型庫存費率更高，越遲開始再造，庫存費用的增加速度減緩。在λ值較大時，系統再造量下降，隨著制造批次的增大，總成本增加。λ增大，再造批量減小，制造批量增大，制造單位生產成本高于再造單位生產成本，總生產成本的增加。對λ分析發現，回收率在一定范圍內增加可使得成本下降，但是超過該范圍后成本反而增加，構建模型是考慮舊產品再造率，使得舊產品不能都用于再造，對于優化ELSPR十分必要。

圖7 回收率參數敏感性分析圖

6 結束語

針對存在于混合生產系統中的批量調度問題，本文建立了舊產品回收率隨機并考慮舊產品處置的ELSPR模型。采用啟發式遺傳算法結合擴展基本時段法對模型進行求解。實驗表明：建模時考慮舊產品回收率，較同等條件下不考慮該參數，能進一步降低總成本達到18.7%；提出的HGA算法在生產率的不同階段均能求得優于文獻[6]的解，并且能保證所得調度的可行性。在將來求解ELSPR時，對初始解的生成采用更優的啟發式排序規則，使初始解包含所有可行排序，或對初始解中的不可行解提出修復規則，使初始解盡量多樣化，以使得最優解進一步優化。

[1]Hsu W L.On the general feasibility test of scheduling lot sizes for several products on one machine[J].Management Science，1983，29（1）：93-105.

[2]Rogers J.A computational approach to the lot scheduling problem[J]. Management Science，1958，4（3）：264-291.

[3]Davis S G.Scheduling economic lot size production runs[J]. Management Science，1990，36（8），985-998.

[4]Raza A S，Akgunduz A.A comparative study of heuristic algorithms on economic lot scheduling problem[J].Computers and Industrial Engineering，2008，55（1）：94-109.

[5]Zanoni S，Segerstedt A，Tang O，et al.Multi-product economic lot scheduling problem with manufacturing and remanufacturing using a basic period policy[J].Computers and Industrial Engineering，2012，62：1025-1033.

[6]Tang O，Teunter R.Economic lot scheduling problem with returns[J].Production and Operations Management，2006，15（4）：488-497.

[7]Teunter R，Kaparis K，Tang O.Multi-product economic lot scheduling problem with separate production lines for manufacturing and remanufacturing[J].European Journal of Operational Research，2008，191：1241-1253.

[8]Teunter R，Tang O，Kaparis K.Heuristics for the economic lot schedulingproblemwithreturns[J].ProductionEconomics，2009，118：322-330.

[9]Feng Y，Viswanathan S.A new lot-sizing heuristic for manufacturing systems with product recovery[J].Production Economics，2011，133：432-438.

[10]Maxwell W L，Singh H.The effect of restricting cycle times in the economic lot scheduling problem[J].IIE Transactions，1983，15（3）：235-241.

[11]Fujita S.The application of marginal analysis to the economic lot size scheduling problem[J].AIIE Transactions，1978，10：354-361.

[12]Sun H，Huang H C，Jaruphongsa W.A genetic algorithm for the economic lot scheduling problem under the extended basic period and power-of-two policy[J].CIRP Journal of Manufacturing Science and Technology，2009，2：29-34.

[13]Chatfield D C.The economic lot scheduling problem：a pure genetic search approach[J].Computers and Operations Research，2007，34：2865-2881.

SHU Manli,XU Kelin,ZHENG Yongqian

School of Mechanical Engineering,Tongji University,Shanghai 201804,China

For the economic lot scheduling problem of a hybrid production line,the ELSPR considering recycling of old product with stochastic return rate is studied.A model under the extended basic period approach is formulated to get minimum total unit cost,in which manufactured and remanufactured products are simultaneously sequenced.A Heuristic Genetic Algorithm（HGA）is proposed,which can effectively get rid of infeasible solutions caused by schedule intersection and capacity restriction.The solution results of Teunter and HGA are compared whether or not considering disposal.The contrast shows the proposed HGA can further reduce costs and ensure the optimal solution feasible.

economic lot scheduling problem;remanufacturing;returns;disposal

針對存在于制造、再造混合生產系統的批量調度問題，研究舊產品回收率隨機的情況下，考慮舊產品回收的多產品經濟批量調度問題。基于擴展基本時段法綜合考慮制造新品和再造產品的批量調度，構建以單位總成本最小為目標的優化模型。提出的改進型遺傳算法對模型求解，能避免不可行解的產生。分別比較考慮和不考慮舊產品廢棄處置兩種情況下，該算法和Teunter方法的優化效果，結果表明提出的算法能進一步降低成本并保證最優解可行。

經濟批量調度問題；再制造；產品回收；廢棄處置

A

TP278

10.3778/j.issn.1002-8331.1301-0139

SHU Manli,XU Kelin,ZHENG Yongqian.ELSPR with stochastic return rate under the extended basic period approach. Computer Engineering and Applications,2013,49（13）：216-220.

國家自然科學基金（No.61273035，No.71071115）；國家高技術研究發展計劃（863）（No.2009AA043000）。

舒曼莉（1988—），女，碩士研究生，主要研究領域為再制造系統庫存與調度管理；徐克林（1945—），女，教授，博導，主要研究領域為供應鏈管理；鄭永前（1965—），男，副教授，碩導，主要研究領域為生產系統工程與管理。E-mail：shumanli@163.com

2013-01-14

2013-03-02

1002-8331（2013）13-0216-05