考慮能耗約束的并行機組批調度

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

考慮能耗約束的并行機組批調度

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

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

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

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

1 并行機組批調度模型

1.1 問題描述

1.2 混合整數規劃線性模型

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

Min:max

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

約束條件：

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

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

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

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

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

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

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

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

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

2 模型求解

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

2.1 組批階段算法

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

1) FFLPT規則如下。

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

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

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

2) BFLPT規則如下。

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

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

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

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

表1 工件詳細屬性信息

根據FFLPT和BFLPT規則，產生的批次見表2和表3。

表2 FFLPT規則產生批次

表3 BFLPT規則長生批次

2.2 批次調度階段算法

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

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

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

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

圖1 批次調度算法流程圖

2.2.1 編碼

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

[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 能耗約束

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

2.2.5 停止準則

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

3 案例研究

3.1 參數設置

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

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

3.2 實驗結果

圖2~4所示分別為不同軋輥規模下并行高溫爐的調度結果以及與其他算法結果的對比。為了更清楚的表現本章結果與2種啟發式算法和標準GA的對比，不同軋輥規模的能耗與max對應關系都分別繪制了1張局部放大圖，可以更清楚地看出本文算法的優越性。

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

表4 軋輥屬性值(20個)

(a) 能耗Cmax對應關系；(b) 能耗與Cmax對應關系局部放大圖

(a) 能耗Cmax對應關系；(b) 能耗與Cmax對應關系局部放大圖

(a) 能耗Cmax對應關系；(b) 能耗與Cmax對應關系局部放大圖

FFLPTERT規則如下。

步驟1：將工件按照FFLPT規則組批。

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

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

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

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

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

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

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

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

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

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

4 結論

1) 所提算法能夠高效地尋找到各個能耗約束下的最優max，與2種經典啟發式算法及標準GA對比優化效果明顯。

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

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

[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] 朱祝林. 以能源節約為目標的軋輥熱處理過程中若干調度優化方法研究[D]. 沈陽: 東北大學信息科學與工程學院, 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] 李小林. 平行機環境下批處理調度問題研究[D]. 合肥: 中國科學技術大學管理科學與工程, 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] 劉民, 吳澄, 蔣新松. 用遺傳算法解決并行多機調度問題[J]. 系統工程理論與實踐, 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] 程八一, 陳華平, 王栓獅. 基于微粒群算法的單機不同尺寸工件批調度問題求解[J]. 中國管理科學, 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] 姜冠成. 帶到達時間分批排序問題的數學模型[J]. 蘇州大學學報, 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

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

喬非，博士，教授，從事生產調度優化、高能效制造研究；E-mail：fqiao@tongji.edu.cn