基于进化禁忌算法的Job-Shop调度问题研究

Solving Job-Shop scheduling problem using genetic tabu algorithm

提出一种进化禁忌混合算法,将遗传算法"适者生存"进化准则融入禁忌搜索算法.该混合算法运用遗传算法引导算法探索有希望的区域,禁忌搜索算法对有希望解的区域进行集中搜索.在混合算法中遗传算法采用基于工序的编码并提出一种IPOX交叉算子,设计了一种基于新邻域结构的高效禁忌搜索算法,使得混合算法在高级的集中搜索和分散搜索之间达到合理的平衡.通过计算大量基准实例并与现有著名算法的结果进行比较,显示了所提算法在合理的时间取得更高质量的解.

An evolutionary tabu search （GTS） is presented, in which the principle of ＂the survival of the fittest＂ from genetic algorithm （GA） is incorporated into tabu search （TS）. Among this hybrid GTS algorithm, GA localizes good areas of the solution space so that TS can start its search with promising initial solutions. The chromosome representation of the GA is based on the operation-based representation and an improved precedence operation crossover （IPOX） is proposed for the GA. An effective neighborhood structure is proposed which is based on the famous TSAB algorithm, to achieve the right balance between intensification and diversification searches. Computational experiments are given and compared with the results from the best algorithms discussed in the literature. The results show that the algorithm can solve the job-shop instances with high accuracy in reasonable time.