分時(shí)電價(jià)和時(shí)變行程時(shí)間下的供應(yīng)鏈調(diào)度

王 君

天津財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，天津，300222

0 引言

經(jīng)濟(jì)與社會(huì)的持續(xù)發(fā)展帶來能源消耗的快速增長，與此伴隨的CO2排放是全球氣候變化的重要因素。工業(yè)生產(chǎn)的能源消耗達(dá)到全球總能源消耗的一半[1]。在大多數(shù)生產(chǎn)企業(yè)中，電力是消耗能源的主要形式[2]。電力不能被有效存儲(chǔ)，只能隨著用戶的需要而進(jìn)行實(shí)時(shí)的生產(chǎn)、運(yùn)輸和供應(yīng)，因此，需求反應(yīng)技術(shù)和負(fù)荷管理對(duì)電力供需的平衡十分重要，分時(shí)電價(jià)(time-of-use electricity tariffs，TOU)政策就是一種最常用的策略[3]。它通過價(jià)格機(jī)制，鼓勵(lì)電力需求敏感的消費(fèi)者把電力使用從需求的波峰時(shí)段移動(dòng)到波谷時(shí)段，從而有效提高電網(wǎng)系統(tǒng)的穩(wěn)定性和效率。

TOU政策下，制定生產(chǎn)計(jì)劃需要考慮訂單(或機(jī)器、工序)的功率消耗，盡量把高功率的訂單放在低電價(jià)下進(jìn)行生產(chǎn)，以達(dá)到節(jié)省電力成本的目的。FANG等[4]以最小化電力成本為目標(biāo)，研究了單機(jī)器生產(chǎn)環(huán)境下的搶占式和非搶占式機(jī)器調(diào)度問題，證明了問題的復(fù)雜度并給出了精確的或近似最優(yōu)的求解算法。CHE等[5]對(duì)類似的單機(jī)器非搶占式機(jī)器調(diào)度問題，設(shè)計(jì)了一個(gè)貪婪插入算法。WANG等[6]針對(duì)生產(chǎn)批次的調(diào)度問題，在最小化電力總成本的同時(shí)，增加了總完工時(shí)間目標(biāo)，給出了一個(gè)得到精確Pareto前沿的算法。DING等[7]以同樣的兩個(gè)優(yōu)化目標(biāo)研究了平行機(jī)生產(chǎn)系統(tǒng)的機(jī)器調(diào)度問題，給出了求解多目標(biāo)問題的啟發(fā)式算法。

生產(chǎn)系統(tǒng)有效利用電力、保持電網(wǎng)穩(wěn)定性是實(shí)現(xiàn)節(jié)能減排的方式之一。對(duì)工業(yè)企業(yè)而言，另一個(gè)節(jié)能減排方式是在配送系統(tǒng)中節(jié)約燃油。UBEDA等[8]在配送系統(tǒng)的案例研究中指出，僅通過減少總行駛里程就能比初始的配送方案減少25.5%的燃油消耗。城市配送中，道路網(wǎng)絡(luò)的擁堵程度類似于分時(shí)電價(jià)，選擇較通暢的時(shí)段進(jìn)行配送有利于減少油耗[9]。因此，企業(yè)有效整合生產(chǎn)和配送系統(tǒng)，有利于同時(shí)節(jié)約電力和燃油總成本，以實(shí)現(xiàn)可持續(xù)調(diào)度[10]。對(duì)生產(chǎn)和配送同時(shí)進(jìn)行決策的問題稱為供應(yīng)鏈調(diào)度問題[11]，這明顯增加了問題的復(fù)雜程度，但目前的研究都沒有考慮分時(shí)電價(jià)和路網(wǎng)的擁堵[12-13]。

本文針對(duì)單機(jī)器、單客戶的供應(yīng)鏈調(diào)度問題，考慮在分時(shí)電價(jià)政策和路網(wǎng)擁堵的條件下，對(duì)工件的開始生產(chǎn)時(shí)刻、配送的批次和開始配送時(shí)刻進(jìn)行決策。以最小化生產(chǎn)電力成本與配送油耗成本之和為目標(biāo)建立模型，然后分析模型的優(yōu)化性質(zhì)?；谀Ｐ偷淖顑?yōu)性質(zhì)，把集成的模型分解為多個(gè)批次的機(jī)器調(diào)度子問題。對(duì)于子問題的優(yōu)化，設(shè)計(jì)了一個(gè)子集劃分的啟發(fā)式算法；對(duì)于主問題的優(yōu)化，設(shè)計(jì)了自適應(yīng)變鄰域搜索算法。數(shù)值計(jì)算表明，供應(yīng)鏈調(diào)度模型和算法比先優(yōu)化生產(chǎn)調(diào)度、后優(yōu)化分批配送的分階段優(yōu)化方法，可節(jié)約更多的電力和油耗成本。

1 問題描述

分時(shí)電價(jià)指每個(gè)時(shí)段的電力價(jià)格隨著電力需求的不同而變化。把加工周期劃分成m1個(gè)時(shí)間段，第k(k=1，2，…，m1)個(gè)時(shí)間段記為Tk，該時(shí)間段的結(jié)束時(shí)刻記為ek。那么Tk可以表示為時(shí)間區(qū)間[ek-1，ek]，Tk內(nèi)的單位電價(jià)為ck。假設(shè)任意一個(gè)工件的加工時(shí)間都小于Tk。分時(shí)電價(jià)下，不同時(shí)間段安排工件的加工所耗費(fèi)的電力成本是不同的，因此生產(chǎn)決策包括工件的加工順序和每個(gè)工件的開始加工時(shí)刻。

時(shí)變行程時(shí)間(time-dependent travel times，TDTT)可描述路網(wǎng)的擁堵。車輛行駛在某個(gè)配送路段的行駛速度依賴于路網(wǎng)的通暢程度。把配送周期分成m2個(gè)時(shí)間段，第η(η=1，2，…，m2)個(gè)時(shí)間段pη的結(jié)束時(shí)刻記為lη，同樣可以用區(qū)間[lη-1，lη]表示pη。假設(shè)在任意完整時(shí)間段內(nèi)都可以完成配送任務(wù)，即車輛在配送時(shí)最多橫跨2個(gè)時(shí)間段。根據(jù)ICHOUA等[14]的TDTT模型，在pη內(nèi)，車輛的行駛速度為sη。該模型把行駛速度表示為時(shí)間的分段函數(shù)，使得模型具有先進(jìn)先出(first in first out，F(xiàn)IFO)性質(zhì)，即先出發(fā)的車輛一定比后出發(fā)的車輛先到達(dá)目的地。路網(wǎng)擁堵條件下，在不同的加工完成時(shí)刻安排配送分批，每個(gè)配送車輛對(duì)應(yīng)的載重、行駛速度是不同的，所以其耗費(fèi)的燃油成本也是不同的。因此，在生產(chǎn)決策已知的情況下，配送決策即為確定配送的批次。

2 模型建立

(1)

(2)

其中，yiv是0-1決策變量，如果工件i由第v個(gè)批次進(jìn)行配送，則yiv=1；否則，yiv=0。

(3)

αη=γ0+γ1sη

(4)

(5)

式中，D為工廠到客戶的行駛路線長度；αη、βv為油耗系數(shù)；γ0、γ1為與速度相關(guān)的參數(shù)，γ0≥0，γ1≥0；μ為長期統(tǒng)計(jì)的車輛載貨量；λ0、λ1為與載重相關(guān)的參數(shù)，λ0≥0，λ1≥0。

顯然，在其他條件不變的前提下，隨著速度的增大，αη增大，油耗減小；隨著載重量的增大，βv減小，耗油增大。

