Flexible Job-Shop Scheduling Problem Based on Improved Wolf Pack Algorithm

doi:10.16182/j.issn1004731x.joss.21-1019

Abstract

Abstract:

An improved wolf pack algorithm is proposed for solving multi-objective scheduling optimization for flexible job shop problems. A multi-objective flexible job shop scheduling model is developed with the maximum completion time of the workpiece and the energy consumption of the machine as the optimization goals. An improved wolf pack algorithm is proposed for solving the shortcomings that traditional wolf pack algorithm is easy to fall into the local optimization. Through improving the intelligent behavior of the wolf pack algorithm, individual codes are designed from the two levels of job's process and machine, and POX(precedence operation crossover) cross operation is introduced to ensure the legality of the solution and improve the search ability of the algorithm. The effectiveness of the improved wolf pack algorithm is verified through comparative experiments on two workshop examples. Experimental results show, the improved wolf pack algorithm not only has good global search ability, but also has an improved optimization ability compared with other algorithms. It can provide new solutions for the manufacturing industry to improve production efficiency.

Key words: improved wolf pack algorithm, job shop scheduling, energy consuming, multi-objective optimization

CLC Number:

TP278

Chaoyang Zhang, Liping Xu, Jian Li, Yihao Zhao, Kui He. Flexible Job-Shop Scheduling Problem Based on Improved Wolf Pack Algorithm[J]. Journal of System Simulation, 2023, 35(3): 534-543.

Figures/Tables 18

Table 1

Symbol Description

符号	定义
$N = {1, 2, ⋯, i, ⋯, n}$	工件
$J = {1, 2, ⋯, j, ⋯, q}$	工序
$M = {1, 2, ⋯, k, ⋯, m}$	机器
$O i, j$	工件 $i$ 的第 $j$ 道工序
$S i, j, k$	$O i, j$ 的开始加工时间
$F i, j, k$	$O i, j$ 的结束加工时间
$C i$	工件 $i$ 的完工时间
$T i, j, k$	$O i, j$ 在机器 $k$ 上的加工时间
$U i, j, k$	整数变量，取0或者1，如果 $O i, j$ 在机器 $k$ 上加工，则为1；否则为0
$P c k$	机器 $k$ 的加工功率
$P i d l e k$	机器 $k$ 的待机功率
$T c k$	机器 $k$ 的加工时间
$T i d l e k$	机器 $k$ 的待机时间
$E k$	机器 $k$ 的总能耗
$E c k$	机器 $k$ 的加工能耗
$E i d l e k$	机器 $k$ 的待机能耗

Table 1

Table 2

Fig. 1

Fig. 2

Fig. 3

Table 3

Table 4

Processing technology of 5 workpieces on 5 machines

工件	工序	机器
工件	工序	$M 1$	$M 2$	$M 3$	$M 4$	$M 5$
J₁	O₁₁	5	4	7	4	10
	O₁₂	4	4	10	3	9
	O₁₃	5	8	3	6	10
J₂	O₂₁	8	9	9	9	4
	O₂₂	3	2	2	1	7
	O₂₃	8	2	4	7	8
J₃	O₃₁	7	2	1	9	9
	O₃₂	8	7	7	8	2
	O₃₃	4	6	1	7	1
J₄	O₄₁	1	8	7	9	8
	O₄₂	7	8	3	4	10
	O₄₃	8	3	1	6	6
J₅	O₅₁	3	7	7	10	6
	O₅₂	2	10	9	5	10
	O₅₃	2	2	5	9	5
加工功率P_c/kW		2	1.8	1.6	2.4	3.8
待机功率P_idle/kW		0.5	0.6	0.3	0.4	0.5

Table 4

Fig. 4

Fig. 5

Fig. 6

Table 5

Table 6

Table 7

Processing technology of 6 workpieces on 6 machines

工件	工序	机器
工件	工序	M₁	M₂	M₃	M₄	M₅	M₆
J₁	O₁₁	10	15		14		14
	O₁₂		6	4	16	15
	O₁₃		5			16	8
	O₁₄	12		13	13
