李國臣，喬非，王俊凱，馬玉敏，盧凱璐

考慮能耗約束的并行機組批調(diào)度

李國臣，喬非，王俊凱，馬玉敏，盧凱璐

(同濟大學(xué)電子與信息工程學(xué)院，上海，201804)

研究并行批處理機的組批調(diào)度問題，考慮爐容相同、功率不同的非等同并行機的總能耗約束，考慮工件尺寸和到達時間不同，以最小化最大完工時間為目標(biāo)建立混合整數(shù)規(guī)劃模型。并行機組批調(diào)度問題屬于NP-hard問題，采用先組批后調(diào)度的兩階段方式求解。組批階段采用基于FFLPT和BFLPT的啟發(fā)式規(guī)則，調(diào)度階段設(shè)計帶鄰域搜索的粒子群?遺傳混合算法對模型進行求解。以軋輥生產(chǎn)企業(yè)并行熱處理設(shè)備為研究案例進行模型和算法驗證，分析不同能耗約束下最大完工時間優(yōu)化值，并比較算法的優(yōu)化性能。實驗結(jié)果表明：本文算法提高標(biāo)準(zhǔn)遺傳算法的收斂速度，且優(yōu)于2種啟發(fā)式算法；能耗與最大完工時間之間存在沖突關(guān)系，通過本文的模型和算法得到能耗與最大完工時間的近似Pareto前沿面，可為企業(yè)的實際生產(chǎn)提供指導(dǎo)。

并行機；組批調(diào)度；能耗約束；最大完工時間；粒子群-遺傳算法；鄰域搜索

1 并行機組批調(diào)度模型

1.1 問題描述

1.2 混合整數(shù)規(guī)劃線性模型

針對工件不同到達時間以及不同尺寸并且考慮能源約束的并行機組批調(diào)度問題，優(yōu)化最大完工時間，建立混合整數(shù)線性規(guī)劃模型(MILP)。模型的目標(biāo)函數(shù)為

Min:max

式中：max為最大完工時間。

約束條件：

式中：為批處理機數(shù)量；為工件數(shù)量。約束(1)表示每一個工件都會被分配到某一批次及某一批設(shè)備上。

約束(2)表示每個批都會且只能分配到1臺機器進行加工。

式中：為批處理機的最大容量；s為工件的尺寸，=1，2，…，。約束(3)表示批內(nèi)工件尺寸總和不能大于批處理機的容量限制。

式中：t為工件的加工時間，=1，2，…，；T,P為批次的加工時間，=1，2，…，。約束(4)表示批的加工時間為批內(nèi)加工時間最長工件的加工時間。

式中：T,S為批次的開始加工時間，=1，2，…，。約束(5)表示最大完工時間大于等于任何一個批的開始加工時間與批加工時間之和，即為最后加工批的完工時間。

式中：T,R為批次的到達時間，=1，2，…，；t為工件的到達時間，=1，2，…，。約束(6)表示批的到達時間大于等于批內(nèi)任何工件到達時間。即批的到達時間為批內(nèi)最晚到達工件的到達時間。

式中：T,C為批次的完工時間，=1，2，…，。約束(7)表示批的開始加工時間為該批的到達時間與該機器內(nèi)上一個批的完工時間之間的較大值。

式中：e為批處理機的單位時間能耗；E為批處理機的總能耗。

式中：max表示能耗約束值。約束(8)和(9)表示能耗約束，即設(shè)備總能耗小于某一上限。

2 模型求解

解決并行機組批調(diào)度問題主要有2種方式：第1種是先將加工工件分配到并行處理機，然后進行分批；第2種是先進行組批，然后對組好的批次進行調(diào)度。BALASUBRAMANIAN等[7]證明第2種方法能得到更優(yōu)的解并耗時更少。為了滿足生產(chǎn)需要，在短時間內(nèi)找到滿意解。本文采取第2種方式進行求解，第1階段采用PINEDO[25]提出的最長加工時間最先入批FFLPT和最長加工時間最優(yōu)入批BFLPT 2種啟發(fā)式規(guī)則。第2階段采用粒子群算法與遺傳算法相結(jié)合的方法求解，并結(jié)合局部搜索技術(shù)提高收斂速度。

2.1 組批階段算法

PINEDO[25]提出的最長加工時間優(yōu)先(LPT)規(guī)則是求解以Makespan為目標(biāo)的并行機調(diào)度問題較好的算法。對于工件具有不同尺寸的組批問題，當(dāng)不考慮工件到達時間時，組批調(diào)度可以看作是一個裝箱問題[5]，對于該問題FFLPT[24]規(guī)則和BFLPT[26]規(guī)則是2種比較有效的啟發(fā)式規(guī)則。本文采用這2種啟發(fā)式規(guī)則進行組批。

