Teaching-Learning-Based Optimization Algorithm for Permutation Flowshop Scheduling

doi:10.16182/j.issn1004731x.joss.20-0983

Abstract

Abstract:

A multi-classes teaching-learning-based optimization (MCTLBO) algorithm is proposed for the permutation flowshop scheduling problem (PFSP) by combining continuous algorithm with discrete strategy. An improved nawaz enscore ham (NEH) population initialization method based on permutation mutation is adopted, which takes into account the quality and diversity of initial solutions. In the teaching stage, discrete adaptive teaching with duplicate removal is introduced to avoid meaningless teaching processes. A new self-learning strategy based on Levy flight is added, and the self-learning in discrete stage is simulated by variable neighborhood search. Learner phase and class communication are combined to improve the efficiency of learning on the basis of ensuring the communication of excellent individuals. The standard test sets of Rec is tested, and compared with other algorithms, the validity and stability of the algorithm are verified.

Key words: permutation flowshop scheduling, multi-classes teaching-learning-based optimization algorithm, duplicate removal, self-learning stragety, communication of excellent individuals

CLC Number:

TP391.9

Qiwen Zhang, Bin Zhang. Teaching-Learning-Based Optimization Algorithm for Permutation Flowshop Scheduling[J]. Journal of System Simulation, 2022, 34(5): 1054-1063.

Figures/Tables 9

Table 1

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 2

Fig. 7

References 21

[1]	Garey M R, Johnson D S, Sethi R. The Complexity of Flowshop and Jobshop Scheduling[J]. Mathematics of Operations Research (S0364-765X), 1976, 1(2): 117-129.
[2]	Chung C S, Flynn J, Kirca O. A Branch and Bound Algorithm to Minimize the Total Flow Time for M-machine Permutation Flowshop Problems[J]. International Journal of Production Economics (S0925-5273), 2002, 79(3): 185-196.
[3]	Ruiz R, Maroto C. A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics[J]. Eur J Oper Res (S0377-2217), 2005, 165(2): 479-494.
[4]	Goldberg D E. Genetic Algorithm in Search, Optimization, and Machine Learning[M]. Massachusetts, USA: Addison-Wesley Pub. Co, 1989.
[5]	Liu H, Gao L, Pan Q. A Hybrid Particle Swarm Optimization with Estimation of Distribution Algorithm for Solving Permutation Flowshop Scheduling Problem[J]. Expert Systems with Applications (S0957-4174), 2011, 38(4): 4348-4360.
[6]	秦旋, 房子涵, 张赵鑫. 混合共生生物搜索算法求解置换流水车间调度问题[J]. 浙江大学学报(工学版), 2020, 54(4): 712-721.
	Qin Xuan, Fang Zihan, Zhang Zhaoxin. Hybrid Symbiotic Organisms Search Algorithm for Permutation Flow Shop Scheduling Problem[J]. Journal of Zhejiang University (Engineering Science), 2020, 54(4): 712-721.
[7]	Rao R V, Savsani V J, Vakharia D. Teaching-Learning- Based Optimization: a Novel Method for Constrained Mechanical Design Optimization Problems[J]. Computer-Aided Design (S0010-4485), 2011, 43(3): 303-315.
[8]	Rao R V, Savsani V J, Vakharia D. Teaching-Learning- Based Optimization: an Optimization Method for Continuous Non-Linear Large Scale Problems[J]. Information Sciences (S0020-0255), 2012, 183(1): 1-15.
[9]	Shao W, Pi D, Shao Z. An Extended Teaching-Learning Based Optimization Algorithm for Solving No-Wait Flow Shop Scheduling Problem[J]. Applied Soft Computing (S1568-4946), 2017, 61: 193-210.
[10]	Rao R V, Patel V. Multi-Objective Optimization of Heat Exchangers Using a Modified Teaching-Learning-Based Optimization Algorithm[J]. Applied Mathematical Modelling (S0307-904X), 2013, 37(3): 1147-1162.
[11]	Rao R V, Patel V. Multi-objective Optimization of two Stage Thermoelectric Cooler Using a Modified Teaching-Learning-Based Optimization Algorithm[J]. Engineering Applications of Artificial Intelligence (S0952-1976), 2013, 26(1): 430-445.
[12]	Pickard J K, Carretero J A, Bhavsar V C. On the Convergence and Origin Bias of the Teaching-Learning- Based-Optimization Algorithm[J]. Applied Soft Computing (S1568-4946), 2016, 46: 115-127.
[13]	Lei D, Gao L, Zheng Y. A Novel Teaching-Learning- Based Optimization Algorithm for Energy-Efficient Scheduling in Hybrid Flow Shop[J]. IEEE Transactions on Engineering Management (S0018-9391), 2017, 65(2): 1-11.
[14]	Gao W F, Huang L L, Liu S Y, et al. Artificial Bee Colony Algorithm Based on Information Learning[J]. IEEE Transactions on Cybernetics (S2168-2267), 2015, 45(12): 2827-2839.
[15]	Rao R, Patel V. An Elitist Teaching-learning-based Optimization Algorithm for Solving Complex Constrained Optimization Problems[J]. International Journal of Industrial Engineering Computations (S1923-2926), 2012, 3(4): 535-560.
[16]	Ruiz R, Pan Q K, Naderi B. Iterated Greedy Methods for the Distributed Permutation Flowshop Scheduling Problem[J]. Omega-Int J Manage S (S0305-0483), 2019, 83: 213-222.
[17]	Yang X S, Deb S. Cuckoo Search Via Lévy Flights[C]//2009 World Congress on Nature & Biologically Inspired Computing (NaBIC). Coimbatore, India: IEEE, 2009: 210-214.
[18]	Walton S, Hassan O, Morgan K, et al. Modified Cuckoo Search: A New Gradient Free Optimisation Algorithm[J]. Chaos Solitons & Fractals (S0960-0779), 2011, 44(9): 710-718.
[19]	Luo Q, Zhou Y, Xie J, et al. Discrete Bat Algorithm for Optimal Problem of Permutation Flow Shop Scheduling[J]. The Scientific World Journal (S1537-744X), 2014, 8: 630280.
[20]	张先超, 周泓. 变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J]. 计算机集成制造系统, 2016, 22(3): 774-781.
	Zhang Xianchao, Zhou Hong. Variable Paramenters Quantum-Inspired Evolutionary Algorithm and Its Application in Permutation Flow-Shop Scheduling Problem[J]. Computer Integrated Manu-Facturing Systems, 2016, 22(3): 774-781.
