Abstract: Hybrid flow shop robotic cells scheduling problem with blocking is researched. Firstly, for constructing feasible solution, Feasible Robotic Activity Insertion Method（FRAIM） is proposed. Secondly, Double Layers Filtered Variable Width Beam Search（DLFVWBS） algorithm is developed for solving the problem according to FRAIM. During search process, to obtain promising nodes, a local evaluation function and a global evaluation function are used. Finally, compared to Variable Neighborhood Search based on the feasible solution which is generated by Branch and Bound（BBVNS）, Branch and Bound（BB） method, Beam Search according to Local evaluation function（LBS）, Beam Search based on Global evaluation function（GBS）, Double Layers Filtered Fixed Width Beam Search（DLFFWBS） algorithm, for solving stochastic generated stances, the results show that the DLFVWBS algorithm can enhance significantly the search efficiency, and the average improvement of solution is 3.07%, 6.07%, 7.79%, 12.62% and 14.47% respectively.

Key words: robotic cells, double layers filtered variable width beam search, hybrid flow shop production, blocking, feasible robotic activity insertion method

摘要： 针对混流生产阻塞机器人制造单元调度问题，给出了可行机器人运动插入法，构建可行解。依据可行机器人运动插入法，提出双层过滤变宽度束搜索算法进行求解。搜索过程利用局部评价函数和全局评价函数对节点进行两次择优选取。通过计算随机生成算例，仿真结果表明，相对于以分支定界算法产生的可行解进行变邻域搜索、分支定界算法、局部评价函数束搜索算法、全局评价函数束搜索算法和双层过滤定宽度束搜索算法，双层过滤变宽度束搜索算法不但能显著提高搜索效率，而且解的平均改进度分别为3.07%、6.07%、7.79%、12.62%、14.47%。

关键词: 机器人制造单元, 双层过滤变宽度束搜索, 混流生产, 阻塞, 可行机器人运动插入法