摘要
针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明:工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。
Focusing on hybrid flow shop robotic cells scheduling problem with blocking, for optimizing simultaneously robotic operation sequence and part input sequence, a branch and bound method was proposed. Firstly, robotic activity was defined to transfer double sequence into single sequence. Secondly, order insertion rule was proposed for obtaining feasible solution. Finally, according to the order insertion rule, branching process was designed. Stochastically generated instances were computed by CPLEX and branch and bound method. When there were three tanks in robotic cells, the value of objective function got by branch and bound method was the same as that of CPLEX; but compared to CPLEX, the average computation time was reduced by 38.58%. So the branch and bound method was effective. When the number of tanks exceeded three and the computation time did not exceed 600 seconds, compared to CPLEX, 85.19% of instances could be found out better solution. It means that the branch and bound method is more valuable, especially for big scale problems.
作者
赵晓飞
郭秀萍
ZHAO Xiaofei;GUO Xiuping(School of Economics and Management,Southwest Jiaotong University,Chengdu Sichuan 610031,China;School of Economics and Management,Chongqing University of Arts and Sciences,Chongqing 402160,China)
出处
《计算机应用》
CSCD
北大核心
2018年第7期2095-2099,2118,共6页
journal of Computer Applications
基金
国家自然科学基金资助项目(71471151
61573264)
中央高校基本科研业务费专项(26816WCX04)
国家社会科学基金资助项目(17BJL101)
重庆市教委科学技术项目(KJ1711293)~~
