Improvement of diversification and intensification in Teaching-learningbased optimization algorithm to solve job shop scheduling problems

摘要

Abstract——Job shop scheduling problem is a strongly NP-hard combinatorial optimization problem. The solution space and computation time of the algorithm can grow exponentially as the number of jobs and machines increase. It’s significant theoretically and practically to study the problem. Teaching-learning-based optimization (TLBO) algorithm is used to solve job shop problems. In the original TLBO algorithm, there are only the teacher and learner phases. In the teacher phase, all the learners learn from the same one teacher and in the learner phase also carry out among the existing learners. This algorithm has a disadvantage of premature convergence when it is put into practice. So, to increase the diversity, firstly we introduce the multi-learning method in the teacher phase; secondly we improve the learning method of the learning phase; thirdly, we improve the decoding procedure; fourthly, we combine the TLBO algorithm with local search technology. To show the efficiency of the improved TLBO, the simulation results for benchmark problems are compared with results derived by the other algorithms.