分布式车间调度

1. 领域概念

分布式车间调度（Distributed Shop Scheduling, DSS）关注的是：在多个地理上分散的工厂之间分配工件，并在各工厂内部进一步完成机器分配与排序，以优化一个或多个生产指标。

相较于传统单车间调度，这类问题多了一层跨工厂分配决策，因此通常要同时解决：

• 工件分配到哪个工厂
• 工厂内分配到哪台机器
• 机器上的工件或工序如何排序
• 多工厂之间如何协调整体目标与局部目标

2. 问题分类

2.1 分布式并行机调度

特点：

• 每个工件通常只有一道工序
• 可分配到任一工厂中的某台并行机加工

核心决策：

• 工件分配到哪个工厂
• 工厂内分配到哪台机器
• 每台机器上的加工顺序

说明：

• 是结构最简单的一类
• 研究相对较少
• 当前多集中在标准、同构、约束较少的情形
• 适合往异构工厂、复杂约束方向扩展

2.2 分布式流水车间调度

特点：

• 每个工件都按相同工艺阶段顺序加工
• 每个工厂对应一个流水车间

（1）分布式置换流水车间

特点：

• 各机器上的工件顺序一致
• 每个工件在同一工厂内完成全部工序

说明：

• 最经典
• 文献最多
• 是很多算法论文的标准测试模型

（2）分布式混合流水车间

特点：

• 至少一个阶段存在并行机
• 除工厂分配和排序外，还需做机器选择

说明：

• 比置换流水车间更复杂
• 很适合做多目标、节能、鲁棒等扩展研究

（3）分布式装配流水车间

特点：

• 前段为分布式流水加工
• 后段进入装配阶段
• 需要考虑部件齐套与装配同步

说明：

• 文献相对较少
• 有较强工程背景
• 是较值得挖掘的方向

2.3 分布式作业车间调度

特点：

• 每个工厂都是一个作业车间
• 不同工件的工艺路径可能不同

核心决策：

• 工件分配到哪个工厂
• 各工序分配到哪台机器
• 各机器上的加工顺序

说明：

• 工艺路径不统一
• 比流水车间更灵活，也更难求解
• 适合研究动态调度、多目标和鲁棒优化

2.4 分布式装配车间调度

特点：

• 包含加工阶段和装配阶段
• 最终产品由多个零部件装配形成

研究重点：

• 零部件加工与装配的协同
• 装配同步关系
• 产品层级结构
• 装配资源约束

说明：

• 更贴近真实制造场景
• 文献量少于流水车间和作业车间
• 但问题本身很有研究价值

2.5 分布式柔性车间调度

特点：

• 一个操作可由多台候选机器加工
• 同时涉及工厂分配、机器选择和工序排序

说明：

• 决策层次多
• 搜索空间大
• 很适合与强化学习、多智能体方法结合

2.6 其他扩展方向

（1）异构多类型车间

特点：

• 不同工厂不再是同一种车间结构
• 可能同时包含流水车间、作业车间、柔性车间等

意义：

• 更符合真实制造系统
• 当前研究仍不充分

（2）动态/不确定分布式调度

常见扰动：

• 紧急订单插入
• 订单取消
• 机器故障
• 维护停机
• 物流扰动
• 交期变化

意义：

• 是当前很重要的扩展方向
• 适合与鲁棒优化、在线调度、学习方法结合

3. 各类问题的横向差异

可以从两条主线理解不同问题的差别。

3.1 工艺结构复杂度

并行机 < 流水车间 < 混合流水/装配流水 < 作业车间 < 柔性车间

3.2 决策层级复杂度

仅排序 → 排序 + 机器选择 → 排序 + 机器选择 + 路径差异 → 再叠加工厂分配

简要理解：

• 分布式并行机：结构最简单，适合基础模型
• 分布式流水车间：研究最成熟，最适合建立基准
• 分布式混合流水车间：复杂度更高，适合做扩展
• 分布式作业车间：路径不统一，搜索难度大
• 分布式装配类：增加同步与层级关系
• 分布式柔性车间：自由度最高，适合智能方法

4. 常见优化目标

分布式车间调度的优化目标已经不再局限于传统单车间调度中常见的“最小化最大完工时间”。在分布式制造环境下，调度不仅要关注加工效率，还要兼顾跨工厂资源配置、运输协同、能耗排放以及实际运营成本等因素。已有综述通常将相关目标概括为经济效益、环境效益和社会效益三类；如果从调度建模的角度来看，也可以进一步归纳为时间类、成本与资源类、绿色制造类以及鲁棒与系统性能类目标。

4.1 时间类目标

时间类目标是分布式车间调度中最基础、最常见的一类，核心仍然是追求生产节拍更紧凑、订单完成更及时。

• 最小化最大完工时间
• 最小化总完工时间
• 最小化总流经时间
• 最小化总拖期
• 最小化加权拖期
• 最小化提前/拖期惩罚

具体来说，最小化最大完工时间反映的是整个系统完成全部任务所需的总周期，是最经典的效率型目标；总完工时间和总流经时间更强调全部工件在系统中的平均滞留水平；而总拖期、加权拖期、提前/拖期惩罚则更贴近交货期管理，适合刻画客户订单满意度、违约风险与交付稳定性。

在分布式场景下，这类目标比单车间更复杂。原因在于工件不仅要排机器，还要先分配工厂，甚至还涉及运输和装配阶段，因此“时间”不再只是加工时间本身，而可能包含加工、等待、运输、装配等多个环节。

4.2 成本与资源类目标

分布式制造天然带有“多工厂、多资源、多地点”的特点，因此成本与资源类目标比传统单车间场景更重要。

• 最小化总加工成本
• 最小化运输成本
• 最小化物流成本
• 最小化维护成本
• 机器负载均衡
• 工厂负载均衡

其中，总加工成本反映的是设备、人工、工艺等直接生产成本；运输成本和物流成本则是分布式场景中特有的重要因素，因为工件或零部件可能需要在不同工厂、车间乃至装配环节之间流动；维护成本往往与设备老化、预防性维护和停机计划相关。

相比之下，机器负载均衡和工厂负载均衡虽然不一定直接表现为货币成本，但本质上同样属于资源利用目标。它们强调不要让某些工厂或机器过载、另一些资源闲置，从而提高整体制造系统的协调性与稳定性。

4.3 绿色制造类目标

随着绿色制造和低碳制造的发展，分布式车间调度研究越来越重视环境效益。相关综述表明，能耗、碳排放和能源成本已经成为近年来的重要优化指标。:contentReference[oaicite:3]

• 最小化能耗
• 最小化碳排放
• 最小化能源成本

这类目标的引入，使调度问题从“单纯追求快”转向“快且绿色”。例如，某些调度方案虽然能缩短完工时间，但可能导致高峰时段集中用电、设备频繁启停或高能耗工厂过度使用，最终并不适合实际应用。因此在分布式环境下，常常需要同时权衡工期和能耗，或者同时优化完工时间、总成本和总碳排放。

4.4 鲁棒与系统性能类目标

当分布式车间调度进一步走向真实制造场景时，仅关注静态效率往往不够，还需要考虑系统对扰动的承受能力和恢复能力。

• 最大化鲁棒性
• 最大化稳定性
• 提升系统韧性
• 提升对扰动的恢复能力

这里的鲁棒性通常指调度方案在加工时间波动、订单变化、机器故障等扰动下仍能保持较好性能；稳定性强调计划执行前后变化不要过大，避免频繁重排；系统韧性则更偏向系统层面，关注分布式制造在面对外部和内部不确定事件时的持续运行能力。

这类目标在动态调度、不确定调度和多目标调度中尤其重要。王思涵等的综述也特别提到，分布式制造模式下需求、物流、临时加单、撤单和机器故障等不确定事件会带来局部或全局影响，因此未来需要从系统韧性的角度来考虑问题。

5. 常见约束与复杂工况

在分布式车间调度中，约束不仅用于保证解的可行性，更重要的是刻画实际生产环境的特征。已有综述指出，当前研究中最常见的特殊约束主要包括模糊、阻塞、有限缓冲区、零等待、零空闲和序列相关准备时间等；此外，还存在可重入、多处理器、批处理以及维护、运输等更复杂的扩展工况。

5.1 经典特殊约束

（1）零等待

零等待约束要求工件在相邻工序之间不能等待，即上一道工序一完成，下一道工序必须立即开始加工。

这类约束常见于对温度、化学反应状态或连续性要求较高的生产场景。它会显著压缩可行调度空间，因为调度时不仅要保证机器可用，还要确保相邻工序之间的时间无缝衔接。对于分布式场景而言，零等待还会进一步影响工厂分配，因为不同工厂的节拍匹配程度不同。

（2）零空闲

零空闲约束要求机器一旦开始加工，就必须连续完成分配给它的全部工件，中间不允许出现空闲。

这类约束常见于不允许频繁停机的设备或工艺过程，例如某些连续加工设备、印刷设备或特定芯片制造工艺。相比普通调度，零空闲约束更强调机器连续运行，因此会明显影响工件排序结构。在分布式环境下，它往往会和节能目标一起出现，因为连续运行既可能提高效率，也可能改变能耗分布。

（3）阻塞

阻塞约束是指当前工序完成后，如果下游机器尚不可用且系统中又没有足够缓冲空间，工件就必须滞留在当前机器上，从而占用该机器，影响后续工件加工。

阻塞现象在无缓冲或缓冲极小的流水型系统中十分常见。它会使“机器完成加工”不等于“机器立即释放”，从而增加调度耦合性。对于分布式流水车间和装配型问题来说，阻塞往往会引发级联效应，使局部延迟扩散为全局延迟。

（4）有限缓冲区

有限缓冲区约束是阻塞问题的一个重要来源，指相邻工序之间的中间存储空间容量受限。

当缓冲区未满时，工件可以暂时离开当前机器进入等待区；当缓冲区满时，当前机器就可能被迫阻塞。该约束特别适合描述空间受限的车间环境，也常与装配、运输和动态调度问题结合出现。相比“无穷缓冲”假设，它更贴近真实生产线。

（5）序列相关准备时间

序列相关准备时间是指机器在加工不同工件之间需要进行切换准备，而准备时间长度依赖于前后工件的加工顺序。

例如印刷行业中，不同油墨颜色、纸张规格或工艺设置之间的切换时间往往不同；前后工件排列不同，准备时间也会随之变化。该约束会使“排序本身”直接影响加工代价，因此不能再简单把准备时间看作常数。在分布式场景下，这种约束还会与车间异构性、运输时间和能耗目标共同作用。

（6）模糊/不确定加工信息

模糊约束通常指加工时间、完成时间、交期或其他关键参数并非确定值，而是存在模糊性或不确定性。

这类情况常来源于设备状态波动、人工操作差异、来料不稳定或缺乏精确历史数据。与确定性模型相比，模糊模型更强调方案在信息不完全条件下的适用性，也更容易与鲁棒优化、协同进化和学习方法结合。

5.2 更贴近实际的约束

除上述几类经典特殊约束外，近年来综述中还提到了一批更贴近工程实际的复杂工况，它们往往是未来研究的重要增长点。

• 设备维护
  指需要将预防性维护、检修窗口或设备老化效应纳入调度决策。设备并非始终可用，维护计划会直接影响加工顺序和资源分配。

• 机器故障
  属于典型动态扰动。机器故障会打断既定调度方案，迫使系统重新分配任务或进行局部重调度。

• 能力退化
  指设备随着使用时间增长，效率、精度或可用性逐渐下降。这类因素会使加工时间或加工质量随时间变化，更贴近真实制造过程。

• 工人轮班
  某些生产场景中，机器是否可用不仅取决于设备本身，也取决于操作人员是否在岗，因此轮班制度会成为重要约束。

• 交通与物流限制
  分布式制造中工件可能跨工厂流动，因此运输时间、运输能力、路线条件和配送时窗等都会影响调度结果。

• 原材料约束
  原材料的到货时间、库存水平和供应能力会限制工件开工时刻，特别是在多工厂协同生产中影响更明显。

• 订单绑定约束
  指同一订单下的工件需要在同一工厂或同一类车间中加工，以减少运输、装配或协调成本。

• 多处理器约束
  某些工序需要多台设备或多类资源同时参与加工，这会使资源协调更加复杂。

• 批处理约束
  指多个工件需要以批的形式共同进入某道工序加工。此时，调度对象不再只是单个工件，还要确定分批与批排序方案。

• 可重入约束
  指工件在加工过程中会重复访问同一道工序或同一类设备，这类问题常见于半导体、热处理等复杂制造过程。

总体来看，经典约束主要回答“调度是否可行”，而这些更贴近实际的复杂工况则更多回答“模型是否真实”。从现有综述看，分布式调度研究虽然已经覆盖了零等待、零空闲、阻塞、模糊和准备时间等典型约束，但对工人轮班、交通限制、复杂物流和更多实际工况的研究仍然相对较少。

6. 主要求解方法

6.1 精确方法

常见：

• 混合整数规划
• 分支定界
• 数学规划求解器

特点：

• 适合小规模问题
• 能提供最优解或下界
• 规模稍大时计算困难

6.2 启发式方法

特点：

• 规则驱动
• 求解速度快
• 适合快速构造可行解

不足：

• 解质量依赖规则设计
• 通用性有限

6.3 元启发式方法

常见：

• 遗传算法
• 迭代贪婪
• 变邻域搜索
• 人工蜂群
• 分布估计算法
• 果蝇算法
• 鲸鱼优化
• Memetic 算法

特点：

• 是当前主流方法
• 适合中大规模问题
• 常与问题特定编码和解码结合

6.4 混合方法

特点：

• 将启发式、元启发式、局部搜索等结合
• 能兼顾全局搜索和局部开发
• 是当前较有效的一条路线

6.5 学习型方法

常见：

• Q-learning
• 强化学习
• 多智能体强化学习

特点：

• 适合动态、在线和不确定环境
• 与分布式调度的多决策主体结构较契合
• 目前仍属于较新的研究方向