Scheduling jobs on Dynamic parallel machines with sequence-dependent setup times

Dynamic parallel machine scheduling problems (DPMSPs) with sequence-dependent setup times represent a very important production scheduling problem but remain under-represented in the research literature. In this study, a restricted simulated annealing (RSA) algorithm that incorporates a restricted search strategy with the elimination of non-effect job moves to find the best neighborhood schedule is presented. The proposed RSA algorithm can reduce search efforts significantly while minimizing maximum lateness on DPMSPs. Extensive computational experiments demonstrate that the proposed RSA algorithm is highly effective as compared to the basic simulated annealing and existing algorithms on the same benchmark problem data set.