A Low-carbon Flexible Job Shop Scheduling Method with Lot Splitting

doi:10.3969/j.issn.1004-132X.2026.07.018

Abstract

Abstract:

A multi-objective batch scheduling model integrating carbon emissions， makespan， and manufacturing cost is established to accommodate the flexible production mode commonly adopted by small and medium-sized manufacturing enterprises. An improved non-dominated sorting genetic algorithm （NSGA-Ⅱ） was proposed to solve the model. To enhance scheduling flexibility and solution efficiency， a four-layer chromosome encoding scheme was designed. A maximum batch number search method was developed to determine a reasonable batching range. Furthermore， an improved precedence operation crossover （POX） operator was introduced to prevent illegal solutions arising from operation overlap， while an adaptive mutation operator was employed to dynamically adjust the mutation probability and strengthen global search capability. The effectiveness and applicability of the proposed algorithm were validated through both benchmark instances and real-world industrial case studies.

Key words: four-layer encoding, maximum batch search, improved precedence operation crossover （POX）, adaptive mutation operator, low-carbon workshop scheduling

摘要：

针对中小制造企业普遍采用的柔性作业生产模式，建立了包含碳排量、完工时间和制造成本的多目标分批调度模型，并采用改进NSGA-Ⅱ算法求解。为提高调度灵活性与求解效率，采用4层染色体编码方式。提出最大批次数搜索方法以确定合理的分批范围。采用改进的优先工序交叉（POX）算子以避免工序叠加产生的非法解。引入自适应变异算子，以动态调整变异概率、提高算法的全局搜索能力。公开算例和实际案例验证了算法的有效性和适用性。

关键词: 四层编码, 最大批次数搜索, 改进优先工序交叉, 自适应变异算子, 低碳车间调度

CLC Number:

TH186

XU Xinsheng, WU Songze, DU Wen, CAO Li, CHEN Xinhang. A Low-carbon Flexible Job Shop Scheduling Method with Lot Splitting[J]. China Mechanical Engineering, 2026, 37(7): 1686-1694.

徐新胜, 吴松泽, 杜文, 曹立, 陈昕航. 考虑低碳的柔性作业车间分批调度方法[J]. 中国机械工程, 2026, 37(7): 1686-1694.

Figures/Tables 20

Fig.1 Carbon emission assessment boundary for machining processes

Fig.2 Flowchart of the uniform batch division method

Fig.3 Flowchart of the maximum batch number search method

Fig.4 Encoding diagram

Fig.5 Illustration of the SWQ layer gene crossover adjustment mechanism

Fig.6 Crossing diagram of OS layer genes

Fig.7 Analytic hierarchy process model diagram

Tab.1 Processing Times of Workpieces

工件	工序	机器
工件	工序	$M 1$	$M 2$	$M 3$	$M 4$	$M 5$	$M 6$
$J 1$	$O 11$	2	3	4
	$O 12$		3		2	4
	$O 13$	1	4	5
$J 2$	$O 21$	3		5		2
	$O 22$	4	3			2
	$O 23$			4		7	11
$J 3$	$O 31$	5	6
	$O 32$				4	3	5
	$O 33$			13		9	12
$J 4$	$O 41$	9		7	9
	$O 42$		6		4		5
	$O 43$	1		3			3

Tab.1 Processing Times of Workpieces

工件	工序	机器
工件	工序	$M 1$	$M 2$	$M 3$	$M 4$	$M 5$	$M 6$
$J 1$	$O 11$	2	3	4
	$O 12$		3		2	4
	$O 13$	1	4	5
$J 2$	$O 21$	3		5		2
	$O 22$	4	3			2
	$O 23$			4		7	11
$J 3$	$O 31$	5	6
	$O 32$				4	3	5
	$O 33$			13		9	12
$J 4$	$O 41$	9		7	9
	$O 42$		6		4		5
	$O 43$	1		3			3

Tab.2 Parameter combinations of the improved NSGA-Ⅱ algorithm and average makespan

组合序号	N	E_n	p_c	p_b	$t ¯$ /min
1	50	200	0.60	0.010	97
2	50	250	0.70	0.015	79
3	50	300	0.80	0.020	87
4	50	350	0.90	0.025	89
5	100	200	0.70	0.020	80
6	100	250	0.60	0.025	90
7	100	300	0.90	0.010	78
8	100	350	0.80	0.015	70
9	150	200	0.80	0.025	90
10	150	250	0.90	0.020	82
11	150	300	0.60	0.015	75
12	150	350	0.70	0.010	79
13	200	200	0.90	0.015	78
14	200	250	0.80	0.010	79
15	200	300	0.70	0.025	87
16	200	350	0.60	0.020	89

