1 引言
生产排程问题，又称排序问题或生产调度问题，是针对一项可分解的工作(如产品制造)，探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况等)的前提下，通过下达生产指令，安排其每步操作使用哪些资源、其加工时间及加工的先后顺序。以获得产品制造时间或制造成本的最优化。
生产排程问题是对于具体生产问题的一种抽象和简化。即便对单机排序问题，如果考虑n个作业而每个作业只考虑加工时间及与序列有关的准备时间，就可以规约到n个城市的TSP问题。一般的生产排程问题就更为复杂了，也就是说，绝大多数的生产排程问题都是NP-hard问题。常规的优化算法研究这些生产排程问题已经有很长一段时间了，而本文采用一种全新的算法和建模思想，使用逻辑优化语言NCL对复杂的多约束、多目标的生产排程问题进行建模研究。
2 NCL介绍
自然约束语言NCL是一门集逻辑、优化算法及求解规则于一体的业务建模和问题求解的智能描述型语言。NCL采用混合集合规划算法系统，支持在多种类型(特别是集合类型)上的混合约束推理，突破了传统的线性求解机制，通过域切割算法体系和高效、灵活的求解规则控制，实现对复杂优化问题的求解。
2.1 NCL语言的特点
NCL是一门以基础数理逻辑为语法的运筹学自然语言。人工智能的模式识别技术广泛应用于NCL的自然语法分析及语义识别，使用户在面对复杂的工业优化问题时，可以在更高层级关注对问题的建模。
混合集合规划(Mixed Set Programming，简称MSP)构成NCL的算法内核：支持求解布尔值、实数、整数、时间、索引及集合类型上的混合约束；支持一阶逻辑、集合推理、实数域数值分析等。混合集合规划支持对复杂大规模问题进行业务逻辑一级的建模并求解。
NCL是一门可以对搜索策略高度简洁地进行编程的语言。它可以简单灵活地实现对搜索树的逻辑控制，包括对分支、回溯、搜索模式的逻辑控制，对软约束的应用，对多目标优化及优化步长的控制，对近似解的控制等。
2.2 NCL语言的算法与求解系统
NCL的算法理念源于约束规划(Constraint Programming)，它的核心思想是通过约束间的网状关系联合推理，合理、有效地切削组合优化问题的解空间，抑制组合爆炸，从而达到求解问题的目的。NCL以混合集合规划(MSP)为算法内核，其算法属于精确算法。混合集合规划并不是在推理中简单地使用集合符号，而是严格、完备地使用集合论作为推理体系的一部分，从而实现一种能够超越线性限制(不同于基于线性松弛算法的线性解算器)的、更通用的算法系统来求解约束满足问题。
简而言之，NCL的求解系统基于约束切割(Constraint Cut)与深度优先搜索(Depth-First Search)原则，其求解框架如图1所示。首先用约束推理切割解的搜索空间：之后通过查询关键变量对解空间进行完备的搜索。
图1 NCL的求解框架
2.3 基于NCL的工程化开发
实际生活中的优化排程问题远比学术问题复杂，如下面所列几项。
- 数据逻辑复杂、约束繁琐；
- 问题规模大，往往是上万道工序：
- 除了优化模型和算法，还需要相应的结果可视化：
- 要求对结果的可视化交互，要求对结果进行二次优化；
- 用户在需求分析过程中对问题的理解经常变化；
- 实施困难：周期长、见效慢、成本高……
NCL是一门支持工程化开发的运筹学语言。NCL中包含丰富的、基础性的、可参数化的优化模块，这些模块往往独立于行业，具有很强的通用性。NCL在需求不断变化时可以进行低成本系统调整，便于使用者进行开发和维护。此外，NCL中包含一体化的结果显示，如甘特图、地图、直方图和统计表等，便于开发者进行高效、并行的开发和部署。
3 建模及求解
3.1 建模
3.1.1 生产排程中的约束
生产排程的主模型是在满足订单优先级、设备生产能力、订单和其工序的生产工艺等约束情况下，按照设备最大利用率、订单最小延迟数等优化目标，在一个周期内，对各个设备上工序进行优化排序。生产排程中的基础约束包括：
- 资源的能力约束；
- 资源的工作时间约束；
- 资源的工作日历约束；
- 订单的优先级约束；
- 不同订单的耦合约束；
- 订单各工序的次序约束；
- 订单时间窗口约束；
- 工序的资源需求约束：
- 工序的时间窗口约束……
3.1.2 生产排程的建模
NCL建模的重点是对问题进行数理逻辑描述以设计优化问题的数学模型。本节介绍对生产排程问题中几个主要约束的建模。
①工作日历约束
对于任意一个工序i，工序实际加工时间长度workTimeTaski等于该工序所需资源的可工作时间ScheduleResourceresourceTaski；和该工序加工时间区间TimeTaski交集WorkTimeTaski的长度。复杂的工作日历约束在NCL中高度简洁的描述如下。
②工序对资源及时间的需求约束
对于任意两个不同工序i，J，所用资源resourceTaski不同或者加工时间TimeTaski不冲突。此约束称为二维排程约束，是生产排程的核心约束。
③订单的时间窗口约束
订单i的加工时间TimeJobi是该订单的所有工序的加工时间集合TimeTask之并，要求TimeJobi在给定的开工时间tlJobi和完工时间t2Jobi之间。
3.2 求解规则
在本模型的求解规则中，首先查询工序所用资源，然后确定工序的开工时间，具体如下。
在搜索策略的设计中，我们将精确算法和启发式思想有机地结合在一起。一方面，生产排程模型中所有的约束都被严格满足，确保求解的精确性；另一方面，求解规则中的最小松弛度和顺序性等原则是启发式的，以确保在求解过程中灵活、个性化地控制搜索树过程。完备的二维排程算法和经过大量数据验证的通用型搜索策略确保对满足所有约束的可行解的求解，并在此基础上以回溯方式寻找更优解直至求得最优解。
3.3 结果输出
生产排程的结果输出主要有表格、甘特图、直方图等几种形式。
①将订单、工序优化后的时间和资源安排输出到表格中，见表1。
②用甘特图表示订单、工序的安排情况。用户不仅能直观地查看生产计划安排，还可对计划进行What-If…交互，如图2所示。
③用负荷图(直方图)呈现资源的周期利用率，以清晰地展现关键资源的使用状况，如图3所示。
3.4 交互功能
交互功能是在结果可视化的基础上，对已有的优化排程结果进行局部调整。其重要性主要体现在：一方面是对突发事件的应急处理，即对生产条件发生变化后的情况迅速地进行处理，以生成新的计划；另一方面体现在通过不断的What-If…交互进行分析并改善排程结果
表1 订单执行计划表
图2 设备-工序甘特图
图3 资源负荷图
基础交互功能包括以下几类。
①删除订单，是指在结果甘特图上，将指定的单个或者多个订单从计划中删除的操作。生产中如果遇到有些订单停止生产，则可以通过该功能来删除订单，并进行二次优化。
②插入订单，是指在结果甘特图上，将一个或多个新的订单安排到原有计划中的操作。生产中如果遇到紧急插单的情况，可以选择不可拖期插入，二次优化算出的结果可以保证新插入的订单无拖期。
③拖拉，是指在结果甘特图上，对指定工序的时间或者所用资源用鼠标进行直觉式修改的操作。拖拉操作可以改变指定工序的加工时问，也可以改变其所用的资源。拖动后优化引擎会进行二次优化，返回新的可行解。
4 应用举例
为验证本文中生产排程模型，我们以一个实例来进行说明。本例是某烟厂离散和流水混合的多条生产线的生产计划与排程问题。在该问题中，工艺在部分设备上呈流水特征，在其它设备上呈离散特征，离散设备和流水设备交替排布。该问题主要目标有：
- 对已有的老式生产线的现有手工计划进行试算，验证其可行性；
- 对尚未建成的新式生产线，验证其设备配置和产品配方是否能达到其产能要求：
- 针对新旧两条生产线，对周期内的订单制定生产排程计划。
烟草行业生产自动化、精细化程度较高，对生产过程控制和质量管理非常严格，生产计划必须严格满足工艺流程要求。而且该问题中行业性约束较多且复杂，如前日留柜、今日留柜、喂丝机选取、换批和换牌时间间隔、储柜容量约束、储柜试用时间的不确定性约束、同一品牌不同模块关系约束等，对数学模型和算法是极大的挑战。由于采用NCL语言建立的排程模型独立于行业、抽象度高，非常易于扩展和维护，作者可以很方便、自然地建立烟草行业的生产排程模型。通过大量真实数据测试，证明算法效率高，计算速度快，结果满足符合生产需要。结果甘特图如图4所示。
图4 烟草生产线结果图
5 总结
本文对工业生产中常见的生产排程问题进行了研究。基于NCL语言和POEM平台，文中给出了全新的生产排程问题的建模方法。该方法使用混合集合规划的求解算法体系，借鉴约束切割和分支搜索的算法思想，特别适用于复杂的、多约束的、多目标的离散生产排程问题。烟草行业的应用结果表明，本文所设计的生产排程模型和算法对于对于大规模的复杂工业问题可以求得满意的解。
核心关注：拓步ERP系统平台是覆盖了众多的业务领域、行业应用，蕴涵了丰富的ERP管理思想，集成了ERP软件业务管理理念，功能涉及供应链、成本、制造、CRM、HR等众多业务领域的管理，全面涵盖了企业关注ERP管理系统的核心领域，是众多中小企业信息化建设首选的ERP管理软件信赖品牌。
转载请注明出处：拓步ERP资讯网http://www.toberp.com/
本文标题：生产排程算法及工业应用
相关文章
