A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times

• A neighborhood search function for the flexible job shop scheduling with sequence-dependent setup times is developed.
• Experimentations are conducted to determine its best working parameters under different problem conditions.
• A tabu search approach is developed to demonstrate the utilization of the developed neighborhood search function.
• Simple lower bounds are introduced to assess the performance of the developed tabu search approach.

This paper addresses the makespan minimization problem in scheduling flexible job shops whenever there exist separable sequence-dependent setup times. An extension to the neighborhood search functions of Mastrolilli and Gambradella, developed for the flexible job shop scheduling problem (FJSP), is provided. It is shown that under certain conditions such an extension is viable. Accordingly, a randomized neighborhood search function is introduced, and its best search parameters are determined experimentally using modified FJSP benchmark instances. A tabu search approach utilizing the proposed neighborhood search function is then developed, and experimentations are conducted using the modified instances to benchmark it against a lower bound. Experimental results show that on average, the tabu search approach is capable of achieving optimality gaps of below 10% for instances with low average setup time to processing time ratios.