关键词: 车间调度, 约束满足, 约束传播算法, 树搜索算法, 启发式修复算法

Abstract: 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.

Key words: Job Shop scheduling, constraint satisfaction, constraint propagation algorithm, tree search algorithm, heuristic repair algorithm, hybrid solution method