記h為燃油價(jià)格；Csum為加工和配送所有工件的總成本；M為無窮大的數(shù)；xij為0-1決策變量，即如果工件i在工件j之前進(jìn)行加工，并且在工件i與工件j之間無其他工件，則xij=1；否則，xij=0?？紤]其他約束，該問題的混合整數(shù)規(guī)劃模型如下：

(6)

s.t.

(7)

(8)

(9)

(10)

(11)

(12)

xij+yiv≤1+yjv+yj,v+1

(13)

xij∈{0,1}

(14)

yiv∈{0,1}

(15)

zi≥0

(16)

模型中，式(6)表示優(yōu)化目標(biāo)是最小化加工和配送的總成本；式(7)表示機(jī)器加工第一個(gè)工件的順序約束；式(8)、式(9)表示機(jī)器加工其他工件的順序約束；式(10)表示每個(gè)工件必須包含在一個(gè)配送批次中；式(11)表示每個(gè)批次的配送量不能超過車輛的載重能力；式(12)表示前一個(gè)工件完成加工后,才能開始加工下一個(gè)工件；式(13)表示相鄰加工的后一個(gè)工件，要么與前一個(gè)工件一個(gè)批次配送，要么在下一個(gè)批次進(jìn)行配送；式(14)、式(15)是0-1變量約束；式(16)是非負(fù)變量約束。

3 模型的求解分析

分析模型及解的性質(zhì)有利于構(gòu)造高效的優(yōu)化機(jī)制，減小搜索空間，提高算法的效率。該優(yōu)化問題包含生產(chǎn)調(diào)度和分批配送兩個(gè)有先后順序的決策子問題，首先對(duì)這兩個(gè)子問題進(jìn)行求解分析。

定義1如果工件的開始加工時(shí)刻和加工完成時(shí)刻都包含在時(shí)間段Tk內(nèi)，那么稱該工件在Tk內(nèi)完全加工；如果工件的開始加工時(shí)刻在Tk內(nèi)，加工完成時(shí)刻在Tk+1內(nèi)，則稱該工件橫跨時(shí)間段Tk和Tk+1，并稱該工件在Tk和Tk+1部分加工[5]。

定義2如果工件i的加工完成時(shí)刻等于工件j的開始加工時(shí)刻，那么稱工件i和j是緊密相鄰的，并稱工件i是j的緊前工件，工件j是i的緊后工件。

定義3如果在加工序列(i1，i2，…，is)中，任意相鄰的兩個(gè)工件都是緊密相鄰的，且i1無緊前工件，is無緊后工件，則稱該加工序列為緊序列，工件個(gè)數(shù)s(s≤n)稱為該緊序列的長度。如果緊序列(i1，i2，…，is)中的某個(gè)工件is′橫跨時(shí)間段Tk和Tk+1，則稱(i1，i2，…，is′)和(is′，is′+1，…，is)分別是在Tk和Tk+1內(nèi)的緊序列。

定義5如果模型的最優(yōu)解唯一，那么稱該最優(yōu)解為最優(yōu)決策方案；如果最優(yōu)解不唯一，那么稱含有緊序列數(shù)量最少的解為最優(yōu)決策方案。

引理1加工某個(gè)工件的電力成本僅取決于各個(gè)時(shí)間段加工該工件的時(shí)間消耗[5]。

引理2若某個(gè)工件在一個(gè)時(shí)間段內(nèi)加工完成，則加工該工件的電力成本與開始加工時(shí)刻無關(guān)[5]。

定理1如果模型存在最優(yōu)解，那么最優(yōu)決策方案存在以下性質(zhì)：

性質(zhì)1在時(shí)間段Tk內(nèi)的某個(gè)緊序列中，任意交換同一配送批次、完全加工工件的次序，模型的最優(yōu)值保持不變。

性質(zhì)2在時(shí)間段Tk內(nèi)，完全加工的非關(guān)鍵工件與同一批次的關(guān)鍵工件必定組成一個(gè)緊序列。

