An Improved Tabu Search Algorithm for Job Shop Scheduling Problem Trough Hybrid Solution Representations

Job shop scheduling problem (JSP) is an attractive field for researchers and production managers since it is a famous problem in many industries and a complex problem for researchers. Due to NP-hardness property of this problem, many meta-heuristics are developed to solve it. Solution representation (solution seed) is an important element for any meta-heuristic algorithm. Therefore, many researchers try to present different encodings to solve this problem. Fattahi et al., and Gen Cheng suggested two solutions for this problem that both have advantages and weaknesses in searching solution space to reach an acceptable solution. In the current paper, a cyclic algorithm based on tabu search algorithm was proposed to improve the exploration and exploitation powers of these encodings. Also, several problems of different sizes are solved by it and the obtained results were compared. Results showed the applicability and effectiveness of the proposed solution representation in comparison with the existing ones.