Genetic algorithms for job scheduling with distinct due dates and arbitrary weights for penalties

Abstract

In this thesis, the single machine job scheduling problem with arbitrary weights is considered and the optimal timing algorithm which is the modification of the algorithm of Garey et. al. is presented. Given a sequence, the optimal timing algorithm locates each job, one at a time. It produced the cost of a sequence. To solve the single machine job scheduling problem, Genetic Algorithm is used as a meta-heuristic. Various operators, a representation scheme of a feasible solution and reproduction rules are examined and compared. In the computational results, it is shown that N best reproduction without duplicates method and Blockwise Recombination with Uniform Crossover are better than others. With these operators, Genetic Algorithm is compared with other heuritic, INT procedure. In this comparison, Genetic Algorithm performs well.