基于约束规划的资源受限并行机调度研究

陈伟嘉，刘建军，钟宏扬,2，曾创锋

（1.广东工业大学机电工程学院，广州 510006；2.佛山职业技术学院，广东 佛山 528137）

0 引言

并行机调度（Parallel Machine Scheduling，PMS）是指作为稀缺资源的若干台并行机器加工一组给定的不同工件，要求确定每一台机器所加工的工件序列，其已被证明是NP-hard 问题[1]。然而，传统的PMS 研究都假设机器是唯一受到限制的资源，但在现实制造系统中，除机器以外的机器操作员、工具、模具等副资源总是受到限制的[2]。为了更符合制造系统的现实场景，已有学者考虑将副资源数量受限这一特征纳入到PMS 中，即资源受限并行机调度（Resource-Constrained Parallel Machine Scheduling，RCPMS）。由于需要在传统PMS 问题的基础之上，同时考虑副资源层面的限制，RCPMS 问题的求解难度更大，显然是一个NP问题。RCPMS问题广泛存在于注塑[3]与发泡成型、刀具调度[4]、半导体制造等众多行业，因此，对其进行研究具有较高的学术意义与应用价值。

近年来开始有学者针对RCPMS 问题展开了研究，RCPMS 问题实质在于需要同时将并行机器和有限副资源以最优成组形式分配给任务进行生产，是经典PMS 问题的现实化扩展。从问题特征上来看，当前可将RCPMS问题分为经典RCPMS 问题与拓展RCPMS 问题。综合现有经典RCPMS研究来看，它们基本都以最大完工时间为优化目标，如文献[5]和文献[6]，少数以交货期相关的指标为优化目标的研究[7]。近年来，为了更加真实地模拟现实制造系统，部分学者开始研究经典RCPMS 的扩展问题。文献[8]研究了一类按订单生产RCPMS中订单接收和调度问题。文献[9]则是研究了以最大完工时间最小化为目标的带有预防性维修（PM）的RCPMS 问题。文献[10]研究了一类来源于塑料注射系统的带批量决策RCPMS问题。文献[4]则针对带批量决策的刀具资源受限RCPMS问题进行了研究。此外，考虑能耗相关的RCPMS绿色调度问题近年来也吸引了一些学者的注意。文献[11]研究了瓶颈工序光刻过程中考虑能源消耗的RCPMS问题。文献[12]则研究了考虑绿色制造需求的RCPMS优化问题。

从求解方法来看，按照能否获得最优解可将RCPMS问题求解算法分为启发式方法、数学规划方法两类。当前，大多数RCPMS问题都是通过启发式方法来进行求解的。启发式方法包括问题特定启发式算法和元启发式算法两类。问题特定启发式算法可以在相对较小的时间成本下寻找到接近最优解的可行解，通过构造不同的启发式算法可以解决各类不同的实际问题[13]。然而，启发式算法只能生成有限的不同解，或者容易终止于较差的局部最优上，而且通常只针对特定问题才有效，不同问题则往往需要重新构造启发式算法。近年来，以获得近似最优解为目标的元启发式算法开始应用于RCPMS 问题中。如迭代贪婪算法[14]，遗传算法[2]和禁忌搜索算法[15]等。此外，也有学者通过将群体进化算法与定制的局部搜索程序混合来加强算法的搜索性能[16]。在实际生产中，往往需要依据决策者的偏好或企业不同时期的生产特点，同时在多个目标之间进行折衷平衡，因此，多目标进化算法也得到了重视[11]。此外，也有使用数学规划方法对RCPMS 问题研究，数学规划方法如整数线性规划[17]将问题表示和解决策略分开，因此一般可通过许多不同的求解器求解。然而，在大规模工业调度问题上使用MIP 方法进行求解往往在求解效率方面难以满足现实需要。

本研究针对家电企业冰箱发泡车间的生产调度问题，其本质上可抽象为一类具有多层决策变量、多维约束的大规模RCPMS问题。前述研究大多数采用启发式方法求解RCPMS问题，但是在面对如多品种小批量冰箱发泡生产调度这类带复杂约束RCPMS问题时存在建模困难、实现难度高的缺点。约束规划（Constraint Program，CP）[18]方法融合了计算机科学、人工智能、运筹学等技术[19]，在求解约束满足问题（Constraint Satisfaction Problem，CSP） 或约束优化问题（Constraint Optimization Problem，COP）时，可系统地采用演绎推理来减少搜索空间，并具备强大高效的复杂逻辑约束表达能力，已被广泛应用于求解焊接车间调度[20]、岸桥调度[19]、资源受限项目调度等组合优化问题。使用CP 方法求解RCPMS问题也已经成为当前的研究热点[21]，而目前国内尚无应用CP 求解RCPMS 问题的相关研究，本文将针对多品种小批量冰箱发泡生产调度问题的特点，基于CP表达复杂逻辑约束的优势，提出两种CP模型求解此问题，并通过实验对比两种模型在不同规模和调度场景下的优劣。

1 问题描述

1.1 多品种小批量冰箱发泡生产调度问题背景

