1.1.2订单层级约束
订单层级约束主要包括以下几种：
（1）最早开工时间：订单最早开始加工的时间；
（2）最晚完工时间：订单最晚完工的时间；
（3）订单间次序关系：如订单A需要排在订单B前执行，即订单B必须在订单A完工后才能开工或订单B必须在订单A开工后才能开工等；
（4）订单的优先级：不同的订单可能有不同的优先级，优先级越高的订单加工次序越早。
1.1.3工序层级约束
工序层级约束主要包括以下几种：
（1）工序的资源需求：如工序a需要在车床1或车床2上进行加工；
（2）工序的加工时间；
（3）工序的时序控制：如工序a完工后一小时，工序b开工；
（4）工序的时间窗口：如工序a的开工时间在10：00～12：00之间；
（5）工序的资源可替代性：如工序a最好用1类资源加工，若无1类资源，那么可用2类资源加工；
（6）工序的工艺流程。
另外还有一些复杂的个性化约束，例如下班前不开工、小批量遗留当班完成……
1.2优化目标
生产排程的优化问题通常都是多目标的，一般有以下优化目标：
（1）最小化订单的时间延迟量；
（2）最小化工期；
（3）最小化订单延迟数量；
（4）最小化工作时间跨度；
（5）最大化主要资源利用率……
2.混合集合规划
混合集合规划（Mixed Set Programming）源于逻辑规划（Logic Programming）和约束规划（Constraint Programming），是以一阶逻辑与集合推理为算法框架的逻辑求解系统，它实现了实数、整数、布尔值、日期/时间及集合类型的混合域上的全局推理，将集合运算、数值约束、逻辑函数及运筹学算法集成于一个语言系统以处理约束满足问题。这里的集合规划概念并非在问题求解中对集合符号、集合变量及集合约束的简单使用，而是系统地将集合推理与运筹学算法相结合，以集合变量为主进行问题建模，以基于集合推理的算法来求解问题。
在实际运用中，许多问题并不能用线性模型和简单的整数或实数变量描述。混合集合规划旨在实现一种超越线性限制的、更通用的算法系统来求解约束满足问题，特别适用于集合覆盖/集合划分、生产排程、路径优化等问题。
3.大规模生产排程问题的建模及求解
本节介绍采用NCL语言（Natural Constraint Language）对大规模的生产排程问题进行建模求解的过程。NCL语言是一门集优化计算、逻辑编程及求解规则于一体的业务建模和问题求解的智能描绘型语言，它支持混合集合规划。
3.1数据逻辑
为支持软件工程，生产排程的数据库设计采用面向对象的方法。
通过问题建模分析可知，生产排程问题涉及三个基础数据类：资源（RESOURCE）、作业(JOB)、工序(TASK)。RESOURCE表对应资源数据类，用来定义资源的标识符(id)、名称(name)、类型(type)等；JOB表对应作业数据类，用以定义作业的标识符(id)、最早开工时间（t1）、最晚完工时间(t2)等；TASK表对应工序数据类，定义工序的标识符(id)、名称(name)、对应的作业编码(idJob)、候选资源标识符集合（IdResource）、可开工时间窗（TimeWin）等。为支持滚动排程，系统引进已占用资源表OCCUPATION定义资源编码（id）、资源占用起始时间（t1）、资源占用结束时间（t2）等。
在实际应用中，用户还将面对产品(PRODUCT)、工艺路线(PROCESS)、订单(ORDER)三个数据类。他们之间的关系如下：
（1）PRODUCT定义车间所能生产的产品的标识符(id)、名称(name)、类型(type)等；
（2）PROCESS定义车间生产各类产品的工艺路线的标识符(id)、名称(name)、生产的产品(idProduct)、加工路线（产品在各资源上的加工路线）等；
（3）ORDER定义车间生产各类产品的订单的标识符(id)、名称(name)、生产的产品(idProduct)、产量（quantity）等。
数据之间的关系如下：由于资源能力的限制，一个订单可能要分批次加工，对应一个或多个作业；由作业表(JOB)及工艺路线表(PROCESS)可派生出工序表(TASK)。
3.2滚动排程
对于大规模生产排程问题，由于其数据量巨大，不可能一次进行全局优化求解，本文采取的方案是基于小规模局部优化的“滚动排程”。该方案的核心是将大规模数据合理地分成若干组小规模数据，这些小规模数据都可以在较短的时间内被混合集合规划算法优化求解，将这些小规模数据的解有机地组合起来即是原问题的一个较优可行解。
3.3模型详解
NCL对生产排程问题的建模在于对问题的数理逻辑描述。
（1）订单分组模型
定义作业分组数变量nbGroup的过程中，每次安排一定数量的工序，直到拆分完所有的订单包含的工序。
（2）生产排程模型
1）工作日历约束：
对于任意一个工序，其有效时间为该工序在所需设备资源上的工作时间段（不同的资源的可工作时间段可不同）和该工序加工时间段的交集。
2）工序对资源及时间的需求约束：
对于任意两个不同的工序，它们用到的资源实体不相同或者加工时间段不冲突。
以上约束称为二维排程约束，是生产排程问题的核心约束。它将工序的资源变量(整数：resourceTaski)及时间变量(集合：TimeTaski)上的约束逻辑描述为：两工序或者占用资源不同，或者加工时间段不相交。
对于任意一个资源，其工作时间段等于所有使用该资源的时间段的并集；对于使用该资源的任意两个不相同的工序，它们的加工时间段不冲突。
3.4求解策略
NCL语言建模的关键之一是对搜索策略的设计。设计合适的搜索策略，才能对建立的生产排程模型高效地进行求解。NCL的求解系统基于约束切割与深度优先搜索（Constraint Cuts and Depth-First Search），其框架如图2所示：首先用约束切割解的搜索空间，如查询变量的值域确定且不为空集则找到解，回溯继续搜索其余解空间以寻求更优解；如查询变量存在值域为空集者，则证明目前状态下无解，回溯继续探索其余解空间以寻求解；如查询变量的取值有未确定者(可以再细分)，则按搜索规则选择某个查询变量，将该变量的值域一分为二，把问题变成对应子域的两个子问题，系统进行分枝以求解子问题。
具体到生产排程的模型中，对于每道工序，系统只需确定工序所用资源和工序开工时间就可确定这道工序的具体加工安排。因而，系统在查询变量的取值时，首先询问工序所用资源，然后再确定工序的开工时间。完善的二维排程算法和经过大量数据验证的通用性搜索策略保证了我们可以得到一个满足所有约束的可行解，并在此基础上进一步回溯以寻找更好的解。
3.5结果输出
基于NCL语言的生产排程问题的结果可以三种可视化形式展现：甘特图、资源负载图、生产模拟。其中甘特图包括资源-工序甘特图，订单-工序甘特图；资源负载图主要用以展示资源的利用率，使用户对瓶颈资源一目了然；生产模拟功能可进行二维平面俯视图上的车间生产过程模拟与虚拟实时跟踪。
4.应用举例
本节以具体实例验证本文生产排程优化问题的模型和NCL的求解效果。运行的硬件环境是配有英特尔酷睿双核T9400处理器（主频2.53Gz），2G DDR2内存的PC机，操作系统为Windows 7，建模求解工具是POEM优化计算平台2.9版。实例为四川成都四威产业园的生产排程问题。测试数据为订单50个，资源设备463个，工序数目为11 700左右的较大规模的数据。在求解过程中，采用滚动排程思想，将11700个工序分成47组，求得整个问题可行解的时间为50分钟17秒左右。
计算结果的可视化按以下三种方法给出：
（1）甘特图，包括工位-工序甘特图和订单-工序甘特图。
（2）资源负载图，用来展示每个资源设备的利用率。用户可直观地分析瓶颈资源，并有针对性地调整资源分配情况，以期得到更合理的分配。
（3）生产模拟。它主要实现二维平面俯视图上的车间生产过程模拟与虚拟实时跟踪功能。用户可查看各资源的模拟工作情况（如该资源是否在工作，资源正在加工哪道工序），查看各作业的加工进度（如作业完成度、已加工完毕的工序、正在加工的工序等）。
5.结论
生产排程问题是一个困扰学术界多年的NP-hard问题，一个简单的Job-Shop的MT10问题就曾经使世界各地学者为之研究长达25年之久才得以解决。由此可知对工业应用中复杂的大规模生产排程问题求解的难度。本文提出了滚动排程的思想，先将大规模问题按排产逻辑分解，再将小规模问题逐一求解，最后通过一定的滚动和衔接逻辑将分解后的小规模问题的解进行合并而形成大规模问题的解。经过实例验证，对于较大规模的数据（10万道工序以上的排产问题），通过滚动排程可有效地求得可行解，并给出完善的可视化结果，起到对生产进行指导的作用。
Research on Large-Scale Production Scheduling By Mixed Set Programming
YANG Long1，MEI Jun2，LIU Mao-hui2
(1.School of Management & Economics，Beijing Institute and Technology，Beijing 10081，China 2.Chengdu SIWI High-Tech Industry Co.，LTD. Chengdu 611731，China)
Abstract：Production Scheduling is an NP-hard combinatorial optimization problem. To deal with a large-scale production scheduling problem，a new method called Iterative Scheduling based on Mixed Set Programming (MSP) is proposed：First，large-scale data is decomposed into groups of small-size data according to the problem logic； second，small-size problems are solved by MSP in an iterative manner； third，some grouping logic is used to sequentially merge the local solutions into a complete solution for the whole problem.
Keywords：Production Scheduling；Mixed Set Programming；Iterative Scheduling.
