戴 敏，張玉偉，曾 勵

(揚(yáng)州大學(xué) 機(jī)械工程學(xué)院，江蘇 揚(yáng)州225127)

近年來，在全球能源日益緊張和自然環(huán)境持續(xù)惡化的背景下，綠色車間調(diào)度研究受到極大關(guān)注。據(jù)統(tǒng)計，到2050年，全球能源需求將增長37%，未來30～40年CO2排放量將增加80%左右[1]。大量數(shù)據(jù)表明，由于加工任務(wù)安排不合理，機(jī)床大部分時間處于空轉(zhuǎn)待機(jī)而非加工狀態(tài)[2]。單從提高機(jī)器效率上進(jìn)行節(jié)能效果一般，而車間調(diào)度是基于制造系統(tǒng)管理角度來優(yōu)化車間生產(chǎn)，是實(shí)現(xiàn)企業(yè)低碳制造的重要途徑。對于車間綠色調(diào)度問題，目前國內(nèi)外學(xué)者已經(jīng)做了大量研究。文獻(xiàn)[3]建立了碳排放、能耗成本和最大完工時間的多目標(biāo)綠色車間調(diào)度模型。文獻(xiàn)[4]研究了柔性作業(yè)車間生產(chǎn)過程中加工時間、機(jī)器負(fù)載、運(yùn)行成本的多目標(biāo)調(diào)度模型。文獻(xiàn)[5]建立了柔性流水車間節(jié)能調(diào)度模型，并采用一種改進(jìn)的遺傳模擬退火算法進(jìn)行求解。文獻(xiàn)[6]主要研究流水車間多目標(biāo)優(yōu)化問題，建立了作業(yè)時間、生產(chǎn)成本和生產(chǎn)能耗的數(shù)學(xué)模型。文獻(xiàn)[7]研究了作業(yè)車間拖期和空閑能耗最低問題并設(shè)計了NSGA-II算法對該問題進(jìn)行求解。從以上文獻(xiàn)可以看出，目前車間綠色調(diào)度問題主要研究作業(yè)車間、流水車間加工能耗和空閑能耗，均忽略了機(jī)器間AGV運(yùn)輸時的能耗，且加工資源和AGV運(yùn)輸資源兩者相互影響，分開調(diào)度很難實(shí)現(xiàn)系統(tǒng)整體節(jié)能效果。目前，對于考慮運(yùn)輸操作的車間調(diào)度問題也有很多研究。文獻(xiàn)[8]研究了實(shí)際制造企業(yè)中具有順序依賴設(shè)置和運(yùn)輸時間可控的置換流車間調(diào)度問題。文獻(xiàn)[9]以完工時間最小為優(yōu)化目標(biāo)研究了具有運(yùn)輸和預(yù)期順序依賴設(shè)置時間的群車間調(diào)度問題。文獻(xiàn)[10]研究了AGV與機(jī)器集成的車間調(diào)度問題，并設(shè)計了新的算法進(jìn)行求解，證明了AGV在車間調(diào)度中的重要性。文獻(xiàn)[11]主要分析了車間和AGV實(shí)時聯(lián)合調(diào)度問題，以完工時間為優(yōu)化目標(biāo)，采用文化基因算法對該問題進(jìn)行求解。上述研究基本上基于生產(chǎn)效率指標(biāo)(如生產(chǎn)時間)進(jìn)行優(yōu)化調(diào)度，未考慮節(jié)能指標(biāo)。本文在以上研究基礎(chǔ)上，以作業(yè)車間調(diào)度(job shop scheduling problem,JSP)為研究對象，考慮機(jī)器間AGV運(yùn)輸時間，將加工資源和運(yùn)輸資源集成調(diào)度，建立完工時間和總能耗的雙目標(biāo)優(yōu)化模型，并提出一種融入模擬退火搜索策略的分布估計算法，分析不同權(quán)重系數(shù)時完工時間和能耗變化的關(guān)系及運(yùn)輸速度對能耗的影響。

1考慮物料運(yùn)輸時間的JSP問題描述及數(shù)學(xué)建模

1.1問題描述

在m臺機(jī)器上加工n個工件且每個工件都有預(yù)定的工序加工順序，所有工序按照規(guī)定的加工工藝路線在m臺機(jī)器上完成操作。已知每道工序的加工時間和任意兩臺機(jī)器之間AGV運(yùn)輸時間，如圖1所示。同時，約束條件如下。

