作业车间调度问题求解框架¶

发布于：2021-08-08 | 分类：optimization , mathematics

---

组合优化问题广泛出现于各行各业，例如生产制造排程，机场航班调度、项目管理计划等，求解这类问题有助于解决实际应用中的调度难题、提高生产效率；考虑到实际的业务逻辑因行业而异且可能相当复杂，本系列文章针对调度类问题的基本模型——作业车间调度（Job Shop Schedule），基于Python开发了一个通用的求解框架：

• 参考文献实现了一些基本解法例如基于规则指派、局部搜索、群体方法等

• 便于快速实施和测试新算法（参考 Python建模）

项目仓库¶

https://github.com/dothinking/jsp_framework

建模¶

作业车间调度问题通常有两类描述方式：

• 以工序开始时间为规划变量的线性规划数学模型

• 以工序顺序（作业工序顺序和机器工序顺序）为基础的析取图描述

本节从这两种描述入手认识作业车间调度问题，并基于此设计了整个求解框架，把问题分解、抽象为可重用的部分，从而专注求解算法的开发、实施和验证。

• 问题描述

• Python建模

• 基于matplotlib的动态甘特图

求解¶

作业车间调度问题通常有两类解法：

• 精确解法例如线性规划、动态规划、分枝定界等

• 近似解法例如局部搜索（禁忌搜索、模拟退火等）、群体算法（遗传算法、蚁群、粒子群等）、基于规则算法等

精确解法理论上总能获得全局最优解，但是求解效率随着问题规模的增大而急剧下降，例如一个 85 job x 8 machines 问题的搜索空间达到了 $10^{880}$。近似解法则追求以合理的计算时间获取较好质量的解，但不保证是全局最优解。

• OR-Tools 约束求解器

• PuLP求解器

• 基于规则指派

• 遗传算法