東 博，朱小林

(上海海事大學(xué)物流研究中心， 上海201306)

?

基于遺傳算法的多階段動態(tài)批量生產(chǎn)問題研究

東 博，朱小林

(上海海事大學(xué)物流研究中心， 上海201306)

在生產(chǎn)系統(tǒng)的供應(yīng)鏈中，有已有制造線和再制造線兩個階段，合理安排兩個階段的生產(chǎn)計劃是實現(xiàn)成本最小化的關(guān)鍵?？紤]庫存費用、制造全新產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量的因素下，建立面向再制造線和已有制造線兩階段的動態(tài)批量生產(chǎn)成本優(yōu)化模型，針對這一模型設(shè)計了自適應(yīng)遺傳算法并結(jié)合實際案例對問題求解，給出了合理的生產(chǎn)計劃，實驗表明:該遺傳算法對解決多產(chǎn)品的動態(tài)批量問題有良好效果。

再制造；動態(tài)批量生產(chǎn)；自適應(yīng)遺傳算法

0 引 言

隨著社會的發(fā)展，人們的環(huán)境意識越來越高，環(huán)境保護(hù)政策也頒布了許多。很多企業(yè)通過產(chǎn)品回收這一過程，來降低產(chǎn)品對環(huán)境造成的破壞；另外，考慮到經(jīng)濟(jì)性，越來越多的企業(yè)在參與產(chǎn)品回收過程中，對回收產(chǎn)品進(jìn)行再制造，獲得額外價值以及更高的利潤。在整個供應(yīng)鏈里，再制造就是一項回收活動，對回收的產(chǎn)品重新利用或者重新制造，可以得到與新產(chǎn)品相同性能的再制造產(chǎn)品，這些產(chǎn)品同樣可以滿足客戶的需求，這樣不但降低制造成本還獲得比較豐厚的利潤。

但是對于企業(yè)來講，將現(xiàn)有的生產(chǎn)系統(tǒng)和再制造進(jìn)行結(jié)合，最關(guān)鍵的是獲得最大利潤。

文獻(xiàn)[1]中以前研究生產(chǎn)問題時，沒有考慮過產(chǎn)品回收這一項，而現(xiàn)在很多研究人員開始考慮了產(chǎn)品回收這一項，并將此項和整個生產(chǎn)計劃進(jìn)行結(jié)合；

文獻(xiàn)[2]中學(xué)者Schrady針對經(jīng)典EOQ模型稍微進(jìn)行了改進(jìn)，在此模型中將產(chǎn)品回收考慮了進(jìn)去，但是文獻(xiàn)沒有考慮到批量問題；

文獻(xiàn)[3～5]對Schrady的模型進(jìn)行了再次擴(kuò)展，這次考慮了采購和回收批量問題；

文獻(xiàn)[6]不再假設(shè)連續(xù)回收處理條件，研究產(chǎn)品回收只在一定期限內(nèi)發(fā)生的經(jīng)濟(jì)批量問題；

文獻(xiàn)[7]和文獻(xiàn)[8]利用現(xiàn)有數(shù)學(xué)模型對多產(chǎn)品生產(chǎn)以及再制造經(jīng)濟(jì)生產(chǎn)問題進(jìn)行了研究；

文獻(xiàn)[9]在總結(jié)供應(yīng)商選擇準(zhǔn)則方法等相關(guān)研究成果的基礎(chǔ)上,以模糊理論為依托,從定量的角度分別研究了在包含模糊和隨機(jī)信息、存在供應(yīng)中斷、折扣價格條件下的供應(yīng)商選擇及訂單分配問題；

文獻(xiàn)[8～12]針對再制造產(chǎn)品和新產(chǎn)品同時滿足需求的生產(chǎn)批量問題，在條件有限時間內(nèi)需求和退貨量一定的情況下，建立了目標(biāo)為成本最小的模型；

文獻(xiàn)[13]針對在需求已知并且動態(tài)，且時間段有限的條件下安排生產(chǎn)，提出了多階段的多目標(biāo)函數(shù)，在求解過程中引進(jìn)VND進(jìn)行求解，并且在求解的過程中討論了不同個數(shù)可變領(lǐng)域?qū)Y(jié)果優(yōu)劣性的影響，并在最后與前學(xué)者所提出的Gurobi算法進(jìn)行對比，驗證了VND的有效性；

文獻(xiàn)[14]中做了一項調(diào)查，關(guān)于美國再制造企業(yè)中，影響生產(chǎn)計劃和控制活動的因素有7個，主要有回收物流時間和數(shù)量上的不確定性、回收物流和產(chǎn)品需求難以一致性、拆卸、物流修復(fù)不確定性、逆向物流、物料匹配要求以及產(chǎn)品加工時間不確定性；

文獻(xiàn)[15]運用Wagner/Whitin算法證明了再制造生產(chǎn)計劃模型存在零庫存性質(zhì)；

文獻(xiàn)[16～18]通過利用前人的研究，推廣和應(yīng)用了Wagner/Whitin算法，解決現(xiàn)有制造和再制造的混合系統(tǒng)生產(chǎn)問題，并還解決基于動態(tài)規(guī)劃的精確多項式優(yōu)化問題。文獻(xiàn)[6～17]將線性規(guī)劃方法應(yīng)用于確定型閉環(huán)供應(yīng)鏈生產(chǎn)計劃中。

然而，以往的多數(shù)文獻(xiàn)要不只考慮現(xiàn)存制造線，要不只考慮了再制造線并提出相關(guān)模型和算法，只有少數(shù)文獻(xiàn)中同時考慮到再制造和現(xiàn)存制造兩個階段，而本文既考慮了再制造線也考慮到現(xiàn)存制造線，合理安排這兩個階段，在庫存費用、制造全新產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量的因素下，建立動態(tài)批量生產(chǎn)成本優(yōu)化模型，設(shè)計自適應(yīng)遺傳算法，結(jié)合實際案例求解，給出兩個階段的生產(chǎn)計劃，這對以后研究這方面工作有一定的借鑒作用。

1 問題描述

在本文中，主要研究的是動態(tài)批量生產(chǎn)問題。在滿足制造商生產(chǎn)計劃條件下，制造商合理安排生產(chǎn)計劃，從而減少制造成本和庫存費用。其中，在制造商作生產(chǎn)計劃時考慮了制造全新產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量。

在不確定環(huán)境下優(yōu)化制造商生產(chǎn)計劃安排中，制造商需要做兩種類型的決策：第一，是否建立制造線和再制造線被視為戰(zhàn)略決策;第二，制造全新產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量被視為戰(zhàn)術(shù)決策。主要可描述為制造商根據(jù)每階段市場需求生產(chǎn)產(chǎn)品，產(chǎn)品來源一部分來自制造線生產(chǎn)，另一部分來自再制造線生產(chǎn)。如果制造商制造的全新產(chǎn)品和再制造產(chǎn)品這兩個來源缺乏合理協(xié)調(diào)會最終影響制造商生產(chǎn)計劃以及不滿足市場需求最終導(dǎo)致經(jīng)濟(jì)損失。如圖1所示，制造商根據(jù)實際情況決定是否建立制造線和再制造線。

圖1 動態(tài)批量生產(chǎn)流程圖

2 模型建立

本文討論的問題是在滿足各時期需求時制造商成本最低。每一個階段市場需求是已知的，由新產(chǎn)品和再制造產(chǎn)品滿足，也知道所有周期的返回產(chǎn)品的數(shù)目，并假定是不固定的。回收的產(chǎn)品能夠被再制造成新的產(chǎn)品，和新產(chǎn)品并無區(qū)別。

本節(jié)研究問題包括是否建立全新產(chǎn)品制造線和再制造產(chǎn)品制造線的多產(chǎn)品動態(tài)批量問題。所建立的模型是在以Sahling模型基礎(chǔ)上建立的，其目的是確定制造和再制造在每個階段生產(chǎn)的數(shù)量，為了盡可能減少建立制造線和再制造線以及所需要的設(shè)備花費的成本。

2.1 符號說明

k:生產(chǎn)數(shù)量，k=1,2,…,K;

t:生產(chǎn)階段，t=1,2,…,T;

D(k,t):每個階段t所需要的產(chǎn)品數(shù)量k;

R(k,t):每個階段t可以被回收的產(chǎn)品數(shù)量k，并可以從新被再制造成新的產(chǎn)品;

hM(k):在每階段每保存一單位的全新產(chǎn)品k的庫存費用;

hR(k):在每階段每保存一單位的再制造產(chǎn)品k的庫存費用;

xM(k,t):在階段t被生產(chǎn)的全新產(chǎn)品數(shù)量k；

xR(k,t):在階段t被生產(chǎn)的再制造產(chǎn)品數(shù)量k；

kM(k):建立一條全新生產(chǎn)線的成本;

kR(k):建立一條再制造生產(chǎn)線的成本;

pM(k):生產(chǎn)一單位全新產(chǎn)成品的成本;

pR(k):生產(chǎn)一單位再制造產(chǎn)成品的成本;

yM(k,t):在每個階段可以被存儲的全新產(chǎn)品數(shù)量;

yR(k,t):在每個階段可以被存儲的再制造產(chǎn)品數(shù)量;

M:一個很大的數(shù)字;

k1:制造商每階段可以儲存的最大全新產(chǎn)品數(shù)量；

k2:制造商每階段可以儲存的最大再制造產(chǎn)品數(shù)量；

k3:制造商每階段可以最多生產(chǎn)全新產(chǎn)品數(shù)量；

k4:制造商每階段可以最多生產(chǎn)再制造產(chǎn)品數(shù)量；

2.2 模型建立

(1)

s.t.yR(k,t)=yR(k,t-1)+R(k,t)-xR(k,t), ?t=1,2,…，T,?k=1,2,…,K,

(2)

yM(k,t)=yM(k,t-1)+xR(k,t)+xM(k,t)-D(k,t), ?t=1,2，…，T,?k=1,2,…,K,

(3)

(4)

(5)

xR(k,t)+xM(k,t)≥D(k,t),

(6)

yM(k,t)≤k1,

(7)

yR(k,t)≤k2,

(8)

XM(k,t)≤k3,

(9)

XR(k,t)≤k4,

(10)

xR(k,t)≤MzR(k,t), ?t=1,2,…,T,?k=1,2,…,K,

(11)

xM(k,t)≤MzM(k,t), ?t=1,2,…,T,?k=1,2,…,K,

(12)

(13)

yR(k,0)=yM(k,0)=0, ?k=1,2,…,K。

(14)

目標(biāo)函數(shù)(1)表示制造商根據(jù)每階段市場需求安排生產(chǎn)使其最后總成本最低；式(2)表示制造全新產(chǎn)品時每階段庫存等式關(guān)系；式(3)表示再制造產(chǎn)品每階段庫存等式關(guān)系；式(6)各階段制造產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量要滿足市場各階段需求；式(7)制造商每階段可以儲存全新產(chǎn)品的最大數(shù)量；式(8)制造商每階段可以儲存的最大再制造產(chǎn)品數(shù)量；式(9)制造商每階段最多可以生產(chǎn)的全新產(chǎn)品數(shù)量；式(10) 制造商每階段最多可以生產(chǎn)的再制造產(chǎn)品數(shù)量；式(11)和式(12)表示當(dāng)設(shè)置生產(chǎn)全新產(chǎn)品線和再制造線時固定成本；式(13)和式(14)表示參數(shù)和決策變量非負(fù)。

3 算法求解

通過采用自適應(yīng)遺傳算法解決本文所研究的動態(tài)批量生產(chǎn)問題。

此算法采用全局搜索技術(shù)，起初生成多個生產(chǎn)方案，但這些方案不是最優(yōu)方案，要根據(jù)所創(chuàng)建適應(yīng)值的大小來進(jìn)行排序，然后通過自適應(yīng)遺傳算法的一系列(選擇、交叉、變異)過程，獲得最優(yōu)解。這種操作達(dá)到最大迭代代數(shù)為止。

3.1 初始種群生成

初始種群生成是以基因編碼為基礎(chǔ)，基因是染色體的單位，而一個染色體由若干基因組成。對于多階段多產(chǎn)品動態(tài)生產(chǎn)問題的設(shè)計，一個染色體就表示一個生產(chǎn)方案。為了增加種群的多樣性，本節(jié)隨機(jī)生成初始化種群，檢驗初始化種群中每一個個體是否滿足約束條件，去除不滿足約束條件的個體，一直到初始種群個體達(dá)到N為止。

圖2 基于遺傳算法的生產(chǎn)方案優(yōu)化求解策略

基于本文研究的問題是多階段多產(chǎn)品動態(tài)生產(chǎn)問題，在本節(jié)的研究中產(chǎn)品的來源涉及到兩方面，一方面是建立全新產(chǎn)品線生產(chǎn)全新產(chǎn)品，一方面是建立再制造線，生產(chǎn)再制造產(chǎn)品，根據(jù)市場的需求，每階段產(chǎn)品的生產(chǎn)量(全新產(chǎn)品與再制造產(chǎn)品)要大于等于每階段的需求量，鑒于問題的復(fù)雜性，本節(jié)設(shè)計2層整數(shù)編碼方式。第一層代表全新產(chǎn)品線所制造的產(chǎn)品數(shù)量，第二層代表再制造線制造的產(chǎn)品數(shù)量。見圖3所示。

圖3 編碼

3.2 適應(yīng)值

適應(yīng)值是用來檢測一個特定的染色體所表示的方案的優(yōu)劣性，本文采用目標(biāo)函數(shù)作為染色體的適應(yīng)值。

3.3 遺傳操作

①選擇

從生成出來的種群中選取適應(yīng)值高的染色體的行為叫選擇，將適應(yīng)度值高的前20%染色體復(fù)制到下一代和父代染色體組成新的染色體種群。通過該機(jī)制確保每代優(yōu)秀個體不會在種群進(jìn)化過程中丟失，確保優(yōu)秀個體進(jìn)入下一代，并且可以保證下一代種群中的最優(yōu)個體不會比上一代差。

②交叉

交叉操作可以讓優(yōu)良的染色體從父代遺傳到子代，所以交叉是此算法的一個關(guān)鍵操作，同時本節(jié)采用多層多點交叉法。具體方法如圖4所示。

隨機(jī)的選擇兩個父代p1，p2，交換切點位置上的基因值，若重新生成的染色體合法，則得到子代染色體c1、c2，若重新生成的染色體不滿足約束條件則該子代染色體不合法，則對該子代染色體進(jìn)行修復(fù)，應(yīng)對策略為拒絕交叉。

圖4 染色體交叉(黑白色)

③突變

突變就是由于各種原因引起遺傳基因發(fā)生了改變。突變可以增加基因的多樣性，使算法避免早熟。在第一層選中2個切點，在第二層選中2個切點，交換他們彼此的基因值。若編碼合法，則生成子代染色體c1，見圖5，若生成的子代染色體不滿足約束條件則該染色體不合法，則對該子代染色體進(jìn)行修復(fù)，應(yīng)對策略為拒絕變異。

圖5 變異

④交叉和突變概率

交叉概率pc和變異概率pm在遺傳算法過程中起著重要的作用，相對于傳統(tǒng)遺傳算法，AGA首先判斷種群代數(shù)，其次判斷f與fave的大小，其特點為交叉和變異概率隨著個體適應(yīng)度、迭代代數(shù)的改變而改變。fmax為群體中最大的個體適應(yīng)度值；f為要變異個體的適應(yīng)度值，fave為每代群體的平均適應(yīng)度值；x為當(dāng)前迭代代數(shù)。N為迭代總代數(shù)。

