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

YANG Shao-wen; QIAN Bin; HU Rong; ZHANG Zi-qi

doi:10.12263/DZXB.20220908

您当前的位置：

首页 >

文章列表页 >

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

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

- Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery
- ACTA ELECTRONICA SINICA Vol. 52, Issue 3, Pages: 909-923(2024)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院，云南昆明 650500
  2.云南省人工智能重点实验室，云南昆明 650500
- 作者简介：
- 基金信息：
  
  Basic Research Key Project of Yunnan Province(202201AS070030)
- DOI：10.12263/DZXB.20220908
  CLC： TP273
- Received：01 August 2022，
  
  Revised：2023-02-18，
  
  Published：25 March 2024
- 稿件说明：
移动端阅览
杨绍文,钱斌,胡蓉,等.混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题[J].电子学报,2024,52(03):909-923.

YANG Shao-wen, QIAN Bin, HU Rong, et al.Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery[J].Acta Electronica Sinica, 2024, 52(03): 909-923.
杨绍文,钱斌,胡蓉,等.混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题[J].电子学报,2024,52(03):909-923. DOI：10.12263/DZXB.20220908

YANG Shao-wen, QIAN Bin, HU Rong, et al.Hybrid Three-Dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery[J].Acta Electronica Sinica, 2024, 52(03): 909-923. DOI：10.12263/DZXB.20220908

摘要

本文针对一类广泛存在的分布式加工装配和车辆配送集成调度问题（Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery，ISP_DPAVD），以最小化运输和延迟惩罚总成本为优化目标，提出一种混合三维分布估计算法（Hybrid three-Dimensional Estimation of Distribution Algorithm，H3DEDA）进行求解.ISP_DPAVD包含两个耦合的子问题，即加工装配阶段子问题（子问题1）和车辆配送阶段子问题（子问题2）.由于每个子问题1的解（部分解1）均会确定1个具体的子问题2，故ISP_DPAVD的解空间非常庞大.根据这一特点，在H3DEDA中，先设计结合邻域变换的启发式规则来快速获取子问题2的优良解，以实现子问题间的部分解耦并明显缩减搜索空间，再设计三维EDA引导的全局搜索和变邻域驱动的局部搜索来获取ISP_DPAVD的高质量解.通过在不同规模测试问题上的仿真实验和算法比较，验证了H3DEDA求解ISP_DPAVD的有效性.

Abstract

This paper proposes a hybrid three-dimensional distribution estimation algorithm (H3DEDA) to minimize the total cost of transportation and delay penalties for a kind of widely existed integrated scheduling problem (ISP_DPAVD)

which includes two coupled subproblems

i.e.

the subproblem in the production and assembly stage (subproblem 1) and the subproblem in the vehicle distribution stage (subproblem 2). Since each solution of subproblem 1 determines a specific subproblem 2

the solution space of the ISP_DPAVD is very large. According to this characteristic

in H3DEDA (Hybrid three-Dimensional Estimation of Distribution Algorithm)

the heuristic rules combined with neighborhood transformation are designed to quickly obtain the excellent solution of subproblem 2

so as to achieve partial decoupling between subproblems and significantly reduce the search space. Then

the global search guided by three-dimensional EDA and the local search driven by variable neighborhood operations are devised to acquire high-quality solution for the ISP_DPAVD. Simulation experiments and comparisons on the test problems with different scales verify the effectiveness of H3DEDA in solving ISP_DPAVD.

关键词

Keywords

references

XIONG F L , XING K Y . Meta-heuristics for the distributed two-stage assembly scheduling problem with bi-criteria of makespan and mean completion time [J ] . International Journal of Production Research , 2014 , 52 ( 9 ): 2743 - 2766 .

XIONG F L , XING K Y , WANG F , et al . Minimizing the total completion time in a distributed two stage assembly system with setup times [J ] . Computers & Operations Research , 2014 , 47 : 92 - 105 .

ZHANG G H , XING K Y . Memetic social spider optimization algorithm for scheduling two-stage assembly flowshop in a distributed environment [J ] . Computers & Industrial Engineering , 2018 , 125 : 423 - 433 .

LEI D M , SU B , LI M . Cooperated teaching-learning-based optimisation for distributed two-stage assembly flow shop scheduling [J ] . International Journal of Production Research , 2021 , 59 ( 23 ): 7232 - 7245 .

陈雅玲 , 雷德明 . 求解分布式两阶段装配流水车间调度的帝国竞争协作算法 [J ] . 控制理论与应用 , 2021 , 38 ( 12 ): 1957 - 1967 .

