电子学报 ›› 2021, Vol. 49 ›› Issue (12): 2419-2427.DOI: 10.12263/DZXB.20201057

• 学术论文 • 上一篇    下一篇

超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题

周丰顺1,2, 胡蓉1,2, 钱斌1,2, 张长胜1, 向凤红1   

  1. 1.昆明理工大学信息工程与自动化学院, 云南 昆明 650500
    2.昆明理工大学云南省人工智能重点实验室, 云南 昆明 650500
  • 收稿日期:2020-09-24 修回日期:2021-03-03 出版日期:2021-12-25
    • 通讯作者:
    • 胡蓉
    • 作者简介:
    • 周丰顺 男,1998年出生,湖南永州人.硕士研究生,研究方向为优化调度与智能算法.E-mail:1445155907@qq.com
      胡 蓉(通讯作者) 女,1974年出生,云南曲靖人.副教授,硕士生导师,研究方向为优化方法与决策支持系统.E-mail:ronghu@vip.163.com
      钱 斌 男,1976年出生,云南曲靖人.教授,博士生导师,研究方向为智能调度理论与方法.E-mail:bin.qian@vip.163.com
      张长胜 男,1970年出生,云南昆明人.副教授,硕士生导师,研究方向为光纤传感器技术与应用.E-mail:1368037752@qq.com
      向凤红 男,1964年出生,四川省盐亭人.教授,硕士生导师,研究方向为智能优化方法.E-mail:xiangfh5447@sina.com
    • 基金资助:
    • 国家自然科学基金 (62173169)

Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem

ZHOU Feng-shun1,2, HU Rong1,2, QIAN Bin1,2, ZHANG Chang-sheng1, XIANG Feng-hong1   

  1. 1.School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
    2.Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming, Yunnan 650500, China
  • Received:2020-09-24 Revised:2021-03-03 Online:2021-12-25 Published:2021-12-25
    • Corresponding author:
    • HU Rong
    • Supported by:
    • National Natural Science Foundation of China (62173169)

摘要:

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(Distributed Permutation Flow-shop and Vehicle Transportation Integrated Scheduling Problem, DPFVTISP), 本文建立问题模型,并提出一种超启发式三维分布估计算法(Hyper-Heuristic three-Dimensional Estimation of Distribution Algorithm, HH3DEDA) 进行求解. 首先, 根据DPFVTISP的问题特性, 采用贪婪策略设计一种新颖的编解码规则. 其次, 为实现对DPFVTISP问题解空间中不同区域的深入搜索, 设计10种低层启发式操作 (即10种有效的邻域操作), 并将其所构成的排列作为高层个体; 同时在高层采用三维分布估计算法 (three-Dimensional Estimation of Distribution Algorithm, 3DEDA) 学习和积累优质高层个体中块结构及其位置信息, 再通过采样3DEDA中的概率模型生成新的高层个体或排列; 进而在低层将高层所生成的每个新个体所表征的一系列有序的启发式操作作为一种新的启发式算法, 对问题解空间执行较深入的邻域搜索. 最后, 通过仿真实验与算法对比验证HH3DEDA可有效求解DPFVTISP.

关键词: 分布式流水线, 车辆运输, 集成调度, 超启发式算法, 三维分布估计算法, 块结构

Abstract:

Aiming at a kind of widely existing distributed permutation flow-shop and vehicle transportation integrated scheduling problem(DPFVTISP), this paper establishes the problem model and proposes a hyper-heuristic three-dimensional estimation of distribution algorithm(HH3DEDA) to solve it. Firstly, a novel coding and decoding rules adopting the greedy strategy is designed via analyzing the characteristics of DPFVTISP. Secondly, in order to search different regions in the solution space of DPFVTISP, ten kinds of low-layer heuristic operations, i.e., ten kinds of effective neighborhood operations, are designed, and their permutations are regarded as high-layer individuals. At the same time, the three-dimensional estimation of distribution algorithm (3DEDA) is used in the high layer to learn and accumulate the information of block structures and their positions in the high-quality high-layer individuals, and then new low-layer individuals or permutations are generated by sampling the probability model in 3DEDA. Furthermore, in the low layer, an ordered series of heuristic operations presenting by each new individual generated in the high layer is regarded as a new heuristic algorithm to execute further neighborhood search in the problem’s solution space. Finally, simulations and comparisons demonstrate that HH3DEDA can effectively solve the DPFVTISP.

Key words: distributed permutation flow-shop, vehicle transportation, integrated scheduling, hyper-heuristic algorithm, three-dimensional estimation of distribution algorithm, block structure

中图分类号: