Scheduling with earliness-tardiness penalties and parallel machines

This is a summary of the author's PhD thesis supervised by Francis Sourd and Philippe Chretienne and defended on 30 January 2007 at the Universite Pierre et Marie Curie, Paris. The thesis is written in French and is available from the author upon request. This work is about scheduling on parallel machines in order to minimize the total sum of earliness and tardiness costs. To solve some variants of this problem we propose: an exact method based on continuous relaxations of convex reformulations derived from a 0-1 quadratic program; a heuristic algorithm that relies on a new exponential size neighborhood search; finally, a lower bound method based on a polynomial time solution of a preemptive scheduling problem for which the cost functions of the jobs have been changed into so called position costs functions.