La soutenance de thèse d'Alexandre Salch aura lieu le vendredi 29 novembre 2013 à 14h en amphi 104 en amphi Gosse (Grenoble-INP site Viallet, 46 avenue Félix Viallet 38000 Grenoble).
Titre :
Ordonnancement stochastique
Résumé :
Le cadre de cette thèse est l'étude de systèmes de production avec impatience et plusieurs classes de clients. Ces systèmes sont modélisés comme des problèmes d'ordonnancement stochastiques avec des dates d'échéance. Dans la littérature, peu de résultats existent sur le contrôle optimal de ces systèmes. Nous considérons un système avec une machine, sur laquelle des tâches sont à exécuter. Les durées d'exécution, les dates d'échéance (ou durées d'impatience) et les dates de disponibilité des tâches sont des variables aléatoires. A chaque tâche est associé un poids et l'objectif est de minimiser l'espérance du nombre pondéré de tâches en retard.
Dans notre étude, nous utilisons différentes modélisations, rendant compte des différentes contraintes régissant des systèmes réels. Notamment, nous faisons la différence entre l'impatience (le fait d'avoir attendu trop longtemps), et l'abandon (le fait de quitter le système suite à l'impatience). Dans la classe des politiques statiques, nous donnons des ordonnancements optimaux pour des problèmes avec impatience. Dans la classe des politiques dynamiques avec préemption, nous donnons de nouvelles conditions garantissant l'optimalité d'une politique stricte pour des problèmes avec abandon. Nous proposons aussi une heuristique plus efficace que celles développées dans la littérature. Enfin, nous explorons des variantes et des extensions de ces problèmes, lorsque le système comporte plusieurs machines et lorsque la préemption n'est pas autorisée.
Membres du jury :
Titre :
Ordonnancement stochastique
Résumé :
Le cadre de cette thèse est l'étude de systèmes de production avec impatience et plusieurs classes de clients. Ces systèmes sont modélisés comme des problèmes d'ordonnancement stochastiques avec des dates d'échéance. Dans la littérature, peu de résultats existent sur le contrôle optimal de ces systèmes. Nous considérons un système avec une machine, sur laquelle des tâches sont à exécuter. Les durées d'exécution, les dates d'échéance (ou durées d'impatience) et les dates de disponibilité des tâches sont des variables aléatoires. A chaque tâche est associé un poids et l'objectif est de minimiser l'espérance du nombre pondéré de tâches en retard.
Dans notre étude, nous utilisons différentes modélisations, rendant compte des différentes contraintes régissant des systèmes réels. Notamment, nous faisons la différence entre l'impatience (le fait d'avoir attendu trop longtemps), et l'abandon (le fait de quitter le système suite à l'impatience). Dans la classe des politiques statiques, nous donnons des ordonnancements optimaux pour des problèmes avec impatience. Dans la classe des politiques dynamiques avec préemption, nous donnons de nouvelles conditions garantissant l'optimalité d'une politique stricte pour des problèmes avec abandon. Nous proposons aussi une heuristique plus efficace que celles développées dans la littérature. Enfin, nous explorons des variantes et des extensions de ces problèmes, lorsque le système comporte plusieurs machines et lorsque la préemption n'est pas autorisée.
Membres du jury :
- Mr Bruno GAUJAL, Directeur de recherche, INRIA Montbonnot, Examinateur
- Mr Jean-Philippe GAYON, Maître de conférence, Institut polytechnique de Grenoble, Directeur de thèse
- Mr Alain JEAN-MARIE, Directeur de recherche, INRIA Sophia Antipolis - Méditerranée, Rapporteur
- Mr Pierre LEMAIRE, Maître de conférence, Institut polytechnique de Grenoble, Co-Encadrant de thèse
- Mr Philippe NAIN, Directeur de recherche, INRIA Sophia Antipolis - Méditerranée, Examinateur
- Mr Christophe RAPINE, Professeur, Université de Lorraine, Rapporteur
Abstract :
In this thesis, production systems facing abandonments are studied. These problems are modeled as stochastic scheduling problems with due dates. In the literature, few results exist concerning the optimal control of such systems. This thesis aim at providing optimal control policies for systems with impatience. We consider a generic system with a single machine, on which jobs have to be processed. Processing times, due dates (or patience time) and release dates are random variables. A weight is associated to each job and the objective is to minimize the expected weighted number of late jobs.
In our study, we use different models, taking into account the specific features of real life problems. For example, we make a difference between impatience, when a customer has been waiting for too long, and abandonment, when a customer leaves the system after getting impatient. In the class of static list scheduling policies, we provide optimal schedules for problems with impatience. In the class of preemptive dynamic policies, we specify conditions under which a strict priority rule is optimal and we give a new heuristic. Those results extend previous ones from the literature. We study variants and extensions of these problems, when several machines are available or when preemption is not authorized.
In this thesis, production systems facing abandonments are studied. These problems are modeled as stochastic scheduling problems with due dates. In the literature, few results exist concerning the optimal control of such systems. This thesis aim at providing optimal control policies for systems with impatience. We consider a generic system with a single machine, on which jobs have to be processed. Processing times, due dates (or patience time) and release dates are random variables. A weight is associated to each job and the objective is to minimize the expected weighted number of late jobs.
In our study, we use different models, taking into account the specific features of real life problems. For example, we make a difference between impatience, when a customer has been waiting for too long, and abandonment, when a customer leaves the system after getting impatient. In the class of static list scheduling policies, we provide optimal schedules for problems with impatience. In the class of preemptive dynamic policies, we specify conditions under which a strict priority rule is optimal and we give a new heuristic. Those results extend previous ones from the literature. We study variants and extensions of these problems, when several machines are available or when preemption is not authorized.