ILS&TS Hybrid Algorithm Based on Random Kick Mechanism for FSFIS Problem
Lixin Tang · Journal of Northeastern University · 2004
An iterative local search algorithm (ILS) is presented and implemented which is based on random kick strategy to solve the flowshop scheduling problem with finite intermediate storage (FSFIS). The kick move of ILS is designed by using several pairs of non-across swap moves with a backtracking mechanism used to make the algorithm search in a promising area. This algorithm has been proved quick and effective by a computer experiment in which the algorithm is implemented with 4 different neighborhood structures and 480 randomly generated problem instances. Because the ILS is a random algorithm and has a very good performance to escape from local optima solutions and tabu search (TS) has a very strong search ability, a hybrid algorithm is constructed to embed random mechanism into the static tabu search algorithm. This hybrid algorithm can synthesize the advantages of the two original algorithms. The computer experiment shows that the hybrid algorithm is better than the best known algorithm by 021% in the worst case.