1) FFLPT規(guī)則如下。

步驟1：全部工件按照工件加工時間非增排序。

步驟2：選擇未分配工件序列中的第1個工件，將該工件分配到第1個可以容納該工件的批中，若沒有找到可以容納該工件的批，則將該工件放入新建 批中。

步驟3：重復(fù)步驟2中的操作，直到所有工件都被分配為止。

2) BFLPT規(guī)則如下。

步驟1：全部工件按照工件加工時間非增排序。

步驟2：選擇未分配工件序列中的第1個工件，在所有可以容納該工件的批中，找出剩余容量最小的批次，將該工件放入。

步驟3：重復(fù)步驟2中的操作，直到所有工件都被分配為止。

以10個工件為例，分別按照上述分批規(guī)則進行分批，表1所示為10個工件的具體屬性信息，機器容量設(shè)為40。具體實例操作結(jié)果如表2和表3所示。

表1 工件詳細(xì)屬性信息

根據(jù)FFLPT和BFLPT規(guī)則，產(chǎn)生的批次見表2和表3。

表2 FFLPT規(guī)則產(chǎn)生批次

表3 BFLPT規(guī)則長生批次

2.2 批次調(diào)度階段算法

經(jīng)過組批后，所有工件都被安排到對應(yīng)的加工批次中。由于批次的體積約束在組批階段中已經(jīng)滿足，故調(diào)度階段算法不再考慮此約束。

粒子群算法，也稱粒子群優(yōu)化算法(PSO)，是近年來發(fā)展起來的一種新的進化算法。PSO算法是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度來評價解的品質(zhì)，相比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的“交叉”(Crossover)和“變異”(Mutation)操作，它通過追隨個體極值和群體極值完成極值來更新粒子的速度和位置從而尋找最優(yōu)解。

雖然標(biāo)準(zhǔn)粒子群算法操作簡單，且能夠快速收斂，但是隨著迭代次數(shù)的不斷增加，在種群收斂集中的同時，各粒子也越來越相似，可能在局部最優(yōu)解周邊無法跳出。

遺傳和粒子群混合摒棄了傳統(tǒng)粒子群算法中的通過跟蹤極值來更新粒子速度和位置的方法，而是引入了遺傳算法中的交叉和變異操作，通過粒子與個體極值和群體極值的交叉以及粒子自身變異的方式來搜索最優(yōu)解。同時，為了加快收斂速度，本文引入局部搜索，即用混合遺傳算法(Hybrid GA)結(jié)合局部搜索來求解并行加熱爐的調(diào)度問題。批次調(diào)度階段算法流程如圖1所示。

圖1 批次調(diào)度算法流程圖

2.2.1 編碼

本階段以工件批次為操作對象，針對此對象在并行機上進行加工的特點，本文采用實數(shù)編碼方式，用1個長度為的數(shù)組代表個批次，數(shù)組中的位置代表相應(yīng)的工件批次，在工件批次對應(yīng)的位置賦予批的值，代表該工件被分配到該機器上進行加工。假設(shè)有15個工件組批后分配到3個并行機進行加工，一種可能的分配方式可以編碼為如下數(shù)組：

[1 2 3 1 2 3 1 2 1 3 3 2 1 3 2]

以上編碼的解釋為：工件批1，4，7，9和13被分配到1號并行機，工件批2，5，8和12被分配到2號并行機，工件批3，6，11和14被分配到3號并行機。

2.2.2 交叉和變異

2.2.3 局部搜索策略

2.2.4 能耗約束

設(shè)置能耗約束值，在每次得到新種群的同時計算該種群中每個個體對應(yīng)的能耗值，若該值超過約束上限，則舍棄該個體，保證種群中所有個體的能耗都在限定范圍內(nèi)。

2.2.5 停止準(zhǔn)則

當(dāng)混合GA滿足下面2個條件中的一個時則迭代停止：1) 設(shè)定最大進化代數(shù)，達到給定的最大代數(shù)Iter即終止算法；2) 算法連續(xù)進行若干次(Gap次)迭代，在此迭代過程中如果全局最優(yōu)解(最優(yōu)個體的適應(yīng)度值)沒有改變，則算法終止。其中Iter和Gap都是由經(jīng)驗給出。

3 案例研究

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

