一、引言

排产调度通过合理安排工件任务的执行顺序和分配制造资源，提高生产效率、优化生产指标，在制造企业的生产过程管理中扮演重要角色。车间排产优化问题具有工艺复杂、约束复杂等特点，是典型的 NP 问题，求解通常面临极大的计算复杂性。现有的车间排产算法分为精确方法和近似方法两大类，其中，精确方法无法求解实际工程中的大规模问题，近似方法往往要求设计者深入理解相关的领域知识，针对特定问题对算法进行定制化的修改，通用性较差。

目前，市面上的高级建模语言包括 MiniZinc、AMPL等， 主流求解器软件包括CPLEX、GUROBI、OR-Tools、SCIP 等。MiniZinc 是一种用于整数和实数上的约束优化和决策问题的高级语言；AMPL是一种解决数学编程问题的语言，适用于线性、非线性规划模型的描述。这两种语言不能完全覆盖实际车间排产场景下涉及物流转运、缓冲决策、转换时间等问题的复杂约束，通常需要利用数学关系和逻辑推导间接对问题建模，建模难度高，求解效率低下。

CPLEX是IBM 公司的一种优秀的专业商用优化求解器，其提供的标准CP求解器以及复杂的搜索策略在复杂优化问题上具有出色的性能。

GUROBI是由美国 Gurobi Optimization 公司开发的新一代商用大规模优化器，广泛应用于线性规划、混合整数线性规划、凸二次规划等问题，且在上述领域具有很强的求解性能，此外 GUROBI 提供了灵活的参数调整工具，支持分布式并行调优。然而利用 CPLEX 与 GUROBI提供的建模接口针对实际场景的车间排产问题进行建模时存在复杂迂回的问题，建模能力明显不足，且在搜索策略的自定义方面不如 SCIP灵 活。

OR-Tools 是一种用于 各类优化的开源软件，能够使用额外的内核显著改善求解的质量与效率。OR-Tools 的库非常全面，尤其是MPSolver 求解模块表现十分出色。 但ORTools在求解大规模问题时，求解质量与效率不如 CPLEX。SCIP 是目前最快的混合整数规划（MIP）和混合整数非线性规划（MINLP）的非商业求解器之一，与大多数商业求解器不同的是，SCIP 为用户提供了对求解过程的低级控制和信息。但 SCIP 对于车间排产问题的求解能力不如 CPLEX 与 GUROBI 等商业求解器，且求解过程存在不稳定性。

针对实际生产场景下的车间排产问题，现有建模语言存在建模难度高、不直观等问题，而现有求解工具和算法面对实际生产规模的排产问题求解速度慢甚至无法求解。因此，本文设计开发了一种面向车间排产的通用建模求解工具：面向排产约束设计了一种建模语言来形式化表述排产问题，提升建模的通用性；通过动态精英解集引导启发式算法对解进行迭代优化，实现实时、高效求解实际生产规模的排产问题。

二、面向车间排产的建模语言设计

针对车间排产场景中的多样化约束和优化目标，本文设计了一种通用的建模语言，可以直接表达排产问题中的特定约束和优化目标、简化建模过程。本建模语言主要包括基础数据类型、决策变量、约束条件和优化目标四个部分。建模语言与说明如表 1 所示。

表 1 建模语言与说明

续表 1 建模语言与说明

决策变量是模型表达能力与求解灵活性的核心。通过为决策变量的取值范围定义一个离散化的区间（该区间存放多个下界与上界），以实现对取值范围的动态管理。约束条件用于描述实际生产环境中的限制与规则，确保模型的可行性。优化目标的设定会直接影响生产效率、资源利用率和交付性能，包括交付时间类优化目标、资源利用类优化目标、成本类优化目标以及生产均衡类优化目标等。

以总装车间排产优化问题为例，应用排产约束建模语言设定任务顺序关系、资源限制等约束，优化目标为最小化最晚完工时间，建立模型示例如下。

总装车间排产问题模型文件示例代码

% 声明工件、工序数量、最晚交期时间、工序加工时间

int jn, tn, deadline,;

int taskTime[tn];

Sint Job within (1..jn);

Sint Task within (1..tn);

Dint start[jobNum][taskNum] within (0, deadline);

Dint size[jobNum][taskNum];

Dint end[jobNum][taskNum] within (0, deadline);

Dbool presence[jobNum][taskNum] within (1, 1);

