2026年五一数学建模竞赛B题成品论文、结果

m0_69827984

411人浏览 · 2026-05-02 08:42:24

m0_69827984 · 2026-05-02 08:42:24 发布

多工序协同作业问题的调度优化研究

摘要

本文针对2026年第二十三届五一数学建模竞赛B题所提出的多工序协同作业调度问题，围绕A、B、C、 D、E五个车间的整修任务，以最小化总完工时间（Makespan）为目标，建立了一套完整的数学规划模型，并结合枚举分析与约束规划方法对四个递进式问题逐一求解。

针对问题1，仅使用班组1的设备完成A车间整修。A车间包含A1、A2、A3三道串行工序，采用全量设备分配策略。其中A2工序涉及高速抛光机与工业清洗机双设备协同，利用"提前释放"机制使清洗机在完成自身工程量后即行转移，不拖延抛光机驱动的工序时长。通过枚举最优台数分配，确定最短完工时长为 37280秒（10:21:20），关键路径为A1→A2→A3。

针对问题2，仍仅使用班组1的设备，完成全部五个车间的整修任务。建立含27道工序（含C3-C5循环×3展开）的单机组调度模型，引入瓶颈分析与设备路线枚举。通过对高速抛光机24种车间访问顺序的全枚举，确定最优路线为A→C→B→D，并结合清洗机的灵活分配策略（B1用5台快速完成后分流各工序），采用精确推导方式确定最短完工时长为215326秒（59:48:46），关键路径为D3→D4→D5→D6。

针对问题3，引入班组2与班组1协同作业。建立双班组析取图调度模型（Disjunctive Graph Scheduling），允许同一工序跨班组混用设备，并调用OR-Tools CP-SAT约束规划求解器进行全局精确求解，求解状态为OPTIMAL（已证明全局最优），最短完工时长为83042秒（23:04:02），相比问题2缩短61.4%，关键路径终点为C5_3工序结束。

针对问题4，在双班组基础上追加500000元设备购置预算。建立双层优化模型：外层枚举满足预算约束的购置方案（按瓶颈优先评分排序，评估Top-40方案），内层对每个方案调用CP-SAT求解调度，总耗时约19秒即完成全部搜索。最优购置方案为：精密灌装机+1台（班组1），高速抛光机+3台（班组1两台、班组2一台），自动传感多功能机+3台（班组1两台、班组2一台），购置总费用恰为500000元。购置后最短完工时长为36440秒（10:07:20），相比问题2缩短83.1%，验证了"均衡瓶颈"原则的有效性。

综合四个问题的建模与求解，本文构建了涵盖工序时长计算、设备转运约束、前驱依赖关系、双设备提前释放及预算约束的完整调度优化框架。结果表明，双班组协同与针对性设备购置对Makespan的压缩效果显著，高速抛光机与自动传感多功能机始终是制约整体进度的核心瓶颈。

关键词：多工序调度；最小化完工时间；析取图模型；CP-SAT约束规划；瓶颈分析；双层优化；设备

《2026年五一数学建模竞赛A,B,C成品论文助攻》

https://www.yuque.com/yuqueyonghufymzmc/soi2fz/vh15xaxw25l4oykh?singleDoc# https://www.yuque.com/yuqueyonghufymzmc/soi2fz/vh15xaxw25l4oykh?singleDoc#

2026五一数学建模A ,B ,C题助攻资料
链接: https://pan.baidu.com/s/1bqM8YBMJxQ1yfph9X9vTUw?pwd=2628 http://2026五一数学建模A ,B ,C题助攻资料链接: https://pan.baidu.com/s/1bqM8YBMJxQ1yfph9X9vTUw?pwd=2628 提取码: 2628提取码: 2628

论文视频讲解

https://www.bilibili.com/video/BV1D3RLBaEeo/https://www.bilibili.com/video/BV1D3RLBaEeo/

一、引言

1. 问题背景

工程项目中多工序协同调度是运筹学与工业工程领域的经典难题，其核心目标是在有限设备资源约束下，通过合理安排各工序的开始时间与设备分配，最小化所有任务的总完工时间。随着制造业与基础设施运维工程规模的不断扩大，涉及多类型设备、多个作业区域、设备跨区转运及预算约束的复杂调度问题日益普遍，对调度模型的建立与求解方法提出了更高要求。

本题以某大型工程设施的五个车间整修任务为背景，涵盖5种类型共15台（单班组）设备的协调调度，工序之间存在严格的前驱依赖关系，设备在不同车间之间转运需消耗时间，部分工序需要两类设备协同完成。特别是C车间的C3-C5工序需循环执行3遍，形成了复杂的串行依赖链。此类问题兼具置换流水车间调度（Permutation Flow Shop）和柔性作业车间调度（Flexible Job Shop）的特征，同时引入了设备转运时间约束，属于NP-hard问题范畴，具有较高的研究与实践价值。

1. 问题重述

本题以A、B、C、D、E五个车间的整修作业为研究对象。整修任务由多道工序构成，每道工序需要指定类型的设备（可能需要两类设备同时工作）在特定车间完成，工序之间存在严格的先后约束。

基本参数设定如下：

设备均从各自班组基地出发，移动速度为2m/s，转运时间向上取整为整秒。工序时长按如下公式计算

（向上取整）：

设工序工程量为Q（m³），参与设备台数为n，设备效率为v（m³/h），则工序时长（秒）为：

对于需要两类设备同时参与的双设备工序，工序时长取两类设备各自完成时间的最大值；当某类设备先于工序结束时，该类设备可立即离开，转移至后续工序（提前释放机制）。

四个递进问题：

问题1：仅班组1，完成A车间，求最短时长

问题2：仅班组1，完成五个车间，求最短时长；

问题3：班组1+班组2协同，完成五个车间，求最短时长；

问题4：班组1+班组2+500000元购置预算，完成五个车间，求最短时长并给出购置方案。

1. 文献综述

最小化Makespan的调度问题（Scheduling to Minimize Makespan）是组合优化中的核心研究方向之一。Graham等（1979）奠定了调度理论的经典框架，指出即使是单机多工件的调度问题，在存在工序前驱约束时也是NP-hard的。

对于柔性作业车间调度（FJSP），Brucker和Schlie（1990）首先证明了其NP-hard性，并提出了枚举方法处理小规模实例。析取图（Disjunctive Graph）模型由Roy和Sussmann（1964）提出，将调度问题转化为图论中的最长路径（关键路径）问题，为后续精确算法和启发式算法的设计提供了统一建模框架。

在精确求解方面，约束规划（Constraint Programming, CP）已成为解决复杂调度问题的重要工具。 Google OR-Tools中的CP-SAT求解器（Perron和Furnon, 2019）集成了SAT求解、线性规划松弛和传播算法，能够对中等规模调度实例提供精确最优解，在工业调度竞赛中表现优异。

在含设备转运时间的调度研究方面，Hurink等（1994）将转运时间建模为工序间距约束（sequence- dependent setup time），本文采用类似建模思路。

对于带资源采购约束的调度优化，Hartmann（2001）提出了资源受限项目调度问题（RCPSP）的双层优化框架，外层确定资源方案，内层求解调度，本文问题4的建模与该框架高度吻合。

二、模型准备

1. 假设与说明

假设1：设备转运时间确定且仅取决于出发地与目的地

设备在两个地点之间的移动路程固定，移动速度固定为2m/s，因此转运时间仅由距离决定，不受交通拥堵、路线选择等不确定因素影响。转运时间公式为：

转运

其中d(a,b) 为地点a 与地点b 之间的距离（米）。该假设在封闭工业园区等结构化环境下具有较高合理性。

假设2：同一工序中参与的设备数量在整个工序执行期间保持不变

即一旦某工序开始，参与该工序的设备台数不再发生变化（不允许工序中途增减设备）。该假设使工序时长为确定性量，便于建立精确调度模型。

假设3：双设备工序中，先自身工程量的设备可立即提前释放

对于需要两类设备协同的工序（如A2需要高速抛光机和工业清洗机），两类设备的工作时长可能不同，工序结束时间取较长者。较短工作时长的设备完成后可立即转移，无需等待工序完全结束。此机制充分利用了设备的空闲时间，是本文调度优化的关键机制之一。

假设4：各班组设备在问题开始时均位于各自基地，处于可用状态

所有设备在时刻0均可从各自班组基地出发。班组1基地到各车间距离：A=400m，B=620m， C=460m，D=710m，E=400m；班组2基地到各车间距离：A=500m，B=460m，C=620m， D=680m，E=550m。

假设5：同一车间内部，设备可以不计时间成本在不同工序之间切换

若设备在同一车间内连续完成两道相邻工序，切换时间为零（无需转运）。该假设等价于将同车间工序间的转运距离设为0。

假设6：各工序只能在满足全部前驱工序完成后方可开始，不允许抢占

工序一旦开始，不允许中断（非抢占调度，Non-preemptive Scheduling）。所有前驱工序完成后，才能为该工序分配设备并启动。