Tab.2 Parameter combinations of the improved NSGA-Ⅱ algorithm and average makespan

组合序号	N	E_n	p_c	p_b	$t ¯$ /min
1	50	200	0.60	0.010	97
2	50	250	0.70	0.015	79
3	50	300	0.80	0.020	87
4	50	350	0.90	0.025	89
5	100	200	0.70	0.020	80
6	100	250	0.60	0.025	90
7	100	300	0.90	0.010	78
8	100	350	0.80	0.015	70
9	150	200	0.80	0.025	90
10	150	250	0.90	0.020	82
11	150	300	0.60	0.015	75
12	150	350	0.70	0.010	79
13	200	200	0.90	0.015	78
14	200	250	0.80	0.010	79
15	200	300	0.70	0.025	87
16	200	350	0.60	0.020	89

Fig.8 Parameter level trends

Tab.3 Machining cost table

	M₁	M₂	M₃	M₄	M₅	M₆
单位时间加工成本PA	240	300	180	180	420	240

Tab.4 Carbon emission factor parameter table

参数	取值
电能排放因子F_e/（kg·kW^-1·h^-1）	0.67
切削废屑处理的排放因子F_removed/（kg·kg^-1）	0.36
切削液处理的排放因子F_coolant/（kg·L^-1）	0.2

Tab.5 Other relevant parameter table

参数	取值
单位体积的切削液成本p_t/（元·L^-1）	120
单位体积的切削废液安全化处理成本p_f/（元·L^-1）	200
单位质量的废屑安全化处理成本p_e /（元·kg^-1）	170
机器k刀具一次磨刀消耗的电能L_k /（kW·h）	0.5
机器k上刀具研磨后恢复的使用寿命时间t_k /s	780
车间照明、排风等系统的额定功率p_a/kW	0.5
单位时间机器的切削液喷射体积q_V /（L·s^-1）	0.04

Fig.9 Multi-objective pareto chart

Tab.6 Batching scheme for the optimal scheduling of the improved NSGA-Ⅱ in this paper

子批序号	工件	工件数量	子批序号	工件	工件数量
1	J₁	10	9	J₅	4
2	J₂	10	10	J₅	6
3	J₃	3	11	J₆	8
4	J₃	3	12	J₆	2
5	J₃	4	13	J₇	1
6	J₄	2	14	J₇	4
7	J₄	5	15	J₇	5
8	J₄	3	16	J₈	10

Fig.10 Gantt chart of the optimal scheduling solution obtained by the proposed algorithm

Fig.11 Gantt chart of the optimal batch scheduling scheme of the NSGA-Ⅱ algorithm

Fig.12 Gantt chart of the optimal scheduling scheme of the multi-objective PSO algorithm

Tab.7 Batching scheme for the optimal scheduling of the multi-objective PSO algorithm

子批序号	工件	工件数量	子批序号	工件	工件数量
1	J₁	10	9	J₅	4
2	J₂	10	10	J₅	6
3	J₃	3	11	J₆	8
4	J₃	3	12	J₆	2
5	J₃	4	13	J₇	1
6	J₄	2	14	J₇	4
7	J₄	5	15	J₇	5
8	J₄	3	16	J₈	10

Tab.8 Algorithm performance comparison

调度方案		本文算法	多目标PSO算法	NSGA-Ⅱ算法
完工时间C_max/s		5915	6386	7594
碳排量/kg	机器运转	37.66	40.76	42.08
	车间照明、排风等系统	11.18	11.46	11.95
	刀具磨损	7.65	8.12	8.39
	废弃物处理	2.35	2.49	2.65
	合计	58.84	62.83	65.07
制造成本/元		1990.80	2018.88	2105.30

References 14

[1]	赵诗奎，王林瑞，石飞. 作业车间调度问题综述［J］. 济南大学学报（自然科学版）， 2016， 30（1）： 74-80.
	ZHAO Shikui， WANG Linrui， SHI Fei. A Review of Job Shop Scheduling Problem［J］. Journal of University of Jinan （Science and Technology）， 2016， 30（1）： 74-80.
[2]	黄海松，刘凯，初光勇. 改进模拟退火算法在柔性调度中的应用［J］. 组合机床与自动化加工技术， 2018（2）： 148-151.
	HUANG Haisong， LIU Kai， CHU Guangyong. Improved Simulated Annealing Algorithm for Low-carbon Flexible Job Shop Scheduling［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2018（2）： 148-151.
[3]	NING Tao， HUANG Yiming. Low Carbon Emission Management for Flexible Job Shop Scheduling： a Study Case in China［J］. Journal of Ambient Intelligence and Humanized Computing， 2023， 14（2）： 789-805.
[4]	杨幸博，罗国富，宋俊杰，等. 多目标柔性作业车间低碳调度研究［J］. 轻工学报， 2020， 35（6）： 93-99.
	YANG Xingbo， LUO Guofu， SONG Junjie， et al. Research on Low Carbon Scheduling of Multi-objective Flexible Job Shop［J］. Journal of Light Industry， 2020， 35（6）： 93-99.
[5]	孟磊磊，张超勇，肖华军，等. 面向加工时间可控的柔性作业车间节能调度问题建模［J］. 计算机集成制造系统， 2019， 25（5）： 1062-1074.
	MENG Leilei， ZHANG Chaoyong， XIAO Huajun， et al. Mathematical Modeling of Energy-efficient Flexible Job Shop Scheduling Problem with Controllable Processing Times［J］. Computer Integrated Manufacturing Systems， 2019， 25（5）： 1062-1074.
[6]	尹家乐. 考虑制造成本的多目标柔性作业车间调度优化研究［D］. 杭州：中国计量大学， 2021.
	YIN Jiale. Research on Multi-objective Flexible Job-shop Scheduling Optimization Considering Manufacturing Cost［D］. Hangzhou： China University of Metrology， 2021.
[7]	HENNING G P， CERDÁ J. A Knowledge-based Approach to Production Scheduling for Batch Processes［J］. Computers & Chemical Engineering， 1996， 20： S1295-S1300.
[8]	SANGROUDI H A， RANJBAR-BOURANI M. Solving a Flexible Job Shop Lot Sizing Problem with Shared Operations Using a Self-adaptive COA［J］. International Journal of Production Research， 2021， 59（2）： 483-515.
[9]	LI Junqing， TAO Xinrui， JIA Baoxian， et al. Efficient Multi-objective Algorithm for the Lot-streaming Hybrid Flowshop with Variable Sub-lots［J］. Swarm and Evolutionary Computation， 2020， 52： 100600.
[10]	王全武，徐震浩，顾幸生. 基于头脑风暴算法的多处理机组合生产批量调度问题［J］. 华东理工大学学报（自然科学版）， 2022， 48（5）： 685-695.
	WANG Quanwu， XU Zhenhao， GU Xingsheng. Multi-processor Combined Production Batch Scheduling Problem Based on Brain Storm Optimization Algorithm［J］. Journal of East China University of Science and Technology， 2022， 48（5）： 685-695.
[11]	张奎，朱斌，郭岳，等. 基于双层编码的柔性作业车间分批调度研究［J］. 组合机床与自动化加工技术， 2020（9）： 167-170.
	ZHANG Kui， ZHU Bin， GUO Yue， et al. Research on Flexible Job Shop Batch Scheduling Based on Bi-level Coding［J］. Modular Machine Tool & Automatic Manufacturing Technique， 2020（9）： 167-170.
[12]	王万良，范丽霞，徐新黎，等. 多目标差分进化算法求解柔性作业车间批量调度问题［J］. 计算机集成制造系统， 2013， 19（10）： 2481-2492.
	WANG Wanliang， FAN Lixia， XU Xinli， et al. Multi-objective Differential Evolution Algorithm for Flexible Job-shop Batch Scheduling Problem［J］. Computer Integrated Manufacturing Systems， 2013， 19（10）： 2481-2492.
[13]	吴亮，周学良，冷杰武，等. 基于改进遗传算法的柔性制造车间等量分批调度问题［J］. 湖北汽车工业学院学报， 2022， 36（4）： 61-67.
	WU Liang， ZHOU Xueliang， LENG Jiewu， et al. Equivalent Batch Scheduling Problem in Flexible Manufacturing Shop Based on Improved Genetic Algorithm［J］. Journal of Hubei University of Automotive Technology， 2022， 36（4）： 61-67.
