机器与AGV联合利用再生能源的混合流水车间调度问题

朱光宇; 贾唯鸿; 李德彪

doi:10.13700/j.bh.1001-5965.2023.0021

机器与AGV联合利用再生能源的混合流水车间调度问题

doi: 10.13700/j.bh.1001-5965.2023.0021

朱光宇^{1, 2, ,},
贾唯鸿¹,
李德彪³

1.
福州大学先进制造学院，泉州 362200
2.
福州大学机械工程及自动化学院，福州 350108
3.
福州大学经济与管理学院，福州 350108

基金项目: 工信部2016智能制造综合标准化与新模式应用项目(工信部联装(2016)213号)；福建省自然科学基金(2023J01256,2024J01349)

详细信息

通讯作者:
E-mail：zhugy@fzu.edu.cn

中图分类号: V221⁺.3；TB553
计量
- 文章访问数: 396
- HTML全文浏览量: 100
- PDF下载量: 18
- 被引次数: 0
出版历程
- 收稿日期: 2023-01-13
- 录用日期: 2023-02-24
- 网络出版日期: 2023-04-11
- 整期出版日期: 2025-02-28

Hybrid flow-shop scheduling problem considering joint of machine and AGV with renewable energy

ZHU Guangyu^{1, 2
, ,},
JIA Weihong¹,
LI Debiao³

1.
School of Advanced Manufacturing，Fuzhou University，Quanzhou 362200，China
2.
School of Mechanical Engineering and Automation，Fuzhou University，Fuzhou 350108，China
3.
School of Economics and Management，Fuzhou University，Fuzhou 350108，China

Funds: MIIT 2016 Intelligent Manufacturing Comprehensive Standardization and New Pattern Application Program, China ((2016)213); Natural Science Foundation of Fujian Province, China (2023J01256,2024J01349)

More Information

Corresponding author: E-mail：zhugy@fzu.edu.cn

摘要

摘要:
中国的制造业正经历着数字化和绿色低碳转型。为实现节能减排，提高设备利用率，针对考虑可再生能源的混合流水车间，建立机器与自动导引车(AGV)联合利用再生能源的混合流水车间调度问题(HFSP-MA-RE)数学模型。为求解该模型，提出基于提前调度的机器与AGV联合调度策略、能源分配策略，在考虑AGV路径优化和充电约束的情况下，实现对最大完工时间、碳排放量、总能耗和AGV利用率4个目标的优化。采用基于正向灰靶模型的多目标最佳觅食算法(PPGT_OFA)求解该问题。通过24个测试实例及1个工程应用，将所提算法与5个多目标优化算法进行实验，验证了HFSP-MA-RE模型及PPGT_OFA算法解决多目标优化问题的有效性。
- 混合流水车间调度 /
- 可再生能源 /
- 多目标优化 /
- A^*算法 /
- 联合调度
Abstract:
The manufacturing industry in China is undergoing a digital and green low-carbon transformation. To achieve energy saving and emission reduction and improve the equipment utilization rate, a mathematical model of the hybrid flow-shop scheduling problem considering the joint of machine and automated guided vehicle (AGV) with renewable energy (HFSP-MA-RE) was established.To resolve this model, a joint scheduling strategy and an energy distribution strategy of machines and AGVs based on advance scheduling were proposed. In the case of AGV path optimization and charging constraints, four objectives of the maximum completion time, carbon emissions, total energy consumption, and AGV utilization rate were optimized.The multi-objective optimal foraging algorithm based on a positive projection gray target (PPGT_OFA) was constructed to resolve this problem. Through twenty-four test cases and one engineering application, the proposed algorithm and five multi-objective optimization algorithms were tested to verify the effectiveness of the HFSP-MA-RE model and PPGT_OFA in solving this multi-objective optimization problem.
- hybrid flow-shop scheduling /
- renewable energy /
- multi-objective optimization /
- A* algorithm /
- joint scheduling

HTML全文

图 1 提前调度

Figure 1. Advance scheduling

下载: 全尺寸图片幻灯片

图 2 顺序调度

Figure 2. Sequential scheduling

下载: 全尺寸图片幻灯片

