接上一篇文章，在了解生产调度问题的背景和基本概念之后，我想先从比较基础的 flowshop和 jobshop 数学模型入手，理解实际调度过程中的问题求解思路。这一篇文章主要面向 flowshop 问题进行数学建模，对于这类比较经典的问题，其实已经有很多现成的模型和求解思路了。我也在网上进行了搜索，看到了3种模型形式，本篇文章将进行列举及描述。

问题描述

n 个工件在 m 台机器上进行流水加工，每个工件在机器上的加工顺序相同。并且每个工件在同一台机器上只加工一次，每台机器在某个时刻只能加工一个工件。各工件在各机器上的加工时间和准备时间已知，求某个调度方案使得调度目标最优。

模型形式1

来自chatgpt的回复。

变量：

·pij：作业 i 在机器 j 上的加工时间。
·决策变量xijk：0-1变量，表示作业 i 是否在时间段 k 被安排在机器 j 上。
·Ci：作业 i 的完工时间。
·Cmax：最大完工时间。

目标函数：

Minimize Cmax

约束条件：

1、每个作业在每台机器上只能被加工一次：

2、每台机器在任意时间只能加工一个作业：

3、确保作业 i 在机器 j 上的完工时间大于等于其在机器 j-1上的完工时间加上加工时间：

4、确保作业 i 在机器 j 上的完工时间大于等于其前一个作业在同一机器上的完工时间加上加工时间：

5、最小化最大完工时间：

模型形式2

来自阿里云开发者社区。

变量：

·xij：工件 i 比工件 j 先加工时取1；否则取0。
·pim：工件 i 需要在机器 m 上的加工时间。
·smi：工件 i 在机器 m 上开始加工的时间。
·Cmax：最大完工时间，即makespan。

目标函数：

min Cmax

约束条件：

1、工件 i 比工件 j 先加工，则工件 j 必然比工件 i 后加工。即xij=1时xji=0，反之亦然。

2、若工件 i 比工件 j 先加工，则在任何机器上工件 j 的开始时间都不早于工件 i 的结束时间（用 Z 表示某一“足够大”的正实数）。

3、工件在后一机器上的开始时间不得早于前一机器上的结束时间。

4、最大完工时间定义。

5、变量的取值范围。

完整表达如下：

模型形式3

来自“运筹优化与数据科学”公众号。

变量：

·Xji：表示工件 j 被安排在位置i。
·Srj：表示机器 r 上第 i 个工序的开始加工时间。
·Trj：表示机器 r 加工工件 j 需要的时间。

目标函数：

最小化所有工件在最后一台机器上的完工时间（其实我并没有理解这里的表达式，有待后续深入）

约束条件：

1、一个工件位置只有一台机器。

2、一台机器上只能安排一个工件位置。

3、第一台机器第一个工件的开始时间为0。

4、在第一台机器上，一个工件的开始时间等于上一个工件的完成时间。

5、在第 r+1 台机器上，第一个工件开始的时间等于第 r 台机器第一个工件的完成时间。

6&7、机器上某个工件开始的时间为 max{当前机器上一个工件的完成时间，上一个机器当前工件的完成时间}。

8、决策变量为0-1变量，Xji=1表示工件 j 被安排在位置 i。

9、机器 r 上第 i 个工件的开始加工时间为非负值。

总结

通过梳理这3种模型形式，我发现第2种形式是更为简洁的。对于flowshop问题来说，工件加工的机器顺序已经确定，就是要求解一组工件的先后顺序，从决策变量定义上看模型形式2更切中要害、易于理解。

参考资料

[1] 面对Flow-shop调度问题如何优化？可用MindOpt来决策
[2] 利用Pyhton+Gurobi求解置换Flowshop问题入门