面向柔性生产资源的分布式农机生产调度优化

doi:10.3778/j.issn.1002-8331.2305-0382

摘要/Abstract

摘要： 在经济全球化背景下，分布式制造和调度系统已成为大型农机生产企业的主流生产模式。针对农机生产过程中多品种小批量的生产特点，构建出一种分布式两阶段异构混合流水车间调度问题模型，提出了一种知识引导的分布估计算法，求解分布式异构混合流水车间调度问题模型的子问题：工厂分配、工件加工顺序和加工机器分配。改进的分布估计算法融合了多种启发式构造和随机方法进行种群初始化，并对候选解进行迭代优化，通过对求解问题的特性进行分析，提高关键加工阶段加工资源的利用率，对于不同规模的调度问题提出了相应的知识引导的强化机制和多种局部搜索策略。通过仿真实验，将提出的算法与其他三类算法进行对比，验证了改进的分布估计算法的有效性和稳定性。实验结果表明，利用调度问题特性引导算法的演化过程，可有效地提升知识引导的分布估计算法对于分布式异构混合流水车间调度问题的求解效率。

关键词: 分布估计算法, 混合流水车间调度, 分布式调度, 知识引导

Abstract: Distributed manufacturing and scheduling system has become the main production mode in large agricultural machinery production enterprises under the background of economic globalization. In this paper, the distributed two-stage heterogeneous hybrid flow-shop scheduling problem (DHHFSP) is constructed based on the property of the agricultural machinery production. A knowledge-guided estimation of distribution algorithm (KEDA) is proposed to solve the DHHFSP. The DHHFSP contains three sub-problems, which are factory allocation, the sequence of job processing and arrangement processing machine. Multiple heuristic structure and random method are proposed for population initialization in KEDA. The candidate solution is optimized iteratively. The knowledge guided reinforcement mechanism and various local search strategies are proposed through analysis on the characteristics of DHHFSP problem. The utilization rate of key processing stages of processing resources can be improved. Through the simulation experiments, the proposed algorithm is compared with other three kinds of algorithms to verify the effectiveness and stability of the improved distribution estimation algorithm. The experimental results show that the efficiency of KEDA algorithm for DHHFSP problem can be improved by using the characteristics of DHHFSP problem to guide the evolution process of the algorithm.

Key words: estimation of distribution algorithm, hybrid flow-shop scheduling, distributed scheduling, knowledge-guided

康立军, 刘欢, 代永强, 秦立静. 面向柔性生产资源的分布式农机生产调度优化[J]. 计算机工程与应用, 2024, 60(19): 363-374.

KANG Lijun, LIU Huan, DAI Yongqiang, QIN Lijing. Distributed Agricultural Machinery Production Scheduling Optimization for Flexible Production Resources[J]. Computer Engineering and Applications, 2024, 60(19): 363-374.

参考文献

