Minimizing Total Weighted Tardiness in Identical Parallel Machine with Sequence Dependent Setup Time Using Genetic Algorithm

Abstract

This paper considers a scheduling problem in an identical parallel machine environment to minimize total weighted tardiness with the consideration of sequence dependent setup times. As the scheduling problem is proven to be NP-hard, a genetic algorithm is developed with the aim of providing good solution in a reasonable time to the scheduling problem. Computational experiments were performed to study the effectiveness of the genetic algorithm solution quality and the CPU time. Various dispatch heuristics were developed to provide initial solutions to the genetic algorithm besides comparing their solution quality with the genetic algorithm’s solution. The developed genetic algorithm has the capability to provide good results and good improvement compared to all the developed dispatching heuristics.