生産计划调度的灵魂：约束规则

3dportalzhao

生産计划调度的灵魂：约束规则

现在，约束计划的开发已经吸引各个领域的专家的高度注意，因爲，它是有潜力解决现实中的非常难的问题。不仅基於很强的理论基础，而且，也广泛吸引商业利益。特别是在对变异的建模优化与满意问题。无论我们是用先进的基因演算法，还是用人机互动式的仿真方法，都需要对制造业的复杂约束，多目标优化，大规模的搜索和车间生産的不确定性的问题进一步研究，以适用实际需要。

在人类努力的大多领域 ， 约束在不断的增加。它们在物理世界形成互相依赖。约束是在一些未知或变化 的简单的逻辑关系，在给定的领域，每一个约束取一值。约束就限制了变化所带来的可能的值，它反映部分资讯，约束也可以是不协调的，它可以在不同领域 互相约束。实际上，我们都用约束来指导推理和决策，是每天的常见行动的重要的一部分。如，我可以从5点到6点在那 。这就是典型的约束，我们用它计划我们的时间。自然，我们不能仅仅解决一个约束，因爲约束很少是独立的。，所以，我们不得不接受的现实是这些问题比较复杂。

约束计划是基於约束规则的电脑系统的程式，约束计划的概念是详述问题的约束来解决问题。结果是找 到让所有的约束满意的方案。计划调度的实施的关键是基於约束规则，基於约束自动的调配资源，优化计划，来达到你所需要的计划目标。对离散的制造行业解决复杂的加工过程如多工序，多资源等（Jobshop调度），对重复式或流程式的制造行业解决顺序问题如优化排序等（Flowshop调度）。

如你的主要目标是一个满足所有任务规定的完成日期吗？ 还是你重点是提高设备利用率，减少非生産时间（准备时间和设备维护时间）？确定基本计划的目标是选择合适的规则的先决条件。一旦决定你的目标，你就可以选择规则来完成目标。

一、基於订单（Job-based）排程方法

