基于约束满足的车间调度算法综述

Constraint-based algorithm for Job Shop scheduling

为了说明如何利用启发式信息构造车间调度的约束满足求解算法,首先概述了常规约束满足求解技术,进而介绍了车间调度问题的约束传播算法、树搜索算法和启发式修复算法的构造原理及适用性。在此基础上,针对目标优化问题,给出两种求解框架。最后,指出近期的研究趋势和进一步的研究工作。

To explain how to use the heuristics information of the problem to construct constraint-based solving algorithm, the general constraint satisfaction solving technology was briefly introduced, then the principles and the applicability of constraint propagation algorithm, tree search algorithm and heuristics repair algorithm for Job Shop scheduling were summarized. Furthermore, two solution frameworks for objective function optimization problem were given. Finally, the research trend of constraint-based scheduling algorithm was pointed out and the prospective research was also proposed.