求解机器人制造单元调度问题的化学反应优化算法

doi:10.12005/orms.2017.0134

运筹与管理 ›› 2017, Vol. 26 ›› Issue (6): 35-40.DOI: 10.12005/orms.2017.0134

求解机器人制造单元调度问题的化学反应优化算法

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

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

收稿日期:2015-12-20 出版日期:2017-06-25
作者简介:赵晓飞(1980-),男,四川盐享人,博士研究生,研究方向:生产调度优化、智能算法;郭秀萍(1977-),女,内蒙古武川人,副教授,博士,博士生导师,研究方向:调度优化,智能算法。
基金资助:
国家自然科学资金资助项目(71471151,70901064,71201132,71090402);新世纪优秀人才支持计划(NCET-11-0709);教育部创新团队(IRT0860);重庆市教委科学技术项目(KJ1501133,KJ1711293);永川区自然科学基金资助项目(Ycstc, 2014nc8002)

Chemical Reaction Optimization Algorithm for SolvingRobotic Cell Scheduling Problem

ZHAO Xiao-fei^1,2, GUO Xiu-ping¹

1.School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China;
2.College of Economics and Management, Chongqing University of Art and Sciences, Yongchuan 402160, China

Received:2015-12-20 Online:2017-06-25

摘要/Abstract

摘要： 针对多类型工件加工机器人制造单元调度NP难题,提出一种局部搜索的化学反应优化算法。该算法采用基于迭代次数的线性排序选择,维持解的多样性;构建紧后工件阻塞时间最小化交换的邻域结构加快收敛速度。此外,该算法主要参数由正交试验获得。通过求解随机产生的算例,仿真结果表明,化学反应优化算法优于遗传算法,提出算法较化学反应优化算法能更有效地搜索到更好解。

关键词: 机器人制造单元, 化学反应算法, 局部搜索

Abstract: A multiple part-type robotic cell scheduling problem is NP-hard. A chemical reaction optimization algorithm based on local search is proposed. In order to maintain the solution diversity, linear ranking selection based on iteration number is applied. Minimization of Blocking Time Close Part Swap is constructed for the sake of speeding up convergence. In addition, the main parameters of proposed algorithm are investigated based on Taguchi method of design-of-experiment, and a set of suitable parameters is suggested. Finally, the presented algorithm is compared to GA by solving randomly generated stances, and the results show that the algorithm is more effectively.

Key words: robotic cell, chemical reaction optimization, local search

中图分类号:

F224

赵晓飞, 郭秀萍. 求解机器人制造单元调度问题的化学反应优化算法[J]. 运筹与管理, 2017, 26(6): 35-40.

ZHAO Xiao-fei, GUO Xiu-ping. Chemical Reaction Optimization Algorithm for SolvingRobotic Cell Scheduling Problem[J]. Operations Research and Management Science, 2017, 26(6): 35-40.

参考文献

[1] Manier M A, Bloch C. A classification for hoist scheduling problems[J]. International Journal of Flexible Manufacturing Systems, 2003, 15(1): 37-55.
[2] Dawande M, Geismar H N, Sethi S P, et al. Sequencing and scheduling in robotic cells: recent developments[J]. Journal of Scheduling, 2005, 8(5): 387-426.
[3] 王跃岗,车阿大.基于混合量子进化算法的自动化制造单元调度[J].计算机集成制造系统,2013,19(9):2193-2201.
[4] 晏鹏宇,车阿大,李鹏等. 具有柔性加工时间的机器人制造单元调度问题改进遗传算法[J].计算机集成制造系统,2010,16(2):404-410.
[5] 晏鹏宇,车阿大,唐小我.基于加工时间分类视角的自动化生产系统调度综述[J].计算机集成制造系统,2012,18(2):332-341.
[6] 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.
[7] Che A,Yan P,Yang N, et al. Optimal cyclic scheduling of a hoist and multi-type parts with fixed processing times[J]. International Journal of Production Research, 2010, 47(5): 1225-1243.
[8] 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-166.
[9] Kharbeche M, Carlier J, Haouari M, et al. Exact method for robotic cell problem[J]. Electronic Notes in Discrete Mathematics, 2010, 36: 859-866.
[10] Kamoun H, Hall N G, Sriskandarajah C. Scheduling in robotic cells: heuristics and cell design[J]. Operations Research, 1999, 47(6): 821-835.
[11] 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.
[12] Zahrouni W, Kamoun H. Sequencing and scheduling in a three-machine robotic cell[J]. International Journal of Production Research, 2012, 49(10): 2823-2835.
[13] Lam A Y S, Li V O K. Chemical-reaction-inspired metaheuristic for optimization[J]. IEEE Transactions Evolutionary Computation, 2010, 14(3): 381-399.
[14] Lam A Y S, Xu J, Li V O K. Chemical reaction optimization for population transition in peer-to-peer live streaming[C]. in: Proceeding of the IEEE Congress on Evolutionary Computation(CEC 2010), Barcelona, Spain, 2010, 7: 1429-1436.
[15] Xu J, Lam A Y S, Li V O K. Chemical reaction optimization for the grid scheduling problem[C]. in: Proceeding of the IEEE International Conference on Communications, Hong Kong, China, 2010, 5: 1-5.
[16] Li J, Pan Q. Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity[J]. Applied Soft Computing, 2012, 12(9): 2896-2912.
[17] Li J, Pan Q. Chemical-reaction optimization for solving fuzzy job-shop scheduling problem with flexible maintenance activities[J]. International Journal of Production Economics, 2013, 145(1): 4-17.
[18] 李俊青,潘全科.求解模糊作业车间调度问题的混合优化算法[J].机械工程学报,2013, 49(23):142-149.
[19] 沈婧楠,王凌,王圣尧.求解分布式置换流水线调度问题的化学反应优化算法[J].清华大学学报(自然科学版),2015,55(11):1184-1189,1196.
[20] Reeves C R. A genetic algorithm for flowshop sequencing[J]. Computers & Operations Research, 1995, 22(1): 5-13.
[21] Merz P, Freisleben B. A genetic local search approach to the quadratic assignment problem[C]. in Proc. 7th Int. Conf. Genetic Algorithms, T. Back, Ed. San Francisco, CA: Morgan Kaufmann, 1997. 465-472.
[22] Ronconi D P. A note on construction heuristics for the flowshop problem with blocking[J]. International Journal of Production Economics, 2004, 87(1): 39-48.
[23] Lam A Y S, Li V O K,Yu J J Q. Real-coded chemical reaction optimization[J]. IEEE Transactions Evolutionary Computation, 2012, 16(3): 339-353.
[24] Montgomery D C. Design and analysis of experiments[M]. Arizona: Wiley, 2005.

求解机器人制造单元调度问题的化学反应优化算法

Chemical Reaction Optimization Algorithm for SolvingRobotic Cell Scheduling Problem

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	庞南生, 叶博童. 项目鲁棒调度的资源分配启发式算法研究[J]. 运筹与管理, 2021, 30(8): 21-27.
[2]	赵晓飞, 郭秀萍. 阻塞混流生产机器人制造单元调度问题可行解性质研究[J]. 运筹与管理, 2019, 28(7): 187-191.
[3]	汪恭书, 张新邦, 邢航, 李贵栋. 改进差分进化算法求解装载率凹费用装箱问题[J]. 运筹与管理, 2017, 26(9): 29-36.
[4]	李俊青 , 潘全科 , 王法涛. 求解混合流水线调度问题的离散人工蜂群算法[J]. 运筹与管理, 2015, 24(1): 157-163.