性質(zhì)3如果一個(gè)同批次配送的加工序列(i1，i2，…，is)是緊序列的一部分，序列中某個(gè)工件is′橫跨時(shí)間段Tk和Tk+1。若ckck+1，則序列(i1，i2，…，is′)中所有工件的加工功率都不大于is′的加工功率，序列(is′，is′+1，…，is)中所有工件的加工功率都不小于is′的加工功率。

位于一六多金屬礦田南部、天門坳—牛公錐西主干斷裂中段西側(cè)、梅子沖銀鉛鋅礦床南約4km處(圖1)。赤老頂銻礦歷史悠久，于清末始被發(fā)現(xiàn)和開采，礦體主要呈似層狀、透鏡狀賦存于天子嶺組內(nèi)的硅化層或硅化斷裂破碎帶中，主礦體賦礦標(biāo)高為409～134m，目前最深開采標(biāo)高至+170m左右。斷裂發(fā)育，具有近SN、NNE、NNW、NW、近EW及NE向等多組斷裂，其中近SN向、NNE向、NNW向組與礦化關(guān)系較密切。圍巖蝕變主要為硅化、方解石化。區(qū)內(nèi)未見巖體出露。

性質(zhì)4如果一個(gè)同批次配送的加工序列是緊序列的一部分，序列中的工件is′橫跨時(shí)間段Tk和Tk+1。若ckck+1，則把該序列的工件按照加工功率升序排列，模型的最優(yōu)值不變。

根據(jù)引理1和引理2容易得到定理1中的性質(zhì)1和性質(zhì)2。圖1給出了性質(zhì)2的示例。在a行中，5個(gè)工件在時(shí)間段Tk內(nèi)完全加工，分2個(gè)批次進(jìn)行配送，根據(jù)引理2，往后推移工件1和2的開始加工時(shí)刻使工件1、2、3緊密相鄰，往后推移工件4的開始加工時(shí)刻使工件4、5緊密相鄰，得到2個(gè)緊序列，如b行所示。由于關(guān)鍵工件3和5未移動(dòng)，所以加工和配送這5個(gè)工件的總成本不變。在c行中，6個(gè)工件組成了1個(gè)緊序列，含有2個(gè)關(guān)鍵工件，示意了1個(gè)緊序列由多個(gè)配送批次組成。

圖1 性質(zhì)2的緊序列示意圖Fig.1 A compact sequence diagram of property 2

從以上分析可以看出，在不改變成本的前提下，時(shí)間段Tk內(nèi)，完全加工的非關(guān)鍵工件的開始加工時(shí)刻具有一定的靈活性。如果可以，把它們的開始加工時(shí)刻在Tk內(nèi)往后(即時(shí)間軸方向)推移，直到與所在批次的關(guān)鍵工件組成緊序列；否則，就把它們的開始加工時(shí)刻在Tk內(nèi)往前(即時(shí)間軸相反方向)推移，直到與前1個(gè)批次的關(guān)鍵工件組成緊序列。

以上分析的目的是為了在多個(gè)最優(yōu)解中，選出最優(yōu)決策方案作為優(yōu)化的最終結(jié)果。最優(yōu)決策方案相比于其他最優(yōu)解，含有最少的緊序列，所以機(jī)器的加工間歇期最少，從而盡量減少機(jī)器在加工和間歇狀態(tài)之間的轉(zhuǎn)換，這符合現(xiàn)實(shí)企業(yè)的操作實(shí)踐。

性質(zhì)3由反證法容易證明，由性質(zhì)1和性質(zhì)3易得到性質(zhì)4。根據(jù)以上分析可知，在最優(yōu)決策方案中，序列內(nèi)工件的次序不唯一。為了在研究中得到最優(yōu)決策方案的唯一解，對(duì)某同批次配送的加工序列(i1，i2，…，is)進(jìn)行分析，如果它是緊序列的一部分，不失一般性，本文約定：①如果該序列在時(shí)間段Tk內(nèi)，那么序列內(nèi)工件按照加工功率升序排列；②如果該序列中的工件is′橫跨時(shí)間段Tk和Tk+1，那么序列內(nèi)工件在ck>ck+1時(shí)，按加工功率升序排列；在ck