1)每個工件必須在前一道工序加工完畢后方可運(yùn)輸?shù)较乱坏拦ば虻募庸C(jī)器上進(jìn)行加工；2)不同工件的工序之間沒有約束；3)同一時刻每臺機(jī)器至多加工一道工序，一個工件也只能在一臺機(jī)器上加工；4)工序的加工過程不允許被中斷；5)機(jī)器與工件開始時間都初始化為0；6)每臺機(jī)器按照所安排的第一道工序的開始時間開機(jī)，最后一道工序的完成時間關(guān)機(jī)，以減少機(jī)床待機(jī)時間；7)AGV完全滿足運(yùn)輸需求，并且在運(yùn)輸過程中互不影響。

圖1 AGVs和機(jī)器集成下調(diào)度甘特圖Figure 1 Gantt chart of the integrated scheduling with AGVs and machines

1.2 AGVs與機(jī)器集成調(diào)度下完工時間建模

以最大完工時間最短為第一個優(yōu)化目標(biāo)，建立考慮AGV運(yùn)輸時間的作業(yè)車間調(diào)度模型

式(1)為第1個優(yōu)化目標(biāo)，即最大完工時間最??；式(2)表示工件i在機(jī)器k上加工的開始時間，式(3)表示其完工時間；式(4)表示工藝約束，同一工件的不同工序有先后加工順序；式(5)表示同一時刻一臺機(jī)器只能加工1個工件；式(6)表示完工時間變量約束條件；式(7)和式(8)分別為指示系數(shù)和指示變量。Sik、Pik、Cik分別為工件i在機(jī)器k上的開始時間、作業(yè)時間和完成時間；Q為一個足夠大的正數(shù)；thk為工件從機(jī)器h運(yùn)輸?shù)綑C(jī)器k消耗的時間；Zk為設(shè)備k可以適用的時刻。

1.3 AGVs與機(jī)器集成調(diào)度下能耗建模

車間能耗主要包括機(jī)床能耗、公共能耗和運(yùn)輸能耗。在現(xiàn)有加工環(huán)境下，建立如圖2所示的單機(jī)運(yùn)行時輸入功率簡化模型[12]。該模型假設(shè)每臺機(jī)器有3種功率級別：開機(jī)功率、空轉(zhuǎn)功率和切削功率。

圖2單機(jī)運(yùn)行功率示意圖Figure 2 Power diagram for single machine working

1.3.1機(jī)床能耗

開機(jī)能耗(E1)SPk(t)表示機(jī)器k的開機(jī)功率。當(dāng)機(jī)器啟動時，機(jī)器部件(液壓部件、冷卻泵)被激活從而消耗能量。消耗的能量可由式(9)計算得到。

其中，tk為機(jī)器k的開機(jī)時間。

切削能耗(E2)加工能耗E2由切削功率CPcikut乘以加工時間t

i

cku

t表示。

分別為工序Oik在機(jī)器k上的切削功率和加工時間。

空轉(zhuǎn)能耗(E3)在實(shí)際加工中，由于工件未到達(dá)，機(jī)器經(jīng)常處于空轉(zhuǎn)狀態(tài)而產(chǎn)生待機(jī)能耗E3。

其中， IPk為機(jī)器k的空轉(zhuǎn)功率；Tk為機(jī)器k開機(jī)和關(guān)機(jī)之間的時間間隔；分別為機(jī)器k的空閑時間和加工時間，空閑時間圖3為在機(jī)器k上加工4道工序的調(diào)度甘特圖。

1.3.2 AGV能耗

圖3機(jī)器k上的調(diào)度甘特圖Figure 3 Schedule Gantt chart on machine k

運(yùn)輸能耗(E4)是指AGV小車在機(jī)器之間運(yùn)輸物料所產(chǎn)生的能耗，即AGV執(zhí)行運(yùn)輸功能時消耗的能量。

式中， TP為運(yùn)輸設(shè)備功率。

1.3.3公共能耗

公共能耗(E5)是指車間公共設(shè)施的能源消耗，為照明，通風(fēng)供暖等能耗的總和。

式中，P0為公共功率；Cmax為最大完工時間。因此，根據(jù)以上作業(yè)車間能耗分析，建立總能耗(E)優(yōu)化目標(biāo)為

2混合分布估計算法設(shè)計

分布估計算法(estimation of distribution algorithm，EDA)的概念最初在1996年被提出，是一種基于概率模型的種群進(jìn)化算法，具有全局搜索能力強(qiáng)、收斂速度快的特點(diǎn)，但因其概率模型單一，易出現(xiàn)早熟現(xiàn)象[13]。模擬退火算法采用單點(diǎn)迭代搜索，具有突跳性強(qiáng)的特點(diǎn)，但學(xué)習(xí)能力較弱，其深度搜索易受降溫函數(shù)的影響[14]。因此，綜合兩者的優(yōu)缺點(diǎn)，本文提出了混合分布估計算法。

