Abstract: Two-machine robotic cell scheduling problem with sequence-dependent setup times which is NP-hard is researched, variable neighborhood search is designed in the field. In order to speed up the convergence, minimization of blocking time close part method which produces initial solution is designed. Parameters of proposed algorithm are analysed for finding better solution. The presented algorithm is compared to SA by solving randomly generated stances, the results show that the algorithm is more effectively.

Key words: variable neighborhood search, robotic cell scheduling problem, simulated annealing algorithm

摘要： 针对排序依赖转换时间的两机器机器人制造单元调度问题的NP难特性，设计了变邻域搜索算法求解。为了加快算法收敛速度，设计了工件阻塞时间最小化生成初始解；为了搜索到更好解，分析了算法的参数取值。通过随机产生算例测试，提出算法优于模拟退火算法，证实了提出算法的有效性。

关键词: 变邻域搜索, 机器人制造单元调度问题, 模拟退火算法