Post-doctoral Research Visit F/m

Le descriptif de l’offre ci-dessous est en Anglais_

**Type de contrat **:CDD

**Niveau de diplôme exigé **:Thèse ou équivalent

**Fonction **:Post-Doctorant

**A propos du centre ou de la direction fonctionnelle**:
The Inria research centre in Lyon is the 9th Inria research centre, formally created in January 2022. It brings together approximately 300 people in 16 research teams and research support services.

Its staff are distributed at this stage on 2 campuses: in Villeurbanne La Doua (Centre / INSA Lyon / UCBL) on the one hand, and Lyon Gerland (ENS de Lyon) on the other.

The Lyon centre is active in the fields of software, distributed and high-performance computing, embedded systems, quantum computing and privacy in the digital world, but also in digital health and computational biology.

**Contexte et atouts du poste**:
**Within the framework of a partnership**:
The study will take place in the scope of the ECLAT laboratory common to CNRS, INRIA, Eviden, Observatoire de la Côte d'Azur, and Observatoire de Paris.

This work will be supervised by Anne Benoit and Frédéric Vivien

**The main aim of this project is **to design of scheduling algorithms and to establish some (in)approximability results.

**Is regular travel foreseen for this post ?**

No

**Mission confiée**:
Radio telescopes can observe astronomical objects 24 hours a day. The Square Kilometre Array (SKA) is an international radio telescope project being built in Australia and South Africa. It is estimated that the peak flow of data from SKA will significantly exceed the processing capabilities of its associated supercomputer (because of budget constraints). Moreover, the storage capacities associated to this supercomputer will only be able to store a day of data (in order of magnitude). However, the flow of data of a radio telescope depends on the observed object (the observation of a close object does not require using all the antennas and, hence, produces a smaller flow of data). A scheduling of observational requests that would interlace observations producing small flows of data with observations producing large flows would enable a better usage of the radio telescope either by minimizing the telescope idle time or by increasing the quality of observations (by enabling the processing of larger flows). Before one starts designing such schedules, one needs to understand the problem of the scheduling of the sole observations, that is, when one ignores the necessary data processing. Because of the specificities of this scheduling problem, almost nothing is known of its complexity and approximability.

An observation request is defined by three values:

- the observation duration;
- the earliest time at which the observation can start;
- the latest time at which the observation can end.

However, an observation request does not contain the day the observation should take place. This is because an observation can happen any day, as long as it is in the defined time window.

We have shown recently that classical approaches such as _Earliest Deadline First_ are not approximation algorithms with constant approximation factors for the observation scheduling problem. However, this result does not mean that there does not exist any approximation algorithms. One can imagine several possibilities:
Astronomical observations are rather long, one hour being a reasonable order of magnitude. The times and lengths of observations are usually expressed using a rather coarse unit of time (for instance 5 or 15 minutes). Let L be the number of time units in a day. Under rather weak hypotheses on scheduling algorithms (like a transposition of the principle of list scheduling), one can show that any ''reasonable'' scheduling algorithm is an L-approximation algorithm. A conjecture is that any ''reasonable'' scheduling algorithm is a log(L)-approximation algorithm.- More generally, recent advances in parametric complexity for scheduling problems with time windows could be used to identify in experimental data which parameters (other than L) have bounded values. The aim would then be to develop new exact or approximated algorithms of parametric complexity. One could study and use the structural characteristics of the time windows and establish dominance properties of optimal algorithms.
- In practice, rather than scheduling together all the observations a radio telescope will have to process in a given amount of time (say, one month), requests are submitted online and the problem is reminiscent of a batch scheduling problem. The produced schedule may contain idle times. Then, when a request is submitted, its owner may not wish their observation to be scheduled as soon as possible but potentially later at a time when the target astronomical object is closer to its zenith (in order to improve the observation quality). One may therefore wish to build schedules which optimize the quality of individual observations. This would require working in close colla