2.1編碼與解碼

選用基于工序的實(shí)數(shù)編碼規(guī)則求解JSP，采用隨機(jī)初始化的方法產(chǎn)生NIND個個體作為初始種群。個體長度為n×m，表示一個加工工序的排列，每個工件號均可出現(xiàn)m次。例如，3×3問題實(shí)例，個體[123311232]，對應(yīng)的工序加工序列可以表示為

(O11，O21，O31，O32，O12，O13，O22，O33，O23)。其中，Oij為第i工件的第j道工序。在解碼過程中，由于AGV運(yùn)輸操作參與車間生產(chǎn)，考慮到AGV在不同機(jī)器之間的運(yùn)輸時間，每道工序在機(jī)器上的加工開始時間確定規(guī)則為：假設(shè)機(jī)器k上前后兩道工序分別為Opq和Oij，Opq在k上的完工時間為Cpqk，Oij所對應(yīng)工件的前一道工序Oi(j-1)在機(jī)器w上的完工時間為Ci(j-1)w，AGV在機(jī)器k、w之間的運(yùn)輸時間為twk，那么工序Oij在機(jī)器k上的最早開始時間Sijk計算如下：若Cpqk≥Ci(j-1)w+twk，則Sijk=Cpqk；若Cpqk＜Ci(j-1)w+twk，則Sijk=Ci(j-1)w+twk。

2.2評價函數(shù)

由于完工時間C和總能耗E是2個相互沖突的目標(biāo)，參考文獻(xiàn)[15]，本文對2個目標(biāo)進(jìn)行去量綱加權(quán)求和構(gòu)成單目標(biāo)函數(shù)

式中，w(0≤w≤1)為權(quán)重系數(shù)，企業(yè)可以通過設(shè)置w的大小來調(diào)整目標(biāo)函數(shù)傾向；Cmax和Cmin分別為目標(biāo)函數(shù)完工時間的最大值和最小值；Emax和Emin分別為目標(biāo)函數(shù)綜合能耗的最大值和最小值。

2.3選擇算子

采用輪盤賭的方式從初始種群中選擇N(N＜NIND)個個體作為模擬退火算法(simulated annealing algorithm，SAA)的初始種群。初始溫度定義為

式中，fmax、fmin分別為群體適應(yīng)度最大值和最小值， Pr為最優(yōu)個體接受概率。

對于每代優(yōu)勢種群中的每個個體隨機(jī)交換染色體中2個位置上的元素，產(chǎn)生一個新個體Popnew運(yùn)用Metropolis抽樣策略，以一定的概率接受新解，接受概率為

黨中央歷來高度重視黨和國家機(jī)構(gòu)建設(shè)和改革。新中國成立后，在我們黨領(lǐng)導(dǎo)下，我國確立了社會主義基本制度，逐步建立起具有我國特點(diǎn)的黨和國家機(jī)構(gòu)職能體系，為我們黨治國理政、推進(jìn)社會主義建設(shè)發(fā)揮了重要作用。尤其是改革開放以來，我們黨積極推進(jìn)黨和國家機(jī)構(gòu)改革，各方面機(jī)構(gòu)職能不斷優(yōu)化、逐步規(guī)范，實(shí)現(xiàn)了從計劃經(jīng)濟(jì)條件下的機(jī)構(gòu)職能體系向社會主義市場經(jīng)濟(jì)條件下的機(jī)構(gòu)職能體系的重大轉(zhuǎn)變，推動了改革開放和社會主義現(xiàn)代化建設(shè)?；赝母镩_放40年來，為適應(yīng)黨和國家工作中心轉(zhuǎn)移、社會主義市場經(jīng)濟(jì)發(fā)展和各方面工作不斷深入的需要，黨和國家機(jī)構(gòu)改革與時俱進(jìn)，不斷深化，構(gòu)成40年改革開放偉大實(shí)踐的重要內(nèi)容。

其中，ue為第e代的溫度，然后隨機(jī)產(chǎn)生一個[0,1]之間的數(shù)Re，如果ρ＞Re，接受新解，否則不接受。模擬退火算法一般采用ue+1=γue的降溫方式。為在運(yùn)行過程中對溫度空間有充分的搜索以避免錯過全局最優(yōu)解，本文提出新的降溫函數(shù)

