Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (7): 2095-2099.DOI: 10.11772/j.issn.1001-9081.2018010135

Previous Articles     Next Articles

Branch and bound algorithm for solving hybrid flow shop robotic cells scheduling problem with blocking

ZHAO Xiaofei1,2, GUO Xiuping1   

  1. 1. School of Economics and Management, Southwest Jiaotong University, Chengdu Sichuan 610031, China;
    2. School of Economics and Management, Chongqing University of Arts and Sciences, Chongqing 402160, China
  • Received:2018-01-16 Revised:2018-03-10 Online:2018-07-10 Published:2018-07-12
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (71471151, 61573264), the Fundamental Research Funds for the Central Universities (26816WCX04), the National Social Science Foundation of China (17BJL101), the Science and Technology Research Program of Chongqing Municipal Education Commission (KJ1711293).

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

赵晓飞1,2, 郭秀萍1   

  1. 1. 西南交通大学 经济管理学院, 成都 610031;
    2. 重庆文理学院 经济管理学院, 重庆 402160
  • 通讯作者: 郭秀萍
  • 作者简介:赵晓飞(1980-),男,四川盐亭人,博士研究生,主要研究方向:生产调度优化、智能算法;郭秀萍(1977-),女,内蒙古武川人,副教授,博士生导师,博士,主要研究方向:调度优化、智能算法。
  • 基金资助:
    国家自然科学基金资助项目(71471151,61573264);中央高校基本科研业务费专项(26816WCX04);国家社会科学基金资助项目(17BJL101);重庆市教委科学技术项目(KJ1711293)。

Abstract: 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.

Key words: robotic cell, branch and bound algorithm, hybrid flow shop, order insertion rule, blocking

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

关键词: 机器人制造单元, 分支定界算法, 混流生产, 顺序插入规则, 阻塞

CLC Number: