舒曼莉,徐克林,鄭永前
同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院,上海 201804
基于擴(kuò)展基本時(shí)段法的隨機(jī)回收率ELSPR
舒曼莉,徐克林,鄭永前
同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院,上海 201804
再制造中的豐厚利潤(rùn),讓許多制造企業(yè)紛紛進(jìn)入再制造市場(chǎng)。再制造市場(chǎng)上的產(chǎn)品,一些再造品價(jià)值低于制造新品,比如汽車發(fā)動(dòng)機(jī)、復(fù)印機(jī)等;另一些再造品,例如一次性相機(jī)、托盤、集裝箱等的再造品與制造新品有相同價(jià)值。合理調(diào)度產(chǎn)品生產(chǎn)順序和批量成為有效減少總生產(chǎn)成本的關(guān)鍵,即經(jīng)濟(jì)批量調(diào)度問題,Hsu證明經(jīng)濟(jì)批量調(diào)度問題是NP-Hard問題[1]。在考慮再造的經(jīng)濟(jì)批量調(diào)度中,需同時(shí)調(diào)度制造和再造批量以滿足需求,并考慮兩種庫(kù)存成本,問題更復(fù)雜,求解可行域更小。針對(duì)再造品和制造新品有同等價(jià)值的情況,如何調(diào)度產(chǎn)品生產(chǎn)批量,包括制造批量和再造批量,從而減少總成本這一問題成為研究熱點(diǎn)。
經(jīng)濟(jì)批量調(diào)度問題最初由Rogers提出,其研究調(diào)度產(chǎn)品生產(chǎn)順序和批量以使成本最低[2]。Davis提出混合整數(shù)規(guī)劃方法求解,可得最優(yōu)解,但隨問題規(guī)模的擴(kuò)大,求解時(shí)間激增[3]。Raza和Akgunduz基于批量變動(dòng)法利用模擬退火方法求解,大幅度縮短求解時(shí)間,但隨問題規(guī)模擴(kuò)大,所得解與最優(yōu)解誤差增加[4]。Zanoni等采用基本時(shí)段法求解,其優(yōu)化結(jié)果較之前研究更優(yōu),計(jì)算時(shí)間比文獻(xiàn)[3]大幅降低,但該算法不能保證所得解可行[5]。結(jié)合實(shí)際生產(chǎn)情況,Tang和Teunter首次研究考慮舊產(chǎn)品回收的經(jīng)濟(jì)批量調(diào)度問題(Economic Lot Scheduling Problem with Returns,ELSPR),并提出復(fù)雜算法求解,結(jié)果表明其方法能有效減少成本[6]。文獻(xiàn)[7]在兩條生產(chǎn)線上分別進(jìn)行制造和再造的情況,雖多啟用一條生產(chǎn)線,但總成本減少量足以抵消新開生產(chǎn)線的成本增加量。由于ESLPR的混合整數(shù)規(guī)劃求解方法過于復(fù)雜,基于公共周期法,Teunter提出啟發(fā)式算法求解,能有效降低部分總成本,但該方法僅對(duì)產(chǎn)品生產(chǎn)率小于50%的情況適用[8]。Feng基于公共周期法建模,假設(shè)產(chǎn)品的制造次數(shù)和再造次數(shù)之比為M/R,M和R不同為1,提出啟發(fā)式算法求解,其假設(shè)更接近實(shí)際,但所提算法過于復(fù)雜,難以推廣[9]。以上研究雖考慮問題時(shí)更結(jié)合實(shí)際,但求解方法仍不理想,或無法求得最優(yōu)解,或所得解不可行。因此,目前的研究仍延續(xù)貼合實(shí)際的趨勢(shì),找尋較優(yōu)求解方法以快速求得最優(yōu)并可行的解。
ELSPR求解方法有:公共周期法、基本時(shí)段法和批量變動(dòng)法。公共周期法限定產(chǎn)品生產(chǎn)周期均相同,只要存在可行調(diào)度,該方法一定能得到可行解,簡(jiǎn)單易行,但所得解通常較最優(yōu)解誤差大。批量變動(dòng)法假設(shè)產(chǎn)品可在一個(gè)周期內(nèi)生產(chǎn)多次,但不易求解同時(shí)考慮制造和再造批次的ELSPR。除文獻(xiàn)[5]外,研究者均采用公共周期法,雖簡(jiǎn)單易行,但優(yōu)化效果差,故本文采用擴(kuò)展基本時(shí)段法(Extended Basic Period Approach,EBP)。該方法放寬了對(duì)周期的限制,所得解優(yōu)于公共周期法,但其難以保證收斂到可行解。不可行解出現(xiàn)的原因:一是超出能力限制,即基本時(shí)段內(nèi)需生產(chǎn)產(chǎn)品超出設(shè)備生產(chǎn)能力;二是排序不當(dāng)造成產(chǎn)品生產(chǎn)時(shí)間沖突,即同一時(shí)刻需設(shè)備生產(chǎn)兩個(gè)或以上產(chǎn)品。本文提出啟發(fā)式遺傳算法,避免由生產(chǎn)時(shí)間沖突造成的不可行解,對(duì)超出能力限制所得不可行解賦予懲罰函數(shù),讓其受遺傳壓力被淘汰,在得到可行解的前提下將問題收斂到最優(yōu)解。
針對(duì)現(xiàn)實(shí)企業(yè)的生產(chǎn)特點(diǎn)(由于生產(chǎn)能力的限制和降低庫(kù)存成本等原因,會(huì)售出部分舊產(chǎn)品以立刻獲取利潤(rùn)),本文假設(shè)回收舊產(chǎn)品都可能存在一定的處置率,即立刻賣出舊產(chǎn)品獲取相應(yīng)利潤(rùn)。同時(shí),為更符合實(shí)際,將舊產(chǎn)品回收率設(shè)為隨機(jī),建立基于擴(kuò)展基本時(shí)段法和隨機(jī)回收率的經(jīng)濟(jì)批量調(diào)度模型,為避免擴(kuò)展基本時(shí)段法造成的不可行解,提出啟發(fā)式遺傳算法,使得求解過程更為快速,并保證所得解可行。
2.1 隨機(jī)回收率的ELSPR問題描述
考慮舊產(chǎn)品回收的經(jīng)濟(jì)批量調(diào)度問題描述為:?jiǎn)我辉O(shè)備或者生產(chǎn)線可制造/再造N種產(chǎn)品,每種產(chǎn)品的制造/再造速度和需求速度Di已知;設(shè)備在任一時(shí)刻只能生產(chǎn)一個(gè)產(chǎn)品,轉(zhuǎn)換為制造/再造另一種產(chǎn)品時(shí)花費(fèi)一定換模成本和時(shí)間;產(chǎn)品的制造/再造單位成本和生產(chǎn)型產(chǎn)品/舊產(chǎn)品庫(kù)存費(fèi)率均已知;舊產(chǎn)品回收率βi隨機(jī);舊產(chǎn)品的處置費(fèi)用Vd已知,舊產(chǎn)品處置是賣出獲利,Vd小于零;假定計(jì)劃期連續(xù)、無限,如何調(diào)度舊產(chǎn)品再造率αi和產(chǎn)品制造/再造時(shí)刻,使得使得生產(chǎn)周期Ti內(nèi)單位總成本最小。
圖1表示存在舊產(chǎn)品回收的混合生產(chǎn)系統(tǒng)結(jié)構(gòu)。其中,舊產(chǎn)品庫(kù)存存放回收舊產(chǎn)品,生產(chǎn)型產(chǎn)品庫(kù)存存放制造新品和再造產(chǎn)品。其余假設(shè)如下:
(1)舊產(chǎn)品回收速度βi服從參數(shù)為λi的指數(shù)分布;
(3)產(chǎn)品在各自生產(chǎn)周期內(nèi)只制造和再造各一次;
(4)再造產(chǎn)品和制造新品均能用于滿足需求;
(5)生產(chǎn)過程中不允許缺貨;
(6)舊產(chǎn)品有一定再造率αi,未再造舊產(chǎn)品被售出。
圖1 制造/再造混合系統(tǒng)結(jié)構(gòu)圖
2.2 基于EBP和隨機(jī)回收率ELSPR的模型
擴(kuò)展基本時(shí)段法假設(shè)每種產(chǎn)品有各自生產(chǎn)周期,產(chǎn)品i生產(chǎn)周期Ti是某基本時(shí)段B的2的冪次方倍(PoT策略,Power of Two),即Ti=kiB,ki為乘子。總生產(chǎn)周期Ttoatal即所有Ti的最小公倍數(shù),Ttoatal=kmaxB。PoT策略使得求解過程更容易得到可行解,Maxwell和Singh證明使用PoT策略,求解結(jié)果誤差不超過6%[10]。
理想情況下,即生產(chǎn)型庫(kù)存為0時(shí),系統(tǒng)開始制造/再造。此時(shí),理想單位總成本IC包括換模成本Cs、生產(chǎn)(制造/再造)成本Cp、舊產(chǎn)品處置成本Cd、舊產(chǎn)品庫(kù)存成本Chr,以及生產(chǎn)型產(chǎn)品庫(kù)存成本Chs:
上述模型中,式(2)表示Ti內(nèi)單位換膜成本,包括制造和再造換膜成本;式(3)表示Ti內(nèi)單位生產(chǎn)成本,其中Diαiβi和Di(1-αiβi)分別表示產(chǎn)品i在Ti內(nèi)單位再造和制造量;式(4)表示Ti內(nèi)單位處置成本,βi(1-αi)Di表示Ti內(nèi)單位處置舊產(chǎn)品量;式(5)表示Ti內(nèi)舊產(chǎn)品單位庫(kù)存成本,αiβiDi和-αiβiDi分別表示(0~t1),(t1~Ti)中產(chǎn)品庫(kù)存增長(zhǎng)率,表示舊產(chǎn)品庫(kù)存量,如圖2中陰影部分所示,其中f(βi)為舊產(chǎn)品回收率βi服從分布函數(shù);式(6)表示Ti內(nèi)生
圖2 舊產(chǎn)品庫(kù)存量
圖3 生產(chǎn)型產(chǎn)品庫(kù)存量
實(shí)際生產(chǎn)中,存在非理想情況,即生產(chǎn)型庫(kù)存不為0時(shí)系統(tǒng)開始制造/再造,產(chǎn)生額外成本:
式(7)表示兩種非理性情況下的額外成本,如圖4、5所示,圖中陰影部分表示額外成本。式(8)、(9)中表 f(x)有:有:[z]+=max{z,0}, [z]-=max{-z,0}。示產(chǎn)品i的實(shí)際制造時(shí)間,Ti(1-βi)表示理想制造時(shí)間。對(duì)
圖4 f(-)>T(1-βi)條件下額外成本
圖5 f(-)<T(1-βi)條件下額外成本
故目標(biāo)函數(shù)為:
式(11)、(12)為約束條件,保證調(diào)度滿足設(shè)備產(chǎn)能限制,即換模和生產(chǎn)時(shí)間之和不超過基本時(shí)段。
遺傳算法(Genetic Algorithm)是模擬達(dá)爾文生物進(jìn)化論自然選擇和遺傳學(xué)機(jī)理生物進(jìn)化過程的計(jì)算方法,是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。Fujita首次運(yùn)用遺傳算法求解ELSP,發(fā)現(xiàn)該問題適合用遺傳算法求解[11]。
實(shí)數(shù)編碼,基因串中分別包含基本時(shí)段B,舊產(chǎn)品再造率α,以及乘子k。規(guī)模為n的問題,染色體長(zhǎng)為2n+1。BUB為該問題用公共周期法所得周期TC,BUB=TC,BLB為該問題用IS(Independent Solution)法求解時(shí)所得最小Ti,即BLB=Timin。α由定義可知α∈[0,1]。對(duì)乘子k,ki=2ai,ai=0,1, 2,…;=1;根據(jù)Hainan Sun[12]可知:
適應(yīng)度函數(shù),遺傳過程中不符合約束(11)、(12)的解賦予懲罰函數(shù)而不丟棄,增加種群多樣性,避免早熟。fitnessj=Fj+,F(xiàn)j表示目標(biāo)函數(shù)值,表示相應(yīng)懲罰函數(shù),t為遺傳代數(shù)。其中:
表示制造/再造過程中實(shí)際生產(chǎn)時(shí)間超過基本時(shí)段B的量,將解的不可行程度量化,不可行程度越高,懲罰函數(shù)就越大。初始種群,使用啟發(fā)式規(guī)則生成初始種群,避免因生產(chǎn)時(shí)間沖突造成的不可行解:
步驟1根據(jù)初始種群中的B以及ki,有Ti=kiB;
步驟3按-+Ti(1-αiβi)下降順序,排序所有再造批次,時(shí)間間隔
步驟4依次比較再造批次中相鄰批次,交換順序并比較目標(biāo)函數(shù)F是否降低,若降低,則交換兩個(gè)批次;
步驟5計(jì)算末尾再造批次結(jié)束時(shí)間Tter以及總周期Ttoatal=kmaxB,總松弛時(shí)間為Tslack=Ttotal-Tter;
步驟6對(duì)滿足的產(chǎn)品的再造批次前加入松弛,直至滿足-=Ti(1-αiβi)或所有的松弛時(shí)間Tslack已分配完。
遺傳操作,在“選擇復(fù)制”中采用輪盤賭結(jié)合精英策略,選取父代中適應(yīng)度函數(shù)最小的10%復(fù)制得到子代,余下90%子代采用輪盤賭方法在父代中選取。在“交叉”中采用均勻交叉,掩碼是隨機(jī)產(chǎn)生的二進(jìn)制串。若掩碼為1,則子1基因點(diǎn)獲取父1的基因信息,子2獲取父2的;若掩碼為0,則子1獲取父2的基因信息,子2則獲取父1的,如圖6所示。“變異”為多點(diǎn)變異,染色體中每段均給予一定變異幾率,變異點(diǎn)隨機(jī)產(chǎn)生,該基因位上的數(shù)值由另一個(gè)隨機(jī)數(shù)代替,隨機(jī)數(shù)的產(chǎn)生服從初始種群產(chǎn)生規(guī)則。遺傳過程中,隨遺傳代數(shù)增加,逐漸降低交叉率,增大變異率,使子代穩(wěn)定遺傳,同時(shí)由于變異率增加也保持了種群的多樣性。
圖6 均勻交叉操作范例
終止條件,達(dá)到一定代數(shù),或相鄰若干代種群平均適應(yīng)值無變化或變化小于閾值,則退出算法。
實(shí)驗(yàn)數(shù)據(jù)源于文獻(xiàn)[6],研究對(duì)象為一機(jī)械部件廠,實(shí)例包含5種產(chǎn)品,各產(chǎn)品相關(guān)參數(shù)如表1所示。通過HGA求解,所得結(jié)果如表2、3所示,其中“當(dāng)前策略”為該機(jī)械部件廠當(dāng)前采用的調(diào)度方法。
表2結(jié)果表明本文提出的模型對(duì)機(jī)械廠目前調(diào)度有所優(yōu)化,成本比文獻(xiàn)[6]下降3.6%。成本降低集中在額外成本和庫(kù)存成本。由于目標(biāo)函數(shù)包含產(chǎn)品制造/再造成本,該成本遠(yuǎn)高于換模及庫(kù)存成本,且對(duì)舊產(chǎn)品再造率αi敏感性小,制造/再造成本變化幅度小,使總成本優(yōu)化幅度減小。若總成本不包括制造/再造成本,單位總成本較文獻(xiàn)[6]所得結(jié)果下降18.7%。本文提出的ELSPR求解方法比文獻(xiàn)[6]有更好的優(yōu)化效果。
若不考慮產(chǎn)品處置,即舊產(chǎn)品均可再造,此時(shí)制造/再造成本作為定值不包括在目標(biāo)函數(shù)中。優(yōu)化結(jié)果如表3所示,單位總成本比文獻(xiàn)[6]所得結(jié)果下降17%。雖然優(yōu)化幅度不大,但建模時(shí)考慮舊產(chǎn)品再造率可進(jìn)一步降低額外成本和庫(kù)存成本。在建模時(shí)考慮舊產(chǎn)品再造率,不僅符合生產(chǎn)實(shí)際,而且可以有效地降低成本。
從表1可看出,算例中研究對(duì)象生產(chǎn)率均較高,在80%左右。下面對(duì)生產(chǎn)率處于中低部分的對(duì)象進(jìn)行研究,實(shí)驗(yàn)數(shù)據(jù)從文獻(xiàn)[8]中獲得,如表4所示。分別用IS和文獻(xiàn)[6]方法及HGA進(jìn)行求解。IS法求得的解若可行,則其為該問題最優(yōu)解,但這幾乎不可能,尤其對(duì)生產(chǎn)率ρ>0.25的問題[13]。故IS通常作為同類問題的下界。由于IS所得解通常不可行,故不考慮IS法額外成本AC。如表5為三種方法求解結(jié)果,由表5可知,在考慮舊產(chǎn)品回收率情況下,HGA所得解比文獻(xiàn)[6]下降9.8%。如表6為HGA求解產(chǎn)品調(diào)度情況,其中表示產(chǎn)品制造/再造的結(jié)束時(shí)間,可以看出HGA所得調(diào)度可行。在不同的產(chǎn)品生產(chǎn)率下,提出的HGA算法均能取得優(yōu)于文獻(xiàn)[6]的解,并且能保證所得調(diào)度的可行性。
表1 求解模型所用參數(shù)
表2 文獻(xiàn)[6]和HGA求解結(jié)果比較
表3 舊產(chǎn)品均可再造情況下求解結(jié)果比較
表4 產(chǎn)品相關(guān)參數(shù)
表5 中低生產(chǎn)率下求解結(jié)果對(duì)比
表6 求解模型所得決策變量參數(shù)值
對(duì)回收率參數(shù)λ進(jìn)行敏感性分析,其余參數(shù)如表4所示,結(jié)果如圖7所示。分析發(fā)現(xiàn),逐漸增大λ值,回收率β均值減小,成本大幅震蕩。λ在[0,10]時(shí),成本震蕩幅度較大,隨著λ逐漸增大,處于[50,100]時(shí),成本逐漸增大。由于生產(chǎn)型庫(kù)存費(fèi)率更高,越遲開始再造,庫(kù)存費(fèi)用的增加速度減緩。在λ值較大時(shí),系統(tǒng)再造量下降,隨著制造批次的增大,總成本增加。λ增大,再造批量減小,制造批量增大,制造單位生產(chǎn)成本高于再造單位生產(chǎn)成本,總生產(chǎn)成本的增加。對(duì)λ分析發(fā)現(xiàn),回收率在一定范圍內(nèi)增加可使得成本下降,但是超過該范圍后成本反而增加,構(gòu)建模型是考慮舊產(chǎn)品再造率,使得舊產(chǎn)品不能都用于再造,對(duì)于優(yōu)化ELSPR十分必要。
圖7 回收率參數(shù)敏感性分析圖
針對(duì)存在于混合生產(chǎn)系統(tǒng)中的批量調(diào)度問題,本文建立了舊產(chǎn)品回收率隨機(jī)并考慮舊產(chǎn)品處置的ELSPR模型。采用啟發(fā)式遺傳算法結(jié)合擴(kuò)展基本時(shí)段法對(duì)模型進(jìn)行求解。實(shí)驗(yàn)表明:建模時(shí)考慮舊產(chǎn)品回收率,較同等條件下不考慮該參數(shù),能進(jìn)一步降低總成本達(dá)到18.7%;提出的HGA算法在生產(chǎn)率的不同階段均能求得優(yōu)于文獻(xiàn)[6]的解,并且能保證所得調(diào)度的可行性。在將來求解ELSPR時(shí),對(duì)初始解的生成采用更優(yōu)的啟發(fā)式排序規(guī)則,使初始解包含所有可行排序,或?qū)Τ跏冀庵械牟豢尚薪馓岢鲂迯?fù)規(guī)則,使初始解盡量多樣化,以使得最優(yōu)解進(jìn)一步優(yōu)化。
[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
針對(duì)存在于制造、再造混合生產(chǎn)系統(tǒng)的批量調(diào)度問題,研究舊產(chǎn)品回收率隨機(jī)的情況下,考慮舊產(chǎn)品回收的多產(chǎn)品經(jīng)濟(jì)批量調(diào)度問題。基于擴(kuò)展基本時(shí)段法綜合考慮制造新品和再造產(chǎn)品的批量調(diào)度,構(gòu)建以單位總成本最小為目標(biāo)的優(yōu)化模型。提出的改進(jìn)型遺傳算法對(duì)模型求解,能避免不可行解的產(chǎn)生。分別比較考慮和不考慮舊產(chǎn)品廢棄處置兩種情況下,該算法和Teunter方法的優(yōu)化效果,結(jié)果表明提出的算法能進(jìn)一步降低成本并保證最優(yōu)解可行。
經(jīng)濟(jì)批量調(diào)度問題;再制造;產(chǎn)品回收;廢棄處置
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.
國(guó)家自然科學(xué)基金(No.61273035,No.71071115);國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863)(No.2009AA043000)。
舒曼莉(1988—),女,碩士研究生,主要研究領(lǐng)域?yàn)樵僦圃煜到y(tǒng)庫(kù)存與調(diào)度管理;徐克林(1945—),女,教授,博導(dǎo),主要研究領(lǐng)域?yàn)楣?yīng)鏈管理;鄭永前(1965—),男,副教授,碩導(dǎo),主要研究領(lǐng)域?yàn)樯a(chǎn)系統(tǒng)工程與管理。E-mail:shumanli@163.com
2013-01-14
2013-03-02
1002-8331(2013)13-0216-05