4 模型的求解算法

由于FANG等[4]已經(jīng)證明分時(shí)電價(jià)下的機(jī)器調(diào)度問題是NP-Hard問題，所以本文研究的供應(yīng)鏈調(diào)度問題也是NP-Hard問題。因?yàn)榛卩徲蛩阉鞯乃惴ㄔ谔幚砩a(chǎn)、配送分批調(diào)度問題中具有很好的優(yōu)化效果[15-17]，所以本文采用文獻(xiàn)[18]提出的自適應(yīng)變鄰域搜索(adaptive variable neighborhood search，AVNS)算法的框架進(jìn)行求解。

4.1 解的編碼結(jié)構(gòu)及解碼

采用基于配送批次和開始配送時(shí)刻的向量組編碼結(jié)構(gòu)，用第v個(gè)向量表示車輛v配送的工件，最后一個(gè)向量表示每個(gè)批次的開始配送時(shí)刻。例如，向量組((2，5)，(3，7，9)，(1，4，6，8)，(100，180，360))表示9個(gè)工件、3個(gè)批次的調(diào)度方案，具體加工配送調(diào)度計(jì)劃如圖2所示。機(jī)器加工完工件2、5后，在時(shí)刻100配送第1批工件；加工完工件3、7、9后，在時(shí)刻180配送第2批工件；最后加工工件1、4、6、8并配送它們。該編碼結(jié)構(gòu)下，每個(gè)批次工件的加工順序可以是任意的，但要求每個(gè)批次最后一個(gè)工件的加工完成時(shí)刻等于該批次的開始配送時(shí)刻。為了得到每個(gè)批次的工件加工次序和工件的開始加工時(shí)刻，需要對(duì)向量組解碼以獲得模型的解。通過定義6和算法1，可以對(duì)向量組的每個(gè)分批進(jìn)行解碼。

圖2 向量組表示的調(diào)度計(jì)劃示意圖Fig.2 The diagram of a scheduling plan expressed by a vector group

定義6根據(jù)向量組編碼結(jié)構(gòu)，對(duì)于某個(gè)分批，在已知機(jī)器準(zhǔn)備就緒時(shí)刻、加工完成時(shí)刻的條件下，確定該批次每個(gè)工件的開始加工時(shí)刻，以最小化該批次生產(chǎn)電力成本為目標(biāo)的優(yōu)化問題稱為分時(shí)電價(jià)下加工完成時(shí)刻已知的機(jī)器調(diào)度問題(子問題1)。

算法1機(jī)器調(diào)度算法

(2)對(duì)工件按照加工功率降序排序得到排列i1、i2、…、is。

(3)Forl=1 tosdo

②把工件il的加工完成時(shí)刻設(shè)置成時(shí)間軸的結(jié)束時(shí)刻，更新Is′和Is′-1。

③Forl′=1 tosandl′≠ldo

b.選擇電力成本增量最小的時(shí)間段、插入方式，插入工件il′。

c.Fork=1 tos′ do更新Ik。

④計(jì)算該批次工件的加工電力成本f(il)。

(4)選擇最小的f(il)對(duì)應(yīng)的方案。

(5)Forl′=1 to s andl′≠ldo依據(jù)性質(zhì)2、性質(zhì)4和最優(yōu)決策方案唯一解的約定，計(jì)算工件l′的開始加工時(shí)刻，算法結(jié)束。

定理2如果電價(jià)是按照批次內(nèi)時(shí)間段升序或降序排列，那么用算法1可以計(jì)算得到子問題1的最優(yōu)解；否則，可以得到子問題1的近似最優(yōu)解。

