13066158880
当前位置:首页 / 新闻动态

生产排产调度的灵魂:约束规则

admin 2022-08-08 新闻动态

现在,约束计划的开发已经吸引各个领域的专家的高度注意,因为,它是有潜力解决现实中的非常难的问题。不仅基于很强的理论基础,而且,也广泛吸引商业利益。特别是在对变异的建模优化与满意问题。

无论我们是用先进的基因算法,还是用人机交互式的仿真方法,都需要对制造业的复杂约束、多目标优化、大规模的搜索和车间生产的不确定性的问题进一步研究,以适用实际需要。

在人类努力的大多领域里,约束在不断的增加。它们在物理世界形成互相依赖。约束是在一些未知或变化里的简单的逻辑关系,在给定的领域里,每一个约束取一值,约束就限制了变化所带来的可能的值,它反映部分信息。约束也可以是不协调的,它可以在不同领域里互相约束。

实际上,我们都用约束来指导推理和决策,是每天的常见行动的重要的一部分。如我可以从5点到6点在那里。这就是典型的约束,我们用它计划我们的时间。自然,我们不能仅仅解决一个约束,因为约束很少是独立的。所以,我们不得不接受的现实是这些问题比较复杂。

约束计划是基于约束规则的计算机系统的程序,约束计划的概念是详述问题的约束来解决问题。结果是找到让所有的约束满意的方案。计划排产调度的实施的关键是基于约束规则,基于约束自动的调配资源、优化排序来达到你所需要的计划目标。

对离散的制造行业解决复杂的加工过程如多工序、多资源等(Job Shop调度),对重复式或流程式的制造行业解决顺序问题如优化排序等(Flow Shop调度)。

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

一、基于订单(Job Based)排程方法

基于订单的优先级决定下一个订单的加工,可以自动识别订单的优先级和手工定义优先级,在计算机自动的根据规则的优先级排出生产计划后,还可以手工介入,修改优先级进行重排,以满足复杂的现实的需要。

基于订单(Job-based)约束规则如下:

(1)瓶颈:基于次要任务选择规则的排列。向前和向后方法来计划所有未分配的任务订单。重点是瓶颈资源的工序的。双向模式只计划需要指明瓶颈资源的任务。能用任何可得到的规则计划剩余任务。

(2)完成日期:基于最早完成日期。

(3)先到先服务:按照先到订单,先安排生产。

(4)升序订单属性值:按规定的订单升序的值排列。订单的属性可以是数值,字母。

(5)优先级:按照最小数值优先。如果你用此规则,优先级字段必须在订单上定义。

(6)加工时间:按照订单最小的加工时间优先。

(7)下达日期:按照最早开始日期优先。

(8)相反优先级:按照最大数值优先。如果你用此规则,优先级字段必须在订单上定义。

(9)闲散时间:按照最小闲散时间优先。

二、基于事件(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,闲散时间是负数,任务就不能按期完成。关键率规则与最小工序闲散时间规则相似。相同的是,它们都是用闲散时间来计算的。不同的是它的剩余工作已完成。它的基本的前提是剩余闲散时间本身在决定最关键订单任务时并不重要,即相关的剩余工作已完成。如我们有许多剩余工作,那么,我们需要较大的闲散时间来保证我们的订单任务不能延迟。

最小化任务过程时间:在一些环境,关键问题是计划设备的效率来最小化订单任务的平均时间。在最小化任务过程时间规则里忽略任务完成日期而集中于减少订单任务的时间。这类规则包括最小化流程时间,最少剩余工序,最小工作剩余。这类规则是基于过程时间最短的概念,减少所有订单任务的平均任务过程时间。

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

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

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

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

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

生产化工纤维材料时,根据产品的型号和厚度对品种进行分类,对品种的最优排产。如取最小值= { 3m/1。4m, 6m/1。4m,…。}来决定在哪个订单的加工顺序及哪个资源最经济。

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

在热处理时,温度是间隔的增加到最高,然后降低。最小准备系列规则结合最小准备时间规则和系列顺序循环规则。最小准备时间和最靠近的系列值的工序被选择。

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

资源选择规则分析

虽然工序选择规则在决定生产计划方面起着重要作用。资源选择规则在加工处理中也能起重要作用。尤其在最小准备时间和系列工序选择规则上,资源选择规则是由工序选择规则自动决定的。(如选择最小准备时间工序规则,最小准备时间资源选择规则被自动选择)。然而,在选择所有的剩余工序选择规则时,你必须在资源选择规则中选择其一。

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

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

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

非瓶颈的最早结束时间规则将首先完成工序的非瓶颈资源。非瓶颈最早开始时间规则将首先开始工序的非瓶颈资源。

三、基于物料约束(Material Constrain)

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

静态物料约束规则(SMC)

先对每一个物料从ERP系统导入建立可用量清单,最早开始的订单和被分配的物料,随着物料业务,订单日期的延迟,或变化,系统会自动调整或显示订单的变化。

动态物料约束规则(DMC)

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

取出库存成套约束(Take from stock kit)

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

放入库存成套约束(Put to stock kit)

定义从工序的父项产出结果。在我们做计划时,考虑产出的约束,必须考虑库位所能容纳的约束。

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

总之,制造业对客户需求的响应越来越强烈。 现在生产计划调度系统正开始将基于约束规则基因搜寻和模拟仿真模式结合起来,解决制造同步化问题和工厂的顺序冲突问题。

现在,约束计划已经成功应用到许多不同问题领域。它和分析DNA结构一样多样化。对医院的时间表和工业的排程。实践证明它能较好适应解决现实的问题。因为,许多应用领域自然的需要约束。分派问题也许是第一个工业应用约束解决工具。用甘特图来描述计划可能是最成功的应用领域如有限约束排程。

在现实中,约束计划可以广泛的运用,但是当前的工具也有可能没有涉及到的领域或局限和缺点。无论是从理论上,还是实际的观点来看,约束的定义促使问题可追踪是非常重要的,约束计划的有效性仍然是不可预测的:何时,如何使用约束。通常直觉是决策的最重要的部分。有时,盲目的快速搜寻如按时间顺序后排比约束进化(基因算法)更有效。在许多约束模型里的特别问题是成本优化。有时,它是对改善起初的方案是非常困难的。且一个小的改善就会花去很多时间。

约束计划也在不断的进化,它们能动态的增加约束。大部分情况下,约束系统产生的计划是可执行的。除了机器故障,延迟的计划,在最坏的情况下,新订单的接受。这是需要快速的重排计划或提高当前的方案来解决未预料的事件。同时,在通常较紧计划优化的方案和可以解决较少差异的,稳定的,次优化的方案之间交替选择。

当前的约束满意系统的缺点标志着未来研究发展方向,在它们之间,建模看上去是最重要的之一。已经开始讨论使用全局约束,把主要的约束预先设置到软件包。(如所有不同的约束规则)。目前,建模语言较多的使用ILOG公司的(ILOG Solver)来表示约束问题。(如名列前矛的商业管理软件供应商均采用此技术)

从较低层次的观点,可视化的技术越来越流行,他们帮助定义系统的瓶颈。各种约束解决方法的交互研究是最具挑战的问题之一。混合算法结合各种约束技术是这个研究的结果。另外感兴趣的研究领域是解决协同和对应的结合的理论。约束满意技术和传统的OR(Operation Research)方法如整数规划是另外的挑战。研究平行和并行的约束已作为提高效率的方法,在这些系统里,多层代理技术可能是最有前景。

但是,随着车间物联网、工业大数据的成熟,通过定位系统的场景化,嵌入式规则或算法和传感器,可以做到分布式控制,使得排产调度更加灵活与智能化。


推荐新闻