CHEN Y L , LEI D M . An imperialist competition and cooperation algorithm for distributed two-stage assembly flow shop scheduling [J ] . Control Theory & Applications , 2021 , 38 ( 12 ): 1957 - 1967 . (in Chinese)

GHARAEI A , JOLAI F . A multi-agent approach to the integrated production scheduling and distribution problem in multi-factory supply chain [J ] . Applied Soft Computing , 2018 , 65 : 577 - 589 .

LI S , ZHONG X L , LI H , et al . Batch delivery scheduling with multiple decentralized manufacturers [J ] . Mathematical Problems in Engineering , 2014 , 2014 : 321513 .

YıLMAZ Ö F , PARDALOS P M . Minimizing average lead time for the coordinated scheduling problem in a two-stage supply chain with multiple customers and multiple manufacturers [J ] . Computers & Industrial Engineering , 2017 , 114 : 244 - 257 .

HAO J H , CAO L S , JIANG D K . Integrated production-distribution scheduling problem with multiple independent manufacturers [J ] . Mathematical Problems in Engineering , 2015 , 2015 : 579893 .

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 : 5120640 .

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 .

QIN H , LI T , TENG Y , et al . Integrated production and distribution scheduling in distributed hybrid flow shops [J ] . Memetic Computing , 2021 , 13 ( 2 ): 185 - 202 .

HOU Y S , FU Y P , GAO K Z , et al . Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows [J ] . Expert Systems with Applications , 2022 , 187 : 115827 .

FU Y P , HOU Y S , CHEN Z H , et al . Modelling and scheduling integration of distributed production and distribution problems via black widow optimization [J ] . Swarm and Evolutionary Computation , 2022 , 68 : 101015 .

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 .

周丰顺 , 胡蓉 , 钱斌 , 等 . 超启发式三维分布估计算法求解分布式流水线和车辆运输集成调度问题 [J ] . 电子学报 , 2021 , 49 ( 12 ): 2419 - 2427 .

ZHOU F S , HU R , QIAN B , 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 . (in Chinese)

郭晨 , 曾思豪 , 郭钧 , 等 . 混合分布估计算法求解模糊分布式装配柔性车间调度问题 [J ] . 系统工程理论与实践 , 2021 , 41 ( 4 ): 1037 - 1048 .

GUO C , ZENG S H , GUO J , et al . Hybrid estimation of distribution algorithm for distributed assembly flexible job shop scheduling problem with fuzzy processing time [J ] . Systems Engineering-Theory & Practice , 2021 , 41 ( 4 ): 1037 - 1048 . (in Chinese)

ZHANG Z Q , QIAN B , HU R , et al . A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem [J ] . Swarm and Evolutionary Computation , 2021 , 60 : 100785 .

POTTS C N , SEVAST'JANOV S V , STRUSEVICH V A , et al . The two-stage assembly scheduling problem: Complexity and approximation [J ] . Operations Research , 1995 , 43 ( 2 ): 346 - 355 .

AL-ANZI F S , ALLAHVERDI A . A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times [J ] . European Journal of Operational Research , 2007 , 182 ( 1 ): 80 - 94 .

BASIR S A , MAZDEH M M , NAMAKSHENAS M . Bi-level genetic algorithms for a two-stage assembly flow-shop scheduling problem with batch delivery system [J ] . Computers & Industrial Engineering , 2018 , 126 : 217 - 231 .

MONTGOMERY D C . Design and Analysis of Experiments [M ] . 6th ed . Hoboken : John Wiley & Sons , 2005 .

胡蓉 , 陈文博 , 钱斌 , 等 . 学习型蚁群算法求解绿色多车场车辆路径问题 [J ] . 系统仿真学报 , 2021 , 33 ( 9 ): 2095 - 2108 .

HU R , CHEN W B , QIAN B , et al . Learning ant colony algorithm for green multi-depot vehicle routing problem [J ] . Journal of System Simulation , 2021 , 33 ( 9 ): 2095 - 2108 . (in Chinese)

李正雯 , 胡蓉 , 钱斌 , 金怀平 , 吕阳 . 学习型离散排超联赛算法求解带时间窗的绿色多车型两级车辆路径问题 [J ] . 控制理论与应用 , 2023 , 40 ( 3 ): 549 - 557 .

LI Z W , HU R , QIAN B , et al . A learning discrete volleyball premier league algorithm for solving green two-echelon heterogeneous-fleet vehicle routing problem with time windows [J ] . Control Theory and Technology , 2023 , 40 ( 3 ): 549 - 557 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

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

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

Related Author

HU Rong

QIAN Bin

YANG Shao-wen

HU Rong

QIAN Bin

ZHANG Chang-sheng

XIANG Feng-hong

ZHOU Feng-shun

Related Institution

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

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

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

⁰