一种用于分布式作业车间调度问题的改进图形方法

《European Journal of Operational Research》：An Enhanced Graphical Method for Distributed Job Shop Scheduling Problems

　　

• •
  所提出的图形化方法克服了两阶段DJSP调度框架的局限性。
• •
  该图形化方法通过双向移动扩展，从而能够探索更丰富的邻域空间。
• •
  基于非支配排序的分层路径规划算法提升了路径搜索效率。
• •
  EGM在210个Taillard基准实例上取得了71项新的最佳结果。

引言

现代制造业面临着双重挑战：日益个性化的客户需求以及不断加剧的市场波动。传统的集中式生产模式往往存在资源分配僵化、反应速度慢等问题，难以适应快速变化的环境需求（Behnamian & Fatemi Ghomi, 2016）。为此，分布式制造被作为一种有效的替代方案提出：通过协调地理位置分散的工厂进行生产，不仅可以缩短供应链响应时间，还能优化空间资源分配，进而降低运输能耗和运营风险。然而，分布式制造的兴起也为调度研究带来了新的挑战。其中，分布式作业车间调度问题（DJSP）就是一个典型且复杂的难题。DJSP指的是将个任务分配到f个工厂”的问题，它涉及两个相互关联的调度决策：一是决定将任务分配到哪个工厂，二是确定每个工厂内的任务执行顺序，后者实际上就是经典的作业车间调度问题（JSP）。尽管关于JSP已有较为成熟的研究成果，但针对如何有效分配任务到各工厂并实现两阶段协同优化的研究仍然有限，仍有很大的改进空间。

现有关于任务到工厂分配的研究大致可分为三类。第一类是静态分配策略，比如?ahman（2021）提出的负载均衡方法，该方法在初始解构建时就将任务固定分配到特定工厂，一旦分配就无法调整，使得算法只能得到单一的固定分配组合。第二类是在搜索过程中采用动态分配策略，例如Chaouch等人（2019）将任务分配机制融入蚁群优化算法中，动态地将一些任务分配给当前负载最低的工厂。虽然这种方法提高了适应性，但其单一规则的分配策略往往会导致局部最优解的产生。第三类则是基于进化运算的分配策略，比如Xie等人（2024）在遗传算法中引入了工厂层面的交叉和变异操作，使得每次迭代都能随机重新分配任务。尽管这种方法增强了分配的多样性，但它会破坏编码结构，还需要频繁重新调度，从而降低了算法的整体效率。

目前大多数方法都采用分层的两步流程：先确定任务分配到哪些工厂，然后再生成详细的车间调度计划。这种处理方式将任务分配和调度视为两个相对独立的子问题，两者之间的耦合度或反馈机制十分有限。尤其是在任务分配阶段，往往缺乏关于任务插入位置的指导，这使得很难得到高质量的调度方案。为了解决这些局限，我们提出了一种基于图形化方法的两阶段协同优化机制（Gon?alves & Resende, 2014）。这种结构化的插入方法能够动态引导任务进入目标工厂，将任务分配和调度过程深度整合在一起，从而提升算法性能和整体调度效果。

图形化方法（GM）最初是由Akers为解决两任务作业车间调度问题而提出的（Akers, 1956）。在此基础上，Gon?alves和Resende将GM扩展到多任务场景，并在57个基准实例上取得了更好的最优解结果（Gon?alves & Resende, 2014）。GM包含两个核心步骤：分解和重构。在分解阶段，通过删除部分任务并对剩余任务进行左移操作来缩短任务完成时间。而在重构阶段，则会构建障碍图，然后通过搜索最短路径（P_min），再根据解码规则来确定任务的重新插入位置，从而实现任务级别的邻域搜索。不过，最短路径搜索过程耗时较长，成为了限制GM实际应用效率的主要瓶颈。

为了提高GM的调度效率，本文扩大了其邻域搜索空间，并引入了一种高效的路径规划算法。在这些改进的基础上，我们进一步开发出了改进型的GM框架，用以更有效地解决DJSP问题。本研究的主要贡献如下：

• (1)
  我们提出了一种带有双向移动功能的GM模型，通过左移和右移操作来安排剩余任务，从而大幅扩展了邻域解空间。
