Total Tardiness Minimization in Flow Shop with Intermediate Due Dates

In this paper minimization of total tardiness with intermediate due dates in flow shop scheduling is presented. There are some situations in which there is a due date for each intermediate operation of a job such as research and development and consulting projects. Usually each project (job) is carried out through different phases (machines) and there is an associated due date for each phase. Thus the tardiness of each phase should be considered. Due to the complex nature of the tardiness in flow shop problems and since this problem is a NP-hard, three Meta heuristic approaches; Simulated Annealing, Genetic Algorithm and Particle Swarm Optimization have been applied to reach near optimal solution. Extensive computational experiments are performed on 96 generated scenarios. Two indicators were used to evaluate the Meta heuristics. The results indicate that Simulated Annealing and Genetic Algorithm presented better solutions for the given scheduling problem. Moreover considering the CPU time, Genetic Algorithm provided the solution in less time.