考虑能耗约束的并行机组批调度-有色金属在线

目录结构

详情信息展示

参考文献

中南大学学报(自然科学版)

DOI: 10.11817/j.issn.1672-7207.2017.08.013

考虑能耗约束的并行机组批调度

李国臣，乔非，王俊凯，马玉敏，卢凯璐

(同济大学电子与信息工程学院，上海，201804)

摘要：

机的组批调度问题，考虑炉容相同、功率不同的非等同并行机的总能耗约束，考虑工件尺寸和到达时间不同，以最小化最大完工时间为目标建立混合整数规划模型。并行机组批调度问题属于NP-hard问题，采用先组批后调度的两阶段方式求解。组批阶段采用基于FFLPT和BFLPT的启发式规则，调度阶段设计带邻域搜索的粒子群-遗传混合算法对模型进行求解。以轧辊生产企业并行热处理设备为研究案例进行模型和算法验证，分析不同能耗约束下最大完工时间优化值，并比较算法的优化性能。实验结果表明：本文算法提高标准遗传算法的收敛速度，且优于2种启发式算法；能耗与最大完工时间之间存在冲突关系，通过本文的模型和算法得到能耗与最大完工时间的近似Pareto前沿面，可为企业的实际生产提供指导。

关键词：

并行机；组批调度；能耗约束；最大完工时间；粒子群-遗传算法；邻域搜索；

中图分类号：O221.4 文献标志码：A 文章编号：1672-7207(2017)08-2063-10

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)

Abstract: 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.

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

高能效调度(EES)是实现制造业节能减排的重要途径。制造业能源消耗占全球总能耗的31%，能源、环境和经济因素为制造企业节能减排提供了有效的动力^[1-2]。传统生产调度仅考虑生产工艺和资源(如设备、物料、人员)等约束，极少关注如能源消耗、负载功耗等与现实需要密切相关的约束。实际中高耗能企业通过与供电公司定期签订购电合同，拟定购电总量和价格，也划定功率负载的上限。在用电高峰期，这些企业需要合理安排生产，在满足能耗限制的前提下最大化生产效率。在制造业中，并行机组批调度(PMBS)是一类常见的生产问题，这类问题具有极强的实际背景，如集成电路芯片测试、轧辊热处理炉、轧钢加热炉、机械加工等。从现有文献来看，考虑能耗的并行机组批调度研究相对较少，朱祝林^[3]针对具有组批和指派的并行机调度问题(轧辊热处理)，提出了以能耗最小化为目标的两种启发式算法，即辊批间尺寸最大差值的组批和辊批批次间加工时间最大差值的低单位功率加热炉优先(LDVRS-BPTLUPFF)、最大辊批尺寸的组批和最长批次加工时间的低功率加热炉优先(LRS-PTLPFF)。LIU^[4]在并行机环境下假设工件同时到达，解决如何组批和如何指派的问题，考虑了碳排放(即总能耗)和总拖期时间两个目标，在求解阶段提出了一种带精英保留策略的多目标遗传算法(ε-AGA)。上述研究都将能耗作为优化目标，而未将其作为约束考虑。在不考虑能耗因素的并行机组批调度研究中，李小林^[5]在工件尺寸和到达时间都不同的情况下提出了2种启发式算法。MALVE等^[6]对工件具有不同到达时间且含有工件族(Job Family)约束的批调度问题，以极小化总误工(..)为目标，采用遗传算法求解。BALASUBRAMANIAN等^[7]更进一步考虑了不相容工件族的情况，采用遗传算法优化总加权拖期时间。这些研究多是采用启发式和元启发式算法求解。当问题规模较大时，遗传算法等智能算法显示出较大优势。单就不考虑组批的并行机调度而言，相关研究较为丰富。YILMAZ和VALLADA等^[8-9]针对同等并行机下优化拖期时间的调度问题，利用遗传算法进行求解。同时，各类启发式算法^[10]和分枝定界算法^[11]等也被用于解决此类问题。刘民等^[12]针对优化最大完工时间问题利用遗传算法求解。WANG和KASHAN等^[13-14]分别利用LISTFIT启发式算法和离散粒子群算法优化最大完工时间问题。YEH等^[15]研究了具有模糊加工时间的并行机调度问题，并采用包括2种启发式算法、模拟退火和遗传算法在内的多种方法求解。从这些研究可以看出，并行机调度的优化目标一般以最大完工时间和拖期时间为主，求解方法从最优化方法到启发式规则再到元启发式和群智能算法都有涉及。单就组批调度来说，当前研究主要集中在针对C_max和拖期时间等生产性能指标的优化上。UZSOY等^[16]提出了一种分支定界算法和若干个有效的启发式规则，针对目标为极小化加权总完工时间的批调度问题进行求解。对于工件数小于25的小规模问题，AZIZOGLUR等^[17]提出了一种分支定界算法进行求解优化相同的目标。程八一等^[18]针对不同尺寸工件的组批调度问题，采用粒子群算法优化最大完工时间C_max。LEE等^[19]则根据不同的延迟批加工方式提出了GRLPT，R1，R2和DELAY等4种启发式规则和一种UPDATE局部搜索方法。文献当中对于机器容量为无限的特殊情况()设计了多项式求解算法，并对仅有2个到达时间r₀和r₁的简化情况设计了一种动态规划求解算法。CHOU等^[20]将LPT-BFF启发式规则与遗传算法(GA)相结合，提出了2种混合遗传算法对工件尺寸和到达时间都不同的问题进行求解。LI等^[21]分析了工件到达时间不同以及不同工件尺寸的动态调度问题，提出了的最差近似(性能)比。姜冠成^[22]则建立了0-1整数规划模型来求解不同工件到达时间的批调度问题，实验得到此数学模型所能求得最优解的问题规模。以上文献都是针对以生产性能为目标的调度问题进行研究，且多为单机环境的组批调度问题。这些研究相对较多，理论也相对成熟，并行机组批调度且考虑能耗约束的研究可以从中借鉴。本文作者针对工件含有不同到达时间，且工件尺寸不同的非等同并行机组批调度问题进行研究，求解目标为加入能耗约束的最大完工时间C_max。求解并行机组批调度问题一般有2种方式：一是先将工件分配到并行机上，然后再进行组批；二是先将工件进行组批，然后再分配到并行机进行调度。本文采用第2种方式，在组批阶段，采取2种常用的启发式算法；在调度阶段设计一种带邻域搜索的粒子群-遗传混合算法进行求解，并在约束中加入能耗约束，求得各个能耗约束下所能得到的C_max优化值。并通过与启发式规则和标准遗传算法对比，验证算法有效性。

