一种基于约束引导Job-shop问题禁忌搜索算法  

A tabu search algorithm based on constraint guided for job-shop problem

作　　者：李文超[1] 杨宏兵[2] 

机构地区：[1]江苏大学汽车与交通工程学院,镇江212013 [2]苏州大学机电工程学院,苏州215021

出　　处：《制造业自动化》2012年第5期77-79,139,共4页Manufacturing Automation

基　　金：国家自然科学基金资助项目(51005160);江苏省高校自然科学研究项目(10KJB410001)

摘　　要：Job-shop问题是生产调度领域一类典型模型,求解问题属于NP完全,大规模Job-shop问题有效算法至今仍未找到。本文在析取有向图模型基础上,提出选取可互换操作对5种方法,通过逐步添加析取约束建立了一种以约束为引导的禁忌搜索算法,该算法在搜索过程中能灵活选取可互换操作对。数值计算结果表明所提算法对于大规模Job-shop问题求解存在较好效果。

关 键 词：JOB-SHOP 禁忌搜索 约束引导 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]