图 3 车间布局及改进A^*算法示意

Figure 3. Illustration of shop layout and improved A* algorithm

下载: 全尺寸图片幻灯片

图 4 机器与AGV联合调度策略流程

Figure 4. Flow of joint scheduling strategy of machine and AGV

下载: 全尺寸图片幻灯片

图 5 解与正负靶心位置关系

Figure 5. Position relation of solution and positive and negative target centers

下载: 全尺寸图片幻灯片

图 6 4×3工序编码

Figure 6. 4×3 operation code

下载: 全尺寸图片幻灯片

图 7 PPGT_OFA算法流程

Figure 7. Process of PPGT_OFA algorithm

下载: 全尺寸图片幻灯片

图 8 Pareto解集分布

Figure 8. Pareto solution set distribution

下载: 全尺寸图片幻灯片

图 9 PPGT_OFA 算法收敛曲线

Figure 9. Convergence curves of PPGT_OFA algorithm

下载: 全尺寸图片幻灯片

图 10 PPGT_OFA 算法最佳方案

Figure 10. Optimal PPGT_OFA scheme

下载: 全尺寸图片幻灯片

图 11 未使用联合调度策略优化方案

Figure 11. Optimization scheme without using joint scheduling strategy

下载: 全尺寸图片幻灯片

表 1 算例测试结果(小规模算例)

Table 1. Example test results (small scale examples)

规模	SP
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
5×3×3	0.08	0.15	0.23	0.19	0.16	0.13
5×4×3	0.10	0.14	0.14	0.16	0.21	0.14
5×5×4	0.10	0.14	0.11	0.15	0.16	0.12
10×3×3	0.11	0.16	0.13	0.15	0.16	0.14
10×3×4	0.09	0.14	0.17	0.10	0.16	0.14
10×3×5	0.07	0.15	0.08	0.13	0.15	0.11
10×4×5	0.09	0.13	0.12	0.18	0.14	0.13
10×5×3	0.09	0.15	0.14	0.15	0.17	0.14
10×5×4	0.08	0.10	0.12	0.15	0.10	0.11
10×5×5	0.12	0.19	0.12	0.10	0.18	0.10

规模	GD
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
5×3×3	0.02	0.11	0.02	0.10	0.09	0.03
5×4×3	0.01	0.11	0.02	0.08	0.09	0.04
5×5×4	0.02	0.11	0.04	0.09	0.10	0.03
10×3×3	0.02	0.12	0.02	0.06	0.11	0.03
10×3×4	0.01	0.13	0.03	0.08	0.12	0.03
10×3×5	0.01	0.11	0.02	0.07	0.09	0.04
10×4×5	0.02	0.10	0.03	0.07	0.09	0.03
10×5×3	0.04	0.14	0.04	0.09	0.12	0.06
10×5×4	0.02	0.10	0.03	0.07	0.09	0.04
10×5×5	0.03	0.10	0.02	0.07	0.08	0.04

规模	IGD
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
5×3×3	0.24	0.35	0.13	0.27	0.27	0.13
5×4×3	0.28	0.36	0.14	0.31	0.27	0.15
5×5×4	0.19	0.34	0.18	0.28	0.27	0.19
10×3×3	0.10	0.37	0.11	0.20	0.21	0.12
10×3×4	0.12	0.48	0.14	0.19	0.28	0.16
10×3×5	0.23	0.35	0.19	0.23	0.27	0.16
10×4×5	0.21	0.31	0.20	0.30	0.25	0.11
10×5×3	0.29	0.47	0.15	0.30	0.32	0.19
10×5×4	0.25	0.33	0.17	0.33	0.27	0.17
10×5×5	0.18	0.38	0.34	0.26	0.31	0.19

下载: 导出CSV

表 2 算例测试结果(大规模算例)

Table 2. Example test results (large scale examples)