證明：顯然步驟②是把問題的解集劃分為s個(gè)子集，在每個(gè)子集中，安排工件il為最后一個(gè)加工工件，對(duì)其他工件的加工調(diào)度轉(zhuǎn)化為一個(gè)分時(shí)電價(jià)下的非搶占式機(jī)器調(diào)度問題(子問題2)。

對(duì)子問題2，算法1的步驟(1)(2)和步驟②～④組成的算法與貪婪插入啟發(fā)式算法[5]一致。因?yàn)镃HE等[5]通過實(shí)驗(yàn)驗(yàn)證了算法的近似最優(yōu)性，而且步驟(5)不改變工件在每個(gè)時(shí)間段的加工時(shí)間，即加工成本不變。因此，通過步驟(4)(5)可以求得所有子集近似最優(yōu)解的最小值(子問題1的近似最優(yōu)解)。

4.2 初始解

為了得到可行的調(diào)度方案，采用算法1的部分步驟得到加工計(jì)劃，然后進(jìn)行批次分配，具體步驟如算法2所示。

算法2初始解生成算法

(1)依次執(zhí)行算法1的步驟(1)(2)和步驟②～④、步驟(5)，得到加工計(jì)劃序列(i1，i2，…，in)。

(2)初始化l:=1,v:=1,Load:=0。

(3)Whilel≤ndo

②置l:=l+1。

(4)利用算法1優(yōu)化每個(gè)批次的機(jī)器調(diào)度問題。

4.3 鄰域結(jié)構(gòu)

在每個(gè)批次包含的工件和批次的開始配送時(shí)刻已知的條件下，根據(jù)機(jī)器調(diào)度算法，能得到供應(yīng)鏈調(diào)度問題的最優(yōu)解或近似最優(yōu)解。因此，對(duì)供應(yīng)鏈調(diào)度問題的全局優(yōu)化，就簡化為對(duì)開始配送時(shí)刻的搜索和對(duì)批次分配的搜索，這是鄰域結(jié)構(gòu)設(shè)計(jì)的出發(fā)點(diǎn)。

定義7對(duì)某個(gè)工件的開始配送時(shí)刻附近進(jìn)行搜索的鄰域，稱為開始配送時(shí)刻鄰域。

假設(shè)配送批次v最后一個(gè)加工的工件為工件i，工件i所在的緊路徑中任意的一個(gè)工件為工件j，即j∈Jj，其中，Jj為工件j所在緊路徑中所有工件的集合，那么有

算法3開始配送時(shí)刻鄰域

(1)隨機(jī)選擇配送批次v，得到該批次最后一個(gè)加工的工件i，假設(shè)包含該批次的緊序列包含的批次為v-s、v-s+1、…、v+s′-1、v+s′(s，s′≥0)。

(2)在時(shí)間軸方向或時(shí)間軸相反方向中隨機(jī)選擇一個(gè)搜索方向。

(5)利用算法1優(yōu)化每個(gè)批次的機(jī)器調(diào)度問題。

定義8把一個(gè)批次中的某個(gè)工件移動(dòng)到另一個(gè)批次稱為批次移動(dòng)鄰域。交換2個(gè)批次中的某個(gè)工件稱為批次交換鄰域。批次移動(dòng)鄰域和批次交換鄰域統(tǒng)稱為批次鄰域。

4.4 AVNS算法總流程

記鄰域u(u=1，2，…，U)的選擇概率為ρu，鄰域u的有效、無效的次數(shù)分別為ρ1,u和ρ2,u。令有效率ρ3,u=ρ1,u/(ρ1,u+ρ2,u)+0.02，那么[18]

(17)

根據(jù)以上自適應(yīng)選擇機(jī)制，結(jié)合4.1、4.2節(jié)的內(nèi)容，得到如下AVNS算法的總流程：

