Abstract: 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 is 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 optimal solutions and tabu search (TS) has a 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 0.21% in the worst case.