混合迭代贪婪算法求解准时生产分布式流水线调度问题
作者:
作者单位:

1.昆明理工大学信息工程与自动化学院;2.昆明理工大学机电工程学院

作者简介:

通讯作者:

中图分类号:

TP273

基金项目:

国家自然科学基金项目(面上项目,重点项目,重大项目)


Hybrid iterated greedy algorithm for just in time distributed permutation flowshop scheduling problem
Author:
Affiliation:

Faculty of Information Engineering and Automation, Kunming University of Science and Technology

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    本文针对以最小化总延迟时间为优化目标的分布式置换流水线问题(Distributed permutation flowshop scheduling problem, DPFSP), 建立问题排序模型, 并提出混合迭代贪婪算法(Hybrid iterated greedy, HIG) 进行求解. 基于问题特点提出最小工期差规则(Smallest due date difference value, SDV) 规则及三种工厂分配规则, 同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法. 首先, 通过实验确定使用分配规则1将工件向各工厂进行分配, 同时将结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解. 其次, 为了增加解的多样性, 提出一种关键工厂的移除策略和适用于问题的模拟退火机制. 然后, 设计基于四种有效邻域操作的两阶段变邻域下降搜索策略, 用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索. 最后, 通过仿真实验和算法比较验证了HIG求解本文问题的有效性.

    Abstract:

    In this paper, for the distributed permutation flowshop scheduling problem, which is optimized to minimize the total tardiness, a problem sorting model is established, and a hybrid iterated greedy algorithm to solve the problem. Based on the characteristics of the problem, this paper proposes the minimum due date difference value (SDV) rule and three kinds of factory assignment rules. At the same time, combining with the nature of the problem, this paper proposes two methods to estimate the lower bound of the target value of the problem when the job is assigned to each factor. At the same time, combining with the nature of the problem, two methods for estimating the lower bound of the target value of the problem are proposed. First, through experimental analysis, it is determined that the SDV is used as a encoding rule, and the NEH combined with the lower bound estimation method is used as an improved heuristic algorithm to generate a higher quality initial solution. Secondly, in order to increase the diversity of solutions, a key factory removal strategy and simulated annealing mechanism are proposed. Then, the design is based on four A two-stage variable neighborhood descent search strategy for effective neighborhood operation is used to search different regions of the problem solution space in depth and detail in each generation of HIG. Finally, simulation experiments and algorithm comparison verify the effectiveness of hig in solving this problem.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-03-15
  • 最后修改日期:2021-07-30
  • 录用日期:2021-08-09
  • 在线发布日期: 2021-09-01
  • 出版日期: