生产调度问题分类——约束视角

获取更多资讯，赶快关注上面的公众号吧！

生产调度问题是实际工作中广泛存在的运筹学问题，可以描述为“给定若干加工任务，根据已有的生产条件，对任务按照一定的生产加工步骤进行安排，并在时间上分配有限的资源，使得某项性能指标最优”。从数学建模方面来说，生产调度问题就是，对于给定的生产任务进行建模，在满足特定的约束条件下，使得目标函数值达到最优或者近似最优。

生产调度问题起源于上世纪50年代，对该问题的研究具有重要的实用价值，吸引了大量国内外研究人员的关注，人们尝试从不同的科学领域去解决该问题，但是大部分车间调度问题属于NP-Hard问题（作业车间调度问题：P还是NP），目前还无法证实P=NP，因此NP问题无法在多项式时间内解决，即无法获得全局最优解。

1979年，Graham等提出了三元组$\alpha |\beta |\gamma$表示法来描述调度问题。其中$\alpha$表示机器环境，$\beta$描述了工件加工特征和详细约束，$\gamma$代表调度性能指标。

上一篇文章中（生产调度问题分类——机器视角），详细介绍了$\alpha$域即机器环境，本文将重点说明$\beta$域。

提交日期

提交日期也称为释放日期（release date），表示工件$j$需要在提交日期$r_j$及之后才能开始。

在陆续抵达的车间调度问题中需要考虑此约束，同时在一些其他场景下，如物料预计到达时间（齐套时间）、机器维修完成时间、人工设置的最早开始时间等，也均可等效为这种约束。

中断

中断（prmp）含义是不必将一个作业在其加工完成之前一直保留在机器上。它允许计划员在任何时间中断一项作业的加工，而把另一项作业放到该机器上。一项中断的作业已经完成的部分不会丢失，即当一项中断的作业重新返回到机器上时，仅需要加工完剩下的作业即可。

在一些机加工车间中，部分机床存在多工作台，机床正在加工的同时，其他工作台正在准备，如果准备的工件优先级较高，可以切换工作台从而中断正在进行的工件。其实这个约束在实际场景中并不是很常见，所以大多数论文中也都会假设工件不允许中断。

优先约束

优先约束（prec）其实可以出现在任意的机器环境中，其表示在一项作业开始加工前，另一项或多项作业必须先完成。

• 如果每项作业最多有一个前置，最多有一个后置，这种优先约束称为链式；
• 如果作业最多有一个后置，该约束称为入树；
• 如果作业最多有一个前置，则称为出树；
• 如果作业可以既可以有多个前置也可以有多个后置，则称为网状。

在存在多个生产过程、指定作业顺序、装配作业场景下，均会存在这种约束。

顺序依赖准备时间

$s_{jk}$表示工件$j$和工件$k$之间的由加工顺序决定的准备时间。如果工件$j$是第1个，则$s_{0k}$表示工件$k$的准备时间；如果工件$j$是最后一个，则$s_{j0}$表示工件$j$之后的清理时间。如果工件$j$和工件$k$之间的准备时间还与机器有关，那么就表示为$s_{ijk}$。

在需要夹治具的机加工（尤其是大件）场景中需要考虑此约束，因为不同的工件需要的夹治具不同，夹治具的拆卸和安装时间也不同，导致工件在按照不同顺序加工时的准备时间也不同；此外，在流水线型的装配制造中，不同的工件需要的物料种类和数量不同，甚至还需要重新准备线体。

工件族

工件族（fmls）是将$n$个工件划分为$F$个类（每一类就是一个工件族）。同一族的工件可能加工时间不同，但都可在同一机器上加工且两者之间不需要准备时间。当机器切换工件族（如从族$g$切换到族$h$）时，需要一定的准备时间。如果这个准备时间取决于工件族$g$和$h$且是顺序依赖的，那么就表示为$s_{gh}$；如果准备时间仅依赖于后置工件族$h$，那么表示为$s_h$；如果不依赖于任何工件族，则表示为$s$。

工件族实际上是更粗粒度的顺序依赖准备时间。顺序依赖准备时间定义的是两个工件之间的准备时间，而工件族则是两类工件之间的准备时间。

这在实际中是有现实意义的。因为某些工件之间仅仅存在较小的差别（比如颜色），对于生产准备没有影响，如果定义到每两个工件之间的准备时间，对于品种较多的工厂来说是非常耗时的一项工作。而如果能把一些工件进行分类（成组技术），在较少的类别上定义准备时间势必减少很多工作量。

批处理

一台机器可同时加工$b$（$b>1$）个工件，即加工批量为$b$，这种为批处理（$batch(b)$）。一个批量中各个工件的加工时间可以不全相同，批次中的最后一个工件都完成后整个批次才算完成，即整个批次的完成时间取决于加工时间最长的工件。

此约束在热处理等场景中非常常见，热处理炉具有一定容积，可同时放入多个工件进行处理。

故障

机器故障（brkdwn）意味着机器不能连续使用，需要进行维修或保养。

其实在休息、节假日期间，机器也不工作（无人车间暂不考虑），所以更准确的叫法是机器停机。

机器适用限制

当机器环境是$m$台并行机（$P_m$）时，机器适用限制（$M_j$）是指并不是所有$m$台机器都有能力加工工件$j$，集合$M_j$表示可以加工工件$j$的机器集合。

在实际车间环境中，当工件对机器有特殊要求或机器不具备特定的人/模治具时，可能会导致并不是所有的机器都可加工该工件。

（ M 1 = { m 1 , m 3 } , M 2 = { m 1 , m 2 } , M 3 = { m 3 } ） （M_1=\{m_1,m_3\},M_2=\{m_1,m_2\},M_3=\{m_3\}） （M1​={m1​,m3​},M2​={m1​,m2​},M3​={m3​}）

排列

在流水车间调度问题中可能出现的约束是每台机器前的队列遵循FIFO规则，即所有工件经过所有机器的顺序保持一致，这种调度问题也称为排列（置换）流水车间调度问题。

阻塞

阻塞（block）是可能出现在流水车间中的现象。如果一个流水车间在两台连续的机器之间只有有限的缓冲区，那么可能出现当缓冲区满的时候，上游的机器不允许释放已经加工好的工作，此时就会阻止或阻塞那台机器加工别的工作。

无等待

无等待（nwt）是流水车间中可能出现的另一种现象。工件不允许在两台连续的机器间等待，即一个工件在第1台机器上的开始时间不得不推迟，以保证该工件可以不必等待任何机器而通过流水车间。

在一些具有特定要求的车间中，如轧钢厂，不允许钢板等待，因为在热轧过程中需要保持一定温度，如果等待时间过长会导致冷却而无法达到温度要求。

再循环

在作业车间或柔性作业车间中，当一个工件可能经过一台机器或加工中心超过一次的时候，发生再循环（recrc），或称为可重入（reentrant）。

该约束广泛出现在许多工业制造过程中，如半导体制造、印刷电路板制造以及需要多次热处理的机加工制造等。