Xiechen ZHANG soutient sa thèse de doctorat le vendredi 12 décembre 2025 à 14h, en salle 334 du bâtiment IBGBI, Université Évry Paris-Saclay.
La séance est également diffusée en ligne, via le lien : A VENIR
Titre: L’optimisation multicritère et stochastique pour l’ordonnancement.
Résumé
L’ordonnancement multi-critères sous incertitude suscite un intérêt croissant dans les milieux académiques et industriels,
en raison de ses nombreuses applications dans le calcul en nuage, la production industrielle et l’efficacité énergétique.
Pourtant, cette thématique demeure peu explorée dans le domaine de l’informatique théorique. La présence simultanée
d’incertitudes et de critères conflictuels soulève une question fondamentale : comment garantir la robustesse des solutions
tout en assurant leur qualité dans des temps de calcul raisonnables ? Cette thèse s’intéresse à trois nouveaux problèmes
stochastiques d’ordonnancement bi-critère, en se concentrant sur des contextes multi-scénarios et des paramètres ne
disposant que d’une information probabiliste partielle.
Dans un premier temps, nous étudions un problème original d’ordonnancement bi-critère sur machines parallèles identiques, où les
temps de traitement des tâches sont modélisés comme des fonctions polynomiales d’un paramètre de scénario continu. Les deux
critères considérés sont le temps total d’achèvement et la durée maximale (makespan). Nous analysons la complexité des cas
mono-critère, proposons un algorithme polynomial exact pour le premier objectif, et concevons un algorithme d’approximation
avec garantie de performance pour le second. Pour le cas bi-critère, nous développons un algorithme 2-approché pour tout
nombre de machines et un algorithme (1 + ϵ)-approché pour un nombre fixe de machines, permettant d’obtenir des ensembles
approximatifs du front de Pareto possible.
Dans un second temps, afin d’améliorer la robustesse de ces ensembles, nous introduisons
la notion d’ensemble efficace multi-scénarios, extension du concept classique de frontière efficace aux contextes incertains.
Nous concevons un algorithme de programmation dynamique itérative muni d’une technique d’élagage renforcée et
démontrons qu’il constitue un FPTAS lorsque le nombre de machines est constant.
Enfin, motivés par les enjeux de durabilité,
nous étudions un problème stochastique bi-critère sur machines parallèles non apparentées sous tarification horaire de l’électricité
(Time-of-Use, ToU), avec des temps de traitement aléatoires partiellement connus. Nous formulons un modèle bi-critère à contraintes de
probabilité (chance-constrained), le transformons en modèles déterministes renforcés par des inégalités valides, puis développons des
algorithmes d’approximation (1 + ϵ) et une méthode de regroupement des intervalles temporels pour réduire leur nombre tout en préservant
la quasi-optimalité.
Composition du jury de thèse/Composition of the doctoral thesis jury
| Membre du jury | Titre | Lieu d’exercice | Fonction dans le jury |
|---|---|---|---|
| Éric ANGEL | Professeur des Universités | Université Évry Paris-Saclay | Directeur de thèse |
| Christian ARTIGUE | , Directeur de Recherche CNRS | LAAS, Université de Toulouse | Rapporteur |
| Cristina BAZGAN, LAMSADE | Professeure des Universités | Université Paris Dauphine | Examinatrice |
| Feng CHU | Professeure des Universités | Université Évry Paris-Saclay, LISN | Co-encadrante de thèse |
| Johanne COHEN | Directrice de Recherche CNRS | LISN, Université Paris-Saclay | Examinatrice |
| Chistophe DÜRR | Directeur de Recherche CNRS | LIP6, Sorbonne Université | Examinateur |
| Imed KACEM, LCOMS | Professeur des Universités | Université de Lorraine | Rapporteur |
| Damien REGNAULT | Maître de Conférences HDR | Université Évry Paris-Saclay, LISN | Co-encadrant de thèse |
Xiechen ZHANG defends his doctoral thesis on Friday December 12th, 2025 at 2 pm, room 334 of the IBGBI building, Évry Paris-Saclay University.
The session is also available online, via the link: ONGOING.
Title: Multi-criteria and stochastic optimization for scheduling problems
Abstract:
Multi-criteria scheduling under uncertainty has attracted increasing interest from academics and practitioners due to its diverse applications,
such as cloud computing, industrial production, and energy efficiency. However, this area remains relatively underexplored in theoretical
computer science. The coexistence of uncertainties and conflicting criteria poses fundamental challenges: how can we ensure the robustness
of solutions while guaranteeing their quality within reasonable computational times? This thesis studies three new bi-criteria stochastic scheduling
problems, focusing particularly on multi-scenario settings and parameters that contain only partial probabilistic information.
First, we study a novel multi-scenario bi-criteria identical parallel machine scheduling problem, where job processing times are polynomial functions
of a continuous scenario parameter. The criteria to simultaneously optimize are the total completion time and the makespan. We analyze the complexity of the
monocriterion cases, propose an exact polynomial-time algorithm for minimizing total completion time, and design an approximation algorithm
with a provable performance guarantee for makespan minimization. For the bi-criteria case, we provide a 2-approximation algorithm for any
number of machines and an (1 + ϵ)- approximation algorithm when the number of machines is fixed to find approximate sets for the possible
Pareto set.
Second, to address the potential low robustness of the possible Pareto set, which may perform well in a few scenarios but poorly
in most, we investigate the computation of the multi-scenario efficient set, an extension of the efficient frontier for multi-criteria problems under
uncertainty. For a refined version of the above problem, we develop an iterative dynamic programming algorithm with an improved pruning
technique and prove that it yields an FPTAS when the number of machines is constant.
Finally, motivated by practical concerns of sustainability, we study stochastic bi-criteria unrelated parallel machine scheduling under time-of-use
(ToU) electricity pricing, where only partial probability information is available for uncertain job processing times. For the problem, we formulate
a chance-constrained bicriteria model, transform it into deterministic models, and reinforce them with valid inequalities. Furthermore, we design
approximation algorithms to compute a (1 + ϵ)-approximate Pareto set and develop a clustering technique for instances with many time intervals,
effectively reducing their number while preserving near-optimality.
- Date : vendredi 12/12/2025, 14h
- Lieu : Salle 334 du bâtiment IBGBI Université Évry Paris-Saclay. La séance est également diffusée en ligne, via le lien : A VENIR
- Doctorant : Xiechen ZHANG, Université Évry Paris-Saclay, IBISC équipe AROBAS
- Direction de thèse : Eric ANGEL (PR Univ. Evry, IBISC équipe AROBAS), Directeur de thèse; Feng CHU (PR Univ. Évry, IBISC équipe AROBAS), co-encadrante de thèse), Damien REGNAULT (MCF HDR Univ. Évry, IBISC équipe AROBAS), co-encadrant de thèse
