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

Citation:
Abdelmaguid, T. F., "A neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times", Applied Mathematics and Computation, vol. 260, pp. 188 - 203, 2015.

Abstract:

Abstract 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.

Notes:

n/a

Related External Link

PreviewAttachmentSize
fjsp-sdst-nb-accepted.pdf281.41 KB