一种基于禁忌搜索的作业车间调度算法

An Algorithm Based on Taboo Search for Job Shop Scheduling

文章描述了一种解决作业车间调度最短完工时间问题的有效的启发式算法。该算法基于禁忌搜索技术和前瞻思想,为了得到更好的结果,还将倒转技术引入到算法中。从对一组问题基准实例的实验计算结果看,该算法在合理的计算时间内,对多个实例得到比2004年提出的ISSB算法和另一种基于禁忌搜索的TSAB算法更好的结果。

In this paper,an effective heuristic algorithm for solving the minimum makespan problem of job shop scheduling is presented.The algorithm is based on the taboo search technique and look-ahead strategy.The reverse technique is also introduced in the algorithm to improve the computational results.Computational experiments on a set of benchmark problem instances show that,in several cases,the approach,in reasonable time,yields better solutions than the ISSB algorithm proposed in 2004 and the TSAB algorithm which is also based on taboo search.