• CN：11-2187/TH
  • ISSN：0577-6686
机械工程学报

机械工程学报 ›› 2015, Vol. 51 ›› Issue (20): 27-35.doi: 10.3901/JME.2015.20.027

• 智能制造和RFID技术专栏 • 上一篇    下一篇

扫码分享

求解随机Job Shop调度问题的混合分布估计算法

肖世昌1, 孙树栋1, 国欢1, 金梅2, 杨宏安1   

  1. 1.西北工业大学现代设计与集成制造技术教育部重点实验室 西安 710072;
    2.中航工业西安航空发动机(集团)有限公司 西安 710021
  • 出版日期:2015-10-15 发布日期:2015-10-15
  • 基金资助:
    国家自然科学基金资助项目(51075337, 51475383)

Hybrid Estimation of Distribution Algorithm for Solving the Stochastic Job Shop Scheduling Problem

XIAO Shichang1, SUN Shudong1, GUO Huan1, JIN Mei2, YANG Hongan1   

  1. 1.Key Laboratory of Contemporary Design and Integrated Manufacturing Technology of Ministry of Education, Northwestern Polytechnical University, Xi’ an 710072;
    2.Xi’an Aero-Engine(Group) Co., Ltd., Xi’ an 710021
  • Online:2015-10-15 Published:2015-10-15

PDF

430

摘要： 提出一种混合分布估计算法用于求解具有随机工时的Job shop调度问题。建立随机Job shop调度问题(Stochastic Job shop scheduling problem, SJSSP)数学模型并给出随机期望值模型的评价方法。为提高种群多样性，将(μ+λ)-进化策略(Evolutionary strategy, ES)的重组、变异过程引入分布估计算法(Estimation of distribution algorithm, EDA)，构造一种混合分布估计算法，ES-EDA。根据所采用的基于工序的编码方式，对父代工序继承率的概念进行了定义，并为重组过程设计基于父代工序继承率的个体重组方法，该方法不仅能使子代有效继承父代的优良特征，同时可避免非法解的产生。在标准算例FT06、FT10、FT20的基础上构造加工时间随机的3组算例，并选择文献中的5种算法作为混合分布估计算法的对比算法，仿真试验结果表明混合分布估计算法在优化性能方面具有明显优势。

关键词: 父代工序继承率, 混合分布估计算法, 进化策略, 随机Job Shop调度问题

Abstract: A hybrid estimation of distribution algorithm(EDA) is proposed to solve the stochastic job shop scheduling problem (SJSSP) with stochastic processing times. The mathematic model of the SJSSP and the evaluation method of stochastically expected model are constructed. To enhance the population diversity, the recombination and mutation process of (μ+λ)-Evolutionary strategy are incorporated in the EDA, thus a hybrid EDA, i.e. ES-EDA is constructed. Based on the encoding method of chromosome adopted in this research, the concept of Inherit rate of the operations in parent individual is defined. Then a new recombination method based on the Inherit rate of the operations in parent individual is designed. This recombination method can not only make the offspring inheriting the excellent characteristics of the parent effectively, but also avoiding infeasible solutions. Three problem instances with stochastic processing times for simulation experiment are constructed based on the benchmark instances FT06, FT10 and FT20, the comparison with the simulation results obtained by the 5 algorithms in literatures shows that the ES-EDA has significant advantages in aspect of optimal performance.

Key words: evolutionary strategy, hybrid estimation of distribution algorithms, inherit rate of the operations in parent chromosome, stochastic Job Shop scheduling problem

中图分类号: 

版权所有 © 2019 《机械工程学报》编辑部 | 京ICP备05055788号-30