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

李小林,張 松,陳華平

（1.中國礦業大學礦業工程學院,江蘇徐州 221116；2.中國科學技術大學管理學院,安徽合肥 230026）

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

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

（1.中國礦業大學礦業工程學院,江蘇徐州 221116；2.中國科學技術大學管理學院,安徽合肥 230026）

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

多目標；調度；蟻群算法；批處理機；分時電價

1 引言

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

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

結合分時電價,將批調度過程進行優化,制定合理的分批加工方案,將有效提高生產的經濟效益,這也是本文關注的主要內容。

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

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

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

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

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

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

2 問題模型

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

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

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

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

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

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

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

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

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

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

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

所研究問題以三參數表示法可表示為1| batch,pi,si≤C|｛Cmax,EC｝其中,batch表示機器為批處理機。pi和si表示工件具有不同加工時間及尺寸。基于上面的假設及符號說明,可建立問題相應數學模型如下：

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

3 兩種蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

3.1 多目標蟻群算法流程

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

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

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

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

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

FFLPT算法流程：

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

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

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

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

3.2 信息素

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

在算法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 啟發式信息

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

（1）算法J-PACO中啟發式信息

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

（2）算法B-PACO中啟發式信息

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

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

3.4 狀態轉移概率

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

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

（1）J-PACO算法中狀態轉移概率

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

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

（2）B-PACO算法中狀態轉移概率

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

3.5 信息素更新

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

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

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

4 仿真實驗與分析

4.1 實驗設計

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

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

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

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

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

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

4.2 參數設置

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

所有算法使用Visual C#語言實現,運行環境為Intel E2200處理器,2GB內存。

4.3 實驗結果與分析

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

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

表2 算法參數設置

表3 各算法求解結果比較

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

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

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

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

5 結語

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

從實驗中也可看出,由于算法設計機制原因,JPACO算法在具有較高復雜度的同時,可以對解的多樣性進行更有效的搜索。下一步可以設計更為有效的算法對問題進行求解,同時也可對機器環境等進行擴展,以應用到調度領域的其它問題。

[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］王栓獅,陳華平,程八一,等.一種差異工件單機批調度問題的蟻群優化算法[J］.管理科學學報,2009,12（6）：72-82.

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

[13］程八一,陳華平,王栓獅,基于微粒群算法的單機不同尺寸工件批調度問題求解[J］.中國管理科學, 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

創新研究群體科學基金資助項目（70821001）；國家自然基金資助項目（71171184）；中國礦業大學青年科技基金項目（2014QNA48）；國家自然科學青年基金項目（71401164）

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