基于教学优化算法求解置换流水车间调度问题

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

系统仿真学报 ›› 2022, Vol. 34 ›› Issue (5): 1054-1063.doi: 10.16182/j.issn1004731x.joss.20-0983

基于教学优化算法求解置换流水车间调度问题

张其文(), 张斌()

兰州理工大学　计算机与通信学院，甘肃　兰州　730050

收稿日期:2020-12-08 修回日期:2021-01-26 出版日期:2022-05-18 发布日期:2022-05-25
通讯作者: 张斌 E-mail:823869941@qq.com;1374289220@qq.com
作者简介:张其文（1975-），男，硕士，副教授，研究方向为智能信息技术处理。E-mail：823869941@qq.com
基金资助:
国家自然科学基金(62063021)

Teaching-Learning-Based Optimization Algorithm for Permutation Flowshop Scheduling

Qiwen Zhang(), Bin Zhang()

School of Computer and Communication, Lanzhou University of Technology, Lanzhou 730050, China

Received:2020-12-08 Revised:2021-01-26 Online:2022-05-18 Published:2022-05-25
Contact: Bin Zhang E-mail:823869941@qq.com;1374289220@qq.com

摘要/Abstract

摘要：

针对置换流水车间调度问题，将连续算法与离散策略相结合，提出一种多班级教学优化算法。采用基于置换变异改进的NEH（nawaz enscore ham）种群初始化方法，兼顾初始解的质量和多样性。在教学阶段，引入离散的自适应教学，并给出去重的操作，避免了无意义的教学过程。新增了基于莱维飞行的自学策略，同时以变邻域搜索的方式模拟离散阶段的自学。将相互学习与班级交流合并，在保证优秀个体交流的基础上，提高学习的效率。通过对标准测试集Rec进行测试，并与其他算法比较，验证了算法的有效性和稳定性。

关键词: 置换流水车间调度, 多班级教学优化算法, 去重操作, 自学策略, 优势个体交流

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

中图分类号:

TP391.9

张其文, 张斌. 基于教学优化算法求解置换流水车间调度问题[J]. 系统仿真学报, 2022, 34(5): 1054-1063.

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

图/表 9

表1

图1

图2

图3

图4

图5

图6

表2

图7

参考文献 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

基于教学优化算法求解置换流水车间调度问题

Teaching-Learning-Based Optimization Algorithm for Permutation Flowshop Scheduling

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 21

相关文章 1

编辑推荐

Metrics

本文评价