考慮分時電價的多目標批調(diào)度問題蟻群算法求解

李小林,張 松,陳華平

（1.中國礦業(yè)大學(xué)礦業(yè)工程學(xué)院,江蘇徐州 221116；2.中國科學(xué)技術(shù)大學(xué)管理學(xué)院,安徽合肥 230026）

考慮分時電價的多目標批調(diào)度問題蟻群算法求解

李小林1,張 松2,陳華平2

（1.中國礦業(yè)大學(xué)礦業(yè)工程學(xué)院,江蘇徐州 221116；2.中國科學(xué)技術(shù)大學(xué)管理學(xué)院,安徽合肥 230026）

對同時優(yōu)化電力成本和制造跨度的多目標批處理機調(diào)度問題進行了研究,設(shè)計了兩種多目標蟻群算法,基于工件序的多目標蟻群算法（J-PACO,Job-based Pareto Ant Colony Optimization）和基于成批的多目標蟻群算法（B-PACO,Batch-based Pareto Ant Colony Optimization）對問題進行求解分析。由于分時電價中電價是時間的函數(shù),因而在傳統(tǒng)批調(diào)度進行批排序的基礎(chǔ)上,需要進一步確定批加工時間點以測定電力成本。提出的兩種蟻群算法分別將工件和批與時間線相結(jié)合進行調(diào)度對此類問題進行求解。通過仿真實驗將兩種算法對問題的求解進行了比較,仿真實驗表明B-PACO算法通過結(jié)合FFLPT（First Fit Longest Processing Time）啟發(fā)式算法先將工件成批再生成最終方案,提高了算法搜索效率,并且在衡量算法搜索非支配解數(shù)量的Q指標和衡量非支配集與Pareto邊界接近程度的HV指標上,均優(yōu)于J-PACO算法。

多目標；調(diào)度；蟻群算法；批處理機；分時電價

1 引言

