2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种基于动态决策块的超启发式跨单元调度方法

田云娜 李冬妮 刘兆赫 郑丹

田云娜, 李冬妮, 刘兆赫, 郑丹. 一种基于动态决策块的超启发式跨单元调度方法. 自动化学报, 2016, 42(4): 524-534. doi: 10.16383/j.aas.2016.c150402
引用本文: 田云娜, 李冬妮, 刘兆赫, 郑丹. 一种基于动态决策块的超启发式跨单元调度方法. 自动化学报, 2016, 42(4): 524-534. doi: 10.16383/j.aas.2016.c150402
TIAN Yun-Na, LI Dong-Ni, LIU Zhao-He, ZHENG Dan. A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling. ACTA AUTOMATICA SINICA, 2016, 42(4): 524-534. doi: 10.16383/j.aas.2016.c150402
Citation: TIAN Yun-Na, LI Dong-Ni, LIU Zhao-He, ZHENG Dan. A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling. ACTA AUTOMATICA SINICA, 2016, 42(4): 524-534. doi: 10.16383/j.aas.2016.c150402

一种基于动态决策块的超启发式跨单元调度方法

doi: 10.16383/j.aas.2016.c150402
基金项目: 

国家自然科学基金 71401014

详细信息
    作者简介:

    田云娜, 北京理工大学计算机学院智能信息技术北京市重点实验室博士研究生, 延安大学数学与计算机科学学院讲师. 主要研究方向为进化计算与智能优化方法.E-mail:ydtianyunna@163.com

    刘兆赫, 北京理工大学计算机学院智能信息技术北京市重点实验室硕士研究生. 主要研究方向为进化计算和生产调度.E-mail:719042341@qq.com

    郑丹, 北京理工大学计算机学院智能信息技术北京市重点实验室硕士研究生. 主要研究方向为进化计算和生产调度.E-mail:zhengdan04@163.com

    通讯作者:

    李冬妮, 北京理工大学计算机学院智能信息技术北京市重点实验室副教授. 主要研究方向为智能优化方法及其在制造业的应用.E-mail:ldn@bit.edu.cn

A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling

Funds: 

National Natural Science Foundation of China 71401014

