动态加强CPT解job-shop调度约束满足优化问题

Dynamic enhanced CPT for the job-shop scheduling constraint satisfaction optimization problem

带有相同到达期与交货期的job-shop调度问题(JSSP)作为多种实际生产调度问题简化模型,是一类典型强NP-hard问题.对优化目标是最小化最大完工时间的JSSP问题,建立了约束满足优化问题模型(JSSC-SOP).利用弧一致约束传播算法和深度优先启发式构造活动调度,逐步加入新约束,实现活动调度集的部分列举与寻优.提出3种动态加强约束传播技术(CPT),嵌入搜索过程,提高求解效率.最后通过随机生成的实例,验证了各方法可行性与有效性.

The job-shop scheduling problem （JSSP） with common release dates and due dates is a class of strong NP-hard problem, which is known as an academic simplification of many realistic scheduling problems. This paper develops job-shop scheduling constraint satisfaction optimization problem model （JSSCSOP） that the objective is to minimize the makespan. The active schedules are constructed by using arc-consistence constraint propagation algorithm and depth-first heuristic. Adding new constraints gradually, the active schedule set can be partial enumerated to obtain an optimal solution. Throe dynamic enhanced constraint propagation techniques （CPT）, which are embedded into the process of search for the solutions, are proposed to increase efficiency. Computational experiences on stochastic test problems verify the feasibility and effectiveness of the methods.