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

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

doi:10.12263/DZXB.20201057

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-12-08

- 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题
- Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem
- 电子学报 2021年49卷第12期页码：2419-2427
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院, 云南昆明 650500
  2.昆明理工大学云南省人工智能重点实验室, 云南昆明 650500
- 作者简介：
  
  [ "周丰顺男,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;61963022)
- DOI：10.12263/DZXB.20201057
  中图分类号： TP273
- 收稿：2020-09-24，
  
  修回：2021-03-03，
  
  纸质出版：2021-12-25
- 稿件说明：
移动端阅览
周丰顺,胡蓉,钱斌等.超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J].电子学报,2021,49(12):2419-2427.

ZHOU Feng-shun,HU Rong,QIAN Bin,et al.Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem[J].ACTA ELECTRONICA SINICA,2021,49(12):2419-2427.
周丰顺,胡蓉,钱斌等.超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[J].电子学报,2021,49(12):2419-2427. DOI： 10.12263/DZXB.20201057.

ZHOU Feng-shun,HU Rong,QIAN Bin,et al.Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem[J].ACTA ELECTRONICA SINICA,2021,49(12):2419-2427. DOI： 10.12263/DZXB.20201057.

摘要

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

关键词

Keywords

references

戚远航 , 蔡延光 , 蔡颢 , 等 . 带容量约束的供应链物流运输调度问题的双层变邻域蝙蝠算法 [J]. 电子学报 , 2019 , 47 ( 7 ): 1434 - 1442 .

Qi Y H , Cai Y G , Cai H , et al . Two-level bat algorithm with variable neighborhood search for capacitated vehicle routing problem in supply chain [J]. Acta Electronica Sinica , 2019 , 47 ( 7 ): 1434 - 1442 . (in Chinese)

Moons S , Ramaekers K , Caris A , et al . Integrating production scheduling and vehicle routing decisions at the operational decision level: A review and discussion [J]. Computers & Industrial Engineering , 2017 , 104 : 224 - 245 .

Mohammadi S , Al-E-hashem S M J M , Rekik Y . An integrated production scheduling and delivery route planning with multi-purpose machines: A case study from a furniture manufacturing company [J]. International Journal of Production Economics , 2020 , 219 : 347 - 359 .

Feng X , Xu Z Y . Integrated production and transportation scheduling on parallel batch-processing machines [J]. IEEE Access , 2019 , 7 : 148393 - 148400 .

Gharaei A , Jolai F . A branch and price approach to the two-agent integrated production and distribution scheduling [J]. Computers & Industrial Engineering , 2019 , 136 : 504 - 515 .

Gharaei A , Jolai F . Two heuristic methods based on decomposition to the integrated multi-agent supply chain scheduling and distribution problem [J]. Optimization Methods and Software , 2020 . DOI: 10.1080/10556788.202.1714615 http://dx.doi.org/10.1080/10556788.202.1714615 .

Abdollahzadeh V , Nakhaikamalabadi I , Hajimolana S M , et al . A multifactory integrated production and distribution scheduling problem with parallel machines and immediate shipments solved by improved whale optimization algorithm [J]. Complexity , 2018 , 2018 : 1 - 21 .

Karimi N , Davoudpour H . A branch and bound method for solving multi-factory supply chain scheduling with batch delivery [J]. Expert Systems with Applications , 2015 , 42 ( 1 ) : 238 - 245 .

Marandi F , Fatemi Ghomi S M T . Integrated multi-factory production and distribution scheduling applying vehicle routing approach [J]. International Journal of Production Research , 2019 , 57 ( 3 ): 722 - 748 .

李尚函 , 胡蓉 , 钱斌 , 等 . 超启发式遗传算法求解模糊柔性作业车间调度 [J]. 控制理论与应用 , 2020 , 37 ( 2 ): 316 - 330 .

Li S H , Hu R , Qian B , et al . Hyper-heuristic genetic algorithm for solving fuzzy flexible job shop scheduling problem [J]. Control Theory & Applications , 2020 , 37 ( 2 ): 316 - 330 . (in Chinese)

Park J , Mei Y , Nguyen S , et al . An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop scheduling [J]. Applied Soft Computing , 2018 , 63 : 72 - 86 .

田云娜 , 李冬妮 , 刘兆赫 , 等 . 一种基于动态决策块的超启发式跨单元调度方法 [J]. 自动化学报 , 2016 , 42 ( 4 ): 524 - 534 .

Tian Y N , Li D N , Liu Z H , et al . A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling [J]. Acta Automatica Sinica , 2016 , 42 ( 4 ): 524 - 534 . (in Chinese)

周雅兰 , 王甲海 , 黄聪 . 求解排列问题的分布估计离散粒子群优化算法 [J]. 电子学报 , 2014 , 42 ( 3 ): 561 - 571 .

Zhou Y L , Wang J H , Huang C . Estimation of distribution-discrete particle swarm optimization algorithm for permutation-based problems [J]. Acta Electronica Sinica , 2014 , 42 ( 3 ): 561 - 571 . (in Chinese)

程玉虎 , 王雪松 , 郝名林 . 一种多样性保持的分布估计算法 [J]. 电子学报 , 2010 , 38 ( 3 ): 591 - 597 .

Cheng Y H , Wang X S , Hao M L . An estimation of distribution algorithm with diversity preservation [J]. Acta Electronica Sinica , 2010 , 38 ( 3 ): 591 - 597 . (in Chinese)

Faraji Amiri M , Behnamian J . Multi-objective green flowshop scheduling problem under uncertainty: Estimation of distribution algorithm [J]. Journal of Cleaner Production , 2020 , 251 : 119734 .

曹政才 , 林诚然 , 黄冉 . 带等待时间约束并行机调度问题的Copula分布估计算法 [J]. 电子学报 , 2017 , 45 ( 12 ): 2949 - 2956 .

Cao Z C , Lin C R , Huang R . An estimation of distribution algorithm based on copula for parallel machine scheduling with constrained waiting time [J]. Acta Electronica Sinica , 2017 , 45 ( 12 ): 2949 - 2956 . (in Chinese)

Wang S Y , Wang L . An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem [J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2016 , 46 ( 1 ): 139 - 149 .

Shao W S , Pi D C , Shao Z S . A Pareto-based estimation of distribution algorithm for solving multiobjective distributed no-wait flow-shop scheduling problem with sequence-dependent setup time [J]. IEEE Transactions on Automation Science and Engineering , 2019 , 16 ( 3 ): 1344 - 1360 .

Montgomery D C . Design and Analysis of Experiments [M]. Hoboken : John Wiley and Sons , 2005 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题

混合帝国竞争算法求解带多行程批量配送的多工厂集成调度问题