[21]	谢锐强, 张惠珍. 求解置换流水车间调度的离散狼群算法[J]. 控制工程, 2020, 27(2): 288-296.
	Xie Ruiqiang, Zhang Huizhen. Discrete Wolf Pack Algorithm for Permutation Flow Shop Scheduling Problem[J]. Control Engineering of China, 2020, 27(2): 288-296.

维数j	1	2	3	4	5	6
X_i,j	-0.55	0.69	-0.33	-0.11	0.03	0.36
工序π	1	3	4	5	6	2
工序π^*	1	6	3	4	2	5
X_i,j^*	-0.55	0.36	-0.11	0.03	0.69	-0.33

Rec?问题集	m×n	C^*	DBA		VP-QEA		DWPA		HSOS		MCTLBO
Rec?问题集	m×n	C^*	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE	BRE	ARE
01	20×5	1 247	0	0.080	0	1.05	0	0	0	0	0	0.120
03	20×5	1 109	0	0.081	0	0.27	0	0	0	0	0	0.068
05	20×5	1 242	0.242	0.242	0.24	0.99	0	0.213	0	0	0	0.217
07	20×10	1 566	0	0.575	1.14	1.56	0	0	0	0	0	0.632
09	20×10	1 537	0	0.638	0.97	2.08	0	0	0	0	0	0
11	20×10	1 431	0	1.167	0.62	2.06	0	0	0	0	0	0
13	20×15	1 930	0.415	1.461	1.34	2.48	0	0.129	0	0.273	0	0.192
15	20×15	1 950	0.154	1.226	0.82	1.84	0	0.213	0	0.523	0	0.356
17	20×15	1 902	0.368	1.277	2.78	3.94	0	0.043	0	1.388	0	0.037
19	30×10	2 093	0.573	0.929	2.34	4.25	0.287	0.978	0.620	1.274	0.287	0.430
21	30×10	2 017	1.438	1.671	1.63	3.52	0.543	1.157	1.437	1.537	1.438	1.557
23	30×10	2 011	0.796	1.173	2.43	3.96	0.403	0.616	0.348	1.280	0.149	0.686
25	30×15	2 513	1.632	2.291	2.62	4.61	0.379	1.027	0.835	2.067	0.199	0.809
27	30×15	2 373	1.011	1.419	2.14	4.04	0.433	0.952	0.969	1.432	0.253	1.016
29	30×15	2 287	1.049	2.580	4.32	5.20	0.475	1.183	0.831	2.488	0	0.822
31	50×10	3 045	2.299	3.392	4.63	6.14	0.987	0.971	0.427	0.644	0.427	1.307
33	50×10	3 114	0.610	0.728	1.28	2.89	0.019	0.156	0	0.565	0.128	0.777
35	50×10	3 277	0	0.037	0.09	1.61	0	0.112	0	0	0	0.026
37	75×20	4 951	3.373	4.872	6.84	7.81	1.158	2.805	2.565	3.001	1.959	2.430
39	75×20	5 087	2.280	3.851	4.97	6.19	1.633	2.374	1.828	2.222	0.904	1.613
41	75×20	4 960	3.810	5.095	6.99	7.80	2.660	3.003	2.388	3.350	1.956	2.601
AVG	?	?	0.955	1.656	2.295	3.538	0.427	0.759	0.583	1.050	0.367	0.747