[14]	赵文强. 基于工艺路线的作业车间节能分批调度研究［D］. 西安：西安工程大学， 2019.
	ZHAO Wenqiang. Research on Energy-saving Batch Scheduling of Job Shop Based on Process Route［D］. Xi'an： Xi'an Polytechnic University， 2019.

[1]	ZHOU Hao1, ZHANG Chaoyong1, 2, LIU Hui1, 3, LUO Min2. Improved Jaya Algorithm for Solving HFSPs [J]. China Mechanical Engineering, 2024, 35(08): 1462-1471,1508.
[2]	YI Qian, LUO Yusong, HU Chunhui, ZHUO Junkang, LI Congbo, YI Shuping. Carbon Consumption Prediction Method of Gear Hobbing Based on Data Migration in Shared Manufacturing [J]. China Mechanical Engineering, 2023, 34(15): 1820-1831.
[3]	LI Xixing, ZHOU Wenlong, TANG Hongtao, WU Rui, . Green Scheduling Optimization Method of Special Vehicle Body-in-White Prototype Shops Considering Equipment Preventive Maintenance [J]. China Mechanical Engineering, 2023, 34(15): 1832-1847.
[4]	ZHU Chuanjun, FENG Shijian, ZHANG Chaoyong, JIN Liangliang, WANG Linlin. Open Shop Scheduling Problems Considering Equipment Preventive Maintenance [J]. China Mechanical Engineering, 2023, 34(14): 1693-1700.
[5]	CHEN Wenchong, RUAN Yuanpeng, LI Jianguo, QI Ershi. Performance Analysis for Information and Part Flow Driven Production Systems with a Repair Loop [J]. China Mechanical Engineering, 2022, 33(21): 2578-2589.
[6]	WANG Qiulian, DUAN Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm [J]. China Mechanical Engineering, 2022, 33(21): 2601-2612.
[7]	YI Qian, LIU Chun, LI Congbo, YI Shuping, HE Shuang. A Low Carbon Optimization Decision Method for Gear Hobbing Process Parameters Driven by Small Sample Data [J]. China Mechanical Engineering, 2022, 33(13): 1604-1612.
[8]	ZHAO Lianpeng, TANG Qiuhua, ZHANG Zikai, MENG kai, . Multi-objective Restart Variable Neighborhood Search Algorithm for Assembly Line Balancing Considering Preventive Maintenance [J]. China Mechanical Engineering, 2021, 32(21): 2606-2616.
[9]	JIAO Yuyang, LI Li, NIE Hua, ZHOU Li, CHEN Xingzheng, LI Tao. Energy Consumption Data Collection and Supervision Systems of Forging Workshops with OPC Unified Architecture [J]. China Mechanical Engineering, 2021, 32(20): 2492-2500.
[10]	YI Qian, HE Shuang, NING Qing, LI Congbo, YI Shuping. An Multi-objective Optimized Production Scheduling for Automobile Prototype Workshops Considering Employee Work Ability#br# [J]. China Mechanical Engineering, 2021, 32(13): 1617-1629.
[11]	GUO Jun, WANG Zhendong, DU Baigang, LI Yibing, . Selective Asynchronous Parallel Disassembly Sequence Planning Considering Indeterminate Degree of Disassembly#br# [J]. China Mechanical Engineering, 2021, 32(09): 1080-1090,1101.
[12]	LIAO Bufan1;LEI Qi1;WU Wenlie2;SONG Yuchuan1;GUO Weifei1. Hybrid Teaching-learning-based Optimization Algorithms for Integrated Scheduling of Multi-workshop Collaborations [J]. China Mechanical Engineering, 2020, 31(16): 1940-1949.
[13]	ZHONG Lingchong, QIAN Bin, HU Rong, WANG Ling. HCS Algorithm for Multi-objective Flow Shop Scheduling Problems with Energy Consumption [J]. China Mechanical Engineering, 2018, 29(22): 2674-2681.
[14]	REN Yinghui, HUANG Xiangming, MA Zhongkai, ZHOU Zhixiong. Time Node Prediction Method for Material Delivery Based on Information Entropy [J]. China Mechanical Engineering, 2018, 29(22): 2725-2732.
[15]	LIU Yongkui, WANG Lihui, WANG Xi Vincent, XU Xun. A Revisit to Cloud Manufacturing [J]. China Mechanical Engineering, 2018, 29(18): 2226-2237.