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

ZHOU Feng-shun; HU Rong; QIAN Bin; ZHANG Chang-sheng; XIANG Feng-hong

doi:10.12263/DZXB.20201057

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2025-12-08

- Hyper-Heuristic Three-Dimensional Estimation of Distribution Algorithm for Solving Distributed Permutation Flow-Shop and Vehicle Transportation Integrated Scheduling Problem
- ACTA ELECTRONICA SINICA Vol. 49, Issue 12, Pages: 2419-2427(2021)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院, 云南昆明 650500
  2.昆明理工大学云南省人工智能重点实验室, 云南昆明 650500
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201057
  CLC： TP273
- Received：24 September 2020，
  
  Revised：2021-03-03，
  
  Published：25 December 2021
- 稿件说明：
移动端阅览
周丰顺,胡蓉,钱斌等.超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题[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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery

Hybrid Imperialist Competitive Algorithm for Solving Multi-Factory Integrated Scheduling Problem with Multi-Trip Batch Delivery

Related Author

YANG Shao-wen

QIAN Bin

HU Rong

ZHANG Zi-qi

YANG Shao-wen

QIAN Bin

HU Rong

TANG Jie-kai

Related Institution

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

Yunnan Key Laboratory of Artificial Intelligence

Yunnan Key Laboratory of Artificial Intelligence， Kunming University of Science and Technology

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

Key Laboratory of Artificial Intelligence in Yunnan Province, Kunming University of Science and Technology

⁰