An integrated tabu search algorithm for the lot streaming problem in job shops

In this paper, we focus on solving the lot streaming problem in a job shop environment, where consistent sublots are considered. The presented three-phase algorithm incorporates the predetermination of sublot sizes, the determination of schedules based on tabu search and the variation of sublot sizes. With regard to tabu search implementation, a constructive multi-level neighbourhood is developed, which effectively connects three isolated neighbourhood functions. Moreover, enhancements of the basic version of tabu search are conducted. Combined with the procedure for varying sublot sizes. the algorithm further exploits the improvement potential. All tested instances show a rapid convergence to their lower bounds. The well-known difficult benchmark problems also achieve substantial makespan reduction. In addition, the performance of specific components is intensively examined in our study. (C) 2008 Elsevier B.V. All rights reserved.