作　　者： ; ; ; ;

机构地区： 上海交通大学电子信息与电气工程学院自动化系

出　　处： 《上海交通大学学报》 2005年第3期381-385,共5页

摘　　要： Job-shop调度问题是典型的NP-难问题.利用微粒群优化的全局搜索能力和高搜索效率以及模拟退火算法的局部搜索能力,发展了一种快速、且易于实现的新的混合启发式算法,并将其应用于求解标准Job-shop调度问题.计算结果以及与其他算法的比较说明,该算法是一种求解Job-shop调度问题的可行且高效的方法. The job-shop scheduling problem (JSP) is an NP-hard problem. A new approximation algorithm was proposed for the problem of finding the minimum makespan in JSP environment. The new algorithm is based on the principle of particle swarm optimization (PSO). PSO combines local search and global search, possessing high search efficiency. The simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, namely HPSO, was developed. The comparison with other results in benchmark JSP problems indicates that the PSO-based algorithm is a viable and effective approach for the JSP problem.

关 键 词： 调度 微粒群优化 模拟退火 混合优化

领　　域： [自动化与计算机技术] [自动化与计算机技术]