关键词: 自动化制造单元, 最小完工时间, 调度, 混合启发式算法

Abstract: 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.

Key words: robotic cell, makespan, scheduling, hybrid heuristic algorithm