Doperation tasks[jobNum][taskNum];

forall(j in Job) forall(t in Task) (Dint size[j][t] within

(taskTime[t], taskTime[t]));

% 声明所有结束工序的数组 A_e

Doperation A_e[jn];

forall (j in Job) (A_e[j] = end[j][tn]);

% 定义任务决策变量

forall (j in Job) (for (t in Task) (Doperation op[j, t]

(start[j, t], size[j, t], end[j, t], presence[j, t]); ) );

% 顺序约束

forall (j in Job) ( forall (t in 2..tn) (

finishAtBeforeStart(op[j][t - 1], op[j][t], 0); ));

% 资源约束，S_r 为占用同一资源的任务集合

cumulativeFunction(S_r, c, C);

MinFinishTime (A_e);

三、动态精英解集引导的启发式求解算法设计与实现

求解器的设计与实现主要分为可行解生成与解的优化两部分。首先，基于排产信息采用启发式方法生成初始可行解；然后，结合目标函数信息和维护的历史解集，引导启发式算法对解进行优化。

（一）基于启发式的初始可行解生成算法

可行解生成的核心目标是构建一个满足所有约束条件的解，一个高质量的可行解能够保证接下来优化求解的效率与质量。此外，可行解的生成需要兼顾解的可行性和求解的效率。启发式算法具有求解速度快、易于实现等特点，广泛应用于车间排产问题中。可行解生成算法依据排产约束信息设计启发值计算公式，进而确定任务的安排顺序。通过为每个任务分配满足所有约束的最早可安排时间进而生成初始可行解。算法流程如图 1 所示。

图 1 可行解生成算法流程

具体描述如下。

步骤一，忽略资源限制，对所有任务进行正排与倒排，获得每个任务最早可安排的开始时间以及保证交货期的最晚开始时间。

步骤二，利用启发值计算公式为每个任务定义启发值 H。该计算公式如下：

上式中， p_i和Let_i分别对应任务的加工时间与最晚结束时间，H_t代表任务的加工时间占比。a、b、c 是权重系数， 表示该任务的前继任务总数量，代表前继任务量越少的任务越倾向于被优先安排。Ω为占用对应资源的任务序号集合，r_Ω和d_Ω分别代表任务集合中最早开始时间与最晚结束时间，H_slack 为资源约束松弛度启发值。Index 表示订单序号，H_order 表示订单启发值。H_C代表约束越多的任务越倾向于被优先安排。Obj 为优化目标值，H_opt 表示优化启发值。

步骤三，选择启发值大的任务优先安排开始时间，设置开始时间为其最早开始时间到最晚开始时间区间内满足所有约束条件的最小值。

步骤四，如果任务由于约束限制不能正常安排，则降低其启发值，等待对应约束条件满足后再进行安排。若任务成功安排则将其从待安排任务集合中移除。通过约束传播缩减剩余任务的取值范围，更新启发值并对任务集合重新排序。

步骤五，当任务集为空时，程序终止，否则继续迭代。

（二）动态精英解集引导的迭代优化算法

迭代优化算法利用优化目标以及维护的历史解集信息指导启发式算法进行迭代求解。通过构建禁忌表，对每次迭代使用的优化启发值进行禁忌处理，防止在搜索过程中返回到已访问的解，同时对生成的优化解进行判定、筛选。其伪代码如下：

优化算法

Input：初始解 x0，目标函数 f(x)，最大迭代次数 max_iterations，优化启发值函数 g(x)

Output：运行时间 t，目标值 v，全局最优解 best_solu

初始化

当前最优解 x←x0；全局最优解 best_solu←x0；禁忌表 tabulist← 空 集； 迭 代 次 数 iter←0；精英解集 eli_solu←x0

重复以下步骤直到 iter≥max_iterations

1．H[]←g(x)，获得不同的优化启发值集合

2．通过不被禁忌的启发值获取最优可行候选解 x’

3．if (f(x) < f(x’))

4． then tabulist←H[]，x←x’，best_solu←x’，eli_solu←x’，输出优化解 x’ 相关信息

5． elseif (Metropolis(x’,x) > 0) 评估准则

6．then tabulist←H[]，eli_solu←x’

7．else

8．then 对优化启发值进行扰动

9．endif

10．更新温度、禁忌期限

11．迭代计数 iter←iter + 1

具体描述如下。

