Reentrant Hybrid Flow Shop Scheduling Problem Based on MOMA

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

Abstract

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

CLC Number:

TP301.6

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

Figures/Tables 22

Fig.1

Table 1

Notation used in this study

符号	含义	符号	含义
$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$

Table 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 2

Table 3

Table 4

Fig. 8

Table 5

Table 6

Table 7

Fig. 9

Fig. 10

Fig. 11

Table 8

Fig. 12

Fig. 13

Fig. 14

References 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