冰箱产品由一个箱体与多个相同或不同型号、数量的门体组成，冰箱的生产分为5 个部分：箱体预装配、箱体发泡、门体预装配、门体发泡、总体装配。箱体发泡是指使用箱体发泡机器与箱体模具完成箱体保温层的制造，箱体发泡机器为箱体模具的通用设备，箱体产品型号与箱体模具型号一一对应，门体与箱体同理。同一种箱体或门体均可能用于装配一种或以上的产品。总装配工序是指将箱体产品与门体产品组装成冰箱成品。多品种小批量冰箱发泡生产调度时间长度为一个月，按照班次进行调度，将月度订单按照产品汇总，需要求解出：（1）每一个班次各型号产品的排产数量；（2）同一箱体发泡生产线的发泡机器在线体内划分为2个区域，箱体模具作为关键资源，在区域层面与线体层面均存在约束，需要精确求解到各班次的各区域的各发泡机器安排哪一个型号的箱体模具发泡；门体发泡过程仅考虑资源数量约束。

因此，多品种小批量冰箱发泡生产调度问题可描述为：有n种确定需求量的产品需要在k个班次内排产完成，需要使用x种有限的箱体模具与y种有限的门体模具资源，各产品的生产效率与其使用的箱体模具一致；箱体模具在有限的M台相同机器上加工，门体模具在无限的P台相同机器上加工；箱体与门体模具均以班次为单位进行排产，箱体与门体模具的排产共同组成各型号产品的排产；某发泡机器上相邻班次之间排产的箱体模具型号若发生变化，即为换模，换模需要占用较长的生产时间，是影响产能的主要原因，在满足约束的前提下减少换模，是本问题的优化目标，因为实际换模时间设计的因素较多（人工经验、运输距离），所以用换模次数来表示换模对生产时间的影响。由问题描述可知，本问题需要两组决策变量，且两组决策变量存在数量或者映射关系，决策变量具有多层次的特性。

1.2 约束描述

相关约束描述及意义如表1所示。由表1可知，各约束属于不同生产阶段，约束对于问题的求解存在不同维度的影响，凸显了多维约束复杂性。

表1 约束描述表

2 约束规划模型

本文所构建的CP 模型使用了IBM ILOG CPLEX Optimization Studio 12.10 中的CP Optimizer 优化引擎，在.Net平台使用C#编程语言实现；CP模型的表达比MIP模型更灵活，基于特定优化引擎的函数库，可以更简洁明了地表达复杂的逻辑型约束；本文将使用CP Optimizer 优化引擎中的函数作为建模语言，这些建模语言的含义都是自明的，在描述约束时也会对建模语言加以解释。

多品种小批量冰箱发泡生产调度是以班次为单位调度的，并且各型号需求量波动较大，在多维约束下通常无法将一个型号排产作为一个任务进行调度，且建模困难；因此本文不使用CP Optimizer 中的区间变量构建决策变量，而是采用常规的离散型整型变量作为决策变量，能够更容易表达本问题中的特定约束，更符合问题的特点。本问题具有多层决策变量且决策变量之间具有映射关系，A 策变量相应的约束也会映射到B 决策变量上，从这个问题特征出发，本文构建了基于映射关系关联决策多层变量与基于数量约束关联多层决策变量的CP 模型，具体模型如下。

2.1 模型参数

模型基础参数如表2 所示。生产调度以班次为时间单位进行调度，产品的生产效率与关键资源箱体模具一致，箱体模具的班次产能由箱体模具生产效率与班次工时决定，为方便建模，定义产品或者箱体模具的排产计算基数，产品b的产能计算基数即为在某个班次排产了产品b的几个班次产能，箱体模具x的排产计算基数即为某个班次排产了几个模具x的班次产能，以此计算产品或者箱体模具的总班次产能，用式（1）表示使用排产计算基数计算产品或箱体模具的总班次产能：

表2 模型基础参数表

约束参数如表3所示。

表3 模型约束参数表

2.2 模型1：基于数量约束关联多层决策变量的CP模型

2.2.1 决策变量

2.2.2 约束表达式

函数if(Expr1)then(Expr2)作用是如果Expr1 为真，则Expr2 生效且为真。(Expr1)And(Expr2)函数表示Expr1与Expr2 同时成立。则约束（3）的含义为：任意班次如果产品b1与产品b2存在互斥约束，则如果b1大于0 时b2必等于0，如果b2大于0 则b1必等于0，即产品b1与产品b2不允许同班次排产。

约束（4）表示，产品b的所有班次排产量总和大于等于其需求量，且小于等于需求量的110%，10%的富裕排产空间是为了让整数决策变量可以取整，且10%的富裕是工厂实际可接受的。

约束（5）表示，任意班次任一种产品其排产产能不可超过其所需的门体模具资源的班次生产能力。

countdifferent(Expr)函数的作用是，计算Expr中取到不同值的决策变量的数量；所以约束（6）表示，任意班次中，区域q内排产的箱体模具种类数量小于等于其区域种类数量上限值。

约束（7）表示，任意班次内箱体发泡线所有发泡机器排产的箱体模具种类数量小于等于全线体种类数量上限值。

