A tabu search with a new neighborhood search technique applied to flow shop scheduling problems

摘要

In this paper, a tabu search algorithm with a new neighborhood technique is proposed for solving flow shop scheduling problems. An idea obtained from a simulation study on the adaptive behavior of a fish school is used to determine the neighborhood search technique. The cooperation and the diversity of job data are defined for describing the data structure by using the given information. According to the definitions, job data are classified into four types, and two of them are treated in this paper. A large number of computational experiments are carried out to study the assignments of both local effort and global effort under a limited search time. The result shows that the allocation of the local and the global effort depends on the job data characteristics, such as cooperation and diversity. The validity of the tabu search algorithm is examined by comparing it with the genetic algorithm. It is found that the proposed tabu search algorithm has better convergence and much shorter computational time than the genetic algorithm.