工作中心WC A 有两个资源
( }5 p) |' G/ o' e/ a& @% _  g2 j* H工作中心WC B 有一个资源
: J  V! b+ Y( q4 q, Q- c订单MO-1 最高优先顺序。
3 n- ^& k% t" p2 C订单MO-2 次优先顺序

是基於订单的优先顺序决定下一个订单的加工，可以自动识别订单的优先顺序和手工定义优先顺序，在电脑自动的根据规则的优选级排出生産计划後，还可以手工介入，修改优先顺序进行重排。以满足复杂的现实的需要。

约束规则如下：
（1）瓶颈：基於次要任务选择规则的排列。向前和向後方法来计划所有未分配的任务订单。重点是瓶颈资源的工序的。双向模式只计划需要指明瓶颈资源的任务。能用任何可得到的规则计划剩馀任务。
, `' Q/ b  H: l! Y' V! u: B（2）完成日期：基於最早完成日期。
- ~$ ^, G: R; p, S（3）先到先服务：按照先到订单，先安排生産。
5 ?. N5 s3 w* Z5 }1 I（4）升幂订单属性值：按规定的订单升幂的值排列。订单的属性可以是数值，字母。
（5）优先顺序：按照最小数值优先。如果你用此规则，优先顺序栏位必须在订单上定义。
（6）加工时间：按照订单最小的加工时间优先。
（7）下达日期：按照最早开始日期优先。
（8）相反优先顺序：按照最大数值优先。如果你用此规则，优先顺序栏位必须在订单上定义。
（9）闲散时间：按照最小闲散时间优先。
二、基於事件（Event-based）的排程方法

) h  ^* S* X$ Y; \/ z/ p. X是基於高利用率的方法。实现其计划的关键是二步导向的规则使用。有二个基本的规则：（1）工序选择规则OSR；（2）资源选择规则RSR。

针对不同産品和资源，必须选择不同的规则，在决定是使用工序选择规则或资源选择规则时，主要考虑的是什麽是一个好的计划标准？一旦确定你的目标，你就可以选择工序和资源选择规则来完成目标。一般来说，先选择工序选择规则，然後选择合适的资源选择规则。在一些情况下，有关的资源选择规则被工序选择规则所决定。

工序选择规则OSR（ Operation Selection  Rule）

至少一个资源是空闲的，二个或多个工序能用於这个资源，采用OSR。此规则决定那一个工序被载入。这就是决定计划结果质量好坏的关键因素。独立的工序选择规则详细介绍如下：

（1）最早完成日期：选择最早完成的工序（也许是订单完成日期）
, f. Z& O" x% k! a, Z/ C（2）最高优先顺序第一：选择最高优先顺序（最低值）的工序
（3）最低优先顺序第一： 选择最低优先顺序（最高值）的工序
: [- D2 \' U0 n* X7 c（4）最高订单属性栏位：选择最高（最大）订单属性栏位的工序
8 \  [% S/ H! T7 p% h（5）最低订单属性栏位： 选择最低（最小）订单属性栏位的工序
（6）动态最高订单属性栏位：选择动态最高（最大）订单属性栏位的工序
5 ~2 E  H' w9 v4 B（7）动态最低订单属性栏位： 选择动态最低（最小）订单属性栏位的工序
（8）计划档案订单：选择订单 出现先到先服务的工序
, k) U  N+ Z) U（9）关键率：选择最小关键率的工序。
关键率=剩馀计划工作时间/（完成日期-当前时间）
6 F+ D8 \6 G2 |% b实际关键率=剩馀实际工作时间/（完成日期-当前时间
（11）最少剩馀工序（静态）：选择最少剩馀工序时间的工序
（12）最长等待时间：选择最长等待时间的工序
（13）最短等待时间： 选择最短等待时间的工序
1 D+ F1 W- E0 g8 {6 Q- o1 ^& A（14）最大过程时间：选择最大过程时间的工序
/ ]) q) O2 f6 O" {) K1 X- V2 x（15）最小过程时间： 选择最小过程时间的工序
（16）最小工序闲散时间：选择最小工序闲散时间的工序。
# ^8 k% ^. S, K; q4 g' \( v订单任务的闲散时间=任务剩馀完成时间-剩馀工作时间
0 }) N/ j% O/ Y' [3 z( X2 M" }工序闲散时间=任务闲散时间/完成任务的剩馀工序数
/ U& ~, v) p0 a; e4 V3 b（17）最小订单闲散时间：选择最小订单任务的闲散时间的工序
（18）最小工作剩馀：选择所有需要完成订单的最小剩馀过程时间的工序。

: ]; v; Y  \3 ^8 ~" Q! r6 P2 b# O! x资源选择规则（RSR） Resource Selection Rule

    RSR选择工序载入到资源组内的哪一资源。

( m# G! n( u- E, h. s2 N$ |（1）最早结束时间：选择将要最先完成工序的资源
6 Z( u+ E' S, j（2）最早开始时间： 选择将要最先开始工序的资源
4 H" {1 {' w  K) C. \* F: N（3）最迟结束时间： 选择将要最迟完成工序的资源
/ C. T. B' E2 p! V1 u3 O（4）与前工序一样： 选择被用於前一工序的资源
' ?' z. K1 @3 e$ v' A: ~（5）非瓶颈最早开始时间：选择将要最早开始工序的非瓶颈资源

2 }: d! R2 U+ |4 p" t3 F5 T相关选择规则：

如果选择一工序选择规则，就自动的选择相应的资源选择规则。

（1）系列顺序回圈：选择同样或下一个最高（最低）系列值的工序。当没有最高值的工序，顺序将相反，选择最低的工序。
1 Y; T' b, W& z7 V. s& ?（2）系列降顺序：选择同样或下一个最低系列值的工序
（3）系列升顺序： 选择同样或下一个最高系列值的工序
" f$ y  N5 p8 k0 d! t, {9 D; V5 ~（4）最小准备系列： 选择最小准备时间及最近的系列值的工序。
（5）最小准备时间： 选择最小准备或换装时间的工序
（6）定时区的系列顺序回圈：选择同样或下一个最高（最低）系列值工序。且只考虑在特定的时区的订单完成日期 的工序。 当没有最高值的 工序，顺序将相反，选择最低的工序。
8 H% N& B% W  U5 \7 I' D（7）定时区的系列降顺序：选择同样或下一个最低系列值工序。且只考虑在特定的时区的订单完成日期 的工序。
（8）定时区的系列升顺序： 选择同样或下一个最高系列值工序。且只考虑在特定的时区的订单完成日期 的工序。
（9）定时区的最小准备系列： 选择最小准备时间及最近的系列值的工序。且只考虑在特定的时区的订单完成日期 的工序。
（10）定时区的最小准备时间： 选择最小准备或换装时间的工序，且只考虑在特定的时区的订单完成日期 的工序。

3dportalzhao

工序选择规则的分析

标准的工序选择规则有二十多个标准规则。不同的规则对应不同的目标。这些规则可以进一步分成静态与动态的规则。

静态规则：爲所有在排队中的订单，所有等待的工序提供一简单的索引机制。这些规则在每一次预先类比时间时不需要再次评估。用於工序选择规则的叁数是固定的。例如规则是最早完成日期规则，完成日期在顺序排程中从未改变。在排队中的第一个工序被分配到一等待资源。因爲规则总是选择第一个等待工序，此规则执行的非常快。

6 t3 @( r3 s5 N; V# T动态规则：每一个在排队的工序被每一次调用的规则检查。因此，我们是基於当前的订单任务和系统的状态决定我们的选择。这个机制充分考虑了任何改变出现的时间和事件的结果。例如，最小工序空闲规则，因爲工序的空闲值随时在改变。因爲动态选择规则需要在每一次事先类比以後检查在排队中的每一个工序，它比静态规则要慢一些。

爲有助於分析规则，我们对规则进行分类。分成四个主要类别来对应四个不同的计划目标。它们是1、预先确定任务的叁数。2、最小化任务缓慢。3、最小化任务流程时间。4、最大化设备利用率。我们将讨论每一个核心目标和相应的工序及资源规则以支援这些目标。规则的分类目的是帮助你爲达到你的核心目标而缩小你的规则的选择。对某一类的规则选择是基於你的计划问题。每一个类别的规则都混合一些静态和动态的规则。

" }: J1 I2 {( T2 ]* G0 g* \7 b预先确定订单任务的叁数：是基於预先定义订单任务的优先顺序来选择下一个工序或用户规定的属性栏位（如成本）。一般来说，每一个规则由特性的最高，最低的值被调用。这类包括最高优先顺序，最低优先顺序，最高订单特性栏位，最低订单特性栏位，动态最高订单特性栏位，动态最低订单特性栏位，计划档案订单，最长等待时间，最短等待时间，和最大过程时间。

* y, J! r' V* D  P最高优先顺序和最低优先顺序是分别用最高或最低优先顺序选择工序的静态规则。

最高订单特性栏位，最低订单特性栏位是和优先顺序规则相似的静态规则，除了基於用户定义属性的选择。例如。最高订单特性栏位规则用一个属性栏位定义，如由成本的最高值来选择任务。因爲这是一个静态规则，它假设当订单任务正在等待处理时成本是不变的。

动态最高订单特性栏位，动态最低订单特性栏位规则是动态的。虽然这些规则执行较慢，它们也适应当订单任务正在等待时属性栏位可以改变的情况。

计划档案订单规则是一静态规则，是基於已进入资料库的订单来选择订单。这个规则和先到先服务规则相似。

最长等待时间，最短等待时间规则是一动态规则，它是基於订单任务被等待计划的时间来选择工序。

最大过程时间规则是用最大过程时间来选择工序。预先确定任务的叁数规则一般用於订单任务的特性的情况。（如优先顺序或成本），不考虑任务完成日期或设备利用率。因爲这些规则忽略完成日期，它们典型更适应面向库存生産（MTS）环境，而不是面向订单生産环境（MTO）。

最小化任务延缓：在许多面向订单生産环境（MTO），计划目标是保证每一个订单任务按期完成。 最小化任务延缓的规则是建立一最小化延缓任务的计划。这类规则包括最早完成日期，最小化运行闲散时间，最小化订单闲散时间，关键率，和实际关键率。这些规则的最简单的是最早完成日期。这是一静态规则。虽然这个规则执行的非常快。这一类所有的规则是基於空闲时间计算的动态规则。空闲时间是完成日期和最早完成时间的差异。

$ o7 G8 ]: a) c' E, }最小订单闲散时间规则选择一个父项任务的工序，父项任务有最小的闲散时间。如它没被选择，这个订单任务大多可能是延迟的。

最小运行闲散时间规则是基於每一个工序的平均闲散时间（订单任务计算的闲散时间/剩馀工序数量）而不是任务的剩馀闲散时间。这个基於闲散时间的规则形成的基本想法是每一个剩馀工序有一固有的风险，根据它延迟的可能性，每一个工序的最小闲散时间的订单任务是最关键的。因此，如果我们在同样的闲散时间中选择订单任务，我们会选择最大剩馀工序数量的订单任务，因次，根据每个工序最小闲散时间的规则来选择处理风险最大的订单任务。

' N& S6 l7 y% _基於闲散时间规则的最後的差异是关键率。这个规则选择父项任务有最大关键率的工序。关键率是剩馀工作时间/（剩馀工作时间+闲散时间）。注意只要闲散时间是正的数，分母大於它，关键率就小於1。就此，任务还没有延迟。如果关键率大於1，闲散时间是负数，任务就不能按期完成。关键率规则与最小工序闲散时间规则相似。相同的是，它们都是用闲散时间来计算的。不同的是它的剩馀工作已完成。它的基本的前提是剩馀闲散时间本身在决定最关键订单任务时并不重要，即相关的剩馀工作已完成。如我们有许多剩馀工作，那麽，我们需要较大的闲散时间来保证我们的订单任务不能延迟。
最小化任务过程时间：在一些环境，关键问题是计划设备的效率来最小化订单任务的平均时间。 在最小化任务过程时间规则 忽略任务完成日期而集中於减少订单任务的时间。这类规则包括最小化流程时间，最少剩馀工序，最小工作剩馀。这类规则是基於过程时间最短的概念，减少所有订单任务的平均任务过程时间。

8 V4 N" U8 S& e6 O1 m案例一：

# |9 Y! n, _  k( T; H有二个订单任务A，B。 在单一的机器上加工处理。让我们假设任务A需要4小时，B需要量10小时。如我们加工A，B，任务A立即开始及4小时完成，産生4小时的过程时间。任务B开始等待4小时，加工10小时産生14小时。两个订单一共用了18小时，所以平均过程时间是9小时。

如我们把加工顺序倒过来，B的过程时间是10，和A的过程时间是14， 。两个订单一共用了24小时，所以平均过程时间是12小时。

虽然，这是一个非常简单的例子。如果有许多机器和许多不同的订单任务的应用就较复杂。不管怎样，这类规则都是用同样的概念-最短处理任务的时间，仅仅不同的它是怎样决定最短任务。最小化处理时间规则是静态规则，用最短工序时间选择工序。最小化工作剩馀规则是动态规则，它是基於父项任务的最小剩馀工作选择工序。剩馀工作是对所有任务的剩馀工序的合计时间。最小化过程时间规则检查单一工序的加工时间，而最小化工作剩馀规则检查所有的剩馀工序的加工时间。最少剩馀工序规则和最小剩馀工作规则相似，除了这个规则是基於剩馀工序数量而不是过程时间的合计。

最大设备能力：在一些面向库存生産的环境（MTS）中，关键的问题是设备效率。即最大化整个设备的生産能力。在最大化设备能力规则 忽略任务的完成日期而集中於设备的能力效率来産生计划。这类规则包括最小准备时间，系列顺序升UP， 系列顺序降DOWN， 系列顺序周期，和用系列的最少准备。另外，每一规则都与时间相连。所有这类规则都集中于减少转变成本，最大化的设备能力。这个转变成本能在一顺序相关的准备时间中设置。我们正努力消除设备的任何没有必要的非生産时间。

如果我们爲整个工序的排序，在连续的工序之间，要考虑顺序相关的准备时间及转变成本，此时，我们就能用系列规则。

6 k. N) ]" n2 l' w4 |案例二：

在混合油漆中，我们在定义好的顺序中一般要逐渐从淡色移动到深色。如从深色移动到淡色时，就有整个清洗混合的油箱的准备时间即转变成本。在一些情况下，我们有事先规定好的顺序。例如，我们也许要处理顔色顺序A，B，C，，D，E的订单，这就称爲系列顺序。如果我们刚要加工顔色A，我们会首先寻找有顔色A的其他订单。如没有，我们会寻找顔色B的订单，依此顺序，等等。系列规则提供这个能力。这些规则允许我们规定一个系列值。（如油漆顔色，温度，等等）。每一个订单/工序及动态建立系列，或自动的增加，减少，或使系列值上下回圈。

在增加系列的情况下，系列升顺序规则选择一系列值并大於或等於被选择工序的系列值的工序。如，如果我们建立一零件尺寸的增加系列值，规则选择同样或下一个最大尺寸的工序。如等待工序没有同样或大的值，规则就开始一个新的系列顺序。

2 M, P5 I! u# X; Z' K# Q9 N- @0 T& H系列降顺序规则也是类似的。

3dportalzhao

: c% n) |. A$ ?* g

案例三：

* c3 `, h2 p$ p# z2 P9 c4 ?. ?生産化工纤维材料时，根据産品的型号和厚度对品种进行分类，对品种的最优排産。

如取最小值=  {  3m/1。4m， 6m/1。4m，┅。}来决定在哪个订单的加工顺序及哪个资源最经济。

系列顺序回圈规则在增加顺序和减少顺序前後交替。如系列增加，它将继续增加，直到没有一样或较大的系列值订单剩馀的订单。当这种情况出现，规则会转爲减少系列值并开始选择有一样或较小系列值的订单。当所有这样的订单耗尽，它就回到增加系列的策略。这个规则以此方式继续，在增加和减少系列值之间重复回圈。

! P7 G1 ?) I3 h1 m案例四：

) a6 x* k+ ~0 f: k! y" O9 `8 {在热处理时，温度是间隔的增加到最高，然後降低。

