Le jury sera composé de :
BILLAUT Jean-Charles: Professeur, Université de Tours (Directeur de thèse)
CHRETIENNE Philippe: Professeur, Université Paris 6, Paris (Rapporteur)
GEORGELIN Christine: Maître de Conférences, Université de Tours
LOPEZ Pierre: DR CNRS. LAAS-CNRS. Toulouse (Rapporteur)
PINSON Eric: Professeur, Université Catholique d’Angers
SOUKHAL Ameur: Professeur, Université de Tours
Abstract:
We consider a single machine scheduling problem with deadlines and we want to characterise the set of optimal solutions, without enumerating them. We assume that jobs are numbered in EDD order and that this sequence is feasible. The key idea is to use the lattice of permutations and to associate to the supremiun permutation the EDD sequence. In order to characterize a lot of solutions, we search for a feasible sequence, as far as possible to the supremum. The distance is the level of the sequence in the lattice, which has to be minimum. This new objective function is investigated. Some polynomially particular cases are identified, but the complexity of the general case problem remains open. Some resolution methods, polynomial and exponential, are proposed and evaluated. The level of the sequence being related to the positions of jobs in the sequence, new objective functions related to the jobs positions are identified and studied. The problem of minimizing the total weighted positions of jobs is proved to be strongly NP-hard. Some particular cases are investigated, resolution methods are also proposed and evaluated.
Keywords: scheduling, single machine, deadlines, positions, lattice, characterization, complexity
