Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2015, Vol. 55 Issue (11): 1184-1189,1196    DOI: 10.16511/j.cnki.qhdxxb.2015.21.009
  自动化 本期目录 | 过刊浏览 | 高级检索 |
求解分布式置换流水线调度问题的化学反应优化算法
沈婧楠, 王凌, 王圣尧
清华大学自动化系, 北京 100084
Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem
SHEN Jingnan, WANG Ling, WANG Shengyao
Department of Automation, Tsinghua University, Beijing 100084, China
全文: PDF(1442 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 针对分布式置换流水线调度问题(DPFSP),提出了一种有效的化学反应优化(CRO)算法。设计了CRO算法求解DPFSP的4种基本操作,通过多样化的操作丰富搜索行为并保证种群的多样性。同时,针对问题特性设计了有效的局部搜索机制,增强了算法局部趋化能力。最后,基于试验设计的方法探讨了参数设置对算法性能的影响,并通过数值仿真以及与已有算法的统计比较验证了所提算法的有效性。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
沈婧楠
王凌
王圣尧
关键词 分布式调度置换流水线调度化学反应优化局部搜索    
Abstract:An effective chemical reaction optimization(CRO) algorithm was developed to solve the distributed permutation flowshop scheduling problem(DPFSP). Four basic CRO algorithm operators were used in the solution to enrich the search behavior and ensure the population diversity. An effective local search procedure was developed based on the DPFSP characteristics to enhance the local exploitation ability of the algorithm. Finally, the effects of the parameter settings on the algorithm were investigated using the design-of-experiment method with the numerical results showing that this algorithm is effective.
Key wordsdistributed scheduling    permutation flowshop scheduling problem    chemical reaction optimization    local search
收稿日期: 2013-10-09      出版日期: 2015-12-01
ZTFLH:  TP182  
通讯作者: 王凌,教授,E-mail:wangling@tsinghua.edu.cn     E-mail: wangling@tsinghua.edu.cn
引用本文:   
沈婧楠, 王凌, 王圣尧. 求解分布式置换流水线调度问题的化学反应优化算法[J]. 清华大学学报(自然科学版), 2015, 55(11): 1184-1189,1196.
SHEN Jingnan, WANG Ling, WANG Shengyao. Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem. Journal of Tsinghua University(Science and Technology), 2015, 55(11): 1184-1189,1196.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2015.21.009  或          http://jst.tsinghuajournals.com/CN/Y2015/V55/I11/1184
  图1 CRO 算法流程图
  表1 针对DPFSP的CRO 算法操作
  图2 两点交叉示意图
  图3 距离保持交叉示意图
  表2 CRO 算法的参数表
  表3 CRO 算法中参数的水平值
  表4 正交表和RV 值
  图4 参数的水平值趋势图
  表5 CRO 算法的参数的参考值
  表6 局部搜索操作对RPD 的影响
  表7 不同算法的RPD
  图5 种群性能变化曲线
[1] Chan H K, Chung S H. Optimisation approaches for distributed scheduling problems[J]. International J of Production Research, 2013, 51(9):2571-2577.
[2] 王凌. 车间调度及其遗传算法[M].北京:清华大学出版社, 2003.WANG Ling. Shop Scheduling with Genetic Algorithms[M]. Beijing:Tsinghua University Press, 2003.(in Chinese)
[3] Naderi B, Ruiz R. The distributed permutation flowshop scheduling problem[J]. Computers & Operations Research, 2010, 37(4):754-768.
[4] Jia H Z, Nee A Y C, Fuh J Y H, et al. A modified genetic algorithm for distributed scheduling problems[J]. J of Intelligent Manufacturing, 2003, 14(3-4):351-62.
[5] Chan F T S, Chung S H, Chan P L Y. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems With Applications, 2005, 29(2):364-371.
[6] Chan F T S, Chung S H, Chan L Y, et al. Solving distributed FMS scheduling problems subject to maintenance:genetic algorithms approach[J]. Robotics and Computer-Integrated Manufacturing, 2006, 22(5):493-504.
[7] Jia H Z, Fuh J Y H, Nee A Y C, et al. Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems[J]. Computers & Industrial Engineering, 2007, 53(2):313-20.
[8] Chung S H, Chan F T S, Chan H K. A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling[J]. Engineering Applications of Artificial Intelligence, 2009, 22(7):1005-1014.
[9] De Giovanni L, Pezzella F. An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European J of Operational Research, 2010, 200(2):395-408.
[10] Gao J, Chen R. A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem[J]. International J of Computational Intelligence Systems, 2011, 4(4):497-508.
[11] Gao J, Chen R, Deng W. An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem[J]. International J of Production Research, 2013, 51(3):641-651.
[12] Lam A Y S, Li V O K. Chemical-reaction-inspired metaheuristic for optimization[J]. IEEE Trans on Evolutionary Computation, 2010, 14(3):381-399.
[13] Xu J, Lam A Y S, Li V O K. Chemical reaction optimization for task scheduling in grid computing[J]. IEEE Trans on Parallel and Distributed Systems, 2011, 22(10):1624-1631.
[14] Li J Q, Pan Q K. Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity[J]. Applied Soft Computing, 2012, 12(9):2896-2912.
[15] Xu J, Lam A Y S, Li V O K. Parallel chemical reaction optimization for the quadratic assignment problem[C]//Proc of the Int Conf on Genetic and Evolutionary Methods. Las Vegas, NV, USA, 2010:125-131.
[16] 郑环宇, 王凌, 方晨. 求解 RCPSP 的一种改进化学反应算法[J/OL].[2012-10-22] http://www.paper.edu.cn/html/releasepaper/2012/10/209/. ZHENG Huanyu, WANG Ling, FANG Chen. An improved chemical reaction optimization algorithm for solving RCPSP[J/OL].[2012-10-22] http://www.paper.edu.cn/html/releasepaper/2012/10/209/.(in Chinese)
[17] Iwata K, Murotsu Y, Oba F, et al. Solution of large-scale scheduling problems for job-shop type machining systems with alternative machine tools[J]. CIRP Annals- Manufacturing Technology, 1980, 29(1):335-338.
[18] Merz P, Freisleben B. A genetic local search approach to the quadratic assignment problem[C]//Proc of the 7th Int Conf on Genetic Algorithms. San Francisco, CA, USA:Morgan Kaufmann, 1997:465-472.
[19] Montgomery D C. Design and Analysis of Experiments[M]. Hoboken:John Wiley and Sons, 2005.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn