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

作者：周丰顺; 胡蓉; 钱斌; 张长胜; 向凤红

来源：电子学报, 2022, 1-19.

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

针对一类广泛存在的分布式流水线和车辆运输集成调度问题(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.

• 单位
  自动化学院; 昆明理工大学