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

摘要

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