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]	Xu Wang, Weidong Ji, Guohui Zhou, Jiahui Yang. Multi-objective Optimization Algorithm Based on Multi-index Elite Individual Game Mechanism [J]. Journal of System Simulation, 2023, 35(3): 494-514.
[2]	Weidong Ji, Yuqi Yue, Xu Wang, Ping Lin. Large-scale Multi-objective Natural Computation Based on Dimensionality Reduction and Clustering [J]. Journal of System Simulation, 2023, 35(1): 41-56.
[3]	Yejian Zhao, Yanhong Wang, Jun Zhang, Hongxia Yu, Zhongda Tian. Application of Improved Q Learning Algorithm in Job Shop Scheduling Problem [J]. Journal of System Simulation, 2022, 34(6): 1247-1258.
[4]	Kui Chen, Li Bi, Wenya Wang. Research on Integrated Scheduling of AGV and Machine in Flexible Job Shop [J]. Journal of System Simulation, 2022, 34(3): 461-469.
[5]	Zi'an Zhao, Hong Zhou, Yingjian Lei. Modeling and Optimization for Manufacturing Cell Scheduling Based on Improved Wolf Pack Algorithm and Simulation [J]. Journal of System Simulation, 2022, 34(2): 201-211.
[6]	Yan Xiuying, Dang Miaomiao. Optimization of Household Electricity Consumption Period Based on Improved Multi-objective Particle Swarm Optimization [J]. Journal of System Simulation, 2022, 34(1): 70-78.
[7]	Hongliang Zhang, Renman Ding, Gongjie Xu. Energy-Efficient Scheduling of Multi-objective Flexible Job Shop Considering Interval Processing Time [J]. Journal of System Simulation, 2022, 34(09): 1976-1987.
[8]	Ran Xiansheng, Yang Jing, Luo Ling, Chen Kai. Multi-objective Optimization of Multi-task Parallel Motorcycle Suspension System Parameters [J]. Journal of System Simulation, 2021, 33(5): 1216-1223.
[9]	Wang Runhong, Wang Hongjun, Zou Xiangjun, Zeng Zeqin, Li Hui, Huang Zhaofeng, Liu WeiLiang. Combined Gearbox Transmission Ratio Optimization Research Based on Hybrid Particle Swarm [J]. Journal of System Simulation, 2021, 33(4): 825-836.
[10]	Chen Kui, Bi Li. Research on FJSP of Improved Particle Swarm Optimization Algorithm Considering Transportation Time [J]. Journal of System Simulation, 2021, 33(4): 845-853.
[11]	Wang Hongfeng, Zhang Yitian, Chen Jingze. An Evolutionary Multi-Objective Simulation Optimization Algorithm for Supply Chain with Uncertain Demands [J]. Journal of System Simulation, 2021, 33(12): 2761-2770.
[12]	Wang Xiaohan, Zhang Lin, Ren Lei, Xie Kunyu, Wang Kunyu, Ye Fei, Chen Zhen. Brief Review on Applying Reinforcement Learning to Job Shop Scheduling Problems [J]. Journal of System Simulation, 2021, 33(12): 2782-2791.
[13]	Li Fei, Su Zhong. Intelligent Control of Wastewater Treatment Processes Based on Adaptive Immune Optimization [J]. Journal of System Simulation, 2021, 33(12): 3012-3020.
[14]	Wei Le, Li Xijin. Dynamic Environmental and Economic Dispatching of Wind Farm Based on Multi-objective [J]. Journal of System Simulation, 2020, 32(9): 1825-1830.
[15]	Wang Xiaofeng, Chen Yang, Zhang Guangjie, Chen Jianyu. Multi-objective Topology Mapping Method for Network Emulation [J]. Journal of System Simulation, 2020, 32(8): 1436-1445.