2.845

2023影响因子

(CJCR)

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

留言板

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

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

求解混合流水车间调度问题的分布估计算法

王圣尧 王凌 许烨 周刚

王圣尧, 王凌, 许烨, 周刚. 求解混合流水车间调度问题的分布估计算法. 自动化学报, 2012, 38(3): 437-443. doi: 10.3724/SP.J.1004.2012.00437
引用本文: 王圣尧, 王凌, 许烨, 周刚. 求解混合流水车间调度问题的分布估计算法. 自动化学报, 2012, 38(3): 437-443. doi: 10.3724/SP.J.1004.2012.00437
WANG Sheng-Yao, WANG Ling, XU Ye, ZHOU Gang. An Estimation of Distribution Algorithm for Solving Hybrid Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2012, 38(3): 437-443. doi: 10.3724/SP.J.1004.2012.00437
Citation: WANG Sheng-Yao, WANG Ling, XU Ye, ZHOU Gang. An Estimation of Distribution Algorithm for Solving Hybrid Flow-shop Scheduling Problem. ACTA AUTOMATICA SINICA, 2012, 38(3): 437-443. doi: 10.3724/SP.J.1004.2012.00437

求解混合流水车间调度问题的分布估计算法

doi: 10.3724/SP.J.1004.2012.00437
详细信息
    通讯作者:

    王圣尧, 清华大学自动化系博士研究生. 主要研究方向为智能优化与生产调度. E-mail: wangshengyao@tsinghua.org.cn

An Estimation of Distribution Algorithm for Solving Hybrid Flow-shop Scheduling Problem

  • 摘要: 针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性.
  • [1] Wang Ling. Shop Scheduling with Genetic Algorithms. Beijing: Tsinghua University Press, 2003. 138-145(王凌. 车间调度及其遗传算法. 北京: 清华大学出版社, 2003. 138-145)[2] Wang Ling, Zhou Gang, Xu Ye, Jin Yi-Hui. Advances in the study on hybrid flow-shop scheduling. Control and Instrument in Chemical Industry, 2011, 38(1): 1-8(王凌, 周刚, 许烨, 金以慧. 混合流水线调度研究进展. 化工自动化及仪表, 2011, 38(1): 1-8)[3] Hoogeveen J A, Lenstra J K, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research, 1996, 89(1): 172-175[4] Portmann M C, Vignier A, Dardilhac D, Dezalay D. Branch and bound crossed with GA to solve hybrid flowshops. European Journal of Operational Research, 1998, 107(2): 389-400[5] Soewandi H, Elmaghraby S E. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transactions, 2003, 35(5): 467-477[6] Figielska E. A genetic algorithm and a simulated annealing algorithm combined with column generation technique for solving the problem of scheduling in the hybrid flowshop with additional resources. Computers and Industrial Engineering, 2009, 56(1): 142-151[7] Xuan Hua, Tang Li-Xin. Lagrangian relaxation algorithm for real-time hybrid flow-shop scheduling with no-wait in process. Control and Decision, 2006, 21(4): 376-380(轩华, 唐立新. 实时无等待HFS调度的一种拉格朗日松弛算法. 控制与决策, 2006, 21(4): 376-380)[8] Riane F, Artiba A, Elmaghraby S E. Sequencing a hybrid two-stage flowshop with dedicated machines. International Journal of Production Research, 2002, 40(17): 4353-4380[9] Zhou Hui-Ren, Tang Wan-Sheng, Wei Ying-Hui. Optimize flexible flow-shop scheduling using genetic algorithm. Computer Engineering and Applications, 2009, 45(30): 224-226(周辉仁, 唐万生, 魏颖辉. 柔性Flow-Shop调度的遗传算法优化. 计算机工程与应用, 2009, 45(30): 224-226)[10] Low C. Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines. Computers and Operations Research, 2005, 32(8): 2013-2025[11] Wang X, Tang L. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Computers and Operations Research, 2009, 36(3): 907-918[12] Alaykyran K, Engin O, Doyen A. Using ant colony optimization to solve hybrid flow shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 2007, 35(5-6): 541-550[13] Tseng C T, Liao C J. A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. International Journal of Production Research, 2008, 46(17): 4655-4670[14] Liu F, Zhang X P, Zou F X, Zeng L L. Immune clonal selection algorithm for hybrid flow-shop scheduling problem. In: Proceedings of the Chinese Control and Decision Conference. Guilin, China: IEEE, 2009. 2605-2609[15] Xu Y, Wang L, Zhou G, Wang S Y. An effective shuffled frog leaping algorithm for solving hybrid flow-shop scheduling problem. In: Proceedings of the International Conference on Intelligent Computing. Zhengzhou, China: Springer, 2011. 560-567[16] Muhlenbein H, Paass G. From recombination of genes to the estimation of distributions I. binary parameters. In: Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1996. 178-187[17] Baluja S. Population-Based Incremental Learning: a Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Technical Report CMU-CS-94-163, Computer Science Department, Carnegie Mellon University, USA, 1994[18] Zhou Shu-De, Sun Zeng-Qi. A survey on estimation of distribution algorithms. Acta Automatica Sinica, 2007, 33(2): 113-124(周树德, 孙增圻. 分布估计算法综述. 自动化学报, 2007, 33(2): 113-124)[19] Brah S A, Luan L L. Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 1999, 113(1): 113-122[20] Cui Jian-Shuang, Li Tie-Ke, Zhang Wen-Xin. Hybrid flowshop scheduling model and its genetic algorithm. Journal of University of Science and Technology Beijing, 2005, 27(5): 623-626(崔建双, 李铁克, 张文新. 混合流水车间调度模型及其遗传算法. 北京科技大学学报, 2005, 27(5): 623-626)[21] Montgomery D C. Design and Analysis of Experiments (Sixth Edition). Hoboken: John Wiley and Sons, 2005
  • 加载中
计量
  • 文章访问数:  2457
  • HTML全文浏览量:  64
  • PDF下载量:  1971
  • 被引次数: 0
出版历程
  • 收稿日期:  2011-06-13
  • 修回日期:  2011-10-24
  • 刊出日期:  2012-03-20

目录

    /

    返回文章
    返回