Single machine scheduling with sequence-dependent setup times and delayed precedence constraints

This research deals with the single machine scheduling problem of minimizing the makespan with sequence dependent setup times and delayed precedence constraints. A makespan calculation model is first proposed. When given a feasible job sequence, the proposed model can calculate the makespan. Then a variable neighbourhood search (VNS) with four phases is proposed for optimizing the job sequence. The proposed VNS adopts five operations to search for new solutions, and modifies all solutions to satisfy precedence constraints. The proposed VNS will accept a worse solution over a better solution with a certain probability, in order to escape from a local optimum. The experimental results show that the proposed VNS provides the best results with less than 10 s of computation time. Therefore it is efficient and effective in solving the single machine scheduling problems.