1 并行机组批调度模型

1.1 问题描述

本文的研究内容为具有批处理能力的非等同并行机的调度问题，不失一般性，用GRAHAM等^[23]介绍的3参数法可以表示为(式中：P为并行机(Parallel)环境；B为机器是具有批(Batch)处理能力的并行机；r_j和s_j分别为工件具有不同的到达时间及尺寸；E≤E_max表示约束中有总能耗约束；C_max为所有工件的最大完工时间，即最后一个批的工件加工完成的时间)。本文研究的并行机组批调度问题中，机器是非等同批处理机，不过机器除了功率不同之外其余性能完全相同。同一批的工件具有相同的开始、结束加工时间，批的加工时间为批内加工时间最长工件的加工时间，批的到达时间为批内最晚到达工件的到达时间，批的尺寸为批内所有工件的尺寸和，批的尺寸不能超过批处理机的容量。

1.2 混合整数规划线性模型

针对工件不同到达时间以及不同尺寸并且考虑能源约束的并行机组批调度问题，优化最大完工时间，建立混合整数线性规划模型(MILP)。模型的目标函数为

Min: C_max

式中：C_max为最大完工时间。

约束条件：

(1)

式中：M为批处理机数量；N为工件数量。约束(1)表示每一个工件都会被分配到某一批次及某一批设备上。

(2)

约束(2)表示每个批都会且只能分配到1台机器进行加工。

(3)

式中：C为批处理机的最大容量；s_j为工件j的尺寸，j=1，2，…，N。约束(3)表示批内工件尺寸总和不能大于批处理机的容量限制。

(4)

式中：t_j为工件j的加工时间，j=1，2，…，N；T_b_,P为批次b的加工时间，b=1，2，…，B。约束(4)表示批的加工时间为批内加工时间最长工件的加工时间。

(5)

式中：T_b_,S为批次b的开始加工时间，b=1，2，…，B。约束(5)表示最大完工时间大于等于任何一个批的开始加工时间与批加工时间之和，即为最后加工批的完工时间。

(6)