批調(diào)度問題是調(diào)度領(lǐng)域一個重要的研究部分,在現(xiàn)實生產(chǎn)制造環(huán)境中有著廣泛的應(yīng)用。如集成電路制造、鋼鐵生產(chǎn)、貨物運輸?shù)壬a(chǎn)加工過程中[1］,均存在將多個工件作為一批同時進行加工處理的情況。典型的如半導(dǎo)體制造系統(tǒng)中芯片的老化程序,這一過程會將多個工件作為一批同時放在一臺測試箱中進行高溫預(yù)燒,以檢驗出有潛在缺陷的芯片。此過程中,測試箱即為批處理機器,由于芯片預(yù)燒時間必須大于等于預(yù)設(shè)值,所以一批芯片的加工時間等于所有芯片加工時間的最大值。由于此過程相對其它操作耗時較長（120h相比4-5h）,這使得批處理機的加工成為一個瓶頸環(huán)節(jié),對該過程進行優(yōu)化將有很大的生產(chǎn)意義。

同時,隨著“綠色制造”概念的提出,在生產(chǎn)加工過程中考慮能源效率變得愈加重要,通過再造工藝流程、優(yōu)化生產(chǎn)計劃以提高設(shè)備利用率、降低能源消耗等也成為研究的重要內(nèi)容。電能是工業(yè)生產(chǎn)中廣泛應(yīng)用的能源,當(dāng)前很多地區(qū)工業(yè)用電采用分時電價（TOU,Time of Use）,這讓生產(chǎn)過程中合理轉(zhuǎn)移用電負荷、削峰填谷以提高效益、降低能耗提供了可能。

結(jié)合分時電價,將批調(diào)度過程進行優(yōu)化,制定合理的分批加工方案,將有效提高生產(chǎn)的經(jīng)濟效益,這也是本文關(guān)注的主要內(nèi)容。

不同于經(jīng)典調(diào)度問題,批調(diào)度問題的一個顯著特征就是批處理機可以將多個工件作為一批同時進行加工。批調(diào)度問題首先由Ikura等[2］提出,其所研究的問題中,工件具有相同尺寸,批容量由其所能容納的工件個數(shù)確定。Uzsoy[3］將問題擴展到工件尺寸不同的情況,對單機情況下最小化Cmax和∑Ci目標函數(shù)進行了研究,結(jié)合裝箱問題證明二者均為NP難的,給出了包含性能較好的FFLPT（First Fit Longest Processing Time）在內(nèi)的若干啟發(fā)式算法。在最小化Cmax為目標函數(shù)情況下,Dupont等[4-5］提出SKP（Successive Knapsack Problem）和BFLPT（Best Fit Longest Processing Time）兩個啟發(fā)式算法,兩者在單機情況下對最小化制造跨度的求解效果優(yōu)于Uzsoy提出的FFLPT啟發(fā)式算法。

啟發(fā)式算法具有實現(xiàn)簡單、求解速度快等優(yōu)點,可以在合理時間內(nèi)給出可行解,但啟發(fā)式算法屬于貪婪算法,無法預(yù)計解的質(zhì)量。也有研究者使用最優(yōu)化算法對問題進行求解。Brucker[6］等對以∑wiUi為目標的批調(diào)度問題進行了研究,當(dāng)所有工件具有相同權(quán)重時,給出了一個時間復(fù)雜度為O（n3）的動態(tài)規(guī)劃算法。Uzsoy等[7］提出了一個分支定界算法求解以最小化總加權(quán)完工時間為目標的單機差異工件批調(diào)度問題。Dupont等[5］結(jié)合FFLPT和BFLPT對最小化制造跨度的單機批調(diào)度問題提出一個分支定界算法,取得較好效果。

但由于本文所研究問題是NP難的,最優(yōu)化的求解方法對大規(guī)模的算例求解時會導(dǎo)致難以接受的計算量。Melouk等[8］首先使用元啟發(fā)式算法對批調(diào)度問題進行求解,將所提的模擬退火算法與商業(yè)軟件CPLEX求解情況做了比較,取得更優(yōu)的效果。之后又有研究分別采用遺傳算法[9-10］、蟻群算法[11-12］和微粒群算法[13］等對該類問題進行了求解和比較,結(jié)果均顯示元啟發(fā)式算法在不同規(guī)模算例下,均可以在合理時間內(nèi)穩(wěn)定的取得較高質(zhì)量的解。

以上研究在目標函數(shù)上均為單目標,在多目標單機批調(diào)度問題方面尚沒有進行廣泛的研究。已有研究中,Kashan等[14］給出兩種混合多目標遺傳算法BHMOGA和SMOGA對最小化制造跨度和最小化最大延遲這兩個目標進行優(yōu)化,結(jié)果顯示BHMOGA優(yōu)于SMOGA。

本文在最小化制造跨度的同時,將能源消耗作為優(yōu)化目標之一對批調(diào)度問題進行求解。將工件加工時間和分時電價結(jié)合起來計算的電力成本,作為能源消耗這一目標的計算依據(jù)。由于分時電價是時間的函數(shù),具有周期性波動的特點,在確定批加工順序之后需要進一步得到各批開始加工時間才能對電力成本進行計算。因此,在對問題進行求解時,提出按時間點進行工件和批分配的兩種螞蟻算法對此類多目標問題進行求解。

對于批調(diào)度及多目標調(diào)度更全面的文獻回顧可參見Potts[15］和Lei Deming[16］。

2 問題模型

本文在研究目標上考慮制造跨度和電力成本,是典型的多目標組合優(yōu)化（MOCO,Multiple-Objective Combinatorial Optimization）問題[17］。一般化的MOCO問題可以描述如下：

x=[x1,…,xN］為N維離散型決策變量, fi（x）為第i個目標函數(shù),D是可行解集。

如果?i∈｛1,…,J｝,有fi（x′）≥fi（x）,并且至少在一個目標i上滿足fi（x′）＞fi（x）,則稱解x支配（dominate）解x′。

在多目標優(yōu)化算法中,針對其當(dāng)前在搜索過程中找到的最優(yōu)個體（即當(dāng)前最優(yōu)解）,我們算法搜索到的當(dāng)前最優(yōu)解稱之為非支配解（Non-Dominated solution）,所有非支配解的集合,稱作當(dāng)前群體的非支配集（Non-Dominated Solutions,NDS）。

如果不存在x′∈D支配解x*,則稱解x*為Pareto最優(yōu)解,所有的Pareto最優(yōu)解的集合稱為Pareto最優(yōu)解集或Pareto前沿。

本文所研究問題可具體描述如下：

（1）n個工件的集合J=｛1,2,…,n｝,工件i的加工時間為pi,尺寸為si。

（2）機器容量為C,單個工件尺寸si均小于機器容量,每個批中工件尺寸之和不超過機器容量。

（3）同一批工件具有相同的開始、結(jié)束加工時間,從一批開始加工直到該批加工完成,整個過程不允許中斷,批b的加工時間Pb由該批中加工時間最大的工件決定。所有機器和工件均在0時刻可用。任一批b開始加工時間為Sb,則其完工時間Cb= Sb+Pb。

（4）兩個最優(yōu)化目標分別為最大制造跨度Cmax和電力成本EC。Cmax為最后一批工件的完工時間。用電價函數(shù)為f（t）來表示任意時刻t的電價。機器功率恒定記為1,用電價乘以一批工件加工時間來表示該批工件加工的電力成本。總的電力成本EC即為所有批加工的電力成本之和。

（5）一個解方案中所有批的集合用B表示,批可以在任意一個時刻開始加工,但每個時刻最多有一個批在加工。

所研究問題以三參數(shù)表示法可表示為1| batch,pi,si≤C|｛Cmax,EC｝其中,batch表示機器為批處理機。pi和si表示工件具有不同加工時間及尺寸?；谏厦娴募僭O(shè)及符號說明,可建立問題相應(yīng)數(shù)學(xué)模型如下：

其中：式（2）和式（3）為優(yōu)化的目標函數(shù)制造跨度Cmax和總電力成本EC。式（4）表示一個工件必須且只能屬于一個批。式（5）要求一個批只由一臺機器在第k位置加工。式（6）表明機器容量約束,一批中所有工件之和應(yīng)小于等于機器容量。式（7）指批的加工時間由批中加工時間最長的工件決定。式（8）計算任一批的完工時間。式（9）表明,前一批加工完成后,后一個批才能開始加工。式（10）和式（11）約束決策變量只能取0或1。

3 兩種蟻群算法

根據(jù)信息存儲和解的編碼的不同,本文給出兩種多目標蟻群算法對所研究的多目標批調(diào)度問題進行求解,本文考慮的兩個目標一個衡量加工時間,另一個衡量在分時電價條件下的電力成本。顯然,在單機情況下,各工件開始加工時間不同,會導(dǎo)致不同的最大完工時間,又由于不同時段電價不同,所以,各工件在不同時間點開始加工同樣會影響電力成本。當(dāng)工件序列成批方案確定后,在極端情況下,當(dāng)所有批連續(xù)加工時,可得到最小的最大完工時間,而當(dāng)所有批避開高電價時段,均在低電價時段加工時,則可得到最小的電力成本,但此時顯然會增大最大完工時間。

兩種蟻群算法通過將工件序列調(diào)整為在不同時間點加工的批來獲得最終的解,從而需要先確定將所有工件加工完成所需要的最大時間長度。下面,通過定義所研究問題Cmax目標的上下界,給出將所有工件加工完成需要的時間點數(shù)。

定義1 將所有工件加工完成的制造跨度為t,對應(yīng)電力成本為ECt,如果不存在t+Δt,Δt＞0,使得ECt+Δt＜ECt,則稱t為制造跨度上界C。

步驟1將工件集合J中所有工件按加工時間非增序排列；

步驟2每個工件單獨成一批,得批序列B；

步驟3從批序列B頭部選擇一個批b,將其安排在第一個未占用低電價時段開始時間點加工。重復(fù)步驟3直至所有批安排加工完成,所得最大完工時間即為制造跨度上界。

步驟1 將工件集合J中每個工件松弛為si個加工時間為pi的單位尺寸工件,得到工件集合Ju；

步驟2 將工件集合Ju中的工件按加工時間非增序排列；

步驟3 依次將Ju中iC+1～（i+1）C個工件分為一批,其中i=0,1,…,|Ju|/C,x表示小于等于x的最大整數(shù),得批集合B；

步驟4 批集合B中所有批加工時間之和即為制造跨度下界。

用一個時間點表示一個單位的時間,顯然將所有工件加工完成所需要的時間點數(shù)N,滿足C≤N≤C。

在電力成本方面給出如下兩個定義,以用于之后對算法的性能分析。

3.1 多目標蟻群算法流程

（1）基于工件序的多目標蟻群算法

基于工件序的多目標蟻群算法（J-PACO,Jobbased Pareto Ant Colony Optimization）構(gòu)造解的方式為,先將工件安排至?xí)r間線的各時間點,再將各時間點上的工件作為一批進行加工。當(dāng)所有工件成批完成后,即可以確定方案的Cmax及EC,繼而根據(jù)兩個目標函數(shù)值分別對各目標的信息素進行更新,循環(huán)直至結(jié)束條件滿足,完成算法對解的搜索。

J-PACO算法對問題求解流程如下：

（2）基于成批的多目標蟻群算法

對于工件尺寸不同的單機批調(diào)度問題,Uzsoy[3］結(jié)合裝箱問題中的FF（First Fit）算法[28］給出了以最小化Makespan為目標,求解批調(diào)度問題的BFF（Batch First Fit）算法,并根據(jù)初始時工件排序不同給出若干種啟發(fā)式算法。其實驗表明,當(dāng)初始時工件按加工時間降序排列,再使用BFF算法將工件成批得到的FFLPT（First Fit Longest Processing Time）算法對問題的求解效果優(yōu)于其它算法。FFLPT算法對單機批調(diào)度問題求解流程如下：

FFLPT算法流程：

步驟1 將工件按加工時間降序排列；

步驟2 依次選擇工件序列中的工件,并將之放在第一個可以容納該工件的批中,如果沒有批可以容納該工件,則將該工件放入新批中。重復(fù)步驟2直到所有工件分批完成。

基于成批的多目標蟻群算法（B-PACO,Batchbased Pareto Ant Colony Optimization）構(gòu)造解的方式為,蟻群算法將工件序按FFLPT算法成批,再將批分到時間線進行加工。所有批加工完成后,即完成整個方案的調(diào)度。根據(jù)Cmax和EC兩個目標函數(shù)值,對解元素的信息素進行更新,循環(huán)算法至終止條件滿足,完成解的搜索。

B-PACO算法對問題求解流程如下：

3.2 信息素

多目標蟻群算法中,可將信息保存在一個信息素矩陣中,也可為每個目標設(shè)置各自的信息素矩陣。為了使信息素對不同的目標具有區(qū)分性,本文采用后者,即對于每個目標k,將信息素保存在不同的信息素矩陣中。當(dāng)蟻群算法對解的構(gòu)造方式不同時,信息素的含義也不同。

在算法J-PACO中,算法在每個時間點選擇合適的工件進行加工,因而,信息素保存在工件和時間點之間。使用τCmax（i,t）表示在Cmax目標的信息矩

陣中,工件i和時間點t之間的信息素,使用τEC（i, t）表示在EC目標的信息矩陣中,工件i和時間點t之間的信息素。初始信息素為τ0。

而在B-PACO算法中,由于工件序列先通過FFLPT成批,蟻群算法主要將批分配到不同時間點,因而,信息素保存在批與時間點之間。使用τCmax（b,t）表示在Cmax目標的信息矩陣中,批b和時間點t之間的信息素,使用τEC（b,t）表示在EC目標的信息矩陣中,批b和時間點t之間的信息素。

3.3 啟發(fā)式信息

啟發(fā)式信息表示螞蟻在構(gòu)建解時,選擇下一個工件的期望程度,好的啟發(fā)式信息可以增加螞蟻找到近優(yōu)解的速度。

（1）算法J-PACO中啟發(fā)式信息

在J-PACO算法中,由于將工件分到時間線上后,按時間點對工件成批,即算法將工件成批和將批分配到機器作為一個整體進行處理,所以只需考慮將一個時間點的工件作為一個批進行構(gòu)造的啟發(fā)式信息。螞蟻確定當(dāng)前未安排工件i,并將之安排在可用時間點集合中合適的時間點來完成解的構(gòu)造。顯然,從工件加工時間考慮,應(yīng)使一個批中工件加工時間盡量接近,加大批的負載均衡。從工件尺寸考慮,應(yīng)使批的剩余空間最小,以提高批的利用率。根據(jù)這些考慮,給出如下的啟發(fā)式信息。

（2）算法B-PACO中啟發(fā)式信息

B-PACO算法對解的構(gòu)造,主要是將批分配到各時間點,為了降低電力成本,算法應(yīng)盡量將批安排到低電價時段進行加工。又由于批加工過程不可中斷,因而算法在構(gòu)造解時,應(yīng)將批分配到剩余時長與批加工時間相近的時間點進行加工。給出如下的啟發(fā)式信息。

其中,Πb,表示對當(dāng)前批而言,可安排的時間點集合。Lt表示時間點t所處的電價時段未安排加工的時間長度。

3.4 狀態(tài)轉(zhuǎn)移概率

蟻群算法構(gòu)建解的過程就是將工件（J-PACO算法中）或批（B-PACO算法中）安排在各時間點的過程,當(dāng)所有工件或批安排完成后,即完成了解的構(gòu)建。本文中設(shè)計的兩種蟻群算法均是順次將未安排的工件或批安排在合適時間點上的過程。

在J-PACO算法中,當(dāng)前可用時間點的確定應(yīng)滿足兩個條件a）時間點未被前一批加工所占用；b）當(dāng)前時間點已經(jīng)安排工件加工尺寸之和不超過機器容量。而B-PACO算法中,由于成批已經(jīng)完成,所以,只需要滿足條件a）即可。

（1）J-PACO算法中狀態(tài)轉(zhuǎn)移概率

J-PACO算法中,螞蟻首先確定當(dāng)前未安排工件i,繼而按式（16）在可用時間點集合Πi中選擇時間點t來安排工件i。

其中,q為[0,1）區(qū)間產(chǎn)生的隨機數(shù),參數(shù)q0（0≤q0＜1）事先確定。顯然,q0越大,則螞蟻越易選擇當(dāng)前最優(yōu)時間點,算法傾向于收斂,q0越小,則算法傾向于按概率選擇最優(yōu)時間點,增加算法對解空間探索能力。參數(shù)α和β用來區(qū)別信息素和啟發(fā)式信息的相對重要程度。

（2）B-PACO算法中狀態(tài)轉(zhuǎn)移概率

與J-PACO算法類似,只需將工件換作批,從可用時間點集合Πb按式（18）選擇時間點t進行加工即可。

3.5 信息素更新

當(dāng)所有工件分到時間線上,并成批完成后,即得到一個完整的調(diào)度方案,當(dāng)方案構(gòu)造完成后,為了增加優(yōu)秀方案中解元素的信息素濃度,降低劣解元素的信息素濃度來指導(dǎo)螞蟻的下一步向近優(yōu)解的搜索。需要對解元素進行信息更新,信息素更新主要包括信息素揮發(fā)和信息素釋放兩部分,記當(dāng)前迭代中所有螞蟻在目標k上得到的迭代最優(yōu)解為,搜索得到的全局最優(yōu)解為。

J-PACO算法中對各個目標k的信息素更新按式（20）進行。

將工件換作批,在B-PACO算法中,對各個目標k的信息素更新按式（22）進行。

4 仿真實驗與分析

4.1 實驗設(shè)計

本文通過隨機生成算例,對所提算法的有效性進行比較。算例的生成,主要考慮工件數(shù)量、工件加工時間、工件尺寸、電價時段個數(shù)、各電價時段長度、各電價時段價格。簡化起見,本文中,考慮電價時段個數(shù)為2,即只分為高電價時段和低電價時段,各電價時段時長相同,且高電價時段電價為低電價時段電價2倍。批處理機容量為10。實驗中,使用JiPiLk（i=1,2,3；i=1,2；k=1,2）來表示各類實例。各因素的具體取值如表1所示。

表1 算例生成的分類因素及取值

不同于單目標問題,多目標問題中對解質(zhì)量的衡量不僅涉及解本身數(shù)值的好壞,還要考慮所求Pareto解解的數(shù)量以及在解空間的分布情況。為了衡量各算法對所研究多目標問題的求解性能,實驗中采用數(shù)量指標Q和超體積指標（Hypervolume Indicator）[19］對算法求解結(jié)果進行比較。

其中,PM表示算法M得到的非支配解集,PR表示所有算法得到的非支配解集。|X|表示集合X中元素個數(shù)。顯然,Q∈[0,1］,該值越大,說明相應(yīng)算法可以找到更多的非支配解。

超體積指標（Hypervolume Indicator）是衡量一個非支配集與Pareto邊界接近程度的指標[19］,該值通過比較不同算法得到的Pareto解集相對于參考點形成的超體積大小來衡量解的質(zhì)量。本文設(shè)置參考點W=（CUmax,ECU）,用各算法所求非支配解與參考點W所形成的超體積比率,來比較算法之間求解效果[14］。

其中,HVX表示算法X所得非支配解相對于參考點W的超體積。取IRS=（CLBmax,ECLB）為理想?yún)⒖技?則HVIRS表示理想?yún)⒖技某w積。Gap值為正時,表示B-PACO算法性能優(yōu)于J-PACO算法。我們使用HVX/IRS來表示X算法的HV值與理想?yún)⒖技疕V值的比率,即HVX/IRS= HVX/HVIRS×100%,此值越大,則表明算法取得更優(yōu)的非支配解集。

4.2 參數(shù)設(shè)置

通過初步實驗,對算法J-PACO和B-PACO的參數(shù)按表2設(shè)置時對問題具有理想的求解效果。將蟻群算法種群規(guī)模增大時,算法可找到更優(yōu)的非支配解集,但運算時間會大幅增加,在本文所測試算例的規(guī)模下,綜合考慮解的質(zhì)量和運算時間,將種群規(guī)模設(shè)置為30。在接下來的實驗中,將兩個算法運行相同的迭代次數(shù),已使結(jié)果更有可比性。

所有算法使用Visual C#語言實現(xiàn),運行環(huán)境為Intel E2200處理器,2GB內(nèi)存。

4.3 實驗結(jié)果與分析

表3給出了各算法對問題的求解結(jié)果比較,表中第一列為算例分類,第三到五列為J-PACO算法的Q值、HV/IRS值和運行時間數(shù)據(jù)。第六到八列為B-PACO算法的Q值、HV/IRS值和運行時間數(shù)據(jù)。最后一列為B-PACO算法相對于J-PACO算法的Gap值。

從Q值可看出,在算法找到的非支配解數(shù)目上,B-PACO具有絕對優(yōu)勢,并且隨著工作數(shù)目的增加,算法B-PACO的Q值優(yōu)于J-PACO的趨勢增加,這說明當(dāng)問題規(guī)模增加時,B-PACO算法更有可能找到更多的非支配解。

表2 算法參數(shù)設(shè)置

表3 各算法求解結(jié)果比較

從HV/IRS值看,隨著問題規(guī)模的增加,二種算法HV/IRS值均變小,這主要是因為,當(dāng)問題規(guī)模增加時,在本文計算方式下,時間線長度會增加很快,從而導(dǎo)致HVIRS的值迅速增加。但B-PACO算法的HV/IRS值始終大于J-PACO算法的HV/ IRS值,這表明,B-PACO算法在所找到非支配解集的質(zhì)量上要優(yōu)于J-PACO算法。從Gap值可看出,兩種算法的HV/IRS值差距在縮小,這表明JPACO在解的構(gòu)造上有優(yōu)勢,這主要是因為,JPACO算法在構(gòu)造解時由于考慮的是將工件分配到時間點,從而在成批的多樣性方面要優(yōu)于B-PACO算法僅使用FFLPT成批,即J-PACO對于解的多樣性搜索能力要優(yōu)于B-PACO算法。

完成相同的迭代次數(shù),J-PACO算法在運行時間上,要遠大于B-PACO算法,這也是因為二者對解的構(gòu)造方式不同導(dǎo)致。B-PACO算法首先將工件成批,再將批分配到時間線上,這相對于J-PACO直接將工件成批和批分配到時間線結(jié)合在一起的方式而言,顯然大大縮小了蟻群算法中解元素的數(shù)目,從而提高了速度。B-PACO算法對算例求解時間包括將工件成批以及將批分配到時間線兩個階段,但由于將工件成批時使用FFLPT啟發(fā)式算法完成,這也大大節(jié)約了算法的求解時間。另外,加工時間和電價時段長度均會影響時間線長度繼而影響蟻群算法解元素個數(shù),從表3中可看出,加工時間和電價時段長度增加時,各算法運行時間均增加。

圖1 各算法求解J2類算例所得非支配解集

圖1顯示了算例規(guī)模為50時,J-PACO算法和B-PACO算法所解得非支配解集對比情況。由圖中易看出,B-PACO算法求解結(jié)果普遍優(yōu)于J-PACO算法,從所搜索的非支配解數(shù)目上,B-PACO算法基本優(yōu)于J-PACO算法的搜索結(jié)果。由于問題優(yōu)化的兩個目標均為最小化目標,而B-PACO算法在各個解目標上均優(yōu)于J-PACO求解效果,所以B-PACO算法所得非支配解集基本分布在J-PACO所得非支配解集的左下方。這里也可以直觀的看出前面所定義超體積指標真實的反映了算法對問題的求解效果。從圖1的各子圖中還可觀察到B-PACO的解向Cmax較小方向上分布,這主要是因為J-PACO算法將工件在整個時間線上分布并構(gòu)造批,而BPACO先使用啟發(fā)式算法成批,批的利用率較高,從而易于找到Cmax較小的解。

5 結(jié)語

本文將批處理機調(diào)度問題擴展到多目標范圍,在單機環(huán)境下,將工件制造跨度以及方案所需電力成本同時進行優(yōu)化。設(shè)計兩種蟻群算法J-PACO和B-PACO對此多目標組合優(yōu)化問題進行了求解,JPACO將工件成批和分配到時間點進行加工作為一個整體進行了考慮,具有較高的算法復(fù)雜度,而BPACO算法先使用FFLPT啟發(fā)式算法將工件成批,之后著重考慮將批分配到不同時間點進行加工,相比之下降低了問題復(fù)雜度,提高了批的利用率。通過之后的實驗也可看出,B-PACO算法在搜索到非支配解的數(shù)量和質(zhì)量上均優(yōu)于J-PACO算法。

從實驗中也可看出,由于算法設(shè)計機制原因,JPACO算法在具有較高復(fù)雜度的同時,可以對解的多樣性進行更有效的搜索。下一步可以設(shè)計更為有效的算法對問題進行求解,同時也可對機器環(huán)境等進行擴展,以應(yīng)用到調(diào)度領(lǐng)域的其它問題。

[1］Ahmadi J H,Ahmadi R H,Dasu S,et al.Batching and scheduling jobs on batch and discrete processors[J］. Operations Research,1992,40（4）：750-763.

[2］Ikura Y,Gimple M.Efficient scheduling algorithms for a single batch processing machine[J］.Operations Research Letters,1986,5（2）：61-65.

[3］Uzsoy R.Scheduling a single batch processing machine with nonidentical job sizes[J］.International Journal of Production Research,1994,32（7）：1615-1635.

[4］Dupont L,Ghazvini F J.Minimizing makespan on a single batch processing machine with non-identical job sizes [J］.APII-JESA Journal Europeen des Systemes Automatises,1998,32（4）：431-440.

[5］Dupont L,Dhaenens-Flipo C.Minimizing the makespan on a batch machine with non-identical job sizes：An exact procedure[J］.Computers&Operations Research, 2002,29（7）：807-819.

[6］Brucker P,Kovalyov M Y.Single machine batch scheduling to minimize the weighted number of late jobs[J］. ZOR-Mathematical Methods of Operations Research, 1996,43（1）：1-88.

[7］Uzsoy R,Yang Yaoyu.Minimizing total weighted completion time on a single batch processing machine[J］.Production and Operations Management,1997,6（1）：57-73.

[8］Melouk S,Damodaran P,Chang Pingyu.Minimizing makespan for single machine batch processing with nonidentical job sizes using simulated annealing[J］.International Journal of Production Economics,2004,87（2）：141-147.

[9］Damodaran P,Manjeshwar P K,Srihari K.Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms[J］.International Journal of Production Economics,2006,103（2）：882-891.

[10］Kashanl A H,Karimi B,Jolai F.Minimizing makespan on a single batch processing machine with non-identical job sizes：A hybrid genetic approach[M］.∥Raidl J G G R.Evolutionary Computation in Combinatorial Optimization.Springer-Verlag Berlin：Berlin, 2006：135-146.

[11］王栓獅,陳華平,程八一,等.一種差異工件單機批調(diào)度問題的蟻群優(yōu)化算法[J］.管理科學(xué)學(xué)報,2009,12（6）：72-82.

[12］杜冰,陳華平,程八一,等.具有不同到達時間的差異工件批調(diào)度問題的蟻群聚類算法[J］.系統(tǒng)工程理論與實踐,201030（9）：1701-1709.

[13］程八一,陳華平,王栓獅,基于微粒群算法的單機不同尺寸工件批調(diào)度問題求解[J］.中國管理科學(xué), 2008,16（3）：84-88.

[14］Kashan A H,Karimi B,Jolai F.An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes[J］.Engineering Applications of Artificial Intelligence,2010,23（6）：911-922.

[15］Potts C N,Kovalyov M Y.Scheduling with batching：A review[J］.European Journal of Operational Research,2000,120（2）：228-249.

[16］Lei Deming.Multi-objective production scheduling：a survey[J］.International Journal of Advanced Manufacturing Technology,2009,43（9-10）：926-938.

[17］Jaszkiewicz A.Genetic local search for multi-objective combinatorial optimization[J］.European Journal of Operational Research,2002,137（1）：50-71.

[18］Johnson D S,Demers A,Ullman J D,et al.Worst-case performance bounds for simple one-dimensional packing algorithms[J］.SIAM Journal on Computing,1974,3（4）：299-325.

[19］Zitzler E,Thiele L.Multiobjective optimization using evolutionary algorithms-A comparative case study [M］//E：ben A E.Parallel problem solving from nature-Ppsn V.Berlin：Springer-Verlag Berlin,1998：292 -301.

Solving Multi-objective Batch Scheduling Under TOU Price Using Ant Colony Optimization

LI Xiao-lin1,ZHANG Song2,CHEN Hua-ping2

（1.School of Mines,China University of Mining and Technology,Xuzhou 221116,China；2.School of Management,University of Science and Technology of China,Hefei 230026,China）

The problem of scheduling batch processing machines is considered in this study.Batch processing machines are encountered in various manufacturing environment and the study is motivated by burningin operation in semiconductor manufacturing while time-of-use electricity price is considered as well.In the problem under study,jobs seizes are non-identical and machines are batch processing machines which can process several jobs simultaneously as a batch.Since the electricity price is time related,the objectives of electrical cost and makespan is influenced by start processing time of each batch.These two objectives were minimized simultaneously on single batch processing machine with non-identical job sizes.Two pareto ant colony optimization algorithms were designed to solve the problem.One is J-PACO（Job-based Pareto Ant Colony Optimization）algorithm and the other is B-PACO（Batch-based Ant Colony Optimization）algorithm.This problem is different from traditional batch scheduling problems.As the price is related to the time,the start processing time of jobs should be determined after the sequence of batches are fixed.In the two algorithms proposed,jobs and batches are scheduled on time line separately.Random job instances are generated in the simulation experimentation to evaluate the performance of algorithms proposed.The experiment results indicate that B-PACO,which group jobs into batches using FFLPT（First Fit Longest Processing Time）,outperforms J-PACO in computational time,numbers of non-dominated solution and hypervolume.The study will be helpful in the application of ACO involving multi objectives.And,the idea of allocating jobs in a time line before they are grouped into batches can also be used in scheduling batch processing machines.

multi-objective；scheduling；ant colony optimization；batch processing machine；TOU price

TP301

A

1003-207（2014）12-0056-09

2012-03-19；

2013-05-14

創(chuàng)新研究群體科學(xué)基金資助項目（70821001）；國家自然基金資助項目（71171184）；中國礦業(yè)大學(xué)青年科技基金項目（2014QNA48）；國家自然科學(xué)青年基金項目（71401164）

李小林（1986-）,男（漢族）,江蘇徐州人,中國礦業(yè)大學(xué)礦業(yè)工程學(xué)院,講師,研究方向：智能優(yōu)化算法、信息系統(tǒng).