步骤一，根据优化目标以及维护的精英解集，分别计算对应任务的优化启发值（H）。该启发值的计算公式为：

上式中，表示上一轮迭代中各任务的优化启发值集合，a、b 为权重系数，S_opt 为需要进行优化的历史解变量集合、S_obj 为优化目标值集合，通过调整权重系数，可以生成不同的优化启发值集合。

步骤二，将不被禁忌的优化启发值分别加入原启发式中，进而构造多个满足所有约束条件的新可行解。

步骤三，选择本次迭代生成的所有可行解中目标值最优的解作为候选解，并判断该解是否为当前最优解。如果是则将对应的优化启发值保存至禁忌链表中以防重复搜索并将该解存入精英解集中；否则利用 Metropolis 准则对该解进行评估。若解的质量劣于当前最优解但基于准则能够接受，仍将优化启发值存储于禁忌表中并将该解存入精英解集中；否则对优化启发值进行扰动并重新迭代求解。

步骤四，根据历史解集的信息更新优化启发值。利用指数退火方法进行降温并对所有禁忌对象的禁忌期限递减。若禁忌期限归零则将该对象从禁忌表中移除。

步骤五，如果当前迭代次数达到设定的全局最大迭代次数，则结束搜索，否则重复上述过程，直至达到停止条件。

四、实验验证与分析

针对实际全自动机加工生产车间进行建模求解，分别对比建模求解工具与 MiniZinc 在复杂约束表达上的区别以及其与 CP-SAT、Chuffed等求解器在求解效率上的差异。

（一）问题描述

全自动机加车间进行两大类共四种产品的生产，配备四台加工中心、两个物流机器人、一台喷码机、一台去工艺夹台、一台清洗机、一台测量机、四套毛坯托盘、两套成品托盘以及两套中转站。使用 AGV 小车运送工件托盘进出车间，整个机加车间的加工流程为：加工中心加工→喷码→去工艺夹→清洗→测量，该生产车间示意如图 2 所示。

图 2 全自动机加工生产车间示意

该车间排产优化问题需满足如下约束条件：约束一，工序顺序约束，需保证上述加工流程；

约束二，托盘容量约束，AGV 小车一次只能运送一个托盘，每个托盘最多只能装载 9 个 A类工件或者 10 个 B 类工件；

约束三，考虑物流转运的资源占用与释放约束，例如当一组任务都需要占用喷码机时，由于喷码机只有一台，故需前一个任务被转运走，下一个任务才能转运至喷码机进行加工；约束四，批次约束，由于订单间存在不混批要求，同一工艺条件下需先完成前一个订单的加工，才允许下一个订单的工件进入生产车间；约束五，转换时间约束，转运机器人 1 执行转运任务时，若前后抓取的工件种类不同，需要留出时间更换机械爪。各工序所需加工时间如表 2 所示。

表 2 各工序所需加工时间

（二）建模语言对比分析

对于一些实际生产会出现的复杂约束如合批约束、考虑物流转运的资源占用与释放约束、转换时间约束等，利用 OR-Tools 或 MiniZinc 对实际场景进行建模，需要用户根据具体约束特征自行编写专门的结构与函数，这不仅大幅增加了建模的复杂性，还降低了代码的可读性与维护性。以考虑物流转运的资源占用与释放约束为例，在使用 MiniZinc 进行建模时，需要定义一个新的任务变量。该变量的开始时间对应运至该机器的转运任务开始时间，结束时间则对应从机器运走的转运任务结束时间。针对该约束，具体建模语言如下：

MiniZinc 针对考虑物流转运的资源占用与释放约束建模

% 定义工件、工序数量、工序加工时间、最晚交期时间

int jn, tn, deadline；

set of int: JOB = 1..jn;

set of int: TASK = 1..tn;

array[TASK] of int: task_dur;

array[JOB, TASK] of var 0..deadline: starts;

array[JOB] of var int: trans_s1;

array[JOB] of var int: trans_s2;

constraint forall(j in JOB) (trans_s1[j] = starts[j, 4]);

constraint forall(j in JOB) (trans_s2[j] = starts[j, 6]);

constraint forall(j, k in JOB where j < k) (no_overlap(

trans_s1[j], task_dur[5] + trans_s2[j] – trans_s1[j],

trans_s1[k], task_dur[5] + trans_s2[k] – trans_s1[k]));

% 若资源能力大于 1，使用 cumulative 进行约束

利用本文提出的排产建模语言，针对考虑物流转运的资源占用与释放约束进行建模，具体如下：

建模语言针对考虑物流转运的资源占用与释放约束建模

# 定义工件数量、资源能力

int jobNum, num;

Doperation S_t1[jobNum];

Doperation S_t2[jobNum];

Doperation S_t3[jobNum];

// 带转运考虑的资源占用释放约束

Transport(S_t1, S_t2, S_t3, num);

本建模求解工具只需利用自定义排产建模语言调用对应 API 即可支持上述复杂约束。通过对比可以看出，本建模语言的建模过程简洁清晰、具备良好的可扩展性。因此，本工具在实际应用中具有显著优势。

（三）求解结果对比分析

实 验 在 Windows11 操 作 系 统（64 位） 下运 行，CPU 为 AMD Ryzen 7 5800H with Radeon Graphics，3.20GHz 主频频率，16.0GB 内存。

分别利用建模求解工具、CP-SAT 求解器（OR-Tools）以及 Chuffed、COIN-BC、Gecode 等求解器（MiniZinc）针对 30 件、50 件和 100 件（实际生产场景）工件规模的生产任务进行性能对比实验。设置求解时间上限为 1 小时，求解优化目标为最小化各订单拖期时间（目标值大于等于 0）。

表 3 30 件工件任务规模对比表

表 4 50 件工件任务规模对比表

表 5 100 件工件任务规模对比表

30 件和 50 件工件规模问题的求解数据对比结果如表 3、表 4 所示。鉴于实际生产过程中快速生成初始可行解对车间的实时响应至关重要，因此在结果中分别列出了初始解与最优解的性能指标（Best 表示对应求解器在限定条件下获得的最优解，“-”代表对应求解器在限定时间内无法获得可行解或无法对可行解进行优化）。鉴于 CP-SAT 等求解器无法求解 100 件工件规模的问题，为评估本工具在实际生产环境中的求解性能，在确保建模求解工具满足所有约束条件的前提下，对 OR-Tools 构建的模型进行约束松弛处理（包括移除转运约束、转换时间约束等限制条件），并将本工具与 CP-SAT 求解器进行性能对比。表 5 展示了 100 件工件规模问题的求解数据对比结果。

实验结果表明：

（1）与 OR-Tools 的 CPSAT 求解器相比，本建模求解工具在该问题求

解中展现出更强的快速求解能力，且在大部分测试样本中，本工具获得的最终解质量更优；

（2）随着问题规模增大，建模求解工具依然能够在合理时间内给出高质量解，而 CP-SAT 求解器的效率明显降低，且不能对实际生产车间做出快速反应、无法满足实际生产车间的需求；

（3）由于启发式算法无法确保解的完备性，导致在求解 50 件工件规模的第四个样本时，出现了在预设最大迭代次数内无法进一步优化解的情况；

（4）Chuffed、Gecode 和 COIN-BC 等求解器针对上述问题无法在 1 个小时内获得可行解。

五、结论与展望

本文开发了一种面向车间排产问题的建模求解工具，实现了建模语言与求解算法的解耦。工具首先通过启发式方法快速生成可行解，然后通过动态精英解集引导启发式算法对解进行优化。为验证本工具的有效性，通过全自动机加工生产车间应用案例，对比了 MiniZinc 与本文提出的建模语言在复杂约束表达上的差异，证明了本建模语言在模型构建过程中更加简洁清晰，且具备良好的可复用性。此外，通过与OR-Tools 的 CP-SAT 求解器以及 MiniZinc 兼容的求解器进行性能对比，本文工具展现了更强的快速求解能力，并能够高效应对实际生产车间规模的排产问题，充分验证了其在实际生产场景下的实用性与优越性。本工具目前仍存在以下改进空间。

（1）对搜索控制的支持：为建模语言设定专门用于搜索控制的 API，如搜索策略、输出格式、搜索结束条件、面向场景等。在建模的过程中通过调用 API，根据实际需求进行参数设置以达到灵活控制搜索过程的目的。

（2）对更大规模问题的适应能力：如装配车间排产问题，这类问题规模往往更大，需要进一步验证本建模求解工具对相关问题的适应能力，以确保对大规模问题的求解效率以及针对多场景的通用性。

原文刊载于《数字化转型》2025 年第4期 作者：中国航空制造技术研究院数字化制造技术航空科技重点实验室 陈骏平 牛冠凯 李啸