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

摘要：

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

关键词：job-shop调度、约束满足优化问题、活动调度、约束传播技术

所属期刊栏目：21

分类号：TP2(自动化技术及设备)

资助基金：国家自然科学基金70171030;60274049;国家杰出青年学者自然科学基金70425003;教育部高等学校优秀青年教师教学科研奖励计划教人司[002]383;教育部霍英东教育基金会高等院校青年教师基金81073

在线出版日期：2007-01-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：583-590