De l'intérêt de l'aléatoire pour les problèmes d'ordonnancements (On Randomness in Scheduling Problems)

Par Fanny Pascual, 16 novembre, 2017

Proposal for an internship under the supervision of:
- <a href="http://www-desir.lip6.fr/~doerr/">Carola Doerr</a>, CNRS researcher at Université Pierre et Marie Curie, Paris 6,
- <a href="https://www.ibisc.fr/~thang/">Thang Nguyen Kim</a>, assistant professor at Université Evry Val d'Essonne, and
- <a href="http://www-poleia.lip6.fr/~pascualf/">Fanny Pascual</a>, assistant professor at Université Pierre et Marie Curie, Paris 6.<br>

<strong>Internship Description </strong>
Scheduling problems deal with the question of how to optimally assign tasks to machines. Common objectives include the expected time needed until all tasks are completed, or the average expected completion time of a task.
Scheduling problems appear almost everywhere in industrial environments, and as such they are subject to extensive research efforts, both in applied and theoretical streams of operations research.

Many practical algorithms are of a randomized nature, i.e., they use probabilistic decisions to guide the allocation of tasks to machines. Randomness plays a central role also in the structure of several scheduling problems, where the instances are often sampled at random, to reflect the uncertainty that practitioners face in real-world scheduling challenges. The role of randomness in scheduling, however, is not very well understood.
The goal of this internship is to shed light on this important question, for a specific problem that we will fix in accordance to the background and the interest of the student.

Potential topics include:
- Advantages of using randomized algorithms over deterministic algorithms in scheduling contexts.
- How to deal with uncertainty in scheduling, e.g., when the lengths of the jobs are not known in advance.
- Online aspects of scheduling: how to deal with jobs that arrive in random order?<br>

<strong>Prerequisites </strong>
The student should have a background in Computer Science or Mathematics. Some basic knowledge about algorithms and probability theory will be needed, but previous experience with randomized algorithms is not required.

The internship will have a focus on mathematical aspects of scheduling problems, but may (depending on the qualification and interest of the intern) also involve some empirical parts, for which some mild background in programming would be useful.<br>

<strong>Additional Information</strong>
Interested students are asked to contact all or at least one of the three supervisors. We will be able to adjust the topic to the background and interest of the student. To this end, we would like to get to know you in person, so that we can have a discussion about the potential focus of your internship.

Lieu
LIP6, UPMC
Encadrant
Fanny Pascual
Co-encadrant
Carola Doerr Thang Nguyen
Fichier descriptif
Tags
Attribué
Non
Année
2018