A genetic algorithm for single machine total weighted tardiness scheduling problem

Abstract

This thesis research presents a genetic algorithm for the single machine scheduling problem with minimize total weighted tardiness, which is a strong NP-hard problem. This genetic algorithm uses the natural permutation representation of a chromosome for encoding. To create the initial population, heuristic dispatching rules was combined with random method for improving the search space. Position-based crossover and exchange- base mutation operators are used for operator simplicity. The best members of the population during generations are used for searching simplicity. The VBA on Excel 2010 was used for coding the algorithm. 40, 50, 100 set of jobs on OR library was used to test efficiency of the proposed algorithm. Keywords: Genetic algorithm, single machine scheduling, total weighted tardiness, VBA Excel