最小准备系列规则结合最小准备时间规则和系列顺序回圈规则。最小准备时间和最靠近的系列值的工序被选择。

定时的规则仅仅考虑任务完成日期正好落入规定的时区的工序。时区必须定义在资料库。如，你要跟踪顔色的系列，但是，你仅想考虑在下一周的完成的订单任务。这个规则既要最小化顔色的改变。又要不能延迟订单任务。

资源选择规则分析

$ L. e9 v9 T4 p& u虽然工序选择规则在决定生産计划方面起着重要作用。资源选择规则在加工处理中也能起重要作用。尤其在最小准备时间和系列工序选择规则上，资源选择规则是由工序选择规则自动决定的。（如选择最小准备时间工序规则，最小准备时间资源选择规则被自动选择）。然而，在选择所有的剩馀工序选择规则时，你必须在资源选择规则中选择其一。

最早结束时间是缺省的资源选择规则。它选择将完成的第一个的工序。基本策略是尽快完成工序。因此，此规则与工序选择规则的最小化过程时间相似。

最早开始时间规则选择将开始第一个工序的资源。这些规则集中减少资源闲散时间。

最迟结束时间规则选择将选择最後完成工序的资源。如果资源不包括在有效资源组，缺省最早结束时间规则。

& x: I$ ?$ D, C5 |2 D; y2 r6 D非瓶颈的最早结束时间规则将首先完成工序的非瓶颈资源。非瓶颈最早开始时间规则将首先开始工序的非瓶颈资源。

