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

doi:10.11772/j.issn.1001-9081.2018010135

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

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

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

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

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

Abstract

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:

TP278
F273

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	JIA Yeling, Dong Shaohua. Whole-set order problem of hybrid flow shop based on heuristic-genetic algorithms [J]. Journal of Computer Applications, 2019, 39(9): 2772-2777.
[2]	LOU Mengying, YUAN Lisha, LIU Yaqin, WAN Xuemei, YANG Feng. Palm vein enhancement method based on adaptive fusion [J]. Journal of Computer Applications, 2019, 39(4): 1176-1182.
[3]	ZHANG Jiangxin, ZHOU Jiabo, MENG Limin. Improved fast image defogging algorithm based on dark channel prior [J]. Journal of Computer Applications, 2017, 37(8): 2324-2328.
[4]	ZHANG Jieyu. Binarization method with local threshold based on image blocks [J]. Journal of Computer Applications, 2017, 37(3): 827-831.
[5]	WANG Qianbo, ZHANG Wenxin, WANG Bailin, WU Zixuan. Agent-based dynamic scheduling system for hybrid flow shop [J]. Journal of Computer Applications, 2017, 37(10): 2991-2998.
[6]	ZHANG Wenda, XU Yuelei, NI Jiacheng, MA Shiping, SHI Hehuan. Image target recognition method based on multi-scale block convolutional neural network [J]. Journal of Computer Applications, 2016, 36(4): 1033-1038.
[7]	QI Xuemei, WANG Hongtao, CHEN Fulong, TANG Qimei, SUN Yunxiang. Novel quantum differential evolutionary algorithm for blocking flowshop scheduling [J]. Journal of Computer Applications, 2015, 35(3): 663-667.
[8]	MA Jian ZHANG Taihong CHEN Yanhong. New inverted index storage scheme for Chinese search engine [J]. Journal of Computer Applications, 2013, 33(07): 2031-2036.
[9]	ZHANG Zhiqiang SUN Chao. Design and implementation of covering software in automatic meteorological station quality control system [J]. Journal of Computer Applications, 2013, 33(04): 1169-1172.
[10]	LU Chunxia MA Shaohui. Approach on irregular block dynamic stacking in shipbuilding based on grid technology [J]. Journal of Computer Applications, 2013, 33(02): 333-337.
[11]	JIANG Yongliang YANG Zhiqiang ZHANG Chengyi. Two-stage segment optimal packing of single size rectangles [J]. Journal of Computer Applications, 2011, 31(06): 1689-1691.
[12]	. Algorithm of H.264 fast deblocking filter on CUDA [J]. Journal of Computer Applications, 2010, 30(12): 3252-3254.
[13]	. Design and implementation of FPGA data communication interface driver based on Linux [J]. Journal of Computer Applications, 2009, 29(09): 2520-2522.
[14]	. Effective de-blocking algorithm for block-DCT images [J]. Journal of Computer Applications, 2007, 27(6): 1460-1462.
[15]	Hong-Mei Wang Zheng Zhao Yong-Hua Zhang. Update strategy based on filtering residual image for motion compensation temporal filtering [J]. Journal of Computer Applications, 2007, 27(11): 2778-2780.