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

摘要

Abstract——Job shop scheduling problem is a strongly NP-hard combinatorial optimization problem. The solution space andcomputation time of the algorithm can grow exponentially as the number of jobs and machines increase. It’s significant theoreticallyand 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 thesame one teacher and in the learner phase also carry out among the existing learners. This algorithm has a disadvantage of prematureconvergence when it is put into practice. So, to increase the diversity, firstly we introduce the multi-learning method in the teacherphase; secondly we improve the learning method of the learning phase; thirdly, we improve the decoding procedure; fourthly, wecombine the TLBO algorithm with local search technology. To show the efficiency of the improved TLBO, the simulation resultsfor benchmark problems are compared with results derived by the other algorithms.