2.2.3 目标函数

Abs(Expr)函数的作用是对Expr 取绝对值，目标函数式（8）的计算逻辑是，从第二个班次开始，计算当前班次v的箱体模具x的排产计算基数count(mmodvk=1…k,x)与上一班次的排产计算基数count(mmodv-1,k=1…k,x)，将两个值相减后取绝对值，即为箱体模具x在班次v和v- 1之间的绝对差值，假如模具从x1换到x2，那么x1的减少与x2的增加是重复计算的，所以将从第一班次开始的各箱体模具的差值变化相加，再除以2，就是实际的换模次数。

2.3 模型2：基于映射关系关联多层决策变量的CP模型

基于映射关系与基于数量约束关联多层决策变量的CP 模型的主要区别是产品排产基数决策变量的形式不同，以及产品排产决策变量与箱体模具排产决策变量的关联方式不一样。

2.3.1 决策变量

本模型一共定义了2组整数类型决策变量：（1）Fvk，为产品排产基数决策变量，表示班次v发泡机器k上排产的箱体模具供应的产品型号编号，其取值范围是：0 ≤Fvk≤b；0为虚拟产品编号，Fvk取到0即为不排产任何产品。（2）箱体模具排产决策变量与基于数量约束关联多层决策变量的CP 模型一致，为mmodvk，其具体含义见上文。本模型中Fvk与mmodvk使用CP Optimizer优化引擎中的Element(Expri,Exprj,Arry)函数通过映射关系关联，Expri与Exprj均是单个决策变量，Arry 是一个数组，数组的索引与Exprj的取值范围对应，Element(Expri,Exprj,Arry)的作用是建立约束：Expri的取值等于Arry 中索引为Exprj的值；建立式（9）：

式（9）建立约束，对于任意的班次v中的发泡机器k，决策变量mmodvk的取值等于Ab中索引为Fvk的值，表达了mmodvk与Fvk之间的映射约束关系。

2.3.2 约束表达式

约束（10）与约束（3）含义一致。

约束（11）与约束（4）含义一致。

约束（12）与约束（5）含义一致。

因为本模型与模型1 的箱体模具排产决策变量一致，故有关mmodvk的约束也与模型1一致，不再重复描述。

2.3.3 目标函数

目标函数与模型1一致，此处不再重复。

3 调度案例

本文使用IBM ILOG CPLEX Optimization Studio 12.10优化软件，在.Net 平台中使用C#编程语言编码，调用求解器为CP Optimizer 优化引擎，相对最优容差值设置为0，求解时间设置为1 800 s，其余设置按照默认设置执行。实验环境为台式计算机，CPU 为12th Gen Intel（R） Core （TM） i5-12490F 3.00 GHz，32GB 内存，Windows 10操作系统。

3.1 数据描述

选取某工厂的13 份历史订单数据使用两个模型进行对比求解实验，所选取数据的基本特征如表4所示。

表4 实验数据基础特征表

3.2 求解结果分析

表5是两个模型在同一参数设置下的求解结果。

表5 模型求解结果

从表5 的求解结果可以看出，模型1 与模型2 在不同的输入数据下均存在模型1更优或模型2更优的情况，说明两个模型各有优势。根据表5 的求解结果，结合输入数据的基本特征，整理出模型1更优的数据及其求解结果如表6所示，模型2更优的数据及求解结果如表7所示。

表6 模型1更优结果表

表7 模型2更优结果表

由表6和表7可知，对于产能需求低且产品种类小于等于10、箱体模具种类小于10的输入数据，基于数量约束关联多层决策变量的CP模型有更大的概率获得更优的求解结果，此时应选择模型1；对于产能需求高、且产品种类大于10、箱体模具种类大于10的输入数据，基于映射关系关联多层决策变量的CP模型则有更大的概率获得更好的求解结果，此时应选择模型2。这是因为，模型1 在产能需求、产品种类与模具种类较少的时候解空间割裂度低、决策变量数量较少，决策变量的取值范围较小，相比于模型2，同一数据的求解规模较小，故更容易在相同时间内求得更好的结果；而当产能需求较大、产品种类与模具种类较多时，解空间割裂度明显变高，且模型2 的决策变量数量不变，其以映射关系关联决策模型能高效利用CP 的约束传播优势，有更高的搜索效率，所以此时模型2能求得更好的结果。

4 结束语

本研究对RCPMS问题进行了描述，将约束规划技术应用于求解一类具有多维约束的RCPMS问题，并结合实际制造系统中的调度场景，选择多品种小批量冰箱发泡生产调度作为典型案例；根据此问题的特点，结合IBM ILOG Cplex Optimization Studio 12.10 中的CP Optimizer优化引擎的高效逻辑约束表达函数，建立了两种CP模型。通过实验求解，并对比了两种模型求解结果的优劣，发现在产能需求较低且产品种类小于等于10、箱体模具种类小于10时模型1的求解结果更好，在产能需求较高、且产品种类大于10、箱体模具种类大于10 时模型2 的求解结果更好，验证了CP求解RCPMS问题的可行性与CP模型的有效性。