More Information
    Author Bio:

    Ph. D. candidate at the Beijing Key Laboratory of Intelli- gent Information Technology, School of Computer Science, Beijing Institute of Technology and lec- turer at the College of Mathematics and Computer Science, Yan0an University. Her research interest covers evolution- ary computation and intelligent optimization approaches.

    Master student at the Beijing Key Laboratory of Intelli- gent Information Technology, School of Computer Science, Beijing Institute of Technology. His research interest covers evolutionary com- putation and production scheduling.

    Master student at the Beijing Key Laboratory of Intelli- gent Information Technology, School of Computer Science, Beijing Institute of Technology. Her research interest covers evolutionary com- putation and production scheduling.

    Corresponding author: LI Dong-Ni Associate professor at the Beijing Key Laboratory of Intelli- gent Information Technology, School of Computer Science, Beijing Institute of Technology. Her re- search interest covers intelligent optimization approaches and their applications to the manufacturing industry. Cor- responding author of this paper.
  • 摘要: 对运输能力受限条件下的跨单元调度问题进行分析, 提出一种基于动态决策块和蚁群优化 (Ant colony optimization, ACO) 的超启发式方法, 同时解决跨单元生产调度和运输调度问题. 在传统超启发式方法的基础上, 采用动态决策块策略, 通过蚁群算法合理划分决策块, 并为决策块选择合适的规则. 实验表明, 采用动态决策块策略的超启发式方法比传统的超启发式方法具有更好的性能, 本文所提的方法在最小化加权延迟总和目标方面有较好的优化能力 并且具有较高的计算效率.
  • 图  1  DABH算法的整体流程图

    Fig.  1  General algorithm of DABH

    图  2  General algorithm of DABH

    Fig.  2  Representation of decision blocks whose size is 1

    图  3  决策块大小不全为1 的编码

    Fig.  3  Representation of decision blocks with di®erent sizes

    图  4  最小化TWT 目标下的单因子主效应图

    Fig.  4  Influence of each factor with respect to minimizing TWT

    图  5  最小化TWT 目标下的双因子交互作用图

    Fig.  5  In°uence of 2-factor interaction with respect to minimizing TWT

    图  6  DABH 与不同决策块划分策略之间的Gap 比较

    Fig.  6  Gap values between DABH and di®erent decision block strategies

    图  7  DABH 与DGBH 的收敛过程比较

    Fig.  7  Evolutionary processes of DABH and DGBH

    表  1  生成算例属性值

    Table  1  Attributes for generating test problems

    算例产生参数取值范围
    工件数U[5, 450]
    机器数U[6, 120]
    单元数(小车数) U(3, 15]
    每个单元内机器数U[2, 6]
    小车容量U[2, 10]
    工件权重U(0, 1]
    工序加工时间U[1, 30]
    单元间转移时间U[6, 50]
    下载: 导出CSV

    表  2  DABH参数

    Table  2  Parameters in DABH

    参数范围
    ρ (0.01, 0.05, 0.2, 0.8)
    Q/τmax (0.01, 0.05, 0.2, 0.8)
    下载: 导出CSV

    表  3  DABH 与静态决策块划分策略的性能比较

    Table  3  Comparison between DABH and static decision block strategies

    测试用例TWT 运行时间(s)GapONE(%) GapALL(%) GapAVG(%)
    DABHDABH-ONEDABH-ALLDABH-AVG
    p5m6c300.00.00.01.8---
    p15m8c300.010.50.04.5---
    p20m11c300.015.50.05.6---
    p40m13c51317.51320.33363.72224.928.20.2155.368.9
    p50m15c54463.44717.47292.85750.638.65.763.428.8
    p60m16c57853.88183.210594.39416.948.94.234.919.9
    p70m20c77966.69736.611216.29798.474.522.240.823.0
    p80m21c716504.919385.319653.919137.884.117.519.116.0
    p90m21c78312.69853.911981.99554.098.918.544.114.9
    p100m25c921774.826339.425924.725197.793.321.019.115.7
    p120m30c941868.645104.247292.244605.0145.27.713.06.5
    p140m35c1143255.447646.44752347284.219910.29.99.3
    p160m40c1153375.961828.756588.856262.823215.86.05.4
    p180m45c137876186352.789622.883336.1299.59.613.85.8
    p200m50c15110299.3119319.6119545.3115330.3323.38.28.44.6
    p250m65c15155422.9167271.9164193.1164003.1447.57.65.65.5
    p300m75c15232254.5255936247079.6243052.9514.510.26.44.6
    p350m90c15303144.1334527.3316700.5314547.5692.010.44.53.8
    p400m100c15378489.1421689.9406151.6397148798.511.47.34.9
    p450m120c15466779.7535080.7489769.7486647.21187.914.64.94.3
    平均值11.526.814.2
    下载: 导出CSV

    表  4  DABH 与DGBH 的性能比较

    Table  4  Comparison between DABH and DGBH

    测试用例TWT运行时间(s)GapDGBH(%)
    DABHDGBH
    p10m1068657048.01.92.7
    p20m102617626686.84.02.0
    p20m153762539070.26.43.8
    p20m2023791.825214.89.36.0
    p25m2041136.744152.314.37.3
    p25m2462536.867871.518.98.5
    p28m25118555.2123994.318.94.6
    p32m25147814.5155273.525.85
    p30m30100600.210550029.44.9
    p40m25207853.8219031.532.25.4
    平均值5.0
    下载: 导出CSV
  • [1] Wemmerlov U, Johnson D J. Cellular manufacturing at 46 user plants: implementation experiences and performance improvements. International Journal of Production Research, 1997, 35(1): 29-49 doi: 10.1080/002075497195966
    [2] Garza O, Smunt T L. Countering the negative impact of intercell flow in cellular manufacturing. Journal of Operations Management, 1991, 10(1): 92-118 doi: 10.1016/0272-6963(91)90037-X
    [3] Solimanpur M, Elmi A. A tabu search approach for cell scheduling problem with makespan criterion. International Journal of Production Economics, 2013, 141(2): 639-645 doi: 10.1016/j.ijpe.2012.10.001
    [4] Tang J, Wang X, Kaku I, Yung K L. Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach. Journal of Intelligent Manufacturing, 2009, 21(4): 525-537 http://cn.bing.com/academic/profile?id=2006533609&encoded=0&v=paper_preview&mkt=zh-cn
    [5] Tavakkoli-Moghaddam R, Javadian N, Khorrami A, Gholipour-Kanani Y. Design of a scatter search method for a novel multi-criteria group scheduling problem in a cellular manufacturing system. Expert Systems with Applications, 2010, 37(3): 2661-2669 doi: 10.1016/j.eswa.2009.08.012
    [6] Zeng C K, Tang J F, Yan C J. Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles. Journal of Intelligent Manufacturing, 2015, 26(5): 845-859 doi: 10.1007/s10845-014-0875-x
    [7] Elmi A, Solimanpur M, Topaloglu S, Elmi A. A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts. Computers & Industrial Engineering, 2011, 61(1): 171-178 http://cn.bing.com/academic/profile?id=1997058568&encoded=0&v=paper_preview&mkt=zh-cn
    [8] Li D N, Wang Y, Xiao G X, Tang J F. Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes. Computers & Operations Research, 2013, 40(5): 1207-1223 http://cn.bing.com/academic/profile?id=1971316543&encoded=0&v=paper_preview&mkt=zh-cn
    [9] Vepsalainen A P J, Morton T E. Priority rules for job shops with weighted tardiness costs. Management Science, 1987, 33(8): 1035-1047 doi: 10.1287/mnsc.33.8.1035
    [10] Ruiz R, Vázquez-Rodríguez J A. The hybrid flow shop scheduling problem. European Journal of Operational Research, 2010, 205(1): 1-18 doi: 10.1016/j.ejor.2009.09.024
    [11] Park S C, Raman N, Shaw M J. Adaptive scheduling in dynamic flexible manufacturing systems: a dynamic rule selection approach. IEEE Transactions on Robotics and Automation, 1997, 13(4): 486-502 doi: 10.1109/70.611301
    [12] Burke E K, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R. Hyper-heuristics: a survey of the state of the art. Journal of the Operational Research Society, 2013, 64(12): 1695-1724 doi: 10.1057/jors.2013.71
    [13] Huang J, Süer G A. A dispatching rule-based genetic algorithm for multi-objective job shop scheduling using fuzzy satisfaction levels. Computers & Industrial Engineering, 2015, 86: 29-42 http://cn.bing.com/academic/profile?id=2063972265&encoded=0&v=paper_preview&mkt=zh-cn
    [14] Zhang R, Song S J, Wu C. A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 2013, 67(1-4): 5-17 doi: 10.1007/s00170-013-4751-1
    [15] Vázquez-Rodríguez J A, Petrovic S, Salhi A. An investigation of hyper-heuristic search spaces. In: Proceeding of the 2007 IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007. 3776-3783
    [16] Vázquez-Rodríguez J A, Petrovic S. A new dispatching rule based genetic algorithm for the multi-objective job shop problem. Journal of Heuristics, 2010, 16(6): 771-793 doi: 10.1007/s10732-009-9120-8
    [17] Li D N, Li M, Meng X W, Tian Y N. A hyperheuristic approach for intercell scheduling with single processing machines and batch processing machines. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(2): 315-325 doi: 10.1109/TSMC.2014.2332443
    [18] 贾凌云, 李冬妮, 田云娜. 基于混合蛙跳和遗传规划的跨单元调度方法. 自动化学报, 2015, 41(5): 936-948 http://www.aas.net.cn/CN/abstract/abstract18668.shtml

    Jia Ling-Yun, Li Dong-Ni, Tian Yun-Na. An Intercell scheduling approach using shuffled frog leaping algorithm and genetic programming. Acta Automatica Sinica, 2015, 41(5): 936-948 http://www.aas.net.cn/CN/abstract/abstract18668.shtml
    [19] 刘兆赫, 李冬妮, 王乐衡, 田云娜. 考虑运输能力限制的跨单元调度方法. 自动化学报, 2015, 41(5): 885-898 http://www.aas.net.cn/CN/abstract/abstract18663.shtml

    Liu Zhao-He, Li Dong-Ni, Wang Le-Heng, Tian Yun-Na. An inter-cell scheduling approach considering transportation capacity constraints. Acta Automatica Sinica, 2015, 41(5): 885-898 http://www.aas.net.cn/CN/abstract/abstract18663.shtml
    [20] Yang T, Kuo Y, Cho C. A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem. European Journal of Operational Research, 2007, 176(3): 1859-1873 doi: 10.1016/j.ejor.2005.10.048
    [21] Huang K L, Liao C J. Ant colony optimization combined with taboo search for the job shop scheduling problem. Computers & Operations Research, 2008, 35(4): 1030-1046 http://cn.bing.com/academic/profile?id=2011649121&encoded=0&v=paper_preview&mkt=zh-cn
    [22] Montgomery D C. Design and Analysis of Experiments (6th Edition). New York: John Wiley & Sons, 2005.
  • 加载中
图(7) / 表(4)
计量
  • 文章访问数:  2097
  • HTML全文浏览量:  227
  • PDF下载量:  1127
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-06-25
  • 录用日期:  2015-12-28
  • 刊出日期:  2016-04-01

目录

    /

    返回文章
    返回