1. 符号说明

符号含义

Q 工序工程量（m³）

v 设备效率（m³/h）

n 参与工序的设备台数

T 工序时长（秒）

d(a,b) 地点a 到地点b 的距离（米）

t_trans(a,b) 设备从地点a 转运至地点b 的时间（秒）

s_j 工序j 的开始时间（秒）

e_j 工序j 的结束时间（秒）

dur_j 工序j 的持续时长（秒）

MS 总完工时间Makespan（秒）

P(j) 工序j 的直接前驱工序集合

x_{ij} 0-1变量，设备i 是否参与工序j

c_{dtype} 设备类型dtype 的单价（元） b_{dtype,team} 决策变量，班组team 新购dtype 类设备台数 B 购置预算上限（元）

1. 数据预处理

本文所用数据来源于题目附件（B-附件.xlsx），包含三个工作表：工序流程表、班组配置表和车间距离表。

设备配置汇总（每班组）：

设备类型	台数	效率（工序相关）	单价（元）
精密灌装机	5台	200 或 350 m³/h	35,000
自动化输送臂	4台	250 或 300 m³/h	50,000
工业清洗机	5台	100 或 250 m³/h	40,000
高速抛光机	1台	100 或 120 m³/h	75,000
自动传感多功能机	1台	100 或 300 m³/h	80,000

工序流程汇总（共27道，含C3-C5展开×3）：

车间	工序编号	工序名称	所需设备类型	工程量(m³)	前驱工序
A	A1	缺陷填补	灌装机+输送臂	300	—
A	A2	表面整平	抛光机+清洗机	500	A1
A	A3	强度检测	传感机	500	A2
B	B1	表面清理	清洗机	120	—
B	B2	垫层构筑	灌装机+输送臂	1500	B1
B	B3	表面密封	灌装机	360	B2
B	B4	表面整平	抛光机+传感机	360	B3
C	C1	旧涂层剥离	清洗机+输送臂	720	—
C	C2	基底填充	灌装机	720	C1
C	C3_1	密封覆盖①	灌装机+输送臂	360	C2

车间	工序编号	工序名称	所需设备类型	工程量(m³)	前驱工序
C	C4_1	表面研磨①	抛光机+清洗机	400	C3_1
C	C5_1	质量检测①	传感机	400	C4_1
C	C3_2	密封覆盖②	灌装机+输送臂	360	C5_1
C	C4_2	表面研磨②	抛光机+清洗机	400	C3_2
C	C5_2	质量检测②	传感机	400	C4_2
C	C3_3	密封覆盖③	灌装机+输送臂	360	C5_2
C	C4_3	表面研磨③	抛光机+清洗机	400	C3_3
C	C5_3	质量检测③	传感机	400	C4_3
D	D1	碎屑清理	清洗机	600	—
D	D2	基底固化	灌装机+输送臂	800	D1
D	D3	表面密封	灌装机	450	D2
D	D4	表面整平	抛光机+传感机	1500	D3
D	D5	承载检测	传感机	1500	D4
D	D6	边缘修整	抛光机	700	D5
E	E1	基础处理	清洗机	1000	—
E	E2	表面密封	灌装机	600	E1
E	E3	稳定性检测	传感机+清洗机	600	E2

三、问题1的建模与求解

1. 问题1的模型建立
  1. 工序时长计算

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

【Matlab】视频行为识别与异常检测算法设计与仿真实现

摘要：本文基于Matlab平台设计了一套视频行为识别与异常检测系统，采用YOLOv8目标检测算法和CNN-LSTM融合模型，实现了对行走、奔跑、跌倒等行为的精准识别。系统通过建立正常行为模型，采用偏差判定方法检测异常事件，并实现分级预警。实验结果表明，该系统行为识别准确率达95%以上，异常检测准确率超过94%，响应时间小于1秒，可满足实时监控需求。Matlab平台为算法开发提供了高效工具，降低了工

AtomGit开源社区

非技术背景的OPC创业者最大误区：以为AI能替你做产品

我见过太多非技术出身的创业者，成也 AI，败也 AI。成，是因为 AI 让他们不用再被技术卡住，快速把想法变成了现实；败，是因为他们误以为 AI 能替自己搞定一切，把产品的控制权，拱手让给了工具。永远记住：AI 应该是你的副驾驶，而不是你的老板。它能帮你踩油门加速，但方向盘，必须牢牢握在你自己手里。而 Zion 无代码，正是帮非技术创业者稳稳握住方向盘的核心载体 —— 不用写一行代码，你就能看清系