6 q' O3 F1 p3 I* S2 m三、基於物料约束（Material Constrain）

当生産计划想要计划一个需要某物料的工序时，它将仅仅计划库存水平足以满足当时或以後的工序。如果在计划时区不能满足条件，物料约束计划将首先查看是否有未分配的定单，産生库存需求。如果它找到这样的定单，它将首先计划定单，然後计划工序的库存需要。如定单産生库存需求另外的未有的库存，物料约束计划将象以前一样寻找定单来计划。这个过程将重复许多次。如果有不够，就需要库存补充。

# v" F! C3 _/ e1 N7 W静态物料约束规则（SMC）

" B) v; b  Q# j! I8 g7 S3 K先对每一个物料从ERP系统导入建立可用量清单，最早开始的订单和被分配的物料，随着物料业务，订单日期的延迟，或变化，系统会自动调整或显示订单的变化。

    MO-3只有在MO-1，MO-2，PO-1完成後，才能开工。

7 O. z% {1 Y8 j4 i) c因爲MO-1的延迟，自动调整MO-3的开工日期

0 l, [( w3 E! A' y& j1 x$ C动态物料约束规则（DMC）

当计划建立时，动态分配物料，允许重新分配物料到另外的一个订单，它可以处理物料的有效期，变化的产出率，和减少在制品等实际问题。

    MO-3 只有在MO-1，MO-2，PO-1完成後，才能开工。

+ G& Q% r9 m. b0 }' ?而MO-1延迟，导致调整MO-3只能用MO-2-1，PO-1，MO-1的物料，而原来的MO-2-2的物料可以重新分配到MO-2，PO-1的完成後就可以开工。

- \% q! n: q4 {) S9 e6 \从库存取出约束（Take from stock kit）

定义在一工序需要的子项。
在我们做计划时，考虑子项物料从库存的可用量的约束来排计划。

% m! S: @5 ~5 n' o' W8 d! s放入库存约束（Put to stock kit）

0 d& T" {& k- `/ u2 Q定义从工序的父项産出结果。在我们做计划时，考虑産出的约束，必须考虑库位所能容纳的约束。

生産计划根据産品结构的相关性来分配物料的约束，查询约束可以按物料编码报告物料约束。也可以按订单号报告物料约束。工具约束：工具子项反映关键工具作爲资源，也可以作爲约束物料，如你可以定义工具産生约束，如工具维修，故障。

: U* F& h; m6 F总之，制造业对客户需求的回应越来越强烈。现在生産计划调度系统正开始将基於约束规则基因搜寻和类比仿真模式结合起来，解决制造同步化问题和工厂的顺序冲突问题。

现在，约束计划已经成功应用到许多不同问题领域。它和分析DNA结构一样多样化。对医院的时间表和工业的排程。实践证明它能较好适应解决现实的问题。因爲，许多应用领域自然的需要约束。分派问题也许是第一个工业应用约束解决工具。用甘特图来描述计划可能是最成功的应用领域如有限约束排程。在现实中，约束计划可以广泛的运用，但是当前的工具也有可能没有涉及到的领域或局限和缺点。无论是从理论上，还是实际的观点来看，约束的定义促使问题可追踪是非常重要的，约束计划的有效性仍然是不可预测的：何时，如何使用约束。通常直觉是决策的最重要的部分。有时，盲目的快速搜寻如按时间顺序後排比约束进化（基因演算法）更有效。在许多约束模型的特别问题是成本优化。有时，它是对改善起初的方案是非常困难的。且一个小的改善就会花去很多时间。

+ P! d( ~, H5 ^; m  c( F& {$ K5 t; M
2 M4 R" n, H4 N+ W$ L; V; q2 ]$ j约束计划也在不断的进化，它们能动态的增加约束。大部分情况下，约束系统産生的计划是可执行的。除了机器故障，延迟的计划，在最坏的情况下，新订单的接受。这是需要快速的重排计划或提高当前的方案来解决未预料的事件。同时，在通常较紧计划优化的方案和可以解决较少差异的，稳定的，次优化的方案之间交替选择。当前的约束满意系统的缺点标志着未来研究发展方向，在它们之间，建模看上去是最重要的之一。已经开始讨论使用全局约束，把主要的约束预先设置到套装软体。（如所有不同的约束规则）。目前，建模语言较多的使用ILOG公司的（ILOG Solver）来表示约束问题。（如名列前矛的商业管理软体供应商均采用此技术）

7 h2 B* @# n0 Z% E/ w3 E# n5 X0 t, M
从较低层次的观点，视觉化的技术越来越流行，他们帮助定义系统的瓶颈。各种约束解决方法的交互研究是最具挑战的问题之一。混合演算法结合各种约束技术是这个研究的结果。另外感兴趣的研究领域是解决协同和对应的结合的理论。约束满意技术和传统的OR（Operation Research）方法如整数规划是另外的挑战。研究平行和并行的约束已作爲提高效率的方法，在这些系统，多层代理技术是最有前景。

liuyuan156334

这个想法好，就是来电资料更爽、哈哈