Teaching-Learning-Based Optimization Algorithm And Its Applied Research For The Shop Scheduling Problem

The essence of the scheduling problem is to achieve the optimization of output,energy consumption,time and other goals through reasonable allocation of resources and reasonable arrangements of procedures or other operations under the constraints of process,equipment,and capital.Shop scheduling is an indispensable part of scheduling problem,which directly determines the production efficiency,thus affecting the operation of manufacturing system,the benefit of enterprises and the market competitiveness.Most shop scheduling problems are NP-Hard problem.As the scale of the problem increases and scientific research continues to deepen,people have higher requirements for computational complexity and solution efficiency.Therefore,the development of simple,efficient and easy-to-implement methods is still research hotspots in this field.Teaching-Learning-Based Optimization Algorithm is a swarm intelligence optimization algorithm inspired by teaching process.TLBO has been widely used in numerical optimization and industrial design because of its simple optimization process and no additional parameters.This article has carried on in-depth research on TLBO,two different improvements have been made to TLBO by analyzing the optimization process and combining this algorithm with other algorithms.At the same time,the improved algorithm is applied to two different shop scheduling problems,and the effectiveness and feasibility of the algorithm are verified through simulation test and experimental analysis.The main research contents and related work are as follows:(1)Aiming at the problem of insufficient information exchange between learners and a single teacher easily falling into local optimum when the standard TLBO algorithm solves discrete problems,this paper proposes Multi-Classes Teaching-Learning-Based Optimization(MCTLBO)algorithm,and use MCTLBO to solve the Permutation Flowshop Scheduling Problem(PFSP).In MCTLBO,an improved NEH population initialization method based on permutation mutation is adopted,which takes into account the quality and diversity of solutions.In the teaching stage,considering the differences between teachers and students,a position based crossover method is proposed,and the meaningless teaching process is avoided by de-duplication operation.The self-study stage is introduced,levy flight is used to eliminate the uncertainty of random variation,and the quality of the solution is improved by variable neighborhood search.In the learning stage,the average fitness of the population is used as the screening condition to avoid the mutual influence between poor students and effectively ensure the communication of superior individuals.The validity and stability of MCTLBO in solving discrete problems are verified by testing the standard test set rec and comparing with the related algorithms.(2)Aiming at the No-Wait Flowshop Scheduling Problem(NWFSP),a discrete teaching-learning-based optimization algorithm(DTLBO)is proposed.In DTLBO,optimization process is redefined from the perspective of sequence difference(student level).In the teaching stage,the teacher adopt different methods according to the different levels of students,so as to achieve the effect of teaching students in accordance with their aptitude.In the learning stage,students also show different learning behaviors according to their own level.In addition,the destruction reconstruction operation of iterated greedy algorithm is used as the local search.The improved algorithm is applied to solve the NWFSP,and the effectiveness of the algorithm is verified by simulation and related result analysis.(3)The destruction process of the iterated greedy algorithm is analyzed,and the inhomogeneity and meaninglessness in the destruction are given.The knowledge base is constructed based on the jobs and their corresponding meaningless destruction times,and the knowledge is obtained from the knowledge base before each destruction,so as to dynamically change the selection method of jobs in destruction.In addition,the early knowledge is erased in the knowledge validity period as a limitation,and only knowledge of a certain number of iterations is retained,which ensures the effectiveness of knowledge accumulation.Finally,the improved destruction is incorporated into DTLBO,and the simulation result shows that the improved destruction is effective in improving the efficiency of the algorithm.