在算法迭代過程中，當(dāng)多次迭代卻不更新最優(yōu)解時，引入回火機(jī)制，人為地增加溫度u，從而提高算法突變概率。設(shè)置回火代數(shù)為10，回火溫度更新函數(shù)為

式中，g為退火次數(shù)，u為回火最終解。

2.4構(gòu)建概率模型

概率模型的合理性對算法性能起關(guān)鍵作用，參照文獻(xiàn)[14,16]構(gòu)建概率模型的思想，結(jié)合自身研究問題的特點(diǎn)設(shè)計了一種n行l(wèi)列的矩陣P來表示解空間分布的概率模型。式(21)為第e代概率模型P(e)。

其中，P(e)中元素∈[0,1],(1≤i≤n,1≤j≤l,l=n×m)為 第e代中工件i位 于第 j個位置的概率。

2.5概率模型的更新及新種群的生成

為了使概率模型矩陣P更準(zhǔn)確地表示解空間的分布情況以及進(jìn)化趨勢，采用機(jī)器學(xué)習(xí)中的Hebb規(guī)則更新概率矩陣中的所有元素。

基于隨機(jī)矩陣P，采用輪盤賭的方式隨機(jī)產(chǎn)生新種群。為了保證分布估計算法迭代過程中最優(yōu)解不退化，在群體采樣時可以使用精英保留策略，即只產(chǎn)生NIND-1個新個體，并與當(dāng)前最優(yōu)個體一起構(gòu)成新一代種群。

2.6 算法流程圖

首先，設(shè)定算法的各種參數(shù)，并隨機(jī)初始化種群。其次，根據(jù)式(15)目標(biāo)函數(shù)計算適應(yīng)度，以一定方式選擇一定數(shù)量的優(yōu)勢群體作為SAA的初始種群。然后，基于模擬退火函數(shù)式(18)產(chǎn)生更多優(yōu)秀個體，并用優(yōu)勢群體來更新概率模型。最后，采用新的概率矩陣P產(chǎn)生新種群。具體流程如圖4所示。

圖4混合分布估計算法流程圖Figure 4 Flow chart of hybrid distribution estimation algorithm

3數(shù)值實(shí)驗

為了驗證混合分布估計算法的有效性，選擇Taillard[17]提出的作業(yè)車間調(diào)度問題的基準(zhǔn)案例FT06、FT10和FT20，采用本文提出算法進(jìn)行求解20次并與EDA[18]、SAA[19]算法進(jìn)行對比，調(diào)度目標(biāo)為最優(yōu)化完工時間(w=0)。實(shí)驗設(shè)計環(huán)境和配置為Intel Core i5-3230M、2.6 GHZ CPU、4.00 G RAM、Windows 7 64位操作系統(tǒng)。程序編譯和運(yùn)行環(huán)境為Matlab R2014a。

參數(shù)設(shè)置為：學(xué)習(xí)速率α=0.38[18]；算法迭代次數(shù) 1 500作為終止條件；種群大小為60；初始接受概率Pr=0.8。優(yōu)化結(jié)果如表1所示。

表1的仿真結(jié)果表明，本文提出的混合分布估計算法3個算例求解結(jié)果均明顯優(yōu)于EDA、SAA算法，證明了該算法的有效性。

表1不同算法優(yōu)化結(jié)果Table 1 Optimization results based on different algorithms

對于FT06問題，先分配機(jī)器調(diào)度后分配AGV調(diào)度，實(shí)際加工時直接產(chǎn)生物料運(yùn)輸時間，最大完工時間為67 min，其調(diào)度甘特圖如圖5所示。將AGV與機(jī)器集成調(diào)度時，采用本文提出的混合分布估計算法和上述參數(shù)設(shè)置進(jìn)行求解，通過實(shí)驗測試10次均可得到最大完工時間為63 min，其調(diào)度甘特圖如圖6所示。最大完工時間數(shù)值從67降到63，生產(chǎn)效率提高了8.95%。這充分說明考慮物料運(yùn)輸與加工資源集成調(diào)度的必要性。

圖5 AGVs與機(jī)器未集成下調(diào)度甘特圖Figure 5 Gantt chart of the unintegrated scheduling with AGVs and machines

圖6 AGVs與機(jī)器集成下調(diào)度甘特圖Figure 6 Gantt chart of the integrated scheduling with AGVs and machines

為驗證考慮物料運(yùn)輸與加工資源集成調(diào)度模型節(jié)能的有效性，本文以FT10案例為基礎(chǔ)，參照文獻(xiàn)[20]設(shè)定機(jī)床生產(chǎn)時的功率(表2)?？疾鞂?shí)際車間布局設(shè)定機(jī)器間運(yùn)輸時間(表3)和運(yùn)輸設(shè)備功率為1.89 kW，整個車間其他輔助設(shè)備平均功耗為1 kW。

