Xiechen ZHANG defends his doctoral thesis on Friday December 12th, 2025 at 2 pm, room 334 of the IBGBI building, Évry Paris-Saclay University.
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.
Composition of the doctoral thesis jury
| Jury member | Title | Place of work | Role in the jury |
|---|---|---|---|
| Éric ANGEL | Full Professor | University of Évry Paris-Saclay | Thesis supervisor |
| Christian ARTIGUE | CNRS Research Director | LAAS, University of Toulouse | Reviewer |
| Cristina BAZGAN, LAMSADE | Full Professor | Paris Dauphine University | Examiner |
| Feng CHU | Full Professor | University of Évry Paris-Saclay | Co-supervisor |
| Johanne COHEN | CNRS Research Director | LISN, Paris-Saclay University | Examiner |
| Chistophe DÜRR | CNRS Research Director | LIP6, Sorbonne University | Examiner |
| Imed KACEM, LCOMS | Full Professor | University of Lorraine | Reviewer |
| Damien REGNAULT | Senior Lecturer HDR | University of Évry Paris-Saclay, LISN | Co-supervisor |
- Date: Friday, December 12, 2025, 2 p.m.
- Location: Room 334 of the IBGBI building, Évry Paris-Saclay University.
- Doctoral student: Xiechen ZHANG, Université Évry Paris-Saclay, IBISC AROBAS team
- Thesis supervisors: Eric ANGEL (Professor, University of Évry, IBISC AROBAS team), Thesis supervisor; Feng CHU (Professor, University of Évry, IBISC AROBAS team), Thesis co-supervisor; Damien REGNAULT (Senior Lecturer, University of Évry, IBISC AROBAS team), Thesis co-supervisor
