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

doi:10.11772/j.issn.1001-9081.2018010135

计算机应用 ›› 2018, Vol. 38 ›› Issue (7): 2095-2099.DOI: 10.11772/j.issn.1001-9081.2018010135

• 应用前言、交叉与综合 • 上一篇下一篇

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

赵晓飞^1,2, 郭秀萍¹

1. 西南交通大学经济管理学院, 成都 610031;
2. 重庆文理学院经济管理学院, 重庆 402160

收稿日期:2018-01-16 修回日期:2018-03-10 出版日期:2018-07-10 发布日期:2018-07-12
通讯作者: 郭秀萍
作者简介:赵晓飞(1980-),男,四川盐亭人,博士研究生,主要研究方向:生产调度优化、智能算法;郭秀萍(1977-),女,内蒙古武川人,副教授,博士生导师,博士,主要研究方向:调度优化、智能算法。
基金资助:
国家自然科学基金资助项目（71471151，61573264）；中央高校基本科研业务费专项（26816WCX04）；国家社会科学基金资助项目（17BJL101）；重庆市教委科学技术项目（KJ1711293）。

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

ZHAO Xiaofei^1,2, GUO Xiuping¹

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).

摘要/Abstract

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

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

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

中图分类号:

TP278
F273

赵晓飞, 郭秀萍. 求解阻塞混流生产机器人制造单元调度问题的分支定界算法[J]. 计算机应用, 2018, 38(7): 2095-2099.

ZHAO Xiaofei, GUO Xiuping. Branch and bound algorithm for solving hybrid flow shop robotic cells scheduling problem with blocking[J]. Journal of Computer Applications, 2018, 38(7): 2095-2099.

参考文献

[1] YAN P, WANG G, CHE A, et al. Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance[J]. Computers & Operations Research, 2016, 76:155-166.
[2] AMRAOUI A E, ELHAFSI M. An efficient new heuristic for the hoist scheduling problem[J]. Computers & Operations Research, 2016, 67(3):184-192.
[3] ZHU Q, ZHOU M, QIAO Y, et al. Scheduling transient processes for time-constrained single-arm robotic multi-cluster tools[J]. IEEE Transactions on Semiconductor Manufacturing, 2017, 30(3):261-269.
[4] KIM D, KIM H, LEE T. Optimal scheduling for sequentially connected cluster tools with dual-armed robots and a single input and output module[J]. International Journal of Production Research, 2017, 55(11):3092-3109.
[5] KIM H, LEE J, LEE T. Noncyclic scheduling of cluster tools with a branch and bound algorithm[J]. IEEE Transactions on Automation Science & Engineering, 2015, 12(2):690-700.
[6] LEI W, CHE A, CHU C. Optimal cyclic scheduling of a robotic flowshop with multiple part types and flexible processing times[J]. European Journal of Industrial Engineering, 2014, 8(2):143-167.
[7] HALL N G, KAMOUN H, SRISKANDARAJAH C. Scheduling in robotic cells:complexity and steady state analysis[J]. European Journal of Operational Research, 1998, 109(1):43-65.
[8] SETHI S P, SRISKANDARAJAH C, SORGER G, et al. Sequencing of parts and robots moves in a robotic cell[J]. Flexible Services and Manufacturing Journal, 1992, 4(3):331-358.
[9] HALL N G, KAMOUN H, SRISKANDARAJAH C. Scheduling in robotic cells:classification, two and three machine cells[J]. Operations Research, 1997, 45(3):421-439.
[10] ANEJA Y P, KAMOUN H. Scheduling of parts and robot activities in a two machine robotic cell[J]. Computer & Operations Research, 1999, 26(4):197-312.
[11] KAMOUN H, HALL N G, SRISKANDARAJAH C. Scheduling in robotic cells:heuristics and cell design[J]. Operational Research. 1999, 47(6):821-835.
[12] ZAHROUNI W, KAMOUN H. Transforming part-sequencing problems in a robotic cell into a GTSP[J]. Journal of the Operational Research Society, 2011, 62(1):114-123.
[13] ZAHROUNI W, KAMOUN H. Sequencing and scheduling in a three-machine robotic cell[J]. International Journal of Production Research, 2012, 50(10):2823-2835.
[14] 赵晓飞,郭秀萍.改进的求解机器人制造单元调度问题的化学反应优化算法[J].系统管理学报,2017,26(2):245-251.(ZHAO X F, GUO X P. Improved chemical reaction optimization algorithm for solving robotic cell scheduling problem[J]. Journal of Systems & Management, 2017, 26(2):245-251.)
[15] 赵晓飞,郭秀萍.求解机器人制造单元调度问题的化学反应优化算法[J].运筹与管理,2017,26(6):34-40.(ZHAO X F, GUO X P. Chemical reaction optimization algorithm for solving robotic cell scheduling problem[J]. Operations Research and Management Science, 2017, 26(6):34-40.)
[16] BRUCKER P, BURKE E, GROENEMEYER S. A branch and bound algorithm for the cyclic job-shop problem with transportation[J]. Computers & Operations Research, 2012, 39(12):3200-3214.
[17] KAMOUN H, HALL N G, SRISKANDARAJAH C. Scheduling in robotic cells:heuristics and cell design[J]. Operations Research, 1999, 47(6):821-835.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	常峥, 罗萍, 杨波, 张晓晓. 基于HHT-MFCC和短时能量的慢性阻塞性肺病患者呼吸声识别[J]. 计算机应用, 2021, 41(2): 598-603.
[2]	赵津, 宋文爱, 邰隽, 杨吉江, 王青, 李晓丹, 雷毅, 邱悦. 儿童阻塞性睡眠呼吸暂停计算机人脸辅助诊断综述[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3394-3401.
[3]	柴恩惠, 智敏. 融合分支定界的可变形部件模型的行人检测[J]. 计算机应用, 2017, 37(7): 2003-2007.
[4]	齐学梅, 王宏涛, 陈付龙, 汤其妹, 孙云翔. 新颖的阻塞流水车间调度量子差分进化算法[J]. 计算机应用, 2015, 35(3): 663-667.
[5]	薛明浩马林华林志国野晓东. 基于LDPC码的跳频抗干扰性能[J]. 计算机应用, 2011, 31(08): 2037-2039.
[6]	姜永亮杨志强张诚一. 基于两阶段的分段单一矩形优化排样[J]. 计算机应用, 2011, 31(06): 1689-1691.
[7]	蒋贵全张辉王国锋. 基于Linux的FPGA数据通信接口驱动设计与实现[J]. 计算机应用, 2009, 29(09): 2520-2522.