文摘
摘要先进的规划和调度(APS)多层次结构化产品的问题。约束规划模型构建问题考虑的优先约束,容量约束,释放时间和到期日期。提出了一种新的约束编程(CP)方法的总成本降到最低。这种方法是基于通过分支界限法迭代求解。在每个节点,约束传播技术是适应域滤波和一致性检查。三个分支策略相比,提高了搜索速度。计算研究的结果表明,该CP方法执行比传统的混合整数规划(MIP)方法。和二进制约束的启发式分支策略比其他两个分支策略更有效。
1。介绍
规划流程的复杂性使得大多数的公司开发企业资源规划(ERP)系统来处理它1]。然而,随着ERP系统的核心模块规划,物料需求计划(MRP)有其局限性。MRP通常会使计划根据有限的物质需求和无限的容量需求,与此同时,生产提前期,实际上是根据生产计划是预先确定的。应对这些限制,先进的规划和调度(APS)已经从软件开发人员和学者。相比,这些传统的规划系统,APS系统提供了优势,计划可以优化边界内的材料和能力约束(2]。
院士和商业APS提供者(如SAP APO、i2和Asprova)试图构建有效的方法来生成详细的生产计划平衡市场的需求与资源能力。数学规划和启发式算法通常被用来实现这种平衡。启发式算法通常专注于瓶颈资源(3]。例如,龚和陈省身提出一个启发式工厂规划算法(HFPA)来解决工厂规划问题与多个最终产品的产品结构。它首先识别瓶颈工作,中心然后排序工作根据不同的标准,最后在三个迭代计划工作(4]。以往的研究往往采用混合整数规划模型来表示计划和调度问题。月球等人提出一种先进的规划和调度模型集成能力制约因素和优先约束最大完工时间最小化5]。陈和霁提出一个混合整数规划模型明确考虑能力约束、操作程序、交货期和约会multiorder环境中(6]。Orenk等人扩展这个模型的情况,一个操作可以分配给其他机器(7]。基本模型的扩展包括顺序相依设置和机器之间的传输时间8]。虽然数学规划和启发式算法被广泛使用,他们的障碍也明显。数学规划方法耗时太长,当问题规模很大,这使得它不实际,而每一个启发式算法只适用于一种特定的问题(9]。
约束编程(CP)方法是一种相对较新的技术。它已被确认为一种战略方向和工业应用的主要形式生产计划和调度10,11]。已经证明是有效的在处理组合优化问题,因为它的范围广泛的代表性和普遍适用的解决算法。CP最初开发解决约束满足问题(CSP)找到一个值为每个变量,约束指定某些值的子集不能一起使用。它一直延伸到约束优化问题(警察),添加了一个目标函数(如成本)。优化解决方案是通过解决问题的目标函数的CSP写成一个约束,迫使它等于一个新值。基于调度规程,研究如何解决调度问题通过使用CP。它是分析和讨论通过使用理论和例子包括目标、如何处理决策变量和惩罚因素在文献[12]。研究小组还提出了一种综合方法,使用MILP的互补优势和CP解决合并后的计划和调度问题在APS系统作为核心优化引擎的一部分(13]。约束编程技术,提出了一种新的遗传算法解决一个先发制人的和无优先调度模型为一体的先进的调度问题在文献[14]。实验结果表明,该方法是有效的。然而,这仅仅是用于作业车间调度问题在一个机器。文献[15)集中于构建一个约束编程模型在柔性制造系统中,但没有讨论解决算法。
摘要约束编程方法,先进的规划和调度系统多层次结构化产品。约束编程模型和多层次结构化产品优先考虑的约束条件,提出了容量约束,释放时间,到期日期。警察将约束规划方法的求解过程与分支定界算法。约束传播和分支策略讨论CSP。本文组织如下。部分2我们研究描述了APS的问题;部分3介绍了约束编程模型和求解算法的细节;计算研究说明这种模型和算法的有效性4;一些结论和进一步的研究方向将部分5。
2。问题描述
先进的规划和调度问题在本文中定义的情况类似文献[6处理它的混合整数规划(MIP)方法。产品被认为是在这个系统多层次结构。产品树结构(物料清单)定义了优先约束的调度问题(图1)。圆了操作中的信息数量和其处理机器。数量上的箭头显示了最终产品所需材料的数量(默认数量为1)。例如,最终产品五(装配5 - 6)是由一个组件(5 - 3)和两个组件(5 - 4和盘中)。与此同时,组件(5 - 3)是由组件(5 - 1和5 - 2)。这种多层次结构是典型的工业生产,往往比这个例子更复杂。
假设生产系统包含机器和产品。每个产品有操作。每个操作可以处理在一个专用的机器。产品的最优安排应该发现最小化总成本包括迟缓的成本和早期的成本。假定一些条件来降低问题的复杂性。产品树结构,释放时间,到期日期是提前知道同样操作的处理时间。lot-for-lot策略是采用制造产品,而设置时间可以忽略不计。
3所示。约束编程方法
的经典定义一个约束满足问题(CSP)如下。CSP是三倍,在那里是一个元组变量,是对应的域的元组这样,是一个元组的约束。CSP是一个解决方案元组,在那里和每个是满意的。该算法求解约束模型可以分为两类:推理和搜索(16]。推理技术可以消除大型地方约束传播子空间的方法。搜索系统地探讨解决方案,经常和单一故障消除子空间。这两种基本策略通常在大多数应用程序相结合。
CSP提供了一个可行的解决方案满足所有的约束。但在现实生活中,我们试图找到一个最优或相对更好的解决方案的一个明确的目标,比如最小化成本或时间。因此,约束优化问题的紧急从CSP (COP)被扩展。警察是基于CSP的解决算法。域定义的目标函数值下界(磅)和上限(乌兰巴托)和逐渐限制与计算过程。目标函数是写成一个约束,迫使它等于(或不足,或以上)一个新值(一般来说,这是一个班轮与磅和乌兰巴托)。然后警察被传送到解决CSP迭代。一旦找到可行解,磅或乌兰巴托是目标是改变和额外的约束限制。搜索终止当磅=乌兰巴托或所有的节点都清楚。
3.1。约束编程模型
为了构建APS约束编程模型,下面的符号是用来描述问题: :产品指数 :机器指数 :操作指数。参数 :数量的产品 :数量的机器 :操作产品的数量 :th操作的产品 :这部分的数量需要 :操作的处理时间 :产品的数量 :产品的释放时间 :由于时间的产品 :1,如果之前操作t否则,0 :每天的有效工作时间TC:迟到的产品成本每一天的工作电子商务:早期产品的成本每一天的工作。变量 :生产时间 :早期的产品(真正的) 产品:迟到的日子(真正的) :早期的产品(整数) 产品:迟到的日子(整数)。
变量约束模型的先进的规划和调度问题是每个操作的开始时间。的变量和分别表示持续时间和结束时间的操作。这个方程澄清他们的关系。节中描述的问题2可以制定以下模型: 受
目标是最小化总成本包括早期的成本和迟缓的成本。迟到的处罚和早熟的意思是即时(提前或延迟发货导致增加成本)。
产品的多级结构是由二进制参数定义的,它可以表达所有的树结构。约束(2)意味着每个操作的开始时间不应小于产品的释放时间。约束(3)定义了每个操作的持续时间。约束(4)表明,每个产品的完成时间应小于或等于考。约束(5)暗示,如果两个操作需要相同的机器,然后一个人不能在年底前开始其他操作。约束(6)确保优先约束基于树结构的产品。约束(7)和(8)定义早期时间和迟到的时间(实际类型)的每个产品。约束(9)和(10)时间值的类型转换为整数类型,因为单位惩罚成本的天。约束(11)表示变量的域。
3.2。解决方法
提出了约束编程模型是一个警察,可以转移到csp的一个目标函数值约束
我们删除了目标函数(1)和添加约束(12CSP)结构。警察可以生成的最优解迭代解决CSP,不断限制约束(12)。详细的解决步骤可以概括如下。
步骤1。计算目标函数的磅,乌兰巴托。
步骤2。添加约束,在那里CSP。
步骤3。解决CSP和设置一个固定的时间截止。如果一个可行的解决方案发现,乌兰巴托是目标函数的值更新。别的,更新。
最初,乌兰巴托的目标函数通过计算解决CSP无约束(12)找到一个初始可行解。乌兰巴托是设置的值等于。而磅的目标函数计算的约束传播技术来确定每个操作的时间窗口将在部分3.2。1磅制定如下: 在哪里等于最后操作的最早开始时间+操作的处理时间。相应地,=最后操作的最新的开始时间+操作的处理时间。符号是最小的整数大于或等于。自从开始上限通常很差,我们减少了差距通过执行一个叉状分枝的搜索。
摘要解决CSP在步骤的过程3基于深度优先搜索树的探索(图2)。在每个节点,会触发一个传播阶段为了检测可能的不一致性,降低了搜索空间。如果这个阶段检测不一致,前面的回溯算法,消除了影响决定。如果没有检测到不一致,一个分支的过程是递归地应用到子节点,直到找到一个解决方案或直到所有搜索空间探索。所以在接下来的两个部分,我们将介绍约束传播技术和分支策略直接影响搜索速度。
3.2.1之上。约束传播
传播阶段基本以减少搜索空间的大小,避免探索一个指数大小的空间。可以基于约束传播时间或资源。通常,时间表方法使用时间窗口来表达当使用约束传播基于时间的约束。一个操作的开始时间的时间窗口是,在这最早开始时间和方式意味着最新的开始时间。时间窗口将收紧约束传播过程中。一旦改变了一个操作的时间窗口,那么成功的时间窗口和之前的操作也将改变。约束传播规则的时间表如下:
每个操作的最早开始时间可以更新公式(14)和(15)。公式(14)定义开始操作之前没有任何操作。最早开始时间成功的更新操作是基于公式(15伴随着前操作的变化。相应地,可以更新最新的每个操作开始时间由公式(16)和(17)。公式(16)定义了操作没有任何操作成功。更新最新的开始时间前操作基于公式(17伴随着成功操作的变化。
3.2.2。分支策略
最早的搜索方法用于CP算法generate-and-test (GT)算法。效率很差,因为noninformed生成器和后期发现的不一致,因此提出了回溯(BT)算法。回溯是基本“完整”的搜索方法约束满足问题。基本的回溯搜索建立一个部分解决方案通过选择变量的值,直到达到一个死胡同,无法持续扩展的部分解决方案。
几个分支策略提出了标准作业车间问题[17]。搜索树的分支策略决定了形状直接影响着搜索速度。在本部分中,我们将考虑三个启发式分支策略。
策略1(二元约束的启发式):它创建一个二叉搜索树的分支定义的两种可能脱节。约束(5)定义了两种可能性。假设两个操作和共享相同的机器,约束发布一个分支和约束对应于另一个分支。
策略2 (variable-based启发式):我们使用变量顺序启发式选择最小的变量域的大小。约束模型中的变量是每个操作的开始时间。域变量的区间的最早开始时间和最新的开始时间。我们选择的变量最小域大小和设置值升序排序。
策略3(任务型启发式):它由一个任务选择策略的定义和价值选择的启发式任务开始时间。我们选择最小的最新任务完成时间,选择值降序排列。
4所示。计算研究
说明拟议的CP先进的规划和调度的方法,给出了一个简单的例子包括以下五种类型的产品和五个类型的机器。图1给出了表征产品的树结构,显示了处理机器。表1提供了有关这些产品的更多信息。一个产品描述由三联体(),需求的数量,是释放时间,是到期日期。操作的处理时间也是这个表所示。迟到和早熟的成本是每天每天25和图5。有效的工作时间是每天80元。
示例模型解决或优化软件工具,称为Xpress-MP 2.53 GHz CPU和4 GB RAM。甘特图如图3(我们添加一个虚拟机分配的虚拟任务)。考的是392。产品4是延迟了两天。优化的总成本是50。
基准不存在这个问题,因为它认为所有的产品树结构,不仅作业车间类型。因此,我们生成的测试问题的基础上,简单的例子。我们扩展数据集三种类型的问题,不同数量的产品,最大数量的操作和机器的数量(表2)。每种类型包含三个实例。实例类型的a - 1 a - 3是5 * 6 * 5(小实例)。实例类型的b - 1酮是10 * 6 * 5(中实例)。实例类型的颈- 1对颈5 * 21 * 5(大型实例)。
MIP和CP模型,分别解决了Xpress-mmxprs和Xpress-Kalis模块。表3显示的大小CP和MIP模型的变量和约束的数量根据上述问题实例。MIP模型包含所有问题的变量数量明显高于CP模型,在约束的数量小于CP模型。计算时间和客观价值也是这个表所示。它应该还指出,当问题规模大,MIP的解决时间迅速增加,甚至不能得到最优解在可接受的时间。大胆的实例结果证明是最优的。最大计算时间将1000年代。CP方法在9中7最优解实例,而MIP法只有5。CP方法的计算时间(策略1)明显小于MIP的方法。
我们计算的分支策略也比较研究。迭代的计算时间和回溯如表所示4。它显然是表明分支策略1优于其他策略的高计算速度和减少回溯时间。
5。结论和未来的工作
我们提出了一种约束编程方法来解决多层次结构化产品先进的规划和调度问题。的合作约束规划方法和分支定界算法应用于处理CP模型。这是被证明是比MIP模型更有效。此外,三个分支策略约束模型进行了比较。结果表明,二元约束分支策略更好的性能。
这项研究表明,约束编程高级计划和调度问题是有效的。虽然我们认为是所有类型的产品结构,仍有一些条件我们并没有考虑到,如设置时间和替代操作(18]。在未来的研究中,我们将构建一个更全面的模型更接近实际生产和设计一个混合算法来解决这个问题。
利益冲突
作者宣称没有利益冲突有关的出版这篇文章。
确认
这项工作已经由上海优秀青年教师项目(shu11008),上海大学的创新发现项目(sdcx2012015)和浙江省自然科学基金(Y6110045)。