非标装配产线具有产品种类多变、工艺路径非固定、任务到达时间随机等典型特征，对多机器人系统的任务分配与实时调度提出了严峻挑战。传统任务分配方法多假设静态确定环境，难以应对实际生产中的设备故障、紧急插单及工时波动等动态事件。本文提出一种面向非标装配产线的双层规划模型，上层为面向全局周期内任务-机器人匹配的整数规划，下层为考虑时间窗与资源约束的作业排序问题。在此基础上，设计基于滚动窗口的动态重调度策略，融合事件驱动与周期触发两种机制，采用改进的带精英策略的非支配排序遗传算法（NSGA-II）与禁忌搜索混合算法进行求解。通过某非标自动化产线实际案例仿真验证，所提方法在任务完成率、平均流程时间及机器人负载均衡度等指标上显著优于固定分配策略和周期性重调度方法，且对动态扰动具有强鲁棒性。
1 引言
随着制造业向“多品种、小批量、定制化”转型，非标自动化装配线在3C电子、汽车零部件、航空航天等领域的应用日益广泛。与标准化流水线不同，非标产线上的产品规格、装配工艺、来料时序均存在高度不确定性，要求生产线具备快速重构与柔顺响应能力。多机器人协作系统因其良好的可扩展性与任务适应性，成为非标装配的主流执行架构。然而，如何为多台异构机器人合理分配不断到达的装配任务，并在扰动发生后实时调整作业计划，是实现产线高效运行的核心难题。
多机器人任务分配（Multi-Robot Task Allocation, MRTA）通常可建模为组合优化问题。现有研究主要分为集中式与分布式两类。集中式方法（如混合整数线性规划、约束规划）在小规模问题中可获取最优解，但计算复杂度随任务数指数增长，难以用于实时调度。分布式方法（如市场机制、拍卖算法）响应快，但容易陷入局部最优，且对全局负载均衡考虑不足。此外，绝大多数研究假设任务参数预先已知且稳定不变，忽略了非标装配中频繁出现的动态事件——包括机器人突发故障、任务取消或加急、装配时间超差等。
针对上述不足，本文提出一种双层规划模型，将长期任务分配与短期作业排序解耦，既兼顾全局优化目标，又保留了对动态扰动的快速响应能力。同时，设计了基于滚动窗口的动态重调度框架，通过事件检测与周期性重优化相结合的方式，实现计划与执行的闭环反馈。
2 问题描述与数学模型
2.1 问题描述
考虑一条非标装配产线，包含 MM 台机器人（记为 R1,R2,…,RMR1,R2,…,RM），机器人之间可能存在功能异构性（例如有的擅长精密压装，有的适合螺钉锁付）。在一段生产周期内，有 NN 个装配任务（记为 J1,J2,…,JNJ1,J2,…,JN）以随机时间间隔到达。每个任务由一系列有序工序组成，但工序执行允许在满足工艺约束的前提下由不同机器人完成（柔性路径）。每个任务有一个发布时刻 rjrj（物料齐套时间）、一个期望完工时间窗 [dj−,dj+][dj−,dj+] 以及一个单位时间延迟惩罚成本 cjcj。机器人一次只能执行一个任务，任务一旦开始执行不可中断（非抢占）。
动态事件类型包括：
机器人故障：某机器人退出服务一段时间，期间其正在执行的任务需转移或等待。
紧急插单：高优先级任务突然到达，需在最短时间内插入执行。
工时偏差：实际装配时间与计划值偏差超过阈值（如±20%）。
目标是在满足工艺约束与资源约束的前提下，最小化总惩罚成本（延迟惩罚+机器人空闲成本+任务切换成本），并兼顾机器人负载均衡。
2.2 双层规划模型
定义决策变量 xij∈{0,1}xij∈{0,1} 表示任务 jj 是否分配给机器人 ii。设任务 jj 对机器人 ii 的“适配度”为 aijaij（由历史数据中该机器人完成任务的平均时间与质量综合计算），机器人 ii 的最大任务容量为 QiQi。上层模型为：max∑i=1M∑j=1Naijxijmaxi=1∑Mj=1∑Naijxijs.t.∑i=1Mxij=1,∀js.t.i=1∑Mxij=1,∀j∑j=1Nxij≤Qi,∀ij=1∑Nxij≤Qi,∀ixij∈{0,1}xij∈{0,1}
上层模型给出每个任务由哪一类机器人执行的最优倾向，但不考虑时间排序。该层本质上是一个分配问题，可采用匈牙利算法或整数规划快速求解。
设机器人 ii 上分配的任务集合为 SiSi，每个任务 jj 有预估加工时间 pijpij（机器人 ii 加工任务 jj 所需时间）。决策变量为 yjki∈{0,1}yjki∈{0,1}（在机器人 ii 上任务 jj 是否在任务 kk 之前执行）以及开始时间 sijsij。
下层目标为最小化加权延迟惩罚与空闲成本之和：min∑i=1M[∑j∈Siωjmax(0,sij+pij−dj+)+γ∑j∈Si(sij−(si,prev(j)+pi,prev(j)))]mini=1∑Mj∈Si∑ωjmax(0,sij+pij−dj+)+γj∈Si∑(sij−(si,prev(j)+pi,prev(j)))
其中 ωjωj 为延迟惩罚系数，γγ 为单位空闲时间成本，prev(j)prev(j) 表示同一机器人上前一个任务。约束包括：
- 同一机器人不能同时执行两个任务：sij+pij≤sik+L(1−yjki)sij+pij≤sik+L(1−yjki) 对所有 j,kj,k。
- 任务发布时间：sij≥rjsij≥rj。
工艺顺序约束（若同一任务的不同工序需固定顺序，由机器人间传递时间体现）。
下层模型是一个带时间窗的并行机调度问题，属于NP-hard，需借助启发式算法求解。
3 动态重调度策略
3.1 滚动窗口框架
采用滚动时域优化（Rolling Horizon）思想，将整个生产时域划分为多个连续的重调度窗口，每个窗口长度为
𝐻
H（例如30分钟）。在每个窗口起点，系统获取当前时刻所有未完成任务的更新信息（包括新到达任务、机器人状态、剩余加工时间等），然后在窗口内求解下层排序模型，确定窗口内任务的执行顺序。窗口末尾的若干时间作为“重叠区”，避免计划断裂。
3.2 双重触发机制
单纯周期重调度响应迟钝，而事件驱动重调度又可能过于频繁。本文采用混合策略：
周期触发：每经过固定时间间隔
Δ𝑇5
ΔT=5 分钟，执行一次重调度。
事件触发：当以下任一事件发生时，立即启动重调度：① 机器人故障或恢复；② 紧急插单到达；③ 实际完工时间与计划偏差超过10%阈值；④ 等待队列长度变化超过30%。
为防止事件触发过于频繁，设置最小重调度间隔
𝑇min1Tmin=1 分钟，连续两次重调度间隔不得低于此值。
3.3 部分任务重分配机制
当机器人故障发生时，被中断任务需要转移至其他空闲机器人。本文设计了一种“能力-负载平衡”迁移策略：首先根据故障机器人上待转移任务的工序要求，筛选出具备该能力的候选机器人集合；然后计算每个候选机器人的当前负载率与预期新增耗时，选择使负载方差增量最小的机器人作为迁移目标。若所有机器人都无法承接，则将该任务标记为“阻塞”，等待故障恢复。
4 求解算法设计
4.1 上层求解方法
上层模型是标准分配问题，任务数𝑁N 通常小于200，采用匈牙利算法𝑂(𝑁3)O(N3) 可在毫秒级完成。对于异构适配度矩阵𝑎𝑖𝑗aij，引入历史成功率和平均装配时间的加权：𝑎𝑖𝑗𝛽⋅successRate𝑖𝑗+(1−𝛽)⋅min𝑘𝑝ˉ𝑘𝑗𝑝ˉ𝑖𝑗aij=β⋅successRateij+(1−β)⋅pˉijmink
pˉkj其中𝛽0.6β=0.6，𝑝ˉ𝑖𝑗pˉij为历史平均加工时间。
4.2 下层混合遗传算法
由于下层调度问题为多目标（延迟最小+负载均衡），采用带精英策略的NSGA-II结合禁忌搜索（TS）进行局部增强。
编码方式：采用基于任务排列的编码。对于每个机器人，将其分配的任务序列排列成一个染色体。多个机器人的序列拼接形成整体染色体。为保证可行性，违反发布时间约束的个体通过惩罚项处理。
交叉算子：针对多机器人问题，设计“顺序保留交叉（Order Crossover, OX）”并在机器人之间交换子任务块，以增加多样性。
局部搜索：在遗传算法每代结束后，对Pareto前沿上的个体进行禁忌搜索。邻域动作包括：交换同一机器人上相邻两个任务的位置、将某任务移动到另一机器人的合适位置（需满足能力约束）。禁忌表长度为15，迭代步数20。
适应度函数：采用Pareto非支配排序并计算拥挤距离。目标函数有两个：① 加权延迟惩罚总和；② 最大机器人负载与最小负载之差（负载均衡度）。最终选择拥挤距离最大的前沿个体作为下一代父代。
4.3 动态更新策略
在每个重调度点，保留已分配但未开始的任务、已开始但未完成的任务（更新剩余时间），并加入新到达任务。使用“右移位”策略快速修复：若原计划因扰动不可行，则保留任务顺序，将开始时间推后至满足约束的最小值。若右移位后仍不可行（超出时间窗较多），则调用混合遗传算法完全重排。
5 仿真实验与结果分析
5.1 实验场景设置
参照某非标自动化产线实际参数：机器人数量𝑀6
M=6（其中2台通用装配机器人，2台精密压装机器人，2台检测机器人）；任务总数𝑁120
N=120，到达过程服从泊松分布（平均间隔2分钟）。每个任务包含2-4道工序，工序顺序有向无环。任务发布时间随机在0-30分钟之间。加工时间服从三角分布（最小值、众数、最大值）。动态事件注入：设两个机器人分别在运行第45分钟和第78分钟发生故障，各持续5分钟和8分钟；在第60分钟注入一个紧急任务（优先级最高，惩罚系数为普通任务5倍）。
对比策略：
策略A（静态分配+无重调度）：开始时一次性分配所有已知任务，执行中不调整。
策略B（周期性重调度）：每5分钟重调度一次，不触发事件重调度。
策略C（事件驱动重调度）：仅事件触发，无周期重调度。
策略D（本文方法）：周期+事件混合，滚动窗口，部分迁移。
5.2 实验结果
蒙特卡洛仿真20次取均值，结果如下：
策略 平均延迟时间(min) 紧急任务完成时间(min) 机器人负载均衡指数 重调度次数
A 28.4 未插队，排在原队列后 0.742 1
B 13.7 9.2 0.851 28
C 11.2 6.1 0.823 11
D 9.3 4.8 0.904 19
策略D相比策略B，平均延迟时间降低32.1%，相比策略C负载均衡度提升9.8%。原因在于：单纯事件驱动策略（C）在无事件时长期不更新计划，导致累积偏差；而单纯周期策略（B）响应故障等突然事件存在滞后。混合策略既能及时捕捉异常，又能周期性优化，且通过部分重分配避免了频繁全局重排带来的计算负担。
针对故障机器人的任务迁移，本文的“能力-负载平衡”策略使得迁移后六台机器人负载方差仅为0.051，而随机迁移方差为0.174，证明负载均衡效果显著。
5.3 算法效率分析
混合遗传算法在典型窗口（任务数约25）的平均求解时间为2.3秒（Intel i7-10750H，MATLAB R2022a），远小于5分钟的周期间隔，满足实时性要求。禁忌搜索的引入将NSGA-II的Pareto前沿质量提升了约15%，但增加了0.8秒耗时，属于可接受开销。
6 结论
本文针对非标装配产线中多机器人任务分配与动态调度问题，建立了双层规划模型，提出基于滚动窗口与双重触发机制的重调度策略，并设计了混合遗传-禁忌搜索求解算法。仿真结果表明，该方法在动态环境下能够显著提升任务准时率和机器人负载均衡度，且计算效率满足工程实时要求。未来工作将扩展到多产线协同与考虑装配质量反馈的自适应调度，进一步引入强化学习以取代部分规则决策。
中研高科教育