(1)初始化批次移動(dòng)和批次交換的有效次數(shù)ρ1,1=ρ2,1=5、無效次數(shù)ρ1,2=ρ2,2=5。利用算法2生成初始解X，并設(shè)置X為當(dāng)前解和最優(yōu)解。初始化φ：=0。

(2)Whileφ<φmax

①根據(jù)兩個(gè)批次鄰域的選擇概率，使用輪盤法隨機(jī)選擇一個(gè)鄰域u。

②Forθ=1 toθmaxdo

a.使用鄰域u對(duì)當(dāng)前解進(jìn)行鄰域操作，得到解X′。

b.使用算法3的開始配送時(shí)刻鄰域?qū)′進(jìn)行局部搜索，得到的最好解記為X″。

c.如果X″優(yōu)于當(dāng)前解，則置ρ1,u:=ρ1,u+1；否則置ρ2,u:=ρ2,u+1。

d.置X″為當(dāng)前解，φ：=φ+1。如果X″優(yōu)于最優(yōu)解，則置X″為最優(yōu)解，φ：=0。

③使用式(17)更新鄰域的選擇概率。

5 數(shù)值計(jì)算分析

隨機(jī)生成參數(shù)不同的18個(gè)算例，來驗(yàn)證模型的正確性、算法的效率以及對(duì)問題規(guī)模的敏感程度。算法用Visual C# 2010編程，在Intel i7-6700 3.4 GHz的CPU、8GB內(nèi)存、Windows7系統(tǒng)的電腦上運(yùn)行。設(shè)置工件數(shù)量為20、40，隨機(jī)生成工件的相關(guān)參數(shù)，各參數(shù)的取值范圍如表1所示。為了在加工周期內(nèi)完成所有工件的加工任務(wù)，隨著工件的增加，每個(gè)工件的平均加工時(shí)間縮短。工件的加工功率設(shè)置為高功率、低功率、高低功率混合三種類型，工件質(zhì)量也有類似設(shè)置。設(shè)置車輛最大載重Qv=20 t，行駛路線長度D=100 km，油價(jià)6元每升，分時(shí)電價(jià)[5]和時(shí)變行程時(shí)間的設(shè)置如表2所示。與油耗相關(guān)的參數(shù)如下[9]：λ0=4.400 276 59，λ1=0.000 033 978 4，γ0=4.537 757 841 4，γ1=0.065 805，μ=15 173.04 kg。參考文獻(xiàn)[15,17-18]對(duì)算法參數(shù)的設(shè)置，令θmax=3，4，…，9；φmax=10，20，30，40，并選取幾個(gè)算例進(jìn)行試優(yōu)化。我們發(fā)現(xiàn)θmax的取值對(duì)算法優(yōu)化結(jié)果的影響不大，較大的φmax會(huì)增加算法的運(yùn)算時(shí)間，因此，經(jīng)過反復(fù)試驗(yàn)后設(shè)置算法參數(shù)：θmax=5，φmax=20。

表1 工件參數(shù)

表2 分時(shí)電價(jià)和時(shí)變行程時(shí)間參數(shù)

