生产排程的混合集合规划算法
倪骅、李照国
（北京营智优化科技有限公司，北京100085）
摘要：生产排程问题是工业生产中常见的一类NP-hard问题。 本文采用自然约束语言NCL和混合集合规划，对复杂的多约束、多目标的生产排程问题进行建模和求解。此外，基于一定的固定和松弛逻辑，用户可直接在甘特图上针对解进行What-If分析。
关键词：生产排程，自然约束语言，混合集合规划
中图分类号：F830.91.文献标识码：A
0.引言
生产排程问题在于如何合理地调度资源从而高效地进行产品生产。制定完工厂战略级生产计划之后，生产排程用于制定车间工序层面的战术级执行计划。
采用传统的优化算法研究生产排程问题已有近60年。本文采用运筹学语言NCL和混合集合规划，对复杂的多约束、多目标的生产排程问题进行建模和求解。
1.NCL语言
作为新一代的优化计算语言，与传统声明型语言及脚本型建模语言不同，NCL是一门采用上下文相关语法的、用于求解约束满足问题的描述型语言。
1.1NCL语言的特征
NCL的特征可概括为如下三方面：
a）自然建模：NCL支持以常规数理逻辑为语法的自然建模，人工智能的模式识别技术广泛应用于NCL的语法分析、语义识别、模型诊断及模型优化上。这使得编程者可将主要精力用于高层级的、业务逻辑一级的模型设计，而无须在低层级、算法细节上停滞。
b）混合集合规划（Mixed Set Programming，简称MSP）：① 实数、整数、布尔值、索引及集合类型的混合域上的全局推理；② 将简化的一阶逻辑、集合推理、数值约束及运筹学算法集成于一个语言系统，用于处理约束满足问题。混合集合规划算法体系的目标为实现一种能够超越线性限制的、更通用的算法系统来求解约束满足问题。
c）求解规则：NCL支持基于规则的求解，使用户可对求解规则高度简洁地进行编程。一方面，在不同的业务领域存在经验性的业务规则，可将业务规则用于NCL的求解规则以规范在搜索树上的求解；另一方面，可将运筹学中丰富的启发式规则（如最小松弛度、最小遗憾度、贪婪性搜索等）用于NCL的求解规则以规避组合爆炸。
1.2NCL语言的算法框架
简而言之，NCL的求解系统基于约束切割（Constraint Cuts）与深度优先搜索（Depth-First Search）原则，首先用约束切削解空间；之后在求解规则的引导下枚举关键变量，对解空间进行完备的搜索。
2.NCL建模求解
2.1.问题描述
生产排程要求在满足订单优先级、设备生产能力、订单及其工序的生产工艺等约束条件下，按照最小化订单的时间延迟量、最小化工期、最大化主要设备利用率等优化目标，在一个周期内，对在各设备上加工的工序进行优化排程。生产排程中的主要约束包括：
设备的能力约束；订单各工序的次序约束；
设备的工作日历约束；订单时间窗口约束；
设备的工作时间约束；工序的设备需求约束；
订单的优先级约束；工序的加工时间约束；
不同订单的耦合约束；工序的时间窗口约束…
2.2.模型详解
1．主要常量和变量
主要常量：
a）对于任意设备i，定义时间集合常量ScheduleResourcei为设备的所有可加工时间段的并集。
b）对于任意订单i，定义时间常量t1Job i为订单i的计划最早开工时间。
c）对于任意订单i，定义时间常量t2Job i为订单i的计划最晚完工时间。
c）对于任意订单i，定义整数集合常量TaskJob i为订单i包含的所有工序。
主要变量：
a）对于任意工序i，定义整数变量resourceTask i为工序i加工所用的设备。
b）对于任意工序i，定义时间集合变量TimeTask i为工序i的加工时间跨度。
c）对于任意工序i，定义时间集合变量WorkTimeTask i为工序i的所有加工时间段的并集。
d）对于任意订单i，定义时间集合变量TimeJob i为订单i的加工时间跨度。
2．主要约束
NCL建模的重点是对生产排程问题的约束进行数理逻辑的描述。
3．优化目标
本模型中考虑的优化目标是最小化所有订单的总延迟时间量。
2.3.求解规则
在本模型的求解规则中，首先枚举工序所用设备，然后确定工序的开工时间。
在求解规则的设计中，我们将精确算法和启发式思想有机地结合在一起。一方面，生产排程模型中所有的约束都被严格满足，确保求解的精确性；另一方面，求解规则中的最小松弛度和顺序性等启发式的原则可确保在求解过程中灵活、个性化地控制搜索树。完备的二维排程算法和经过大量数据验证的通用型求解规则确保求得的解满足所有约束，并在找到一个可行解的基础上以回溯方式寻找更优解直至找到最优解。
2.4.结果输出
生产排程的结果输出主要有表格、甘特图、统计图等几种形式。
3.What-If分析
What-If分析可使用户对已有排程结果进行局部的调整和优化。What-If分析有助于用户进一步理解和改善已有的排程结果。
生产排程的What-If交互可在甘特图上直觉式的进行，成功则在甘特图上显示交互后的结果并将结果写入结果表；失败则给出个性化的提示信息，保持原有排程结果。
What-If交互主要包括以下三种：
a）删除订单：在甘特图上，通过鼠标右键菜单的方式将指定的单个或多个订单从排程结果中删除。实际生产中如遇到要求停止生产的订单，可通过该方式来删除订单并进行二次优化。
b）插入订单：在甘特图上，通过鼠标右键菜单的方式将指定的单个或多个新的订单加入到原有排程结果中。实际生产中如遇到紧急插单的情况，可将选择的订单优化的加入到原排程结果中。
c）拖拉工序：在甘特图上，通过鼠标左键拖拉的方式对指定工序的开工时间或所用设备进行调整。工序拖拉后后会自动调用优化引擎进行二次优化计算。
4.优化算法效果举例
为验证本文中生产排程模型和算法的求解效果，我们用两个实例来说明。运行的硬件环境是配有AMD双核速龙5600+（主频2.8G Hz）处理器、3G DDR2-800内存的PC机，软件环境是Windows XP操作系统，建模求解工具采用POEM优化计算平台2.9版。
5.结语
本文对工业生产中常见的生产排程问题的建模及求解进行了研究。基于NCL语言和POEM优化计算平台，文中给出了一种全新的生产排程问题的建模求解方法。该方法基于混合集合规划算法体系，采用约束切割和分支搜索的算法，特别适用于复杂的多约束的、多目标的生产排程问题。两个例子的求解说明：本文中的NCL模型算法对于一定规模的生产排程问题可以最优求解并最优求证，对于较大规模的复杂生产排程问题绝大多数都可求得较满意的可行解。
参考文献
J.Zhou.Introduction to the constraint language NCL.JLP 45（1-3）：71-103（2000）
J.Zhou.A Note On Mixed Set Programming，in Proc.of The 7th International Symposium on Operations Research and Its Applications，pp.131-140.Lijiang，China，October 2008
周建阳.自然约束语言[M].北京：科学出版社，2009
J.Zhou.A permutation-based approach for solving the Job-shop problem.Constraints 2（2）：185-213，（1997）
Muth，J.F.& Thompson，G.L.Industrial Scheduling，Prentice Hall，1963
Production Scheduling By Mixed Set Programming
NI HuaLI Zhao-Guo
（Beijing Enginest Technology Co.，Ltd，Beijing 10085，China）
Abstract：Production Scheduling is a general type of NP-hard problem in industrial production.Multi-objective scheduling problems with many complex constraints can be modeled and solved by NCL（Natural Constraint Language）and MSP（Mixed Set Programming）.Based on relaxation logic，users can carry out What-If analysis for a solution on Gantt chart.
Keywords：Production Scheduling，Natural Constraint Language，Mixed Set Programming
考虑外包的多产品生产计划问题模型与仿真
杨柳、钟金宏
（合肥工业大学管理学院，安徽合肥230009）
摘要：外包已成为企业专注于自身核心业务和降低成本的一个常用策略，是企业与合作伙伴间常用的合作方式。外包的实际应用情况较广泛，但国内外研究现状不足，本文在此基础上研究了带外包的生产能力受限多产品动态批量问题，设计了该问题的通用模型，模型中包含生产成本、外包成本和库存成本，并通过实例说明了如何利用商用软件Cplex求解这类模型。最后以某汽车生产企业为背景，进行仿真实验，给出一个算例，得出最优值。
关键字：经济批量模型；外包；生产计划
中图分类号：F830.91.文献标识码：A
0.引言
在如今竞争愈发激烈的环境中，越来越多的企业把主要精力放在企业的关键业务（企业核心竞争力）上，以充分发挥其优势，将企业非核心业务交由合作企业完成，这就是所谓的业务外包。近年来，外包已成为许多企业经营的常见策略之一，它已经越来越广泛的被企业所接受和采纳。但在学术研究的角度上讲，对考虑外包的生产计划问题的研究并不多。单产品研究方面，Aksen等考虑了带有外包的无能力约束的单产品批量问题并在时变线性生产、库存和失去销售成本函数的条件下提出了一个复杂度为O（T2）前向动态规划算法。多产品研究方面，过去的研究集中在供应商和分销商的外部集成上，没有考虑制造伙伴的内部集成；研究多集中在单级产品结构，未考虑多级BOM结构。Cohen等对生产和原料的全球协作提出了一个标准管理模型。
此外，企业中较为广泛的使用ERP、MIS等系统为企业制定可行的生产计划，这类系统虽然能为企业的生产计划给出可行解，但是却不能得到最优的生产计划。而目前已经有较为成熟的商用软件，如Lingo、Cplex等，可以为企业提供更优的生产计划。本文针对这样一种情况，将这些实际问题抽象成这些商用软件可解的问题，得到一个通用的问题模型，这样就可以使类似的实际问题通过这类商用软件有效的解决。
1.问题描述及数学模型
实际问题中的外包业务生产多种多样，下面以一种较为普遍的情况抽象出数学模型。假设在每个周期内，产品的需求是已知的，生产能力受限，且不允许延期交货。
已知量为：dit——产品i在t时段的外部需求；ai——生产每单位i产品所消耗的生产能力；ct——t时段可以达到的总生产能力；hit——t时段产品i的单位库存费用；sit——t时段产品i外包的单位生产费用；pit——t时段产品i的单位生产费用；N——生产产品种类数；T——计划周期数。
决策变量为：xit——产品i在t时段的内部生产量；yit——产品i在t时段外包出去的生产量；Iit——产品i在t时段末的库存量。
目标函数（1）为库存成本，生产成本和外包生产成本的最小值；约束（2）为物料平衡公式；约束（3）为生产能力约束；约束（4）~（6）分别为外包生产量，内部生产量和库存的非负约束；约束（7）表示初始和结束周期的库存状态为0。
2.仿真实验
下面以安徽某汽车公司的货车生产为例给出仿真数据和仿真实验。该公司的货车是其主要车型之一，生产量在国内同行业中位居前列。货车生产的零部件一部分是通过大型汽车配件生产商购得，其他零部件可以自己生产，也可以通过外包给其他汽车零部件生产商来生产。该公司的零部件生产不仅满足本公司的汽车制造需求，还需满足其他零部件需求商的订单。下面给出这些可以外包亦可以自己生产的零部件的最优生产计划的求解方法。该公司的所有相关生产数据不能全部精确获得，所以通过仿真数据来给出。
