Genetic Algorithms for Single Machine Job Scheduling with Common Due Date and Symmetric Penalties

Abstract

A single machine n-job scheduling problem is examined to minimize sum of absolute deviations of completion times from a common due date. Simple and hybrid genetic Algorithms are developed by investigating basic operators for the applications of job sequencing problems. For the simple genetic algorithm two heuristic crossover schemes: Algorithm VASX and Algorithm VADX are developed based on important properties of the scheduling problem. Local Improvement techniques are considered to enhance the solution quality of the simple genetic algorithm. The power of a genetic algorithm is illustrated by comparing the performance with branch and bound procedure.