cplex中的约束规划求解调度问题的性能超越数学规划和许多智能算法

大家都知道，ibm cplex（全称IBM ILOG CPLEX Optimization Studio）是市场遥遥领先的数学规划优化软件，其数学规划（包括线性规划、混合整数规划等）求解器已成为行业标杆。

但大家可能不知道，cplex中还含有另一种类型的求解器，那就是约束规划（constraint programming）求解器，其求解大规模调度问题的性能远超数学规划求解器。要说明的是，cplex中的约束规划求解器针对调度问题做了特殊优化，性能远超其他约束规划求解器。

调度问题（如生产调度）通常都是所谓NP难题，其规模一大，数学规划求解器就无能为力了，这时用户往往转向各种启发式算法（如遗传算法等）求解，但启发式算法将约束硬编码在程序中，难以理解，难以修订约束，不够灵活。要知道企业运营环境多变，经常要修订约束，如果约束硬编码在算法程序中，那是很难修订的。而采用约束规划的方法，用户只要声明性地、以自然的方式定义好约束和目标函数，求解器就能自动求解，修订约束只要在模型层执行，无需深入到算法层，这就大大方便了优化系统的部署和实施。

下面，我们以一个经典的无缓冲的大规模混合流水车间调度的例子，来比较一下约束规划和数学规划的求解性能。下图是一个三阶段的混合流水车间的示意图，圆形表示工件，方形表示机器。每一个工件要经过三道加工工序，即三个阶段的加工。它在第一阶段的两台机器中选一个完成加工，然后在第二阶段的三台机器中选一个完成加工，再转到第三阶段的两台机器之一进行最后的加工。要决策的问题是，如何安排工件的机器分配和加工顺序，使得完成所有工件加工的时间最短。注意，这里各个阶段间无缓冲区。

混合流水车间问题如果规模小，可以用数学规划技术求解，但若规模太大，则无法求解。这时，cplex中的约束规划技术就派上用场了。例如，我们生成了一个大的算例数据，该算例有1000个工件（n=1000），三个阶段（m=3），第一阶段6台机器，第二阶段30台机器，第三阶段14台机器（mm[i] = [6 30 14]），零件k在阶段i的加工时间为p[i][k]。目标函数为完工时间最小化。我用约束规划模型求解此问题，在50秒求得目标值17005，距离最优解的差距（gap）小于1%。您可以从百度云下载算例数据文件，然后用任何数学规划求解器求解，您会发现数学规划求解器都是无法求解的。您可以试一试用各种启发式算法求，结果应该也是比不上cplex中的约束规划求解器的。如果您感兴趣，可以联系我们，提供您我们的约束规划模型和数学规划模型源程序，或者给您演示我们的求解过程。