Minimizing total tardiness on a single machine using Ant Colony Optimization

Ant Colony Optimization is a relatively new meta-heuristic that has demonstrated its quality and versatility on various combinatorial optimization problems such as the traveling salesman problem, the vehicle routing problem and the job shop scheduling problem. The paper introduces an Ant Colony Optimization approach to solve the problem of determining a job-sequence that minimizes the overall tardiness for a given set of jobs to be processed on a single, continuously available machine, the Single Machine Total Tardiness Problem.