求解阻塞混流生产机器人制造单元调度问题的分支定界算法

摘要 针对阻塞混流生产机器人制造单元调度问题，为了同时优化机器人运行顺序和工件加工顺序，提出了分支定界算法。首先，定义机器人活动，将双排序转化为单排序；其次，构建顺序插入规则生成可行解；最后，依据顺序插入规则，设计了分支过程。通过计算随机生成算例，计算结果表明：工作站个数为3时，分支定界算法得到的目标函数值与CPLEX相同，但平均运行时间比CPLEX降低38.58%，证实了分支定界算法的有效性；工作站个数大于3时，与CPLEX相比，在同等时间内，有85.19%的算例搜索到更好解，因此，对于大规模情形，分支定界算法更有价值