優(yōu)化算法的權(quán)重系數(shù)w在[0,1]之間變化，將運(yùn)輸服務(wù)資源與加工資源分別獨(dú)立調(diào)度和運(yùn)輸服務(wù)資源與加工資源集成調(diào)度2種情形在不同權(quán)重系數(shù)下運(yùn)行20次，優(yōu)化的完工時間和能量消耗取平均值，測試結(jié)果如表4所示。

表2機(jī)器功率信息Table 2 Information on machines power

表3 AGV在機(jī)器間的運(yùn)輸時間Table 3 Transportation time of AGVs between machines s

表4 AGVs與機(jī)器集成和未集成的調(diào)度實(shí)驗結(jié)果Table 4 Experimental results of the integrated or unintegrated scheduling with AGVs and machines

在實(shí)際生產(chǎn)中，能量消耗和完工時間相互排斥，不能同時達(dá)到最優(yōu)。如表4所示，當(dāng)w=0時，AGV運(yùn)輸與加工資源集成調(diào)度，平均完工時間為980.32 min，能量消耗為975.65 kWh；當(dāng)w=1時完工時間為1 202.32 min，總能耗提高約4.67%。這在企業(yè)交貨期不緊張時可以適當(dāng)調(diào)節(jié)權(quán)重，減少能量消耗。

AGV運(yùn)輸與加工資源集成調(diào)度與分開調(diào)度相比，在不同權(quán)重系數(shù)下能量消耗平均降低約1%，完工時間平均降低1.6%。這表明AGV運(yùn)輸與加工資源集成調(diào)度既能提高生產(chǎn)效率又可以降低能量消耗。

4不同AGV運(yùn)輸速度時的車間總能耗變化

以表3數(shù)據(jù)為基準(zhǔn)運(yùn)輸時間，分別以2倍和10倍基準(zhǔn)運(yùn)輸時間作為中速和低速作業(yè)模式。3種不同AGV運(yùn)輸速度下的能耗變化如圖7～9所示。

圖7 w=0時不同運(yùn)輸速度下能量消耗Figure 7 Energy consumption at different transport speeds with w=0

圖8 w=0.5時不同運(yùn)輸速度下能量消耗Figure 8 Energy consumption at different transport speeds with w=0.5

圖9 w=1.0時不同運(yùn)輸速度下能量消耗Figure 9 Energy consumption at different transport speeds with w=1

圖7～9表明加工能耗不受調(diào)度的影響，始終保持不變。不同權(quán)重系數(shù)w下，當(dāng)速度提高2倍時，總能耗平均降低3.2%，空轉(zhuǎn)能耗平均降低16.3%，公共能耗平均降低6.71%；當(dāng)速度提高10倍時，總能耗平均降低17.6%，空轉(zhuǎn)能耗平均降低56.3%，公共能耗平均降低23.1%，運(yùn)輸能耗降低10倍。但本文沒有充分考慮運(yùn)輸速度的變化對AGV功率的影響。一般地，速度提高，相應(yīng)的功率會變大，運(yùn)輸能耗也會增加，后續(xù)研究工作會在運(yùn)輸速度變化引起的功率能耗的變化上進(jìn)行深入研究，進(jìn)一步提高車間能耗的節(jié)能效率。

5結(jié)論

本文分析作業(yè)車間調(diào)度的特點(diǎn)，結(jié)合實(shí)際生產(chǎn)需要，對車間加工資源和AGV運(yùn)輸進(jìn)行集成調(diào)度，建立完工時間和能量消耗的多目標(biāo)作業(yè)車間調(diào)度模型。提出一種融入模擬退火思想的分布估計算法，并設(shè)計新的退火函數(shù)，引入回火機(jī)制。實(shí)驗結(jié)果表明：當(dāng)不考慮能耗影響時，通過協(xié)同優(yōu)化加工時間和AGV運(yùn)輸時間可以使完工效率提高8.95%；分析不同物料運(yùn)輸速度下的能量消耗，物料運(yùn)輸速度提高10倍，總能耗降低17.6%；當(dāng)交貨期不緊張時，可以調(diào)節(jié)權(quán)重系數(shù)w，節(jié)能可達(dá)4.67%。這可為企業(yè)適應(yīng)當(dāng)下節(jié)能、環(huán)保的大環(huán)境提供幫助，為企業(yè)可持續(xù)發(fā)展提供新思路。