式中：T_b_,R为批次b的到达时间，b=1，2，…，B；t_j为工件j的到达时间，j=1，2，…，N。约束(6)表示批的到达时间大于等于批内任何工件到达时间。即批的到达时间为批内最晚到达工件的到达时间。

(7)

式中：T_b_,C为批次b的完工时间，b=1，2，…，B。约束(7)表示批的开始加工时间为该批的到达时间与该机器内上一个批的完工时间之间的较大值。

(8)

式中：e_m为批处理机m的单位时间能耗；E_m为批处理机m的总能耗。

(9)

式中：E_max表示能耗约束值。约束(8)和(9)表示能耗约束，即设备总能耗小于某一上限。

(10)

(11)

约束(10)~(11)为决策变量的定义，表示工件j被分配到批b，并安排到批设备m进行加工，z_bm=1表示批b被分配到批设备m进行加工。

2 模型求解

对于问题，UZSOYR^[24]证明了该问题等同于装箱问题(Bin packing problem，BPP)，而BPP已经是NP-hard问题。而本文研究的是在问题的基础上演化而来，较其更为复杂。问题可以看成本文研究问题的1个特例。李小林^[5]证明将批分派到大于1台机器的最大完工时间最小化问题是NP-hard问题，本文是在此基础上加上能耗约束，故而本文研究的问题仍是NP-hard问题，因此，难以在多项式时间内找到最优调度方案。

解决并行机组批调度问题主要有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 工件详细属性信息

Table 1 Detailed information of job attributes

根据FFLPT和BFLPT规则，产生的批次见表2和表3。

表2 FFLPT规则产生批次

Table 2 Results of batching by FFLPT rule

表3 BFLPT规则长生批次

Table 3 Results of batching by BFLPT rule

2.2 批次调度阶段算法

经过组批后，所有工件都被安排到对应的加工批次中。由于批次的体积约束在组批阶段中已经满足，故调度阶段算法不再考虑此约束。

粒子群算法，也称粒子群优化算法(PSO)，是近年来发展起来的一种新的进化算法。PSO算法是从随机解出发，通过迭代寻找最优解，通过适应度来评价解的品质，相比遗传算法规则更为简单，它没有遗传算法的“交叉”(Crossover)和“变异”(Mutation)操作，它通过追随个体极值和群体极值完成极值来更新粒子的速度和位置从而寻找最优解。

虽然标准粒子群算法操作简单，且能够快速收敛，但是随着迭代次数的不断增加，在种群收敛集中的同时，各粒子也越来越相似，可能在局部最优解周边无法跳出。

遗传和粒子群混合摒弃了传统粒子群算法中的通过跟踪极值来更新粒子速度和位置的方法，而是引入了遗传算法中的交叉和变异操作，通过粒子与个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。同时，为了加快收敛速度，本文引入局部搜索，即用混合遗传算法(Hybrid GA)结合局部搜索来求解并行加热炉的调度问题。批次调度阶段算法流程如图1所示。

图1 批次调度算法流程图

Fig. 1 Algorithm flow chart of batch scheduling

2.2.1 编码

本阶段以工件批次为操作对象，针对此对象在并行机上进行加工的特点，本文采用实数编码方式，用1个长度为n的数组代表n个批次，数组中的位置代表相应的工件批次，在工件批次对应的位置赋予批的值，代表该工件被分配到该机器上进行加工。假设有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 交叉和变异

1) 交叉算子。采用单点交叉策略，对种群中的2个个体和，生成随机数，根据r₁产生交叉点，如下式所示：

(12)

式中：B为批的数量，即为个体数组的长度；表示取靠近x的整数中较大的1个。将看作和的1个切点，将切点两侧分别看作2个子串，将右侧的子串分别交换得到2个新的个体和，交叉后需要比较2个个体的适应度值而选出较优者，交叉具体操作如下：

2) 变异算子。采用双位点变异策略，即将不同批设备中板坯进行交换。对种群中的个体，分别产生2个随机数和，然后根据这2个随机数再产生2个随机数代表取到的不同批设备中的板坯，如式(13)和(14)所示。

(13)

(14)

同一个批设备中的不同工件交换的变异没有任何意义，故如果个体数组中和这2个位置的值相等，根据编码方式，说明2个批在同一个批设备，则需要重新生成r₂和，直到2个位置的值不相等为止。变异操作流程如下所示：

2.2.3 局部搜索策略