本文對不同規(guī)模(加工工件數(shù)量不同)實例分別進行了仿真實驗。實驗中本文采用CHOU等[20]提出的測試算例。其中，小規(guī)模的工件數(shù)量=20，中規(guī)模和大規(guī)模的工件數(shù)量分別為=50和100，數(shù)據(jù)模擬實際生產(chǎn)數(shù)據(jù)隨機產(chǎn)生。以20個軋輥為例，其各種參數(shù)值如表4所示。并行批處理機的容積設(shè)定為40 m3，機器數(shù)量設(shè)為3臺，3臺機器單位能耗分別設(shè)為1，2，3(100 kW)。max是根據(jù)啟發(fā)式算法得到的可行解的能耗值設(shè)定。最大迭代次數(shù)Iter=200，初始種群數(shù)目NIND=200。本實驗在Matlab 2013a上實現(xiàn)，運行于Windows 7操作系統(tǒng)的PC機(Intel Core i5/ CPU2.4GHZ/RAM 4.0G)上。實驗結(jié)果如圖2~4所示。

以往的不禮貌言語分析主要在語篇層面展開，分析的材料大多是單一的文本資料，較少涉及多媒體資源。多模態(tài)話語分析的運用，能夠最大程度地還原真實情境下話語互動的內(nèi)容與意義。這個部分將以Culpeper(2005)的不禮貌策略以及Culpeper et al.(2003)的不禮貌回應(yīng)策略為理論基礎(chǔ)，以視頻的圖片截圖為輔助，來闡釋副語言中的視覺以及言語元素在話語意義生成中的相互作用。

3.2 實驗結(jié)果

圖2~4所示分別為不同軋輥規(guī)模下并行高溫爐的調(diào)度結(jié)果以及與其他算法結(jié)果的對比。為了更清楚的表現(xiàn)本章結(jié)果與2種啟發(fā)式算法和標(biāo)準(zhǔn)GA的對比，不同軋輥規(guī)模的能耗與max對應(yīng)關(guān)系都分別繪制了1張局部放大圖，可以更清楚地看出本文算法的優(yōu)越性。

需要說明的是，這里用來對照的2種啟發(fā)式算法是經(jīng)過FFLPT和BFLPT組批之后，在批次分配時又采用最早到達時間優(yōu)先加工的(ERT)規(guī)則生成的，分別稱之為FFLPTERT和BFLPTERT[5]。選擇ERT啟發(fā)式算法的原因在于，在組批時沒有考慮工件的到達時間，而只考慮工件加工時間和尺寸，這可能會造成到達時間差別很大的工件組成一批，影響生產(chǎn)效率。而在將批次分配給并行機加工時需要著重考慮工件的到達時間，比較常用的就是ERT規(guī)則。因而，將二者進行組合，有利于降低整個加工流程的完工時間。

表4 軋輥屬性值(20個)

(a) 能耗Cmax對應(yīng)關(guān)系；(b) 能耗與Cmax對應(yīng)關(guān)系局部放大圖

(a) 能耗Cmax對應(yīng)關(guān)系；(b) 能耗與Cmax對應(yīng)關(guān)系局部放大圖

(a) 能耗Cmax對應(yīng)關(guān)系；(b) 能耗與Cmax對應(yīng)關(guān)系局部放大圖

FFLPTERT規(guī)則如下。

步驟1：將工件按照FFLPT規(guī)則組批。

步驟2：全部批次按照批次到達時間非減序排列得到工件序列，其中批次的到達時間以批內(nèi)最晚到達工件的到達時間為準(zhǔn)。

步驟3：將中的工件依次放入第1個空閑的批處理機；若同時有多個機器空閑，則選擇功耗最低的機器加工。

步驟4：重復(fù)步驟3中的操作，直到所有批都被分配。

從圖2~4可見：星形點形成了混合GA在不同能耗約束下的max走勢圖，近似于Pareto前沿面，可以發(fā)現(xiàn)2類指標(biāo)之間存在沖突關(guān)系；而其他幾種算法由于不考慮能耗因素，故僅能得到各自唯一的max優(yōu)化值，然后計算得到相應(yīng)的能耗。混合GA得到的近似Pareto前沿面上的解位于其他算法得到的解的左下方，說明該前沿面上的解對其他算法的解都是占優(yōu)的，即在相同的能耗約束值下，提出的算法取得了更小的max。同時，其他算法求得的解對應(yīng)的能耗值往往較高，位于橫坐標(biāo)右端，說明這些算法無法應(yīng)對總能耗有限制的情況；而本章提出的協(xié)同模型可以在不同的能耗約束下到相應(yīng)的max優(yōu)化解，滿足了生產(chǎn)需求。以100個軋輥為例，圖4顯示了不同能耗約束下優(yōu)化得到的最優(yōu)max散點圖，實際生產(chǎn)中可以根據(jù)不同的總能耗約束要求選擇相應(yīng)的生產(chǎn)方案。

