基于MOMA的可重入混合流水车间调度问题研究

doi:10.16182/j.issn1004731x.joss.22-1038

摘要/Abstract

摘要：

针对可重入制造系统多具有多品种、大规模、混流生产等特点，构建带批处理机的可重入混合流水车间调度问题（reentrant hybrid flow shop scheduling problem with batch processors， BP-RHFSP）模型，提出一种改进的多目标蜉蝣算法（multi-objective mayfly algorithm， MOMA）进行求解。提出了单件加工阶段和批处理阶段的解码规则；设计了基于Logistic混沌映射的反向学习初始化策略、改进的蜉蝣交配和变异策略，提高了算法初始解的质量和局部搜索能力；根据编码规则设计了基于变邻域下降搜索的蜉蝣运动策略，优化了种群方向。通过对不同规模大量测试算例的仿真实验，验证了MOMA相比传统算法求解BP-RHFSP更具有效性和优越性。所提出的模型能够反映生产的基础特征，达到减少最大完工时间、机器负载和碳排放的目的。

关键词: 可重入混合流水车间, 生产调度, 批处理, 蜉蝣算法, 碳排放

Abstract:

For the characteristics of multi-variety, large-scale and mixed-flow production of reentrant manufacturing systems, the reentrant hybrid flow shop scheduling problem with batch processors (BP-RHFSP) is constructed, and an improved multi-objective mayfly algorithm (MOMA) is proposed for BP-RHFSP. Firstly, decoding rules for single-piece processing stage and batch-processing stage are proposed. Then, a reverse learning initialization strategy based on logistic chaotic mapping is designed to improve the quality of the initial solution of the algorithm, also an improved mayfly mating strategy is designed to improve the local search ability of MOMA. Finally, a VND-based mayfly movement strategy is designed based on the coding rule to ensure the quality of the population evolves in a good direction. Through the simulation experiments of a large number of test studies of different scales, it is verified that MOMA is more effective and superior than the traditional algorithm in solving BP-RHFSP. The proposed model can reflect the basic characteristics of production, reducing the makespan, machine load, and carbon emissions.

Key words: reentrant hybrid flow shop, production scheduling, batch processor, mayfly algorithm, carbon emission

中图分类号:

TP301.6

秦红斌,李晨晓,唐红涛等 . 基于MOMA的可重入混合流水车间调度问题研究[J]. 系统仿真学报, 2024, 36(1): 131-148.

Qin Hongbin,Li Chenxiao,Tang Hongtao,et al . Reentrant Hybrid Flow Shop Scheduling Problem Based on MOMA[J]. Journal of System Simulation, 2024, 36(1): 131-148.

图/表 22

图1

表1

模型符号定义

符号	含义	符号	含义
$n$	工件总数	$M l$	$l$ 工位上批处理机数量
$i$	工件索引， $i = 1,2, …, n$	$M l C d$	第 $l$ 工位上第 $d$ 台批处理机的最大容量
$N i$	工件 $i$ 的总工序数	$B$	在批处理机上加工的总批数
$j$	工件 $i$ 的工序索引， $j = 1,2, …, N i$	$b$	在批处理机上加工的批数索引， $b = 1,2, …, B$
$s$	工位数	$S b$	批处理机上第 $b$ 批的开工时刻
$l$	工位索引， $l = 1,2, …, s$	$C b$	批处理机上第 $b$ 批的完工时刻
$m l$	工位 $l$ 上的不相关并行机台数	$P T$	机器运转的额定运行功率
$k$	工位 $l$ 上的机器索引， $k = 1,2, …, m l$	$P I$	机器空转的额定运行功率
$I i$	工件 $i$ 的总层次数	$P W$	机器调整的额定运行功率
$L i$	工件 $i$ 所在的层次，其中 $L i$ =1为第一层， $L i = 2,3, …, I i$ 为重入层	$q i$	工件 $i$ 的材质编号
$O i j$	工件 $i$ 的第 $j$ 个工序	$X i$	工件 $i$ 的同种类型工件数量
$S i j$	工序 $O i j$ 的开工时间	$U l$	在工位l上加工的所有工序的集合
$T i j l k$	$O i j$ 在第 $l$ 工位中机器 $k$ 的加工时间	$N$	一个充分大的正数
$S i j l k$	$O i j$ 在第 $l$ 工位中机器 $k$ 的开工时间	$x i j l k$	决策变量， $O i j$ 在第 $l$ 个工位中机器 $k$ 上进行加工， $x i j l k = 1$ ，否则 $x i j l k = 0$
$C i j l k$	$O i j$ 在第 $l$ 工位中机器 $k$ 的完工时间	$Y i j, g h, l k$	决策变量， $O i j$ 先于 $O g h$ 在第 $l$ 工位中机器 $k$ 上进行加工， $Y i j, g h, l k = 1$ ，否则 $Y i j, g h, l k = 0$
$I l k$	第 $l$ 工位的机器 $k$ 的空转时间	$λ i b$	决策变量，工件i被分配到任务批 $b$ 进行加工， $λ i b = 1$ ,否则 $λ i b = 0$
$W i j l k$	$O i j$ 在到达第 $l$ 工位中机器 $k$ 前的调整时间	$α b d$	决策变量，任务批 $b$ 由批处理机 $d$ 进行加工， $α b d = 1$ ，否则 $α b d = 0$
$C i$	工件 $i$ 的完工时间	$β b g$	决策变量，任务批 $b$ 在任务批 $g$ 之前进行加工， $β b g = 1$ ，否则 $β b g = 0$