J₂	O₂₁	15		6	16.5	11
	O₂₂		15	10	7		12
	O₂₃	5		16	10	14
	O₂₄		10
J₃	O₃₁	14	15	6	5	4
	O₃₂		5	6		16
	O₃₃	5	8		11		15
	O₃₄		6	17	14	12
J₄	O₄₁	20		19	13	15
	O₄₂		10	7	14	7	15
	O₄₃	4	8				16
	O₄₄	9		6		6
J₅	O₅₁		6		7	12	8
	O₅₂	8		12	16		6
	O₅₃	13	12			16	8
	O₅₄		4	6	5	12
J₆	O₆₁		11			7	8
	O₆₂			8	12		6
	O₆₃	10	5		13	6
	O₆₄	16		8			12
加工功率 $P c / k W$		2.66	2.23	1.83	2.56	2.35	1.35
待机功率 $P i d l e / k W$		0.50	0.40	0.35	0.41	0.36	0.25

Table 7

Table 8

Table 9

Fig. 7

Fig. 8

Table 10

Comparison results of large-scale instances

目标参数	50×5		60×6
目标参数	IWPA	GA	IWPA	GA
$f 1$ 完工时间	77	87	346	358
$f 2$ 能耗值	818.1	832.9	3 606.2	3 746.4
$f$ 归一化值	0.15	0.24	0.25	0.28

Table 10

References 20

1	Johnson S M. Optimal Two-and Three-Stage Production Schedules with Setup Times Included[J]. Naval Research Logistics Quarterly (S0894-069X), 1954, 12(1): 336-353.
2	Chaudhry, Imran, Ali, et al. A Research Survey: Review of Flexible Job Shop Scheduling Techniques[J]. International Transactions in Operational Research (S0969-6016), 2005, 23(3): 551-591.
3	Pezzella F, Morganti G, Ciaschetti G. A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2008, 35(10): 3202-3212.
4	Yuan Y, Xu H. Flexible Job Shop Scheduling Using Hybrid Differential Evolution Algorithms[J]. Computers & Industrial Engineerin (S0360-8352), 2013, 65(2): 246-260.
5	Ham A, Park M J, Kim K M, et al. Energy-Aware Flexible Job Shop Scheduling Using Mixed Integer Programming and Constraint Programming[J]. Mathematical Problems in Engineering (S1024-123X), 2021: 1-12.
6	Gao K Z, Suganthan P N, Chua T J, et al. A Two-stage Artificial Bee Colony Algorithm Scheduling Flexible Job-Shop Scheduling Problem with New Job Insertion[J]. Expert Systems with Applications (S0957-4174), 2015, 42(21): 7652-7663.
7	Ishikawa S, Kubota R, Horio K. Effective Hierarchical Optimization by a Hierarchical Multi-space Competitive Genetic Algorithm for the Flexible Job-Shop Scheduling Problem[J]. Expert Systems with Applications (S0957-4174), 2015, 42(24): 9434-9440.
8	Jiang T, Deng G. Optimizing the Low-Carbon Flexible Job Shop Scheduling Problem Considering Energy Consumption[J]. IEEE Access (S2169-3536), 2018, 6: 99.
9	Lei D M, Li M, Wang L. A Two-Phase Meta-Heuristic for Multiobjective Flexible Job Shop Scheduling Problem with Total Energy Consumption Threshold[J]. IEEE Transactions on Cybernetics (S2168-2267), 2018, 49(3): 1097-1109.
10	王雷, 蔡劲草, 石鑫. 基于改进遗传算法的多目标柔性作业车间节能调度问题[J]. 南京理工大学学报(自然科学版), 2017, 41(4): 494-502.
	Wang Lei, Cai Jincao, Shi Xin. Multi-objective Flexible Job Shop Energy-saving Scheduling Problem Based on Improved Genetic Algorithm[J]. Journal of Nanjing University of Science and Technology(Natural Science Edition), 2017, 41(4): 494-502.