(15)

(16)

在交叉過程中，適應(yīng)度高的染色體有更多機(jī)會產(chǎn)生新染色體，而當(dāng)進(jìn)化趨于穩(wěn)定時，交叉的概率就會減少；即pc隨著迭代代數(shù)增大而減少，pm也隨著迭代代數(shù)增大而減少，此時適應(yīng)值高的染色體會被保護(hù)起來；但是對于低于平均適應(yīng)值的染色體要盡量通過突變來擊破它，讓它進(jìn)行變化。

4 設(shè)計實例

某一制造企業(yè)每年生產(chǎn)10個月，每個月由于季節(jié)問題以及市場需求，所生產(chǎn)的產(chǎn)品數(shù)量是動態(tài)不確定的，制造企業(yè)為了滿足市場需求，產(chǎn)品來源一部分是生產(chǎn)全新產(chǎn)品，一部分來自回收產(chǎn)品的再制造，每個月回收產(chǎn)品的數(shù)量見表1所示。儲存一單位的hR(k)={0.2,0.5,0.8}，建立制造線成本kR(k)={200,500,2 000}，建立再制造成本kM(k)={200,500,2 000}。每個階段的回收量服從均勻分布U(0,100)中生成，制造商每個階段生產(chǎn)產(chǎn)品數(shù)量服從均勻分布U(0,1 000)。參數(shù)Popsize=100，最大迭代代數(shù)maxgen=500，pc、pm如上文所示。采用MATLAB語言編程實現(xiàn)算法開發(fā)。

表1 每個階段需求量

5 結(jié)果分析

根據(jù)上述設(shè)置的遺傳算法參數(shù)和求解步驟，利用自適應(yīng)遺傳算法對模型進(jìn)行求解。制造商安排生產(chǎn)計劃，分別針對不同儲存單位hR(k)，建造制造線成本kR(k)，建造在制造線成本kM(K)有以下3種情況，見表2，通過Matlab計算分別可以獲得它們的利潤，并做出收斂圖(圖6)進(jìn)行對比得到結(jié)論。

表2 制造商安排生產(chǎn)計劃

圖6 遺傳算法收斂圖

Fig.6 Genetic algorithm converges

6 結(jié) 語

在本文中，筆者已經(jīng)解決了多產(chǎn)品的動態(tài)批量問題，產(chǎn)品回收和回收的逆向物流。在制造商、生產(chǎn)商作生產(chǎn)計劃時，考慮回收產(chǎn)品對生產(chǎn)計劃的影響，在建立約束條件時考慮庫存費用以及生產(chǎn)控制合理安排生產(chǎn)全新產(chǎn)品數(shù)量和再制造產(chǎn)品數(shù)量，最后根據(jù)實際的企業(yè)生產(chǎn)控制計劃提出了制造業(yè)成本最低的數(shù)學(xué)優(yōu)化模型，假設(shè)了實例數(shù)據(jù)，采用遺傳算法對該模型進(jìn)行開發(fā)，并給出了合理的優(yōu)化設(shè)計方案，實驗表明，該遺傳算法對解決多產(chǎn)品的動態(tài)批量問題有良好效果。

雖然本文對多產(chǎn)品的動態(tài)批量問題建立了相應(yīng)的模型，并運用遺傳算法求得最佳生產(chǎn)控制計劃。但是在實際的多產(chǎn)品的動態(tài)批量問題中復(fù)雜程度遠(yuǎn)遠(yuǎn)大于理想狀態(tài)，在實際生產(chǎn)過程中，還有許多因素需要考慮，例如回收產(chǎn)品價格的變化、原材料價格變化等。而這種擴(kuò)展模型可以更切近實際問題，這將會成為今后研究的重點。

[1] SHORROCK B, ORLICKY J.Material requirements planning[J]. Encyclopedia of Operations Research & Management Science, 2009, 86(6):283-294.

[2] SCHRADY D A.A deterministic inventory model for repairable items[J]. Naval Research Logistics Quarterly, 1967,14(3):391-398.

