链上镖师 / Chain Biaoshi
EJOR|电池装配线的产品运输与物料补给：AGV-AMR联合调度
在拉式无缓冲产线上，用MILP与数学启发式协调装配、运输和补料
论文把装配、AGV产品运输和AMR物料补给放入同一张时间表，并用MILP与数学启发式降低拉式电池装配线的整体完工时间。
- 01：决策同时覆盖AGV与AMR任务分配、机器人任务排序和工位作业时间。
- 02：真实电池示范线案例中，最优完工时间由2638.67秒降至1641.80秒。
- 03：数学启发式结合迭代局部搜索、线性规划和约束缩减MILP。
- 04：大规模实例中，数学启发式相对当前实践的完工时间改善幅度为15%至35%。
一条装配线为何需要三类任务同步
论文研究拉式流水装配环境中的三类相互依赖任务：工位执行装配，AGV在准备工位、装配工位和成品仓库之间运输产品，AMR从物料仓库向工位补给物料。系统没有工位间缓冲区，产品只有在下游工位可用时才能继续移动，运输、补料与装配的时间关系会直接决定全部作业的完工时间。
物料补给载具与AGV产品运输方式，来源：Fig. 1
车间布局及AGV、AMR运行区域，来源：Fig. 2
01AGV决策：运输任务分配、任务顺序、装卸和行驶时间。
02AMR决策：补给任务分配、补给顺序、满载与空载行程。
03工位决策：装配开始时间、完成时间和产品进入顺序。
04统一目标：最小化最后一个产品进入成品仓库的时间。
补料策略如何进入调度约束
论文区分周期补给和连续补给。周期补给采用拖车，一次补充可服务多个作业，库存降至最低水平时触发任务，并恢复到最高库存水平。连续补给采用料箱车，每次配送服务一个作业，工位可设置多个停车位。两类策略都要求物料在对应产品到达工位前就位。
周期补给与连续补给的工位运行机制，来源：Fig. 3
阶段 1 工位库存或空位状态触发AMR补给任务
阶段 2 AMR从物料仓库装载并驶向指定工位
阶段 3 产品由AGV从上游工位运往同一工位
阶段 4 产品和所需物料到位后启动装配
阶段 5 装配完成且下游工位空闲时启动下一段运输
拉式规则把工位占用、产品运输和物料到达锁定在同一条时间链上。任一环节提前或延迟，都可能形成机器人等待、工位闲置或后续作业推迟。
从精确模型到可扩展数学启发式
MILP以最小完工时间为目标，变量描述AGV和AMR的任务分配、同一机器人上的任务先后关系，以及装配、运输和补给任务的起止时间。约束同时处理工艺顺序、机器人任务互斥、装卸与行驶时间、拉式无缓冲规则、两种补给策略和对称解消除。
ILS、LP与R-MILP组成的数学启发式主流程，来源：Algorithm 1 Matheuristic
1构造式启发算法生成初始AGV任务分配与顺序
2局部搜索交换或插入AGV运输任务
3LP快速计算候选方案的任务时间表
4扰动操作扩大搜索范围并跳出局部最优
5达到计算时限后由R-MILP补全AMR调度
数学启发式参数测试范围与最终取值，来源：Table 2
最终参数取容差阈值0.10、邻域规模4、最大扰动次数10。实验分别采用600秒和7200秒停止时限，并对随机算法执行10次独立运行。
电池示范线怎样落到一张联合时间表
工业案例来自VDL Nedcar电池示范线，共有一个准备工位和六个装配工位。AGV负责产品在各工位及成品仓库之间的移动，AMR负责物料配送。工位20和50使用连续补给，工位10和30使用周期补给，论文依据真实加工时间、位置间运输时间和机器人活动区域构造实验实例。
电池示范线的工位与机器人运行布局，来源：Fig. 10
示例一的装配、产品运输与物料补给联合时间表，来源：Fig. 5
联合时间表同时记录工位装配、AGV载货与空驶、AMR补给与空驶。产品到达、物料就位和工位释放被安排在统一时间轴上。
真实案例的完工时间降到1641.80秒
当前实践的完工时间为2638.67秒。MILP在600秒和7200秒时限下都于4秒内找到1641.80秒的最优解，改善37.78%。数学启发式在600秒时限下得到1687.10秒，距离MILP最优解约2%；时限延长至7200秒后，同样达到1641.80秒。
电池示范线案例的求解结果与当前实践差距，来源：Table 5
当前实践完工时间
2638.67秒
联合调度最优完工时间
1641.80秒
三个作业、一台AGV和一台AMR的最优调度，来源：Fig. 12
最优解中，作业1在工位10完成后，AGV 1等待合适的发车时点，使产品与AMR 1配送的物料同时抵达工位20，装配任务随即开始。
作业规模、车队配置与多线扩产
大规模实验改变作业数、AGV数量、AMR数量和装配线数量。600秒内，MILP在全部八作业实例及一个六作业实例中未找到可行解，数学启发式为全部实例生成方案，其中三分之一达到最优。7200秒时，数学启发式在一半实例中达到最优，其余实例与MILP的完工时间差距均小于3%。
不同车队与作业规模下的大实例求解结果，来源：Table 6
单线与多线生产场景的算法结果，来源：Table 7
资源配置及一体化调度对系统表现的影响，来源：Fig. 13
数学启发式在大实例中相对当前实践改善15%至35%，平均约27%。多线扩产时，有限的AGV数量可能形成瓶颈并增加跨线行驶；ILS方案在600秒和7200秒实验中均显著优于VNS，Wilcoxon检验的p值均小于0.001。
模型适用条件与研究边界
研究结论适用于论文设定的拉式流水装配系统：作业按固定工位顺序加工，工位之间没有产品缓冲区，AGV与AMR在限定区域运行，物料采用周期补给或连续补给。实证基础是电池示范线及其扩展实例，计算结果受车队规模、作业规模、装配线数量和求解时限共同影响。
✓已覆盖：AGV产品运输、AMR物料补给与工位装配的同步调度。
✓已覆盖：单线和多线、不同作业数量及不同机器人车队规模。
✓计算条件：Gurobi 11.0.1、Python 3.12.3，停止时限为600秒或7200秒。
✓论文未报告：实时订单插入、机器人故障、动态拥堵和随机加工时间下的结果。
✓论文未报告：研究方法向非流水车间或具有中间缓冲区系统的直接外推效果。
扩充装配线需要同步检查AGV运输能力。实验显示，第二条装配线带来的加工能力可能受AGV行驶时间限制，车队规模应与产线数量共同配置。
论文：A matheuristic for integrated scheduling of manufacturing assembly, product transport, and material supply
作者：Bilgenur Erdogan，Quang-Vinh Dang，Mehrdad Mohammadi，Ivo Adan
期刊：European Journal of Operational Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
