New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

A Variable Neighborhood Search for Minimizing Total Weighted Tardiness with Sequence Dependent Setup Times on a Single Machine

SpeakerCeyda Oguz

Co-authorGokhan Kirlik

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup times. Firstly, a mathematical model is proposed to describe the problem formally. Since the problem is NP-hard, then, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. GVNS is a variation of variable neighborhood search heuristic in which a constructive heuristic is used to obtain good initial solutio. Lastly, the effectiveness of the proposed heuristic is shown by using test instances available for the single machine total weighted tardiness problem with sequence dependent setup times. GVNS outperformed the best known solutions so far in the literature for 28 out of 120 instances while performing the same for 59 instances.