A parallel tabu search algorithm based on uniform sampling for generalized job-shop scheduling problems

Shop scheduling system plays a very important role in production. However, there are different shop scheduling problems in different enterprises, or even in different workshops of the same enterprise. Therefore, to improve the development efficiency and reduce the development cost of a shop scheduling system, it is necessary to design an algorithm that can solve different scheduling problems effectively. This paper proposes a parallel tabu search algorithm based on uniform sampling for the generalized job-shop scheduling problem, that is, the proposed algorithm can solve a set of job-shop scheduling problems with different production constraints or production objectives effectively. Firstly, by analyzing the characteristics of the job-shop scheduling problem and the existing algorithms, the shortcomings of the existing research were pointed out. Then a uniform sampling method is proposed for the problem. After that, the proposed algorithmic framework is introduced. The algorithm is compared with the other two state-of-the-art algorithms on three different job-shop scheduling problems. The experimental results show that the proposed algorithm has an excellent performance, including optimality and stability, on these three problems. The limitations of the algorithm and future research directions are also given in the paper. © 2023 Computers and Industrial Engineering. All rights reserved.