GENETIC AND TABU SEARCH ALGORITHMS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SET-UP TIMES AND DETERIORATING JOBS

Abstract

This paper introduces the effects of job deterioration and sequence dependent set- up time in a single machine scheduling problem. The considered optimization criterion is the minimization of the makespan (Cmax). For this purpose, after formulating the mathematical model, genetic and tabu search algorithms were developed for the problem. Since population diversity is a very important issue in preventing from being trapped in a local optimum, two methods were used to overcome this problem. Because of the novelty of the considered problem, there was no standard benchmark available to test the developed algorithms, so the results were checked by a lower bound which was calculated by a procedure that emphasizes on job deterioration effects. The tests and evaluations illustrate the effectiveness of the presented algorithms.