为使算法能够在探索到较优解时可以在其附近搜索更优的解，设计了局部邻域搜索策略，以兼顾算法搜索广度(exploration)和深度(exploitation)的范围。在个体内随机选取一个批，先产生随机数，然后根据该随机数再产生另外一个随机数代表取到某个批设备中的批，如下式：

(15)

将处的值分别设为除当前值之外小于等于批设备数量M的所有值，则会生成M-1个局部可行解，然后根据适应度值选出最优解。以5个批和3个批设备为例，局部搜索操作过程如下所示。

2.2.4 能耗约束

设置能耗约束值，在每次得到新种群的同时计算该种群中每个个体对应的能耗值，若该值超过约束上限，则舍弃该个体，保证种群中所有个体的能耗都在限定范围内。

2.2.5 停止准则

当混合GA满足下面2个条件中的一个时则迭代停止：1) 设定最大进化代数，达到给定的最大代数n_Iter即终止算法；2) 算法连续进行若干次(n_Gap次)迭代，在此迭代过程中如果全局最优解(最优个体的适应度值)没有改变，则算法终止。其中n_Iter和n_Gap都是由经验给出。

3 案例研究

3.1 参数设置

本文对不同规模(加工工件数量不同)实例分别进行了仿真实验。实验中本文采用CHOU等^[20]提出的测试算例。其中，小规模的工件数量N=20，中规模和大规模的工件数量分别为N=50和100，数据模拟实际生产数据随机产生。以20个轧辊为例，其各种参数值如表4所示。并行批处理机的容积C设定为40 m³，机器数量设为3台，3台机器单位能耗分别设为1，2，3(100 kW)。E_max是根据启发式算法得到的可行解的能耗值设定。最大迭代次数n_Iter=200，初始种群数目n_NIND=200。本实验在Matlab 2013a上实现，运行于Windows 7操作系统的PC机(Intel Core i5/ CPU2.4GHZ/RAM 4.0G)上。实验结果如图2~4所示。

3.2 实验结果

图2~4所示分别为不同轧辊规模下并行高温炉的调度结果以及与其他算法结果的对比。为了更清楚的表现本章结果与2种启发式算法和标准GA的对比，不同轧辊规模的能耗与C_max对应关系都分别绘制了1张局部放大图，可以更清楚地看出本文算法的优越性。

需要说明的是，这里用来对照的2种启发式算法是经过FFLPT和BFLPT组批之后，在批次分配时又采用最早到达时间优先加工的(ERT)规则生成的，分别称之为FFLPTERT和BFLPTERT^[5]。选择ERT启发式算法的原因在于，在组批时没有考虑工件的到达时间，而只考虑工件加工时间和尺寸，这可能会造成到达时间差别很大的工件组成一批，影响生产效率。而在将批次分配给并行机加工时需要着重考虑工件的到达时间，比较常用的就是ERT规则。因而，将二者进行组合，有利于降低整个加工流程的完工时间。

表4 轧辊属性值(20个)

Table 4 Attribute values of rollers (20 rollers)

图2 工件数为20的求解结果

Fig. 2 Results of 20 jobs

图3 工件数为50的求解结果

Fig. 3 Results of 50 jobs

图4 工件数为100的求解结果

Fig. 4 Results of 100 jobs

FFLPTERT规则如下。

步骤1：将工件按照FFLPT规则组批。

步骤2：全部批次按照批次到达时间非减序排列得到工件序列L，其中批次的到达时间以批内最晚到达工件的到达时间为准。

步骤3：将L中的工件依次放入第1个空闲的批处理机；若同时有多个机器空闲，则选择功耗最低的机器加工。

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

从图2~4可见：星形点形成了混合GA在不同能耗约束下的C_max走势图，近似于Pareto前沿面，可以发现2类指标之间存在冲突关系；而其他几种算法由于不考虑能耗因素，故仅能得到各自唯一的C_max优化值，然后计算得到相应的能耗。混合GA得到的近似Pareto前沿面上的解位于其他算法得到的解的左下方，说明该前沿面上的解对其他算法的解都是占优的，即在相同的能耗约束值下，提出的算法取得了更小的C_max。同时，其他算法求得的解对应的能耗值往往较高，位于横坐标右端，说明这些算法无法应对总能耗有限制的情况；而本章提出的协同模型可以在不同的能耗约束下到相应的C_max优化解，满足了生产需求。以100个轧辊为例，图4显示了不同能耗约束下优化得到的最优C_max散点图，实际生产中可以根据不同的总能耗约束要求选择相应的生产方案。

