[转帖]生产计划调度的灵魂：约束规则1
生产计划调度的灵魂：约束规则（一）
蔡颖
现在，约束计划的开发已经吸引各个领域的专家的高度注意，因为，它是有潜力解决现实中的非常难的问题。不仅基于很强的理论基础，而且，也广泛吸引商业利益。特别是在对变异的建模优化与满意问题。 无论我们是用先进的基因算法，还是用人机交互式的仿真方法，都需要对制造业的复杂约束，多目标优化，大规模的搜索和车间生产的不确定性的问题进一步研究，以适用实际需要。
在人类努力的大多领域里， 约束在不断的增加。它们在物理世界形成互相依赖。约束是在一些未知或变化里的简单的逻辑关系，在给定的领域里，每一个约束取一值。约束就限制了变化所带来的可能的值，它反映部分信息，约束也可以是不协调的，它可以在不同领域里互相约束。实际上，我们都用约束来指导推理和决策，是每天的常见行动的重要的一部分。如，我可以从5点到6点在那里。这就是典型的约束，我们用它计划我们的时间。自然，我们不能仅仅解决一个约束，因为约束很少是独立的。，所以，我们不得不接受的现实是这些问题比较复杂。
约束计划是基于约束规则的计算机系统的程序，约束计划的概念是详述问题的约束来解决问题。结果是找到让所有的约束满意的方案。 计划调度的实施的关键是基于约束规则，基于约束自动的调配资源，优化计划，来达到你所需要的计划目标。对离散的制造行业解决复杂的加工过程如多工序，多资源等（Jobshop调度），对重复式或流程式的制造行业解决顺序问题如优化排序等（Flowshop调度）。
如你的主要目标是一个满足所有任务规定的完成日期吗？ 还是你重点是提高设备利用率，减少非生产时间（准备时间和设备维护时间）？ 确定基本计划的目标是选择合适的规则的先决条件。一旦决定你的目标，你就可以选择规则来完成目标。
一、基于订单（Job-based）排程方法
工作中心WC A 有两个资源 工作中心WC B 有一个资源
订单MO-1 最高优先级。
订单MO-2 次优先级
基于订单任务示意图
是基于订单的优先级决定下一个订单的加工，可以自动识别订单的优先级和手工定义优先级，在计算机自动的根据规则的优选级排出生产计划后，还可以手工介入，修改优先级进行重排。以满足复杂的现实的需要。
约束规则如下：
（1）瓶颈：基于次要任务选择规则的排列。向前和向后方法来计划所有未分配的任务订单。重点是瓶颈资源的工序的。双向模式只计划需要指明瓶颈资源的任务。能用任何可得到的规则计划剩余任务。
（2）完成日期：基于最早完成日期。
（3）先到先服务：按照先到订单，先安排生产。
（4）升序订单属性值：按规定的订单升序的值排列。订单的属性可以是数值，字母。
（5）优先级：按照最小数值优先。如果你用此规则，优先级字段必须在订单上定义。
（6）加工时间：按照订单最小的加工时间优先。
（7）下达日期：按照最早开始日期优先。
（8）相反优先级：按照最大数值优先。如果你用此规则，优先级字段必须在订单上定义。
（9）闲散时间：按照最小闲散时间优先。
蔡颖
现在，约束计划的开发已经吸引各个领域的专家的高度注意，因为，它是有潜力解决现实中的非常难的问题。不仅基于很强的理论基础，而且，也广泛吸引商业利益。特别是在对变异的建模优化与满意问题。 无论我们是用先进的基因算法，还是用人机交互式的仿真方法，都需要对制造业的复杂约束，多目标优化，大规模的搜索和车间生产的不确定性的问题进一步研究，以适用实际需要。
在人类努力的大多领域里， 约束在不断的增加。它们在物理世界形成互相依赖。约束是在一些未知或变化里的简单的逻辑关系，在给定的领域里，每一个约束取一值。约束就限制了变化所带来的可能的值，它反映部分信息，约束也可以是不协调的，它可以在不同领域里互相约束。实际上，我们都用约束来指导推理和决策，是每天的常见行动的重要的一部分。如，我可以从5点到6点在那里。这就是典型的约束，我们用它计划我们的时间。自然，我们不能仅仅解决一个约束，因为约束很少是独立的。，所以，我们不得不接受的现实是这些问题比较复杂。
约束计划是基于约束规则的计算机系统的程序，约束计划的概念是详述问题的约束来解决问题。结果是找到让所有的约束满意的方案。 计划调度的实施的关键是基于约束规则，基于约束自动的调配资源，优化计划，来达到你所需要的计划目标。对离散的制造行业解决复杂的加工过程如多工序，多资源等（Jobshop调度），对重复式或流程式的制造行业解决顺序问题如优化排序等（Flowshop调度）。
如你的主要目标是一个满足所有任务规定的完成日期吗？ 还是你重点是提高设备利用率，减少非生产时间（准备时间和设备维护时间）？ 确定基本计划的目标是选择合适的规则的先决条件。一旦决定你的目标，你就可以选择规则来完成目标。
一、基于订单（Job-based）排程方法
工作中心WC A 有两个资源 工作中心WC B 有一个资源
订单MO-1 最高优先级。
订单MO-2 次优先级
基于订单任务示意图
是基于订单的优先级决定下一个订单的加工，可以自动识别订单的优先级和手工定义优先级，在计算机自动的根据规则的优选级排出生产计划后，还可以手工介入，修改优先级进行重排。以满足复杂的现实的需要。
约束规则如下：
（1）瓶颈：基于次要任务选择规则的排列。向前和向后方法来计划所有未分配的任务订单。重点是瓶颈资源的工序的。双向模式只计划需要指明瓶颈资源的任务。能用任何可得到的规则计划剩余任务。
（2）完成日期：基于最早完成日期。
（3）先到先服务：按照先到订单，先安排生产。
（4）升序订单属性值：按规定的订单升序的值排列。订单的属性可以是数值，字母。
（5）优先级：按照最小数值优先。如果你用此规则，优先级字段必须在订单上定义。
（6）加工时间：按照订单最小的加工时间优先。
（7）下达日期：按照最早开始日期优先。
（8）相反优先级：按照最大数值优先。如果你用此规则，优先级字段必须在订单上定义。
（9）闲散时间：按照最小闲散时间优先。
没有找到相关结果
已邀请:
RSS Feed
2 个回复
fxwu_001 (威望:0)
赞同来自:
蔡颖
二、基于事件（Event-based）的排程方法
是基于高利用率的方法。实现其计划的关键是二步导向的规则使用。有二个基本的规则：（1）工序选择规则OSR；（2）资源选择规则RSR。
基于事件示意图
针对不同产品和资源，必须选择不同的规则，在决定是使用工序选择规则或资源选择规则时，主要考虑的是什么是一个好的计划标准？一旦确定你的目标，你就可以选择工序和资源选择规则来完成目标。一般来说，先选择工序选择规则，然后选择合适的资源选择规则。在一些情况下，有关的资源选择规则被工序选择规则所决定。
工序选择规则OSR（ Operation Selection Rule）
至少一个资源是空闲的，二个或多个工序能用于这个资源，采用OSR。此规则决定那一个工序被加载。这就是决定计划结果质量好坏的关键因素。独立的工序选择规则详细介绍如下：
（1）最早完成日期：选择最早完成的工序（也许是订单完成日期）
（2）最高优先级第一：选择最高优先级（最低值）的工序
（3）最低优先级第一： 选择最低优先级（最高值）的工序
（4）最高订单属性字段：选择最高（最大）订单属性字段的工序
（5）最低订单属性字段： 选择最低（最小）订单属性字段的工序
（6）动态最高订单属性字段：选择动态最高（最大）订单属性字段的工序
（7）动态最低订单属性字段： 选择动态最低（最小）订单属性字段的工序
（8）计划档案订单：选择订单里出现先到先服务的工序
（9）关键率：选择最小关键率的工序。
关键率=剩余计划工作时间/（完成日期-当前时间）
（10）实际关键率：选择最小实际关键率的工序
实际关键率=剩余实际工作时间/（完成日期-当前时间
（11）最少剩余工序（静态）：选择最少剩余工序时间的工序
（12）最长等待时间：选择最长等待时间的工序
（13）最短等待时间： 选择最短等待时间的工序
（14）最大过程时间：选择最大过程时间的工序
（15）最小过程时间： 选择最小过程时间的工序
（16）最小工序闲散时间：选择最小工序闲散时间的工序。
订单任务的闲散时间=任务剩余完成时间-剩余工作时间
工序闲散时间=任务闲散时间/完成任务的剩余工序数
（17）最小订单闲散时间：选择最小订单任务的闲散时间的工序
（18）最小工作剩余：选择所有需要完成订单的最小剩余过程时间的工序。
资源选择规则（RSR） Resource Selection Rule
RSR选择工序加载到资源组内的哪一资源。
（1）最早结束时间：选择将要最先完成工序的资源
（2）最早开始时间： 选择将要最先开始工序的资源
（3）最迟结束时间： 选择将要最迟完成工序的资源
（4）与前工序一样： 选择被用于前一工序的资源
（5）非瓶颈最早开始时间：选择将要最早开始工序的非瓶颈资源
相关选择规则：
如果选择一工序选择规则，就自动的选择相应的资源选择规则。
（1）系列顺序循环：选择同样或下一个最高（最低）系列值的工序。当没有最高值的工序，顺序将相反，选择最低的工序。
（2）系列降顺序：选择同样或下一个最低系列值的工序
（3）系列升顺序： 选择同样或下一个最高系列值的工序
（4）最小准备系列： 选择最小准备时间及最近的系列值的工序。
（5）最小准备时间： 选择最小准备或换装时间的工序
（6）定时区的系列顺序循环：选择同样或下一个最高（最低）系列值工序。且只考虑在特定的时区里的订单完成日期里的工序。 当没有最高值的 工序，顺序将相反，选择最低的工序。
（7）定时区的系列降顺序：选择同样或下一个最低系列值工序。且只考虑在特定的时区里的订单完成日期里的工序。
（8）定时区的系列升顺序： 选择同样或下一个最高系列值工序。且只考虑在特定的时区里的订单完成日期里的工序。
（9）定时区的最小准备系列： 选择最小准备时间及最近的系列值的工序。且只考虑在特定的时区里的订单完成日期里的工序。
（10）定时区的最小准备时间： 选择最小准备或换装时间的工序，且只考虑在特定的时区里的订单完成日期里的工序。
工序选择规则的分析
标准的工序选择规则有二十多个标准规则。不同的规则对应不同的目标。这些规则可以进一步分成静态与动态的规则。
静态规则：为所有在排队中的订单，所有等待的工序提供一简单的索引机制。这些规则在每一次预先模拟时间时不需要再次评估。用于工序选择规则的参数是固定的。例如规则是最早完成日期规则，完成日期在顺序排程中从未改变。在排队中的第一个工序被分配到一等待资源。因为规则总是选择第一个等待工序，此规则执行的非常快。
动态规则：每一个在排队的工序被每一次调用的规则检查。因此，我们是基于当前的订单任务和系统的状态决定我们的选择。这个机制充分考虑了任何改变出现的时间和事件的结果。例如，最小工序空闲规则，因为工序的空闲值随时在改变。因为动态选择规则需要在每一次事先模拟以后检查在排队中的每一个工序，它比静态规则要慢一些。
为有助于分析规则，我们对规则进行分类。分成四个主要类别来对应四个不同的计划目标。它们是1、预先确定任务的参数。2、最小化任务缓慢。3、最小化任务流程时间。4、最大化设备利用率。我们将讨论每一个核心目标和相应的工序及资源规则以支持这些目标。规则的分类目的是帮助你为达到你的核心目标而缩小你的规则的选择。对某一类的规则选择是基于你的计划问题。每一个类别的规则都混合一些静态和动态的规则。
预先确定订单任务的参数：是基于预先定义订单任务的优先级来选择下一个工序或用户规定的属性字段（如成本）。一般来说，每一个规则由特性的最高，最低的值被调用。这类包括最高优先级，最低优先级，最高订单特性字段，最低订单特性字段，动态最高订单特性字段，动态最低订单特性字段，计划档案订单，最长等待时间，最短等待时间，和最大过程时间。
最高优先级和最低优先级是分别用最高或最低优先级选择工序的静态规则。
最高订单特性字段，最低订单特性字段是和优先级规则相似的静态规则，除了基于用户定义属性的选择。例如。 最高订单特性字段规则用一个属性字段定义，如由成本的最高值来选择任务。因为这是一个静态规则，它假设当订单任务正在等待处理时成本是不变的。
动态最高订单特性字段，动态最低订单特性字段规则是动态的。虽然这些规则执行较慢，它们也适应当订单任务正在等待时属性字段可以改变的情况。
计划档案订单规则是一静态规则，是基于已进入数据库的订单来选择订单。这个规则和先到先服务规则相似。
最长等待时间，最短等待时间规则是一动态规则，它是基于订单任务被等待计划的时间来选择工序。
最大过程时间规则是用最大过程时间来选择工序。预先确定任务的参数规则一般用于订单任务的特性的情况。（如优先级或成本）， 不考虑任务完成日期或设备利用率。因为这些规则忽略完成日期，它们典型更适应面向库存生产（MTS）环境，而不是面向订单生产环境（MTO）。
最小化任务延缓：在许多面向订单生产环境（MTO），计划目标是保证每一个订单任务按期完成。 最小化任务延缓的规则是建立一最小化延缓任务的计划。这类规则包括最早完成日期，最小化运行闲散时间，最小化订单闲散时间，关键率，和实际关键率。这些规则的最简单的是最早完成日期。这是一静态规则。虽然这个规则执行的非常快。这一类所有的规则是基于空闲时间计算的动态规则。空闲时间是完成日期和最早完成时间的差异。
最小订单闲散时间规则选择一个父项任务的工序，父项任务有最小的闲散时间。如它没被选择，这个订单任务大多可能是延迟的。
最小运行闲散时间规则是基于每一个工序的平均闲散时间（订单任务计算的闲散时间/剩余工序数量）而不是任务的剩余闲散时间。这个基于闲散时间的规则形成的基本想法是每一个剩余工序有一固有的风险， 根据它延迟的可能性，每一个工序的最小闲散时间的订单任务是最关键的。因此，如果我们在同样的闲散时间中选择订单任务，我们会选择最大剩余工序数量的订单任务，因次，根据每个工序最小闲散时间的规则来选择处理风险最大的订单任务。
基于闲散时间规则的最后的差异是关键率。这个规则选择父项任务有最大关键率的工序。关键率是剩余工作时间/（剩余工作时间+闲散时间）。注意只要闲散时间是正的数，分母大于它，关键率就小于1。就此，任务还没有延迟。如果关键率大于1，闲散时间是负数，任务就不能按期完成。关键率规则与最小工序闲散时间规则相似。相同的是，它们都是用闲散时间来计算的。不同的是它的剩余工作已完成。它的基本的前提是剩余闲散时间本身在决定最关键订单任务时并不重要，即相关的剩余工作已完成。如我们有许多剩余工作，那么，我们需要较大的闲散时间来保证我们的订单任务不能延迟。
最小化任务过程时间：在一些环境，关键问题是计划设备的效率来最小化订单任务的平均时间。 在最小化任务过程时间规则里忽略任务完成日期而集中于减少订单任务的时间。这类规则包括最小化流程时间，最少剩余工序，最小工作剩余。这类规则是基于过程时间最短的概念，减少所有订单任务的平均任务过程时间。
案例一：
有二个订单任务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， 系列顺序周期，和用系列的最少准备。另外，每一规则都与时间相连。所有这类规则都集中于减少转变成本，最大化的设备能力。这个转变成本能在一顺序相关的准备时间中设置。我们正努力消除设备的任何没有必要的非生产时间。
如果我们为整个工序的排序， 在连续的工序之间，要考虑顺序相关的准备时间及转变成本，此时，我们就能用系列规则。