微粒群优化在Job-shop调度中的应用

Job-shop调度问题是典型的NP-难问题，利用微粒群优化的全局搜索能力和高搜索效率以及模拟退火算法的局部搜索能力，发展了一种快速、且易于实现的新的混合启发式算法，并将其应用于求解标准Job-shop调度问题，计算结果以及与其他算法的比较说明，该算法是一种求解Job-shop调度问题的可行且高效的方法。

Application of Particle Swarm Optimization in the Job-Shop Scheduling Problem

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, namly 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.