如表3所示，算法的計(jì)算結(jié)果分為兩部分：一部分是運(yùn)用本文提出的供應(yīng)鏈調(diào)度優(yōu)化模型和AVNS算法得到的計(jì)算結(jié)果；另一部分是把加工調(diào)度和批次配送調(diào)度分成兩個(gè)階段先后優(yōu)化，即先采用文獻(xiàn)[5]的方法優(yōu)化加工調(diào)度，然后在加工計(jì)劃給定的條件下優(yōu)化分批得到的計(jì)算結(jié)果。優(yōu)化分批采用本文提出的ANVS算法框架和相同的參數(shù)設(shè)置，其算法中鄰域結(jié)構(gòu)的設(shè)置如下：①將某個(gè)批次的第一個(gè)工件移動(dòng)到前一個(gè)批次；②將某個(gè)批次的最后一個(gè)工件移動(dòng)到后一個(gè)批次。表3中，加粗字體顯示較好的結(jié)果。從計(jì)算時(shí)間上看，作為對(duì)比的分階段優(yōu)化算法用時(shí)很少，這是因?yàn)槲墨I(xiàn)[5]采用的是貪婪插入算法，缺少全局搜索過程。從總成本的對(duì)比結(jié)果看，以供應(yīng)鏈整體視角進(jìn)行的優(yōu)化比分階段優(yōu)化減少4.85%～18.47%的成本。再分別對(duì)加工和配送的成本進(jìn)行分析。供應(yīng)鏈整體優(yōu)化的配送成本都明顯小于分階段優(yōu)化的成本。算例2a、2b、3a、6a、7a、7b的分階段優(yōu)化的加工成本大于整體優(yōu)化方式，這是因?yàn)樵跁r(shí)間段較多并且電價(jià)不是按照時(shí)間段有序排列的情況下，用文獻(xiàn)[5]的算法優(yōu)化加工調(diào)度僅能取得近似最優(yōu)解。整體優(yōu)化方式僅在批次內(nèi)部進(jìn)行加工調(diào)度的優(yōu)化，而每個(gè)批次的時(shí)間區(qū)間包含的時(shí)間段要少很多，那么配送成本就進(jìn)一步接近甚至等于最優(yōu)解。因此，本文提出的供應(yīng)鏈整體視角的優(yōu)化模型和AVNS算法在優(yōu)化加工和配送總成本方面具有很好的效果。

表3 算例計(jì)算結(jié)果

由表3可知，當(dāng)工件較少(20個(gè)工件)時(shí)，AVNS算法在30 s內(nèi)就能取得最終結(jié)果。當(dāng)工件數(shù)量增加到40時(shí)，運(yùn)算時(shí)間明顯延長。這是因?yàn)檫\(yùn)算時(shí)間主要取決于鄰域的搜索范圍和算法的迭代次數(shù)。批次較多或配送成本明顯大于加工成本，會(huì)增加鄰域范圍和搜索的深度。算例8b同時(shí)滿足以上兩個(gè)條件，其運(yùn)算時(shí)間最長，但也沒有超過10 min，其運(yùn)算過程見圖3。在前50次迭代中，總成本目標(biāo)的下降速度較快，下降到4 196.52 元，已經(jīng)優(yōu)化了97.64%，說明AVNS算法在運(yùn)算過程的前期具有較好的優(yōu)化效果。在運(yùn)算后期，當(dāng)前解在最優(yōu)解上方隨機(jī)波動(dòng)，說明AVNS算法的隨機(jī)搜索性能較理想。

圖3 算例8的迭代過程Fig.3 Iterative process of example 8

6 結(jié)論

(1)在分時(shí)電價(jià)政策和時(shí)變行程時(shí)間下，研究了單機(jī)器的集成生產(chǎn)計(jì)劃和配送分批的供應(yīng)鏈調(diào)度問題，對(duì)每個(gè)工件的開始加工時(shí)刻、配送的分批進(jìn)行決策，目標(biāo)是優(yōu)化總成本。

(2)建立了混合整數(shù)規(guī)劃模型，分析了模型的最優(yōu)化性質(zhì)，設(shè)計(jì)了自適應(yīng)變鄰域搜索算法進(jìn)行求解。數(shù)值計(jì)算的實(shí)驗(yàn)表明，供應(yīng)鏈集成調(diào)度模型比分階段先后獨(dú)立優(yōu)化具有很大的優(yōu)勢。

(3)對(duì)單機(jī)器、單個(gè)客戶的供應(yīng)鏈調(diào)度問題進(jìn)行了研究。由于企業(yè)的生產(chǎn)系統(tǒng)、配送系統(tǒng)具有多樣性，考慮多機(jī)器、多客戶、車輛路徑規(guī)劃等條件下的供應(yīng)鏈調(diào)度問題，是下一步研究的方向。