自动化制造单元最小完工时间调度问题的混合启发式算法

Hybrid heuristic algorithm for the scheduling problem in robotic cell with makespan criterion

自动化制造单元最小完工时间调度问题属于NP-hard难题,目前尚缺乏有效的调度方法。为此,提出基于遗传和禁忌搜索的混合启发式算法,用以搜索一组最满意的机器人搬运作业排序。以遗传算法为基本结构,在初始种群产生和交叉、变异操作中引入禁忌搜索技术,以提高优化质量。基于搬运作业规则的初始种群构造算法和两阶段交叉、变异算子克服了传统算子对可行搬运作业排序的破坏,而邻域移动算子则保证了禁忌搜索的多样性和集中性。最后,随机实验结果验证了算法的有效性。

There was no effective scheduling methods for the makespan scheduling problem in robotic cell,which was a NP-hard problem.A hybrid heuristic algorithm based on gentic algorithm and tabu search was proposed to search the optimal robot moving sequence for this problem.This algorithm borrowed basic structures of the genetic algorithm,and tabu search was introduced after the generation of initial population,crossover and mutation operations to improve the qualities of the solutions.Besides,a constructive heuristic method and two-phase crossover and mutation operations were respectively designed to overcome the faults of the traditional operations.A move operation was proposed to reach the neighborhood in the tabu search to guarantee the diversification and intensification.Finally,computation results based on the randomly generated instances indicated the effectiveness of this algorithm.