• (2)
  为提升GM的搜索效率，我们开发了一种基于非支配排序的分层路径规划算法，可快速找到最短路径P_min。
• (3)
  针对DJSP问题，我们提出了改进型图形化方法（EGM）。EGM首先通过图形化调度方法构建高质量的初始解，然后运用三种基于GM的邻域结构实现任务在工厂间的动态重新分配，最后通过动态禁忌搜索进行局部优化，进一步提升解决方案的质量。
• (4)
  所提出的方法在210个Taillard基准实例上进行了测试，并与四种现有的先进算法进行了比较。实验结果表明，EGM在最优解质量和计算效率方面都具有更优的表现。

章节节选

DJSP研究的进展

DJSP源自经典的JSP问题，主要研究多工厂协作生产中的流程优化问题。自从Jia等人（2002）首次提出DJSP问题以来，这一领域的研究趋势一直是算法多样化以及问题复杂度的不断提升。表1总结了过去十年间DJSP研究的发展状况。现有的方法大致可分为精确求解法和近似求解法两类。最近的进展表明，现代约束编程技术

问题描述

分布式作业车间调度问题（DJSP）指的是将一组任务J={1, 2, ..., n}分配到多个工厂的问题，每个工厂独立运作，可视为一个独立的JSP问题。每项任务都由一系列操作组成，这些操作必须按照指定顺序在相应的机器上进行处理，而且同一项任务的所有操作都必须在同一个分配到的工厂内完成。在任何时刻，一台机器只能处理一个操作，且一旦开始运行就必须持续不停。

从两任务调度到多任务调度

Akers（1956）率先使用GM方法来解决两任务JSP问题。以表3中工厂1里的任务J₁和J₂为例，图2a展示了GM模型，该模型的横轴和纵轴分别代表J₁和J₂。在模型中，如果横轴上的某个操作和纵轴上的某个操作需要在同一台机器上执行，那么对应的矩形区域就会变得不可行，从而形成一块矩形障碍区域。我们将整个坐标系以及这些

算法框架

在前文中，我们已经为图形化方法设计了两种改进策略：其一是通过引入GM-BS机制来扩大邻域搜索空间；其二则是开发LPP-NS算法以提高路径搜索效率。在此基础上，本文进一步提出了一种改进型图形化方法（EGM），用于解决DJSP问题。所提出的EGM包括四个关键组成部分，分别是初始解的构建、基于图形化方法的图形搜索

实验测试

在本节中，我们设计了三组实验来评估EGM的性能。第一组实验用于参数调优，第二组用于验证混合策略的有效性，第三组则用于测试EGM的实际性能。实验所使用的测试实例均为Taillard（Taillard, 1993）提出的210个知名基准实例。所有算法均基于MATLAB 2023b实现，并在配备3.4 GHz CPU和32 GB RAM的工作站上运行。

结论

分布式制造已成为大型企业广泛采用的生产模式，而分布式调度问题至今仍属于处于探索初期的核心挑战之一。在本研究中，我们研究了DJSP问题，并提出了一种改进型图形化方法（EGM）。大量的实验结果证明了所提出方法的优越性能。本研究的主要贡献如下：

• (1)
  提出了一种基于双向移动的图形化方法（GM-BS）。在

数据获取途径

本研究中所使用的基准实例以及详细的计算结果均可在以下地址公开获取：https://github.com/jobshop2025/DJSP2026/tree/main/DJSP2026

作者贡献

黄林：概念设计、方法论构建、数据整理、原文撰写与编辑。唐敦兵：监督指导、论文审阅及资金筹集。刘长春：论文审阅与编辑。张泽群：资金筹集。朱海华：资金筹集。

未引用参考文献

Heinz, Vilím和Hanzálek，2025；Huang, Wang和Zhao，2026；Li等人，2022；Rohaninejad, Vahedi-Nouri, Hanzálek和Tavakkoli-Moghaddam，2024

CRediT作者贡献说明

黄林：论文审阅与编辑、原文撰写、方法论构建、数据整理、概念设计。唐敦兵：论文审阅与编辑、监督指导、资金筹集。张泽群：资金筹集。朱海华：资金筹集。刘长春：论文审阅与编辑。

黄林|唐敦兵|张泽群|朱海华|刘长春