11	张新, 李珂, 严大虎, 等. 改进入侵杂草算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2018, 30(11): 4469-4476.
	Zhang Xin, Li Ke, Yan Dahu, et al. Improved Intrusion Weed Algorithm for Solving Flexible Job Shop Scheduling Problem[J]. Journal of System Simulation, 2018, 30(11): 4469-4476.
12	吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2015, 21(5): 1262-1270.
	Wu Xiuli, Zhang Zhiqiang, Du Yanhua, et al. Improved Bacteria Foraging Optimization Algorithm for Flexible Job Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5): 1262-1270.
13	吴虎胜, 张凤鸣, 吴庐山. 一种新的群体智能算法—狼群算法[J]. 系统工程与电子技术, 2013, 35(11): 2430-2438.
	Wu Husheng, Zhang Fengming, Wu Lushan. New Swarm Intelligence Algorithm-Wolf Pack Algorithm[J]. Systems Engineering and Electronics, 2013, 35(11): 2430-2438.
14	董亚科, 杜军, 李博, 等. 多选择背包问题离散狼群算法研究[J]. 传感器与微系统, 2015, 34(6): 21-23, 26.
	Dong Yake, Du Jun, Li Bo, et al. Research on Discrete Wolf Pack Algorithm of Multiple Choice Knapsack Problem[J]. Transducer and Microsystem Technologies, 2015, 34(6): 21-23, 26.
15	Wu H S, Zhang F M, Li H, et al. Discrete Wolf Pack Algorithm for Traveling Salesman Problem[J]. Control & Decision (S1001-0920), 2015, 30(10): 1861-1867.
16	李斌. 基于改进狼群算法的森林灭火资源调度研究[D]. 长沙: 中南林业科技大学, 2018.
	Li Bin. Research on Forest Fire-fighting Resource Scheduling Based on Improved Wolves Algorithm[D]. Changsha: Central South University of Forestry and Technology, 2018.
17	Wang F, Tian Y, Wang X. A Discrete Wolf Pack Algorithm for Job Shop Scheduling Problem[C]// 2019 5th International Conference on Control, Automation and Robotics (ICCAR). Beijing: IEEE, 2019.
18	谢锐强, 张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
	Xie Ruiqiang, Zhang Huizhen. Two-Vector Wolf Pack Algorithm for Flexible Job Shop Scheduling Problem[J]. Computer Engineering and Applications, 2021, 57(7): 251-256.
19	张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Job-Shop调度问题[J]. 中国机械工程, 2004(23): 83-87.
	Zhang Chaoyong, Rao Yunqing, Liu Xiangjun, et al. An Improved Genetic Algorithm for the Job-Shop Scheduling Problem[J]. China Mechanical Engineering, 2004(23): 83-87.
20	解潇晗, 朱晓春, 周琦, 等. 低能耗柔性作业车间调度研究[J]. 机电工程,2020, 37(2): 132-137.
	Xie Xiaohan, Zhu Xiaochun, Zhou Qi, et al. Scheduling of Low Energy Consumption Flexible Job Shop[J]. Mechanical & Electrical Engineering Magazine, 2020, 37(2): 132-137.

参数名	数值
种群规模	100
迭代次数	200
探狼比例因子	0.4
最大游走次数	10
工序游走步长	4
机器游走步长	2
更新比例因子	0.3

实验序号	α₁	α₂	最大完工时间	能耗值	适应度值
1	1	0	10	80.0	12.300
2	0.9	0.1	10	76.3	12.410
3	0.8	0.2	11	86.0	13.834
4	0.7	0.3	10	79.8	12.800
5	0.6	0.4	10	76.3	12.720
6	0.5	0.5	11	78.3	13.620
7	0.4	0.6	10	76.3	12.931
8	0.3	0.7	10	76.3	13.037
9	0.2	0.8	11	74.4	13.120
10	0.1	0.9	11	74.4	13.071
11	0	1	12	74.0	12.950