同樣以100個軋輥的案例為例，由表7可以看出：本文算法可以找出max和能耗均優(yōu)于2種啟發(fā)式算法的解。例如表7中第7列的解max與能耗相對BFLPTERT算法分別降低0.579%和0.065%；而第3列中的解相對于FFLPTERT算法max和能耗分別降低0.565%和0.659%；第4列的解max與能耗相對FFLPTERT算法分別降低0.755%和0.164%，證明了本算法的有效性。

不過，有些解的表現(xiàn)則有所不同，例如第3列的解相對于BFLPTERT算法max雖提高1.883%，但是能耗卻降低1.351%，相對于標(biāo)準(zhǔn)GAmax雖提高3.013%，但是能耗卻降低1.614%；同樣第8列的解相對于FFLPTERT算法能耗雖提高0.747%，但max降低3.288%，相對于標(biāo)準(zhǔn)GA，max雖提高0.387%，但能耗降低0.195%。這說明max和總能耗存在沖突關(guān)系，即追求max的降低可能引起能耗的增加。反之亦然。

表5 混合GA相對于其他算法的降低比例(20個工件)

表6 混合GA相對于其他算法的降低比例(50個工件)

表7 混合GA相對于其他算法的降低比例(100個工件)

綜合比較表5~7可知：無論對比啟發(fā)式算法還是標(biāo)準(zhǔn)GA，都可看出隨著軋輥數(shù)量的增加混合GA的優(yōu)化比例逐漸減小。這說明隨著軋輥數(shù)量的增加，問題的求解難度劇增，混合GA的尋優(yōu)能力略有減弱。故未來可以繼續(xù)研究大規(guī)模問題下更為有效的求解算法。

4 結(jié)論

1) 所提算法能夠高效地尋找到各個能耗約束下的最優(yōu)max，與2種經(jīng)典啟發(fā)式算法及標(biāo)準(zhǔn)GA對比優(yōu)化效果明顯。

2) 混合GA算法在問題規(guī)模較小時優(yōu)勢明顯，隨著軋輥數(shù)量的增加，混合GA算法的優(yōu)勢略有下降。

3) 為了應(yīng)對企業(yè)供能限制，在約束中加入總能耗約束，使得企業(yè)在實際生產(chǎn)時可以根據(jù)能耗供應(yīng)要求選擇最大完工時間最小的生產(chǎn)方案。

[1] IEA. Tracking industrial, energy efficiency and CO2Emissions. [2007?09].http://www.iea.org/textbase/nppdf/free/2007/tracking_ emissions.pdf.

[2] JOVANE F, YOSHIKAWA H, ALTING L, et al. The incoming global technological and industrial revolution towards competitive sustainable manufacturing[J]. Annals of the CIRP, 2008, 57(2): 641?659.

[3] 朱祝林. 以能源節(jié)約為目標(biāo)的軋輥熱處理過程中若干調(diào)度優(yōu)化方法研究[D]. 沈陽: 東北大學(xué)信息科學(xué)與工程學(xué)院, 2011: 1?60. ZHU Zhulin. Scheduling optimization methods for thermal treatment process in mill roller production aiming at energy conservation[D]. Shenyang: Northeastern University. College of Information Science and Engineering, 2011: 1?60.

[4] LIU C H. Approximate trade-off between minimisation of total weighted tardiness and minimisation of carbon dioxide (CO2) emissions in bi-criteria batch scheduling problem[J]. International Journal of Computer Integrated Manufacturing, 2014, 27(8): 759?771.

[5] 李小林. 平行機環(huán)境下批處理調(diào)度問題研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué)管理科學(xué)與工程, 2012: 1?25. LI Xiaolin. Research on scheduling batch processing machines in parallel[D]. Hefei: University of Science and Technology of China, Management Science and Engineering, 2012: 1?25.

[6] MALVE S, UZSOY R. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job gamilies[J]. Computers & Operations Research, 2007, 34(10): 3016?3028.

[7] BALASUBRAMANIAN H, MONCH L, FOWLER J W, et al. Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness[J]. International Journal of Production Research 2004, 42(8): 1621?1638.

[8] YILMAZ E D, OZMUTLU H C, OZMUTLU S. Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times[J]. International Journal of Production Research, 2014, 52(19): 5841?5856.

[9] VALLADA E, RUIZ R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[J]. European Journal of Operational Research, 2011, 211(3): 612?622.

[10] TANAKA S, ARAKI M. A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines[J]. International Journal of Production Economics, 2008, 113(1): 446?458.