规模	SP
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
30×3×3	0.10	0.12	0.19	0.16	0.18	0.18
30×3×5	0.07	0.11	0.11	0.14	0.14	0.12
30×4×3	0.11	0.11	0.10	0.11	0.12	0.12
30×4×4	0.08	0.10	0.09	0.14	0.12	0.12
30×4×5	0.08	0.12	0.12	0.11	0.12	0.13
30×5×4	0.08	0.14	0.09	0.11	0.15	0.13
30×5×5	0.10	0.11	0.11	0.12	0.12	0.11
50×3×3	0.08	0.17	0.14	0.12	0.10	0.12
50×3×5	0.06	0.08	0.13	0.09	0.12	0.10
50×4×3	0.10	0.11	0.13	0.11	0.11	0.13
50×4×4	0.07	0.12	0.12	0.14	0.13	0.11
50×4×5	0.09	0.11	0.10	0.11	0.10	0.10
50×5×4	0.10	0.14	0.13	0.14	0.14	0.15
50×5×5	0.07	0.11	0.12	0.12	0.10	0.10

规模	GD
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
30×3×3	0.05	0.13	0.04	0.08	0.13	0.04
30×3×5	0.03	0.12	0.04	0.09	0.11	0.06
30×4×3	0.02	0.10	0.04	0.07	0.08	0.04
30×4×4	0.03	0.10	0.04	0.08	0.10	0.04
30×4×5	0.02	0.10	0.03	0.07	0.09	0.03
30×5×4	0.04	0.12	0.04	0.06	0.11	0.04
30×5×5	0.03	0.10	0.04	0.08	0.08	0.04
50×3×3	0.04	0.11	0.04	0.09	0.11	0.06
50×3×5	0.05	0.13	0.06	0.07	0.11	0.09
50×4×3	0.02	0.12	0.03	0.10	0.11	0.03
50×4×4	0.03	0.11	0.03	0.07	0.10	0.03
50×4×5	0.03	0.10	0.03	0.05	0.08	0.03
50×5×4	0.02	0.10	0.04	0.06	0.11	0.03
50×5×5	0.01	0.10	0.03	0.06	0.09	0.01

规模	IGD
规模	PPGT_OFA	BCE-MOEA/D	NSGA-Ⅱ/SDR	NMPSO	MOEA/D-DU	NSGA-Ⅱ
30×3×3	0.14	0.38	0.20	0.28	0.29	0.16
30×3×5	0.33	0.46	0.15	0.27	0.29	0.15
30×4×3	0.14	0.31	0.17	0.35	0.19	0.14
30×4×4	0.22	0.36	0.15	0.38	0.29	0.14
30×4×5	0.25	0.38	0.13	0.32	0.29	0.14
30×5×4	0.30	0.50	0.22	0.31	0.31	0.13
30×5×5	0.15	0.30	0.16	0.38	0.26	0.20
50×3×3	0.14	0.05	0.12	0.37	0.27	0.19
50×3×5	0.22	0.42	0.18	0.51	0.32	0.20
50×4×3	0.18	0.30	0.17	0.44	0.24	0.12
50×4×4	0.31	0.42	0.21	0.34	0.32	0.12
50×4×5	0.25	0.39	0.21	0.41	0.32	0.12
50×5×4	0.16	0.38	0.24	0.31	0.28	0.18
50×5×5	0.19	0.39	0.20	0.29	0.35	0.11

下载: 导出CSV

表 3 各批电池在每道工艺不同机器上的加工时间

Table 3. Processing time of each batch of batteries on different machine for each process h

工序	机器	第1批电池	第2批电池	第3批电池	第4批电池	第5批电池	第6批电池	第7批电池	第8批电池	第9批电池	第10批电池
电芯组装	M1	3.9	3.6	4.2	4.8	3.4	4.1	3.6	4	2.7	3
电芯组装	M2	2.5	4.5	3.3	3.4	2.6	2.5	3	4.8	2.2	4.4
端板侧板焊接	M3	3.1	3.8	3.3	2.7	2.3	4.9	3.6	2.5	4.3	4.4
	M4	2.5	3	2.4	4.3	4.5	3.6	3.2	4.8	4	4.6
	M5	4.3	2.9	2.1	4.6	2.5	4	3.1	4.4	4.1	3.5
线束隔板激光焊接	M6	4.6	3.4	2.9	4.2	2.5	2.1	2.5	3.7	3.9	3.9
线束隔板激光焊接	M7	3.1	3.3	3	3.9	4	4.4	2.8	3.3	3.3	4.9
模组测试	M8	4.1	3.1	4	2.3	4.7	4.2	2.1	2.8	3.2	3.3
模组测试	M9	2.9	3.7	4.9	4	3.5	2.4	4.8	4.3	4.4	2.2

下载: 导出CSV

表 4 实例优化结果

Table 4. Instance optimization results

算法	最大完工时间/h	碳排放量/kg	总能耗/ (kW·h)	AGV 利用率
PPGT_OFA	57.5	723.8	4061.7	0.647
BCE-MOEA/D	66.3	1135.8	4394.9	0.606
NSGA-II/SDR	63.6	1041.0	4294.3	0.627
NMPSO	61.2	1437.2	4341.1	0.632
MOEA/D-DU	63.2	1078.0	4590.8	0.622
NSGA-II	62.6	850.2	4507.4	0.639
车间方案	84.6	2101.3	5416.6	0.471

下载: 导出CSV

参考文献(28)

[1]	李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23): 2798-2813. doi: 10.3969/j.issn.1004-132X.2020.23.004 LI Y L, LI X Y, GAO L. Review on hybrid flow shop scheduling problems[J]. China Mechanical Engineering, 2020, 31(23): 2798-2813 (in Chinese). doi: 10.3969/j.issn.1004-132X.2020.23.004
[2]	HAOUARI M, HIDRI L, GHARBI A. Optimal scheduling of a two-stage hybrid flow shop[J]. Mathematical Methods of Operations Research, 2006, 64(1): 107-124. doi: 10.1007/s00186-006-0066-4
[3]	MOCCELLIN J V, NAGANO M S, NETO A R P, et al. Heuristic algorithms for scheduling hybrid flow shops with machine blocking and setup times[J]. Journal of the Brazilian Society of Mechanical Sciences and Engineering, 2018, 40(2): 40. doi: 10.1007/s40430-018-0980-4
[4]	LEI D M, SU B. A multi-class teaching-learning-based optimization for multi-objective distributed hybrid flow shop scheduling[J]. Knowledge-Based Systems, 2023, 263: 110252. doi: 10.1016/j.knosys.2023.110252
[5]	QIN H X, HAN Y Y, ZHANG B, et al. An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem[J]. Swarm and Evolutionary Computation, 2022, 69: 100992.
[6]	SCHULZ S, NEUFELD J S, BUSCHER U. A multi-objective iterated local search algorithm for comprehensive energy-aware hybrid flow shop scheduling[J]. Journal of Cleaner Production, 2019, 224: 421-434. doi: 10.1016/j.jclepro.2019.03.155
[7]	周宁, 张嵩霖, 张晨. 融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题[J]. 北京航空航天大学学报, 2024, 50(2): 398-408. ZHOU N, ZHANG S L, ZHANG C. Discrete sparrow search algorithm incorporating rough data-deduction for solving hybrid flow-shop scheduling problems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2024, 50(2): 398-408(in Chinese).
[8]	WU X L, SUN Y J. A green scheduling algorithm for flexible job shop with energy-saving measures[J]. Journal of Cleaner Production, 2018, 172: 3249-3264. doi: 10.1016/j.jclepro.2017.10.342
[9]	任彩乐, 张超勇, 孟磊磊, 等. 基于改进候鸟优化算法的混合流水车间调度问题[J]. 计算机集成制造系统, 2019, 25(3): 643-653. REN C L, ZHANG C Y, MENG L L, et al. Hybrid flow-shop scheduling problems based on improved migrating birdsoptimization algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25(3): 643-653(in Chinese).
[10]	耿凯峰, 叶春明. 带工序跳跃的绿色混合流水车间机器与AGV联合调度[J]. 控制与决策, 2022, 37(10): 2723-2732. GENG K F, YE C M. Joint scheduling of machines and AGVs in green hybrid flow shop with missing operations[J]. Control and Decision, 2022, 37(10): 2723-2732(in Chinese).
[11]	SINGH N, DANG Q V, AKCAY A, et al. A matheuristic for AGV scheduling with battery constraints[J]. European Journal of Operational Research, 2022, 298(3): 855-873. doi: 10.1016/j.ejor.2021.08.008
[12]	KARIMI B, NIAKI S T A, NIKNAMFAR A H, et al. Multi-objective optimization of job shops with automated guided vehicles: A non-dominated sorting cuckoo search algorithm[J]. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2021, 235(2): 306-328.
[13]	LI W M, HAN D, GAO L, et al. Integrated production and transportation scheduling method in hybrid flow shop[J]. Chinese Journal of Mechanical Engineering, 2022, 35(1): 12. doi: 10.1186/s10033-022-00683-7
[14]	胡晓阳, 姚锡凡, 黄鹏, 等. 改进迭代局部搜索算法求解多AGV柔性作业车间调度问题[J]. 计算机集成制造系统, 2022, 28(7): 2198-2212. HU X Y, YAO X F, HUANG P, et al. Improved iterative local search algorithm for solving multi-AGV flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2022, 28(7): 2198-2212(in Chinese).
[15]	吴秀丽, 崔琪. 考虑可再生能源的多目标柔性流水车间调度问题[J]. 计算机集成制造系统, 2018, 24(11): 2792-2807. WU X L, CUI Q. Multi-objective flexible flow shop scheduling problem with renewable energy[J]. Computer Integrated Manufacturing Systems, 2018, 24(11): 2792-2807(in Chinese).
[16]	刘建昌, 李飞, 王洪海, 等. 进化高维多目标优化算法研究综述[J]. 控制与决策, 2018, 33(5): 879-887. LIU J C, LI F, WANG H H, et al. Survey on evolutionary many-objective optimization algorithms[J]. Control and Decision, 2018, 33(5): 879-887(in Chinese).
[17]	蔡磊, 李文锋, 罗云. 个性化定制车间生产-物流协同调度框架与算法研究[J]. 机械工程学报, 2022, 58(7): 214-226. CAI L, LI W F, LUO Y. Framework and algorithm of customized workshop production-logistics collaborative scheduling[J]. Journal of Mechanical Engineering, 2022, 58(7): 214-226(in Chinese).
[18]	FU B, CHEN L, ZHOU Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics and Autonomous Systems, 2018, 106: 26-37. doi: 10.1016/j.robot.2018.04.007
[19]	ZHU G Y, ZHANG W B. Optimal foraging algorithm for global optimization[J]. Applied Soft Computing, 2017, 51: 294-313.
[20]	JIAN Z Q, ZHU G Y. Affine invariance of meta-heuristic algorithms[J]. Information Sciences, 2021, 576: 37-53. doi: 10.1016/j.ins.2021.06.062
[21]	朱光宇, 张峥. 基于正向投影灰靶模型的多目标流水车间调度优化[J]. 计算机集成制造系统, 2022, 28(4): 1087-1098. ZHU G Y, ZHANG Z. Multi-objective flow-shop scheduling optimization based on positive projection grey target model[J]. Computer Integrated Manufacturing Systems, 2022, 28(4): 1087-1098(in Chinese).
[22]	LI M Q, YANG S X, LIU X H. Pareto or non-Pareto: Bi-criterion evolution in multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 645-665.
[23]	TIAN Y, CHENG R, ZHANG X Y, et al. A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 331-345.
[24]	LIN Q Z, LIU S B, ZHU Q L, et al. Particle swarm optimization with a balanceable fitness estimation for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 32-46.
[25]	YUAN Y, XU H, WANG B, et al. Balancing convergence and diversity in decomposition-based many-objective optimizers[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 180-198. doi: 10.1109/TEVC.2015.2443001
[26]	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[27]	ZHU G Y, JU X W, ZHANG W B. Multi-objective sequence optimization of PCB component assembly with GA based on the discrete Fréchet distance[J]. International Journal of Production Research, 2018, 56(11): 4017-4034. doi: 10.1080/00207543.2018.1440091
[28]	COELLO C A C, CORTÉS N C. Solving multiobjective optimization problems using an artificial immune system[J]. Genetic Programming and Evolvable Machines, 2005, 6(2): 163-190. doi: 10.1007/s10710-005-6164-x