生产排程算法及工业应用陶春周建阳倪骅（北京营普优化科技有限公司，北京100085）摘 S：生产排程何题是工业生产和实际生活中常见的一类问題.该类问题绝大多数都是复杂的NP-hard 问題，求解这些问题非常困难.本文使用自然约束语言NCL设计生产排程问題的模型.得益于NCL的 混合集合规划算法系统，该模型可以考虑复杂的多约束、多目标的生产推程问题.同时，基于NCL的 逻辑推理功能，通过What-If.式交互，可在甘特图上宜观地对结果进行分析和修改.关键词：生产排程自然约束语言混合集合规划1引言生产排程问题，又称排序问题或生产调度问题，是针对一项可分解的工作（如产品制 造），探讨在尽可能满足约束条件（如交货期、工艺路线、资源情况等）的前提下，通过下 达生产指令，安排其每步操作使用哪些资源、其加工时间及加工的先后顺序，以获得产品 制造时间或制造成本的最优化.生产排程问题是对于具体生产问题的一种抽彖和简化.即便对单机排序问题，如果考 虑n个作业而每个作业只考虑加工时间及与序列有关的准备时间，就可以规约到n个城市 的TSP问题.一般的生产排程问题就更为复杂了，也就是说，绝大多数的生产排程问题都 是NP-hard问题。常规的优化算法研究这些生产排程问题己经有很长一段时间了，而本文 采用一种全新的算法和建模思想，使用逻辑优化语言NCL对复杂的多约束、多目标的生产 排程问题进行建模研究。2 NCL介绍自然约束语言NCL是一门集逻辑、优化算法及求解规则于一体的业务建模和问题求解 的智能描述型语言。NCL采用混合集合规划算法系统，支持在多种类型（特别是集合 类型）上的混合约束推理，突破了传统的线性求解机制，通过域切割算法体系和高效、灵 活的求解规则控制，实现对复杂优化问题的求解。2.1 NCL语言的特点NCX是一门以基础数理逻辑为语法的运筹学自然语言人工智能的模式识别技术广泛 应用于NCL的自然语法分析及语义识别，使用户在面对复杂的工业优化问题时，可以在更 高层级关注对问题的建模。混合集合规划（Mixed Set Programming,简称MSP）囚构成NCL的算法内核：支持求 解布尔值、实数、整数、时间、索引及集合类型上的混合约束；支持一阶逻辑、集合推理、 实数域数值分析等。混合集合规划支持对复杂大规模问题进行业务逻辑一级的建模并求解.NCL是一门可以对搜索策略高度简洁地进行编程的语言。它可以简单灵活地实现对搜8 索树的逻辑控制，包括对分支、回溯、搜索模式的逻辑控制，对软约束的应用，对多目标 优化及优化步长的控制，对近似解的控制等.2.2 NCL语言的算法与求解系统NCL的算法理念源于约束规划(Constraint Programming),它的核心思想是通过约束 间的网状关系联合推理，合理、有效地切削组合优化问题的解空间，抑制组合爆炸，从而 达到求解问题的目的。NCL以混合集合规划(MSP)为算法内核，其算法属于精确算法.混 合集合规划并不是在推理中简单地使用集合符号，而是严格、完备地使用集合论作为推理 体系的一部分，从而实现一种能够超越线性限制(不同于基于线性松弛算法的线性解算器) 的、更通用的算法系统来求解约束满足问题。简而言之,NCL的求解系统基于约束切割(Constraint Cut)与深度优先搜3(Depth-First Search)原则，其求解框架如图1所示。首先用约束推理切割解的搜索空间；之后通过査 询关键变量对解空间进行完备的搜索。2.3基于NCX的工程化开发实际生活中的优化排程问题远比学术问题复杂，如下面所列几项。数据逻辑复杂、约束繁琐；问题规模大，往往是上万道工序；除了优化模型和算法，还需要相应的结果可视化；要求对结果的可视化交互，要求对结果进行二次优化；用户在需求分析过程中对问题的理解经常变化；实施困难：周期长、见效慢、成本高NCL是一门支持工程化开发的运筹学语言.NCL中包含丰富的、基础性的、可参数化 的优化模块，这些模块往往独立于行业，具有很强的通用性.NCL在需求不断变化时可以 进行低成本系统调整，便于使用者进行开发和维护此外，NCL中包含一体化的结果显示,如甘特图、地图、直方图和统计表等，便于开发者进行高效、并行的开发和部署。3建模及求解3.1建模3.1.1生产排程中的约束生产排程的主模型是在满足订单优先级、设备生产能力、订单和其工序的生产工艺等 约束情况下，按照设备最大利用率、订单最小延迟数等优化目标，在一个周期内，对各个 设备上工序进行优化排序.生产排程中的基础约束包括：资源的能力约束：资源的工作时间约束；资源的工作日历约束；订单的优先级约束；不同订单的耦合约束；订单各工序的次序约束；订单时间窗口约束：工序的资源需求约束；工序的时间窗口约束3.1.2生产排程的建模NCL建模的重点杲对问题进行数理逻辑描述以设计优化问题的数学模型。本节介绍对 生产排程问题中几个主要约束的建模. 工作日历约束对于任意一个工序i,工序实际加工时间长度workTimeTask,等于该工序所需资源的可 工作时间ScheduIeResourceregteTuiq和该工序加工时间区间TimeTask,交集WorkTimeTaskj 的长度.复杂的工作日历约束在NCL中高度简洁的描述如下。VieTASK(WorkTimeTaskj = TimeTaskj c ScheduleResourcegjursTaskj，# WorkTimeTaskj = workTimeTask；.) 工序对资源及时间的需求约束对于任意两个不同工序i,j,所用资源resourceTaskj不同或者加工时间TimeTask,不冲 突。此约束称为二维排程约束，是生产排程的核心约束.VijelASKresourceTaskj * resourceTaskj V TimeTaskjn TimeTaskj = 0 订单的时间窗口约束订单i的加工时间TimeJob,是该订单的所有工序的加工时间集合TimeTask Z并，要求 TimeJobi在给定的开工时间tlJobi和完工时间o之间.VieJOB(TimeJobj = U j .丁圖會 TimeTaskj,TimeJobj u tlJobi, t2JobJ,)，3.2求解规则在本模型的求解规则中，首先査询工序所用资源，然后确定工序的开工时间，具体如 下.VieTASK-(maxi e TaskCriticalResource,%工序按资源类分组mintlTasku%顺序性搜索mint2Taski%顺序性搜索minslackResourceTasku%全局最小松弛度min# resourceTaskj,%局部最小松弛度min# TimeTask”%局部最小松弛度Vj e A resourceTask,- (minslackTimeResourcej.%局部最小松弛度minsumTimeResourcej %贪婪性)(resourceTaskj = j ?,tlTask, = ?,),在搜索策略的设计中，我们将精确算法和启发式思想有机地结合在一起.一方面，生 产排程模型中所有的约束都被严格满足，确保求解的精确性；另一方面，求解规则中的最 小松弛度和顺序性尊原则是启发式的，以确保在求解过程中灵活、个性化地控制搜索树过 程.完备的二维排程算法和经过大量数据验证的通用型搜索策略确保对满足所有约束的可 行解的求解，井在此基础上以回溯方式寻找更优解直至求得最优解.3.3结果输出生产排程的结果输出主要有表格、甘特图、直方图等几种形式。 将订单、工序优化后的时间和资源安排输出到表格中，见表 用甘特图表示订单、工序的安排情况.用户不仅能直观地査看生产计划安排，还可 对计划进行What-If.交互，如图2所示. 用负荷图(直方图)呈现资源的周期利用率，以清晰地展现关键资源的使用状况, 如图3所示.3.4交互功能交互功能是在结果可视化的基础上，对己有的优化排程结果进行局部调整.其重要性 主要体现在：一方面是对突发事件的应急处理，即对生产条件发生变化后的情况迅速地进 行处理，以生成新的计划；另一方面体现在通过不断的What 交互进行分析并改善排程结果。裹1订单执行计划長订单 编号产品编号下达时间載止时间时何安排订单延期BP-1BP2009/01/01 8:002009/01/02 22:002009/01/02 12:04:55-2009/01/02 13:47:250天BP2BP2009/01/01 8:002009/01/02 22.002009/01/02 12:54:55-2009/01/02 14:37:240天HF-1HF2009/01/01 8:002009/01/02 22:002009/01/02 10:24:57-2009/01/02 20:45:280天HQ-1HQ2009/01/01 &002009/01/02 22:002009/01/02 08:00:00-2009/01/02 15:58:390天HQ-2HQ2009/01/01 8:002009/01/02 22:002009/01/02 09:09:59-2009/01/02 16:54:530天HQ-3HQ2009/01/01 8:002009/01/02 22:002009/01/02 10:19:58-2009/01/02 18:06:000天HQ-4HQ2009/01/01 8:002009/01/02 22:002009/01/02 11:29:57-2009/01/02 19:15:590天HQ-5HQ2009/01/01 8:002009/01/02 22:002009/01/02 12:39:56-2009/01/02 21:41:420天HQ-6HQ2009/01/01 8:002009/01/02 22:002009/01/02 18:09:51-2009/01/02 21:14:520天HQ-7HQ2009/01/01 &002009/01/02 22:002009/01/02 19:19:50-2009/01/02 22:24:510天HQ-8HQ2009/01/01 8:002009/01/02 22:002009/01/02 20:29:49-2009/01/02 23:34:500天图2设备工序甘待图Hstoevn基础交互功能包括以下几类.12 删除订单,是指在结果甘特图上，将指定的单个或者多个订单从计划中删除的操作. 生产中如果遇到有些订单停止生产，则可以通过该功能来删除订单，并进行二次优化。 插入订单,是指在结果甘特图上，将一个或多个新的订单安排到原有计划中的操作。 生产中如果遇到紧急插单的情况，可以选择不可拖期插入，二次优化算出的结果可以保证 新插入的订单无拖期。 拖拉，是指在结果甘特图上，对指定工序的时间或者所用资源用鼠标进行直觉式修 改的操作。拖拉操作可以改变指定工序的加工时间，也可以改变其所用的资源。拖动后优 化引華会进行