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