表1

图2

图3

图4

图5

图6

图7

表2

表3

表4

图8

表5

表6

表7

图9

图10

图11

表8

图12

图13

图14

参考文献 31

1	Lin Chuncheng, Liu Wanyu, Chen Y H. Considering Stockers in Reentrant Hybrid Flow Shop Scheduling with Limited Buffer Capacity[J]. Computers & Industrial Engineering, 2020, 139: 106154.
2	Graves S C, Meal H C, Stefek D, et al. Scheduling of Re-entrant Flow Shops[J]. Journal of Operations Management, 1983, 3(4): 197-207.
3	Kumar R, Tiwari M K, Allada V. Modelling and Rescheduling of a Re-entrant Wafer Fabrication Line Involving Machine Unreliability[J]. International Journal of Production Research, 2004, 42(21): 4431-4455.
4	顾涛, 李苏建, 林莹璐, 等. 周期式退火炉作批处理机的可重入批离散机流水车间调度[J]. 机械工程学报, 2020, 56(2): 220-232.
	Gu Tao, Li Sujian, Lin Yinglu, et al. Research on the Re-entrant Batch Discrete Flow Shop Scheduling for Periodic Annealing Furnace as Batch Processor[J]. Journal of Mechanical Engineering, 2020, 56(2): 220-232.
5	李颖俐, 李新宇, 高亮. 混合流水车间调度问题研究综述[J]. 中国机械工程, 2020, 31(23): 2798-2813, 2828.
	Li Yingli, Li Xinyu, Gao Liang. Review on Hybrid Flow Shop Scheduling Problems[J]. China Mechanical Engineering, 2020, 31(23): 2798-2813, 2828.
6	Yan Xiaoyan, Wu Xiuli. An Improved Reentrant-bottleneck Heuristic for the Reentrant Hybrid Flow Shop Scheduling[C]//2020 Chinese Automation Congress (CAC). Piscataway, NJ, USA: IEEE, 2020: 4170-4175.
7	Yan Xiaoyan, Wu Xiuli. IMOEA/D to Optimize Job Release Problem for a Reentrant Hybrid Flow Shop[J]. Computers & Industrial Engineering, 2022, 163: 107800.
8	Hekmatfar M, Fatemi Ghomi S M T, Karimi B. Two Stage Reentrant Hybrid Flow Shop with Setup Times and the Criterion of Minimizing Makespan[J]. Applied Soft Computing, 2011, 11(8): 4530-4539.
9	Achmad Pratama Rifai, Setyo Tri Windras Mara, Sudiarso Andi. Multi-objective Distributed Reentrant Permutation Flow Shop Scheduling with Sequence-dependent Setup Time[J]. Expert Systems with Applications, 2021, 183: 115339.
10	Chamnanlor C, Sethanan K, Chien C F, et al. Hybrid Genetic Algorithms for Solving Reentrant Flow-shop Scheduling with Time Windows[J]. Industrial Engineering and Management Systems, 2013, 12(4): 306-316.
11	Chamnanlor Chettha, Sethanan Kanchana, Gen Mitsuo, et al. Embedding Ant System in Genetic Algorithm for Re-entrant Hybrid Flow Shop Scheduling Problems with Time Window Constraints[J]. Journal of Intelligent Manufacturing, 2017, 28(8): 1915-1931.
12	Mason S J, Oey K. Scheduling Complex Job Shops Using Disjunctive Graphs: A Cycle Elimination Procedure[J]. International Journal of Production Research, 2003, 41(5): 981-994.
13	Jia Wenyou, Jiang Zhibin, Li You. Combined Scheduling Algorithm for Re-entrant Batch-processing Machines in Semiconductor Wafer Manufacturing[J]. International Journal of Production Research, 2015, 53(6): 1866-1879.
14	Jia Wenyou, Chen Hao, Liu Li, et al. Full-batch-oriented Scheduling Algorithm on Batch Processing Workstation of β1→β2 Type with Re-entrant Flow[J]. International Journal of Computer Integrated Manufacturing, 2017, 30(10): 1029-1042.
15	Jing Xuelei, Pan Quanke, Gao Liang, et al. An Effective Iterated Greedy Algorithm for the Distributed Permutation Flowshop Scheduling with Due Windows[J]. Applied Soft Computing, 2020, 96: 106629.
16	Cho Hang-Min, Bae Suk-Joo, Kim Jungwuk, et al. Bi-objective Scheduling for Reentrant Hybrid Flow Shop Using Pareto Genetic Algorithm[J]. Computers & Industrial Engineering, 2011, 61(3): 529-541.
17	Zhou Binghai, Hu Liman, Zhong Zhenyi. A Hybrid Differential Evolution Algorithm with Estimation of Distribution Algorithm for Reentrant Hybrid Flow Shop Scheduling Problem[J]. Neural Computing and Applications, 2018, 30(1): 193-209.
18	董君, 叶春明, 万孟然. 考虑可再生能源的可重入混合流水车间调度问题[J]. 计算机集成制造系统, 2022, 28(4): 1112-1128.
	Dong Jun, Ye Chunming, Wan Mengran. Reentrant Hybrid Flow Shop Scheduling Problem with Renewable Energy[J]. Computer Integrated Manufacturing Systems, 2022, 28(4): 1112-1128.
19	Zervoudakis Konstantinos, Tsafarakis Stelios. A Mayfly Optimization Algorithm[J]. Computers & Industrial Engineering, 2020, 145: 106559.
20	Guo Xiaokai, Yan Xianguo, Jermsittiparsert Kittisak. Using the Modified Mayfly Algorithm for Optimizing the Component Size and Operation Strategy of a High Temperature PEMFC-powered CCHP[J]. Energy Reports, 2021, 7: 1234-1245.
21	A M Shaheen Mohamed, Hasanien Hany M, El Moursi M S, et al. Precise Modeling of PEM Fuel Cell Using Improved Chaotic MayFly Optimization Algorithm[J]. International Journal of Energy Research, 2021, 45(13): 18754-18769.
22	Majumdar Kingsuk, Kumar Roy Provas, Banerjee Subrata. Implementation of Multi-objective Chaotic Mayfly Optimisation for Hydro-thermal-solar-wind Scheduling Based on Available Transfer Capability Problem[J]. International Transactions on Electrical Energy Systems, 2021, 31(11): e13029.
23	Liu Zhenkun, Jiang Ping, Wang Jianzhou, et al. Ensemble Forecasting System for Short-term Wind Speed Forecasting Based on Optimal Sub-model Selection and Multi-objective Version of Mayfly Optimization Algorithm[J]. Expert Systems with Applications, 2021, 177: 114974.
24	Gao Zhengming, Li Suruo, Zhao Juan, et al. Self-organizing Hierarchical Mayfly Optimization Algorithm[C]//2020 International Conference on Big Data & Artificial Intelligence & Software Engineering (ICBASE). Piscataway, NJ, USA: IEEE, 2020: 355-358.
25	Bhattacharyya Trinav, Chatterjee Bitanu, Pawan Kumar Singh, et al. Mayfly in Harmony: A New Hybrid Meta-heuristic Feature Selection Algorithm[J]. IEEE Access, 2020, 8: 195929-195945.
26	Rim Cholmin, Songhao Piao, Li Guo, et al. A Niching Chaos Optimization Algorithm for Multimodal Optimization[J]. Soft Computing, 2018, 22(2): 621-633.
27	刘公致, 吴琼, 王光义, 等. 改进型Logistic混沌映射及其在图像加密与隐藏中的应用[J]. 电子与信息学报, 2022, 44(10): 3602-3609.
	Liu Gongzhi, Wu Qiong, Wang Guangyi, et al. A Improved Logistic Chaotic Map and Its Application to Image Encryption and Hiding[J]. Journal of Electronics & Information Technology, 2022, 44(10): 3602-3609.
28	Wang Yongzhen, Chen Yan, Lin Yan. Memetic Algorithm Based on Sequential Variable Neighborhood Descent for the Minmax Multiple Traveling Salesman Problem[J]. Computers & Industrial Engineering, 2017, 106: 105-122.
29	Han Honggui, Zhang Linlin, Hou Ying, et al. Adaptive Candidate Estimation-assisted Multi-objective Particle Swarm Optimization[J]. Science China Technological Sciences, 2022, 65(8): 1685-1699.
30	潘楚光, 谭平, 熊瑞平, 等. 基于MOGWO的拟人机械手连杆长度优化[J]. 组合机床与自动化加工技术, 2022(6): 19-23.
	Pan Chuguang, Tan Ping, Xiong Ruiping, et al. Optimization of Link Lengths of Anthropomorphic Manipulator Based on MOGWO[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2022(6): 19-23.
31	王丽萍, 任宇, 邱启仓, 等. 多目标进化算法性能评价指标研究综述[J]. 计算机学报, 2021, 44(8): 1590-1619.
	Wang Liping, Ren Yu, Qiu Qicang, et al. Survey on Performance Indicators for Multi-objective Evolutionary Algorithms[J]. Chinese Journal of Computers, 2021, 44(8): 1590-1619.

参数名称	取值范围	参数名称	取值范围
重入次数	小规模[1,2] 大规模[1,6]	工件数量	小规模[10,20] 大规模[20,50]
工位数量	[4,6]	机器空转功率	[10,20]
每个工位并行机器数	[1,3]	机器调整功率	[5,10]
加工时间	[1,30]	标准煤碳排放系数	2.457
批处理工序	[1,6]	电能标煤系数	0.122 9
机器运转功率	[30,50]

参数	参数水平
参数	1	2	3
种群规模(Pop)	20	30	40
重力系数(g)	0.6	0.7	0.8
舞蹈系数(d)	4	5	6
随机游走系数(fl)	0.5	1.0	1.5

实验编号	参数				IGD平均值
实验编号	Pop	g	d	fl	IGD平均值
1	1(20)	1(0.6)	1(4)	1(0.5)	42.151 8
2	1(20)	2(0.7)	2(5)	2(1.0)	44.914 6
3	1(20)	3(0.8)	3(6)	3(1.5)	56.702 3
4	2(30)	1(0.6)	2(5)	3(1.5)	43.343 2
5	2(30)	2(0.7)	3(6)	1(0.5)	42.746 3
6	2(30)	3(0.8)	1(4)	2(1.0)	32.771 5
7	3(40)	1(0.6)	3(6)	2(1.0)	36.112 3
8	3(40)	2(0.7)	1(4)	3(1.5)	55.272 4
9	3(40)	3(0.8)	2(5)	1(0.5)	42.666 6

算法	参数	取值
NSGA-II	变异率	0.1
NSGA-II	交叉率	0.8
MOGWO	协同系数向量 A	[-2,2]
MOGWO	协同系数向量 C	[0,2]
MOPSO	惯性常数	0.7
MOPSO	加速常数	2

算例	规模工件，工序，重入	GD		IGD		SP
算例	规模工件，工序，重入	MOMA	MA	MOMA	MA	MOMA	MA
j10p4r1	(10,4,1)	1.619 1	2.315 3	9.672 8	11.485 3	2.542 6	3.124 5
j11p4r1	(11,4,1)	1.897 0	3.453 6	15.308 3	20.753 4	6.071 5	7.286 4
j12p4r1	(12,4,1)	2.949 1	2.554 5	29.105 9	30.417 5	7.330 7	8.954 2
j14p5r1	(14,5,1)	6.120 3	8.586 3	30.159 3	34.247 8	7.554 7	10.354 2
j15p5r1	(15,5,1)	6.005 8	7.356 4	54.512 5	49.451 2	19.535 5	26.168 5
j20p5r1	(20,5,1)	4.635 2	3.214 8	26.530 6	28.147 5	9.832 7	10.783 5
j14p6r1	(14,6,1)	3.231 9	5.369 7	28.259 2	29.478 7	9.052 3	10.553 6
j17p6r1	(17,6,1)	3.620 2	4.534 7	33.992 7	36.147 5	9.100 1	11.896 5
j20p6r1	(20,6,1)	2.610 8	3.457 4	28.610 3	30.583 1	7.636 3	8.314 5
j29p4r1	(29,4,1)	4.525 0	5.572 1	38.457 2	42.364 8	10.829 4	11.235 1
j30p4r3	(30,4,3)	8.760 8	12.714 2	128.599 7	178.315 2	16.583 5	19.325 8
j45p4r5	(45,4,5)	9.444 8	14.142 3	161.301 7	204.432 9	26.774 7	35.742 8
j26p5r4	(26,5,4)	8.401 9	15.484 7	110.351 5	163.418 3	22.590 6	28.168 4
j37p5r2	(37,5,2)	4.602 8	5.142 3	58.011 3	76.415 8	16.638 1	18.328 5
j28p5r1	(28,5,1)	3.346 2	4.586 6	41.165 2	40.238 4	14.540 8	18.452 3
j21p6r1	(21,6,2)	4.765 4	5.143 7	47.255 5	55.123 7	13.864 3	15.153 2
j28p6r3	(28,6,3)	29.208 3	34.639 7	153.480 6	236.813 5	26.321 2	35.628 1
j39p6r1	(39,6,1)	4.161 9	5.786 2	37.115 4	45.364 1	12.178 3	17.152 4