为了更具体地表达本章所提算法和2种启发式算法的对比效果，针对2种不同的轧辊规模进行求解，分别取C_max较优的6~8个解与2种启发式算法作对比，计算所提算法的C_max降低百分比，如表5~7所示。为了在表中便于展示，进行如下简写：用BFLE-C代表BFLPTERT-C，表示BFLPTERT算法求得解的最大完工时间；BFLE-E代表BFLPTERT-E，表示BFLPTERT算法求得解的能耗；FFLE-C代表FFLPTERT-C，表示FFLPTERT算法求得解的最大完工时间，FFLE-E代表FFLPTERT-E，表示FFLPTERT算法求得解的能耗。GA-C和GA-E分别代表标准GA算法求得解的最大完工时间和总能耗。

同样以100个轧辊的案例为例，由表7可以看出：本文算法可以找出C_max和能耗均优于2种启发式算法的解。例如表7中第7列的解C_max与能耗相对BFLPTERT算法分别降低0.579%和0.065%；而第3列中的解相对于FFLPTERT算法C_max和能耗分别降低0.565%和0.659%；第4列的解C_max与能耗相对FFLPTERT算法分别降低0.755%和0.164%，证明了本算法的有效性。

不过，有些解的表现则有所不同，例如第3列的解相对于BFLPTERT算法C_max虽提高1.883%，但是能耗却降低1.351%，相对于标准GA C_max虽提高3.013%，但是能耗却降低1.614%；同样第8列的解相对于FFLPTERT算法能耗虽提高0.747%，但C_max降低3.288%，相对于标准GA，C_max虽提高0.387%，但能耗降低0.195%。这说明C_max和总能耗存在冲突关系，即追求C_max的降低可能引起能耗的增加。反之亦然。

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

Table 5 Reduction ratio of hybrid GA compared with other algorithms (20 jobs) %

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

Table 6 Reduction ratio of hybrid GA compared with other algorithms (50 jobs) %

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

Table 7 Reduction ratio of hybrid GA compared with other algorithms(100 jobs) %

综合比较表5~7可知：无论对比启发式算法还是标准GA，都可看出随着轧辊数量的增加混合GA的优化比例逐渐减小。这说明随着轧辊数量的增加，问题的求解难度剧增，混合GA的寻优能力略有减弱。故未来可以继续研究大规模问题下更为有效的求解算法。

4 结论

1) 所提算法能够高效地寻找到各个能耗约束下的最优C_max，与2种经典启发式算法及标准GA对比优化效果明显。

2) 混合GA算法在问题规模较小时优势明显，随着轧辊数量的增加，混合GA算法的优势略有下降。

3) 为了应对企业供能限制，在约束中加入总能耗约束，使得企业在实际生产时可以根据能耗供应要求选择最大完工时间最小的生产方案。

参考文献：

[1] IEA. Tracking industrial, energy efficiency and CO₂ Emissions. [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 (CO₂) 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.

(编辑陈爱华)

收稿日期：2016-09-25；修回日期：2016-12-20

基金项目(Foundation item)：国家自然科学基金资助项目(71690234，61273046)(Projects (71690234, 61273046) supported by the National Natural Science Foundation of China)

通信作者：乔非，博士，教授，从事生产调度优化、高能效制造研究；E-mail：fqiao@tongji.edu.cn

摘要：研究并行批处理机的组批调度问题，考虑炉容相同、功率不同的非等同并行机的总能耗约束，考虑工件尺寸和到达时间不同，以最小化最大完工时间为目标建立混合整数规划模型。并行机组批调度问题属于NP-hard问题，采用先组批后调度的两阶段方式求解。组批阶段采用基于FFLPT和BFLPT的启发式规则，调度阶段设计带邻域搜索的粒子群-遗传混合算法对模型进行求解。以轧辊生产企业并行热处理设备为研究案例进行模型和算法验证，分析不同能耗约束下最大完工时间优化值，并比较算法的优化性能。实验结果表明：本文算法提高标准遗传算法的收敛速度，且优于2种启发式算法；能耗与最大完工时间之间存在冲突关系，通过本文的模型和算法得到能耗与最大完工时间的近似Pareto前沿面，可为企业的实际生产提供指导。