[11] CHAUDHRY I A, DRAKE P R. Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms[J]. The International Journal of Advanced Manufacturing Technology, 2009, 42(5): 581?594.

[12] 劉民, 吳澄, 蔣新松. 用遺傳算法解決并行多機調(diào)度問題[J]. 系統(tǒng)工程理論與實踐, 1998, 18(1): 14?17. LIU Min, WU Cheng, JIANG Xinsong. Genetic algorithm method for identical parallel machine scheduling problem[J]. System Engineering-Theory & Practice, 1998, 18(1): 14?17.

[13] WANG L Y, HUANG X, JI P, et al. Unrelated parallel-machine scheduling with deteriorating maintenance activities to minimize the total completion time[J]. Optimization Letters, 2014, 8(1): 129?134.

[14] KASHAN A H, KARIMI B. A discrete particle swarm optimization algorithm for scheduling parallel machines[J]. Computers & Industrial Engineering, 2009, 56(1): 216?223.

[15] YEH W C, LAI P J, LEE W C, et al. Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects[J]. Information Sciences, 2014, 269: 142?158.

[16] UZSOY R, YANG Y. Minimizing total weighted completion time on a single processing machine[J]. Production and operations Management, 1997, 6(1): 57?73.

[17] AZIZOGLU M, WEBSTER S. Scheduling a batch processing machine with non-identical job sizes[J]. International Journal of Production Research, 2000, 38(10): 2173?2184.

[18] 程八一, 陳華平, 王栓獅. 基于微粒群算法的單機不同尺寸工件批調(diào)度問題求解[J]. 中國管理科學(xué), 2008, 16(3): 84?88. CHENG Bayi, CHEN Huaping, WANG Shuanshi. Scheduling a single batch-processing machine with non-identical job sizes based on practice swarm optimization[J]. Chinese Journal of Management Science, 2008, 16(3): 84?88.

[19] LEE C Y, UZSOY R. Minimizing makespan on a single batch processing machine with dynamic job arrivals[J]. International Journal of Production Research, 1999, 37(l): 219?236.

[20] CHOU F D, CHANG P C, WANG H M A. Hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2006, 31(3): 350?359.

[21] LI S G, LI G J, WANG X L, et al. Minimizing makespan on a single batching machine with release times and non-identical job sizes[J]. Operations Research Letters, 2005, 33(2): 157?164.

[22] 姜冠成. 帶到達時間分批排序問題的數(shù)學(xué)模型[J]. 蘇州大學(xué)學(xué)報, 2005, 21(2): 22?27. JIANG Guancheng. Formulating the batch scheduling with release time as a mathematical programming model[J]. Journal of Suzhou University, 2005, 21(2): 22?27.

[23] GRAHAM R, LAWLER E, LENSTRA J, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(2): 287?326.

[24] UZSOY R. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615?1635.

[25] PINEDO M L. Scheduling theory, algorithms, and systems[M]. 3th ed, New York, USA: Springer, 2008: 1?52.

[26] 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.

(編輯 陳愛華)

Parallel machine batching scheduling considering energy constraints

LI Guochen, QIAO Fei, WANG Junkai, MA Yumin, LU Kailu

(College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Non-identical parallel machines with same capacity but different power were considered for batching scheduling problems. A mixed integer programming model minimizing makespan was established, with different job sizes and arrival times. As the parallel machine batching scheduling problem was NP-hard, a two-phase method, that was, first batching and then scheduling, was adopted to solve the model. At the phase of batching, two heuristic rules, FFLPT and BFLPT, were employed; and a PSO-GA hybrid algorithm with neighborhood search was designed at the phase of scheduling. The proposed model and algorithm were validated under a case study of parallel heat treatment equipment in roller manufacturing. Optimized makespans under different energy consumption constraints were analyzed, and the performance of different algorithms were compared. The results show that the proposed algorithm improves the convergent speed of standard genetic algorithm, and outperforms the other two heuristic algorithms. Meanwhile, there exists trade-offs between energy consumption and makespan. And the approximate Pareto frontier of these two indicators obtained by the proposed model and algorithm may provide guidance for real production in enterprises.

parallel machines; batch scheduling; energy consumption constraints; makespan; PSO-GA; neighborhood search

10.11817/j.issn.1672?7207.2017.08.013

O221.4

A

1672?7207(2017)08?2063?10

2016?09?25；

2016?12?20

國家自然科學(xué)基金資助項目(71690234，61273046)(Projects (71690234, 61273046) supported by the National Natural Science Foundation of China)

喬非，博士，教授，從事生產(chǎn)調(diào)度優(yōu)化、高能效制造研究；E-mail：fqiao@#edu.cn