Stochastic scheduling with impatience

Le sujet de cette thèse est l'étude de systèmes de production avec impatience. 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 ce genre de systèmes. C'est dans ce cadre que s'inscrit cette thèse. Nous considérons un système générique 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. À 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 et nous proposons une heuristique plus efficace que celles que l'on trouve 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.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 aims 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, both extending previous results from the literature. We study variants and extensions of these problems, when several machines are available or when preemption is not authorized