Job Shop Schedule 生产调度问题 (一) 简介

生产调度问题(Job Shop Schedule Problem)是一个非常经典的组合优化问题，在生产制造、项目管理的计划排班上广泛存在；学界对这个课题的研究已经超过50年了，建立了各种理论模型并提出了多种算法，应该说该问题属于最难处理的组合优化问题之一，一方面实际的业务逻辑会相当复杂，学界讨论的很多表现良好模型太过理想化，不太好直接应用到实际，另一方面问题规模的扩大很容易引起计算量的指数增长，无论采用哪种算法都不可能完全解决性能问题。我们先通过一个简单直观的例子来了解JSP的概念。
假设某个工厂每天需要生产三个产品，它们各自属于不同的类型，有不同的加工流程：

工厂内有三台加工设备来进行产品的各个工艺流程。对于某个产品的一个工艺，会有一台指定的设备进行加工，相应的也有个固定的加工耗时；对于每台设备，容量只有1单位，即同一时间只能加工一个产品。如下图所示，虚线框框起来的工艺属于同一台设备，右上角的红色数字表示加工耗时

我们现在的任务就是需要安排所有产品的工艺流程在各个设备上的加工开始时间，下图是一种最直接的安排方式，一个产品加工完后再安排下一个

这种安排方式的最晚完成时间(一般称之为makespan)是27h。显然这种安排方式太低效，事实上最优的安排方式如下图所示，这是的makespan是14h

上面的例子就是最基本的JSP的一个实例。JSP可以描述为在满足资源(设备、人员、时间等)约束的情况下安排加工序列，使得总消耗(时间、成本)最小的问题。最基本的JSP就如上面的例子所示，只有两个约束和一个目标：

• 流程内的工序必须按照工艺顺序进行，即后一道工序必须在前一道工序完成后才开始
• 设备同一时间只能处理一个工序
• 最小化最晚的工序完成时间

具体的数学表述：我们定义一个集合 J J J，每个元素job就代表了某种产品的加工工艺流程；一个包含m个元素的集合 M M M，每个元素表示了一台设备；一个集合 O O O，每个元素代表了某个产品的某个加工工序，也就是说对于每个 v ∈ O v \in O v∈O，都属于某个 J v ∈ J J_v \in J Jv​∈J，并且需要某个确定的 M v ∈ M M_v \in M Mv​∈M来加工，相对的处理时间为 t v t_v tv​。自定义一个符号 → \to →来表示集合 O O O里的序列关系，即如果 v → w v \to w v→w，那么 J v = J w J_v=J_w Jv​=Jw​，并且不存在 x ∉ { v , w } x \notin \{v,w\} x∈/​{v,w}使得 v → x v \to x v→x或者 x → w x \to w x→w。我们需要确定每个工序 v ∈ O v \in O v∈O的开始时间 S v S_v Sv​，使得
m a x v ∈ O ( S v + t v ) (1) max_{v \in O}(S_v+t_v) \tag{1} maxv∈O​(Sv​+tv​)(1)
达到最小值，同时满足约束：
S v ≥ 0      f o r   a l l   v ∈ O ( 2 ) S w − S v ≥ t v      i f   v → w ,   v , w ∈ O ( 3 ) S w − S v ≥ t v ∨ S v − S w ≥ t w      i f   M v = M w ,   v , w ∈ O ( 4 ) \begin{aligned} &S_v \geq 0\ \ \ \ &for\ all\ v \in O \qquad\qquad&(2)\\ &S_w-S_v\geq t_v\ \ \ \ &if\ v\to w,\ v,w \in O \qquad\qquad&(3)\\ &S_w-S_v \geq t_v \lor S_v-S_w \geq t_w\ \ \ \ &if\ M_v=M_w,\ v,w\in O \qquad\qquad&(4) \end{aligned} ​Sv​≥0    Sw​−Sv​≥tv​    Sw​−Sv​≥tv​∨Sv​−Sw​≥tw​    ​for all v∈Oif v→w, v,w∈Oif Mv​=Mw​, v,w∈O​(2)(3)(4)​

不等式2表示所有工序的开始时间必须大于零；不等式3表示属于同一个加工流程的相邻工序，必须满足序列约束；不等式4则是设备资源占用约束，每台设备上工序的加工时段不能有重叠。
依据实际的业务逻辑，基础JSP会扩展出各种更复杂的JSP问题，例如某些工序可能有多个可选设备，不是强制在某台设备进行，这样等于决策变量增加一维，即设备选择情况，这种问题一般称为Flexible Job Shop Scheduling Problem(FJSP)；再比如说，加工设备其实属于一种特定资源，实际加工时还可能有其他类型的资源被占用，例如某类工具，加工某个产品的工序时，该工具也会被占用，那么计划结果也要保证工具资源的占用时间不会冲突，这种问题则属于多资源的JSP。

表达式1至4既是JSP问题的数学描述，也是最直接的整数规划模型(一般会限定 t v t_v tv​为整数)，因此可以直接利用实现了高效整数优化算法的求解器进行求解，可以得到精确解。不过精确求解很容易受到问题规模的限制，学界为了使用元启发算法进行近似求解，提出了Disjunctive Graph的表述模型，这是最流行的JSP表述模型之一，在它的基础上比较容易进行元启发算法的实现。

我们定义一个图结构 G = ( V , A , E ) G=(V,A,E) G=(V,A,E)，其中：

• V V V是顶点集， V = O ∪ { 0 , N + 1 } V=O \cup \{0,N+1\} V=O∪{0,N+1}，每个点代表一个工序，这里0和 N + 1 N+1 N+1表示两个虚拟的工序，它们对应的加工时间都是0( t 0 = t N + 1 = 0 t_0=t_{N+1}=0 t0​=tN+1​=0)
• A A A是有向实线集， A = { ( v , w ) ∣ v , w ∈ O , v → w } ∪ { ( 0 , w ) ∣ w ∈ O , ∄ v ∈ O : v → w } ∪ { ( v , N + 1 ) ∣ v ∈ O , ∄ w ∈ O , v → w } A=\{(v,w)|v,w \in O,v \to w\} \cup \{(0,w)|w \in O, \nexists v \in O:v \to w\} \cup \{(v,N+1)|v \in O, \nexists w \in O,v\to w\} A={(v,w)∣v,w∈O,v→w}∪{(0,w)∣w∈O,∄v∈O:v→w}∪{(v,N+1)∣v∈O,∄w∈O,v→w}。也就是说 A A A的每个元素就代表同一个job的两个相邻operation，或者是从虚拟首节点0到每个job第一个operation，或者每个job的最后一个operation到虚拟末节点
• E E E是虚线集， E = { ( v , w ) ∣ M v = M w } E=\{(v,w)|M_v=M_w\} E={(v,w)∣Mv​=Mw​}，也就是说在 E E E所表示的边的两头的顶点是在同一台设备上加工的两个operation

以上面的产品样例为例，下面的图就表示了一个尚未求解的Disjunctive Graph模型：

比照表达式1至4，每条实线边就对应不等式3，而每条虚线对应不等式4。如果规定虚线从一个节点指向另一个节点，就表示节点对应的operation要早于另一个节点，那么求解上述的整数优化模型，表现在Disjunctive Graph上就是要确定所有虚线的方向，也就是在确定每台设备上operation的先后顺序。对应上述makespan为14h的最优解，其Disjunctive Graph为：

另外对于一个已经确定了所有虚线方向的Disjunctive Graph，它表示的schedule结果的makespan就对应从首节点到末节点的最长路径的长度，如下图的红线所示，每条红边对应的数字是处理时间

Disjunctive Graph的表述方式其实就是设备上的operation的序列排布的图形化演示，以它为基础可以更方便地进行元启发算法的应用。比如我们定义决策变量为 c i j   i , j ∈ V a n d   M i = M j c_{ij}\ i,j \in V and\ M_i=M_j cij​ i,j∈Vand Mi​=Mj​，并且 c i j ∈ { 0 , 1 } c_{ij} \in \{0,1\} cij​∈{0,1}，这种决策变量其实就是表示每条虚线的方向，规定如果 c i j = 1 c_{ij}=1 cij​=1，表示虚线是从节点 i i i指向节点 j j j，即operation i要在operation j之前开始。这样一个JSP问题的解就可以表示为一个二值变量串：
c 14 c 16 c 46   ∣   c 23 c 28 c 38   ∣   c 57 c_{14}c_{16}c_{46}\ |\ c_{23}c_{28}c_{38}\ |\ c_{57} c14​c16​c46​ ∣ c23​c28​c38​ ∣ c57​
显然，基于这种解形式，原生的进化算法或邻域搜索算法就可以直接套用了。进一步的，我们要求的解就是所有设备的operation的先后顺序，所以直接用operation的置换序列作为解的形式也是最常见的编码形式之一，像这样
o 20 o 00 o 11   ∣   o 21 o 12   ∣   o 10 o 01 o 22 o_{20}o_{00}o_{11}\ |\ o_{21}o_{12}\ |\ o_{10}o_{01}o_{22} o20​o00​o11​ ∣ o21​o12​ ∣ o10​o01​o22​
不过需要指出的是，基于Disjunctive Graph的解形式属于间接决策变量，我们实际要求的是开始时间，因此从特殊编码到实际结果间存在额外的编解码工作。

最后，用一个demo来演示JSP的计算过程，下面的gif展示了一个5X5的JSP求解过程，求解方式是使用Google OR-Tools的整数规划求解器

关于demo：这是我个人处于兴趣在Github上发布的一个演示使用不同算法求解JSP的网页系统，使用.Net Core API，Angular和Java程序编写，运行在docker上，提供了源码和安装脚本，项目地址: JSP-Presentation