Abstract
Nowicki and Smutnicki【1996】reported an improved tabu search method called fast tabu search algorithm to solve job shop scheduling problem. When the definition of move is that x and y are successive operations on certain machine, and x and y are on a critical path, the move is to swap x and y. The fast tabu search algorithm can reduce the neighborhood size. Therefore, the fast tabu search algorithm can obtain a good solution of job shop problem in a shorter time.The difference between flexible job shop problem and job shop problem is that, in flexible job shop problem, a machine type may consist of identical parallel machines. Because of this characteristic, the algorithm for job shop problem is not suitable for solving flexible job shop problem.This study combines tabu search, fast tabu search algorithm, and the proposed superior critical path algorithm to solve flexible job shop problem. This study hopes to develop an algorithm that can find a good solution in a short time.Computational experiments show that the algorithm can solve large size flexible job shop problem and find a good solution in a short time.Keywords: job shop problem, flexible job shop problem, tabu search, fast tabu search algorithm, superior critical path algorithm.