实验序号	α₁	α₂	最大完工时间	能耗值
1	1	0	37	424.8
2	0.9	0.1	39	420.3
3	0.8	0.2	40	382.1
4	0.5	0.5	44	375.5
5	0.2	0.8	41	386.8
6	0.1	0.9	44	375.3
7	0	1	54	370.7

[1]	Chen Juan, Zheng Wang, Liu Qianqian, Lu Bin. Automatic Multi-objective Optimization Based on Dynamic Storage Location Allocation Strategy [J]. Journal of System Simulation, 2025, 37(6): 1435-1448.
[2]	Wu Zisong, Chang Daofang, Gai Yuchun. Optimization of Cargo Location Allocation in Four-way Shuttle Warehousing System Based on Two-stage Hybrid Algorithm [J]. Journal of System Simulation, 2025, 37(5): 1234-1245.
[3]	Liu Xiang, Jin Qiankun. Research on PAC-Bayes-Based A2C Algorithm for Multi-objective Reinforcement Learning [J]. Journal of System Simulation, 2025, 37(12): 3212-3223.
[4]	Ding Xinhuan, Wang Huaqing, Dang Xu. Multi-objective Optimization of Signal Timing at Intersections Considering Tailpipe Emissions [J]. Journal of System Simulation, 2025, 37(10): 2687-2700.
[5]	Wang Ke, Guan Sijia, Xiyan Yin, Li Xixing, Tang Hongtao. Research on Mixed-model Assembly Line Balancing Optimization Based on Hybrid Genetic Tabu Search Algorithm [J]. Journal of System Simulation, 2025, 37(1): 167-182.
[6]	Li Feixing, Xing Lining, Zhou Yu. Adversarial Simulation Testing Algorithm for SVM Based on Multi-objective Evolutionary Optimization [J]. Journal of System Simulation, 2024, 36(9): 2016-2031.
[7]	Li Erchao, Zhang Shenghui. UAV Online Track Planning Based on DMOEA-APTC Algorithm [J]. Journal of System Simulation, 2024, 36(9): 2086-2099.
[8]	Zhang Wenqiang, Wang Xiaomeng, Zhang Xiaoxiao, Zhang Guohui. Hybrid Evolutionary Multi-objective Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup [J]. Journal of System Simulation, 2024, 36(8): 1914-1928.
[9]	Jiang Quan, Wei Jingxuan. Real-time Scheduling Method for Dynamic Flexible Job Shop Scheduling [J]. Journal of System Simulation, 2024, 36(7): 1609-1620.
[10]	Deng Mingjun, Hu Xinxia, Li Xiang, Xu Liping. Arterial Coordination Optimization Method Based on Vehicle Speed Guidance and Inductive Control [J]. Journal of System Simulation, 2024, 36(6): 1309-1321.
[11]	Wen Tingxin, Guan Tingyu. Hybrid Flow Shop Scheduling with Limited Buffers Considering Energy Consumption and Transportation [J]. Journal of System Simulation, 2024, 36(6): 1344-1358.
[12]	Zhao Jia, Lai Zhizhen, Wu Runxiu, Cui Zhihua, Wang Hui. Hierarchical Guided Enhanced Multi-objective Firefly Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1152-1164.
[13]	Wang Yubo, Hu Chengyu, Gong Wenyin. Handling Constrained Multi-objective Optimization Problems Based on Relationship Between Pareto Fronts [J]. Journal of System Simulation, 2024, 36(4): 901-914.
[14]	Zeng Shaoda, Liu Hailin. Planning Modeling and Optimization Algorithm for 5G Indoor Distribution System [J]. Journal of System Simulation, 2024, 36(3): 659-672.
[15]	An Jing, Si Guangya, Zeng Miaoting. Construction of Surrogate Model Driven by Model and Data [J]. Journal of System Simulation, 2024, 36(3): 756-769.