[1] ZHAO F, MA R, WANG L. A self-learning discrete Jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in heterogeneous factory system [J]. IEEE Transactions on Cybernetics, 2022, 52(12): 12675-12686.
[2] CAI J, ZHOU R, LEI D. Dynamic shuffled frog-leaping algorithm for distributed hybrid flow shop scheduling with multiprocessor tasks [J]. Engineering Applications of Artificial Intelligence, 2020, 90: 103540.
[3] ZHAO F, ZHAO L, WANG L, et al. An ensemble discrete differential evolution for the distributed blocking flowshop scheduling with minimizing makespan criterion [J]. Expert Systems with Applications, 2020, 160: 113678.
[4] ZHAO F, HE X, WANG L. A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem[J]. IEEE Transactions on Cybernetics, 2021, 51(11): 5291-5303.
[5] CAI J, LEI D. Distributed two-stage hybrid flow shop scheduling with setup times [J]. Computer Integrated Manufacturing Systems, 2020, 26(8): 2170-2179.
[6] 李纪岳, 陈志, 杨敏丽, 等.基于农机农艺结合的玉米生产机械化系统研究[J]. 农业机械学报, 2012, 43(8): 83-88.
LI J Y, CHEN Z, YANG M L, et al. Mechanized corn production systems based on combination of machinery and agronomy[J]. Transactions of the Chinese Society of Agricultural Machinery, 2012, 43(8): 83-88.
[7] 王凌, 邓瑾, 王圣尧. 分布式车间调度优化算法研究综述[J]. 控制与决策, 2016, 31(1): 1-11.
WANG L, DENG J, WANG S Y. Survey on optimization algorithms for distributed shop scheduling[J]. Control and Decision, 2016, 31(1): 1-11.
[8] 葛茂根, 刘明周, 张明伟, 等. 计及机器调整和物料运送时间的Job-Shop调度算法[J]. 农业机械学报, 2008(11): 127-131.
GE M G, LIU M Z, ZHANG M W, et al. Job-shop scheduling algorithm considering machine set-up and material transit time[J]. Transactions of the Chinese Society of Agricultural Machinery, 2008(11): 127-131.
[9] RUIZ R, VAZQUEZ-RODRIGUEZ J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1-18.
[10] 李俊青, 李文涵, 陶昕瑞, 等. 时间约束混合流水车间调度问题综述[J]. 控制理论与应用, 2020, 37(11): 2273-2290.LI J Q, LI W H, TAO X R, et al. A survey on time constrained hybrid flow shop scheduling problems[J]. Control Theory and Applications, 2020, 37(11): 2273-2290.
[11] 袁帅鹏, 李铁克, 王柏琳. 带运输时间混合流水车间成组调度的协同进化文化基因算法[J]. 控制理论与应用, 2023, 40(3): 430-440.
YUAN S P, LI T K, WANG B L. Co-evolutionary memetic algorithm for the hybrid flow shop group scheduling with transportation times[J]. Control Theory and Applications, 2023, 40(3): 430-440.
[12] ZHANG B, PAN Q K, MENG L L, et al. A collaborative variable neighborhood descent algorithm for the hybrid flowshop scheduling problem with consistent sublots[J]. Applied Soft Computing, 2021, 106: 1-20.
[13] LU C, GAO L, PAN Q, et al. A multi-objective cellular grey wolf optimizer for hybrid flowshop scheduling problem considering noise pollution[J]. Applied Soft Computing, 2019, 75: 728-749.
[14] LI J Q, SONG M X, WANG L, et al. Hybrid artificial bee colony algorithm for a parallel batching distributed flow-shop problem with deteriorating jobs[J]. IEEE Transactions on Cybernetics, 2020, 50(6): 2425-2439.
[15] CAI J, LEI D, WANG J, et al. A novel shuffled frog-leaping algorithm with reinforcement learning for distributed assembly hybrid flow shop scheduling[J]. International Journal of Production Research, 2023, 61(4): 1233-1251.
[16] LEI D, GAO L, ZHENG Y. A novel teaching-learning-based optimization algorithm for energy-efficient scheduling in hybrid flow shop[J]. IEEE Transactions on Engineering Management, 2018, 65(2): 330-340.
[17] LI Y, LI X, GAO L, et al. A discrete artificial bee colony algorithm for distributed hybrid flowshop scheduling problem with sequence-dependent setup times[J]. International Journal of Production Research, 2021, 59(13): 3880-3899.
[18] LI Y, LI X, GAO L, et al. An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times[J]. Computers and Industrial Engineering, 2020, 147: 10 6638.
[19] SHAO W, SHAO Z, PI D. An ant colony optimization behavior-based MOEA/D for distributed heterogeneous hybrid flow shop scheduling problem under nonidentical time-of-use electricity tariffs[J]. IEEE Transactions on Automation Science and Engineering, 2022, 19(4): 3379-3394.
[20] CAI J, LEI D. A cooperated shuffled frog-leaping algorithm for distributed energy-efficient hybrid flow shop scheduling with fuzzy processing time[J]. Complex and Intelligent Systems, 2021, 7: 2235-2253.
[21] LI J, PAN Q, DUAN P. An improved artificial bee colony algorithm for solving hybrid flexible flowshop with dynamic operation skipping [J]. IEEE Transactions on Cybernetics, 2016, 46(6): 1311-1324.
[22] 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.
[23] ZHANG G, WANG L, XING K. Dual-space co-evolutionary memetic algorithm for scheduling hybrid differentiation flowshop with limited buffer constraints[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(11): 6822-6836.
[24] MARICHELVAM M K, GEETHA M, TOSUN ?. An improved particle swarm optimization algorithm to solve hybrid flowshop scheduling problems with the effect of human factors-a case study[J]. Computers and Operations Research, 2020, 114: 104812.
[25] 姜雪洁, 房立金. 基于模拟退火算法的机械臂刚度辨识构型优化与实验[J]. 农业机械学报, 2023, 54(1): 419-424.
JIANG X J, FANG L J. Method and experiment of configuration optimization for manipulator stiffness identification based on simulated annealing algorithm[J]. Transactions of the Chinese Society of Agricultural Machinery, 2023, 54(1): 419-424.
[26] WANG S Y, WANG L, LIU M, et al. An order-based estimation of distribution algorithm for stochastic hybrid flow-shop scheduling problem[J]. International Journal of Computer Integrated Manufacturing, 2015, 28(3): 307-320.
[27] PAN Q K, WANG L, LI J Q, et al. A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation[J]. Omega, 2014, 45: 42-56.
[28] ALFARO-FERNáNDEZ P, RUIZ R, PAGNOZZI F, et al. Automatic algorithm design for hybrid flowshop scheduling problems[J]. European Journal of Operational Research, 2020, 282(3): 835-845.
[29] 廖作文, 龚文引, 王凌. 基于改进环拓扑混合群体智能算法的非线性方程组多根联解[J]. 中国科学: 信息科学, 2020, 50(3): 396-407.
LIAO Z W, GONG W Y, WANG L. Multi-root joint solution of nonlinear equations based on improved ring topology hybrid swarm intelligence algorithm[J]. SCIENTIA SINICA Informationis, 2020, 50(3): 396-407.
[30] 裴小兵, 祁文博, 戴毓彤. 求解柔性作业车间调度问题的新型改进Jaya算法[J]. 计算机工程与应用, 2022, 58(19):318-325.
PEI X B, QI W B, DAI Y T. New improved Jaya algorithm for solving flexible job shop scheduling problem[J]. Computer Engineering and Applications , 2022, 58(19): 318-325.
[31] 李聪波, 王睿, 寇阳, 等. 考虑设备预维护的柔性作业车间调度节能优化方法[J]. 机械工程学报, 2021, 57(10): 220-230.
LI C B, WANG R, KOU Y, et al. Energy saving optimization method of flexible job shop scheduling considering preventive maintenance[J]. Journal of Mechanical Engineering, 2021, 57(10): 220-230.
[32] LIU H, ZHAO F, WANG L, et al. An estimation of distribution algorithm with multiple intensification strategies for two-stage hybrid flow-shop scheduling problem with sequence-dependent setup time [J]. Applied Intelligence, 2023, 53(5): 5160-5178.
[33] YU C, SEMERARO Q, MATTA A. A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility [J]. Computers and Operations Research, 2018, 100: 211-229.
[34] UMAM M S, MUSTAFID M, SURYONO S. A hybrid genetic algorithm and tabu search for minimizing makespan in flow shop scheduling problem [J]. Journal of King Saud University-Computer and Information Sciences, 2022, 34(9): 7459-7467.