2026年数学建模国赛B题算法（35）：基于混合整数规划与增强Benders分解的作业车间/流水车间调度问题研究

摘要作业车间调度问题（Job-Shop Scheduling Problem, JSP）与流水车间调度问题（Flow-Shop Scheduling Problem, FSP）作为组合优化领域的经典难题，在智能制造、半导体制造、航空装配等高端制造场景中具有广泛的应用背景。本文以最小化最大完工时间（Makespan）为目标，系统建立了JSP/FSP的统一混合整数规划（Mixed Integer Programming, MIP）模型，提出了一种融合Benders分解、Lazy约束生成与局部搜索增强的精确求解框架。针对JSP的析取图结构和FSP的置换特性，本文分别建立了面向一般JSP的析取MIP模型和面向置换FSP的改进MIP模型，并设计了面向大规模实例的分解协调算法。在OR-Library标准算例上的数值实验表明，本文提出的增强Benders分解算法在中等规模算例上可实现平均37.5%的求解时间缩减，在较大规模算例上可在1800秒内获得平均偏差小于2.8%的高质量可行解。本文还进一步探讨了模型在动态扰动场景下的鲁棒性扩展，为实际生产调度决策提供了系统化的方法论支撑。关键词：作业车间调度；流水车间调度；混合整数规划；Benders分解；Lazy约束生成；析取图模型目录摘要1. 引言1.1 研究背景与意义1.2 文献综述1.3 本文工作与贡献2. 问题描述与符号系统2.1 基本假设2.2 索引集合与参数2.3 析取图与调度表示3. 混合整数规划模型3.1 JSP的析取MIP模型3.2 FSP的MIP模型3.3 两种模型的结构对比与统一框架4. 增强Benders分解算法4.1 Benders分解的基本原理4.2 增强策略1：Pareto-最优割生成4.3 增强策略2：Lazy约束池与回切4.4 增强策略3：局部搜索增强4.5 算法流程与收敛性分析5. 数值实验5.1 实验设置5.2 JSP算例结果5.3 FSP算例结果5.4 参数灵敏度分析6. 动态场景扩展6.1 带机器故障的鲁棒调度模型6.2 动态重调度的滚动时域框架1. 引言1.1 研究背景与意义当前全球制造业正经历从大规模标准化生产向多品种、小批量、定制化生产的深刻转型。在这一背景下，生产调度作为制造执行系统（Manufacturing Execution System, MES）的核心决策模块，其优化水平直接决定了设备利用率、订单交付周期和企业响应速度。作业车间调度问题（JSP）与流水车间调度问题（FSP）作为生产调度理论中最基本的两类模型，自上世纪五十年代以来一直是运筹学与管理科学领域的研究热点（Johnson, 1954; Fisher, 1963）。JSP描述的是这样一类场景：有 n 个工件需要在 m 台机器上加工，每个工件包含 m 道工序，各工序按照预先给定的工艺顺序在指定的机器上加工，且每台机器在同一时刻只能加工一个工序。FSP则是JSP的一种特殊但同样重要的情形：所有工件的加工路径完全相同，即都依次经过机器1,2,...,m。这两种模型虽然结构迥异，但共同构成了现代调度理论的两大支柱。从计算复杂性角度看，JSP是强NP-难的（Garey et al., 1976），即便对于 m=3 的情形也已是NP-难；FSP在 m≥3 时同样是NP-难的。这意味着不存在多项式时间的精确算