[3] RCHTER K.An EOQ repair and waste disposal model[C]//Proceedings of the Eighth International Working Seminar on Production Economics. Austria: Innsbruck, 1994：83-91.

[4] RICHTER K.The EOQ repair and waste disposal model with variable setup numbers[J]. European Journal of Operational Research, 1996, 95(2):313-324.

[5] RICHTER K.Pure and mixed strategies for the EOQ repair and waste disposal problem[J]. Operations Research-Spektrum, 1997, 19(19):123-129.

[6] TEUNTER R H.Economic ordering quantities for recoverable item inventory systems[J]. Naval Research Logistics, 2001, 48(6):484-495.

[7] TANG O, RUUD T.Economic lot scheduling problem with returns[J]. Production & Operations Management, 2006, 15(4):488-497.

[8] 史玉雷，陸志強(qiáng).基于供應(yīng)商經(jīng)濟(jì)生產(chǎn)批量的供應(yīng)鏈訂單分配問題[J]. 上海交通大學(xué)學(xué)報, 2011, 45(12):1747-1752.

[9] 何東.L公司的多供給源選擇與訂貨量分配研究[D]. 成都：電子科技大學(xué), 2009.

[10]GUIDERJR V D R, JAYARAMAN V, SRIVASTAVA R.Production planning and control for remanufactureing: astate-of-art survey[J]. Robotics and Computer-Integrated Manufacturing, 1999,15(3):221-230.

[11]RICHTER K, SOMBRUTZKI M.Remanufacturing planning for the reverse Wagner/Within models[J]. European Journal of Operational Research, 2000,121(2):304-315.

[12]TEUNTER R H, BAYINDIR Z P, HEUVEL W V D.Dynamic lot sizing with product returns and remanufacturing[J]. International Journal of Production Research, 2006,44(20):4377-4400.

[13]GOLANY B, YANG J, YU G.Economic lot-sizing with remanufacturing options[J]. IIE Transactions,2001,33(11):995-1003.

[14]CLEGG A J, WILLIAMS D J, UZSOY R.Production planning for companies with remanufacturing capability[C]//Proceedings of the 1995 IEEE International Symposium on Electronics and the Environment. US: IEEE Service Center, 1995:186-191.

[15]JAYARAMAN V.Production planning for closed-loop supply chains with product recovery and reuse: An analytical approach[J]. International Journal of Production Research, 2006,44(5):981-998.

[16]WU Q H,CAO Y J,WEN J Y.Optimal reactive power dispatch using an adaptive genetic algorithm[J]. Electrical Power & Energy Systems,1998,20(8):563-569

(責(zé)任編輯 梁碧芬)

Research on multistage dynamic batch production problem based on genetic algorithm

DONG Bo, ZHU Xiao-lin

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China)

In the supply chain of production system, there are two stages including already manufacturing line and re-manufacturing line. Reasonable arrangement for the production plans of the two-stage is a key to minimize costs. Considering the factors, such as the cost of inventory, the number of new product manufacturing and the remanufacturing quantity of product, a dynamic batch production cost optimization model for the two-stage manufacturing line is designed. The adaptive genetic algorithm associated with the model is also given, which gives the reasonable production plan in practical cases. The given experiments show that the genetic algorithm is good for solving the problem of dynamic multi-product batch production.

remanufacturing; dynamic mass production; adaptive genetic algorithm

2016-05-07；

2016-06-22

國家自然科學(xué)基金資助項目(11301334);上海市科委重點項目(12510501700)

朱小林(1975—)，男，湖南人，上海海事大學(xué)副教授;E-mail:zhuxl@shmtu.edu.cn。

東博，朱小林.基于遺傳算法的多階段動態(tài)批量生產(chǎn)問題研究[J].廣西大學(xué)學(xué)報(自然科學(xué)版)，2016，41(5)：1594-1602.

10.13624/j.cnki.issn.1001-7445.2016.1594

F9; TP301.6

A

1001-7445(2016)05-1594-09