GILLES SIMONIN's website
Research
In the Constraints and Optimisation research group we are concerned with decision-making and problem-solving in all organisations and enterprises within the private and public sectors. We term this the study of decision analytics. In the research strand we consider both predictive and prescriptive approaches to decision analytics. The primary objective of decision analytics is to make better decisions by utilising data. In some sense, the ultimate purpose of all data analytics activity is to inform decision making. This research strand brings together a number of strands and WPs from the fundamental science level, such as scalable and robust optimisation, Bayesian methods, and machine learning. We will develop leading-edge decision analytics technology capable of supporting decision making in settings that are characterised by: independent and strategically self-interested agents; concerns about the impact of decisions on communities, societies and groups; highly stochastic and online real-time settings; and open-ness and constant change.
The postdoctoral position consists in a collaboration between LAAS in Toulouse and the Centre National d'Etudes Spatiales (CNES) on scheduling maneuvers and scientific experiments of the Rosetta/Philae spacecraft. Rosetta is a mission of the European Space Agency (ESA) and will involve the first ever landing on a Comet (67P / Churyumov - Gerasimenko)
The project is concerned with developing algorithms for scheduling the various activities of the lander (Philae) in three phases. First, in the Separation, Descent and Landing (SDL) phase, the lander will be separated from the orbiter module and will land on the surface of the comet. Second, during the First Science Sequence (FSS), the main scientific experiments will be run using the onboard batteries as energy source. This phase should last three to four days, depending on the load of the batteries and on the quality of the schedule. Finally, during the Long Term Science phase, scientific activities will be resumed at a much slower pace, using the lander's own solar panels to partially reload the batteries.
The experiments of the FSS and LTS -- and to some extent the maneuvers of the SDL -- need to be scheduled to satisfy a number of constraints involving the concurrent use of energy (batteries), and of the main CPUs as well as each instrument's memory. Another important constraint concerns the transfer of data and the notion of "visibility", that is, the availability of the orbiter to act as relay to transmit the data back to earth, which depends on its orbit and on the length of a cometal day. A tool developed using Ilog Scheduler and Solver (MOST) is currently used to model this problem and to generate feasible plans. Every instrument, subsystem and experiment has been modeled with this library, and it is therefore possible to verify solutions with a great degree of confidence of its feasibility. However, the complexity of the problem, in particular during the FSS phase, makes it difficult to find solutions in a reasonable time.
My role will be to explore ways of obtaining better solutions quicker, and to develop prototypes to assess the gain. This might be done by improving the model, the propagation algorithms and the search strategies currently employed, or by developing radically new models whose solutions can then be fed back to MOST.
The last couple of years have seen the advent of sub-marine machines like the sub-marine torpedo. This torpedo execute two kind of tasks: acquisition tasks and treatment tasks. The acquisition tasks are equivalent to coupled-tasks, and treatment tasks are equivalent to classical tasks with preemption allowed. The torpedo possess several captors in order to realize the acquisitions, few captors cannot be used in same time because of the interferences. In this way, we introduce a compatibility graph in order to represent the acquisition tasks which can be executed in the same time. The torpedo possess a mono-processor used to execute the different tasks.
In the first part, we introduce the model of the problem, and define the different tasks and their constraints. We discuss on the impact of the compatibility constraint on the general problem. Lastly, we finish this part with a related works on general scheduling theory, on coupled-tasks, and on the different cover problems in the graph theory. In a second part, we give the classification of the different problems according to the parameters of the coupled-tasks. We give several proofs of complexity for specific problem which are at the limit between polynomiality and completeness. For each studied problem, we propose either a optimal solution with an algorithm in polynomial time, or an approximation algorithm with guarantee of performance. For few problems, we study the complexity in details according to specific parameters or different topologies for the compatibility graph. All the long of this part, we try to show the impact of the introduction of the compatibility constraint on the scheduling problem with coupled-tasks.
I have studied the torpedo problem in a point of view more practical with a stochastic study. The model was the following: the acquisition and treatment tasks are send to the torpedo in real-time according to a distribution law. The set of tasks received must be process before a deadline. After this deadline, the tasks must be re-executed periodically. When the set of tasks is not executed in time, the torpedo remove this set and continue to schedule the others sets. The work has consisted in modeling the problem, then in proposing different priority rules in order to obtain different scheduling. Several simulation have made, and a paper in french has been published in ROADEF 2009.
I have also worked on the study in permanent regime for the torpedo problem. The first work has been to model the torpedo problem according to the particular structure of acquisition tasks and the preemptivity of the treatment tasks. This work is in collaboration with Jean-François Pineau.
At last, from my results on vertices cover problem by disjoints paths of length inferior to two, a collaboration with Jean Daligault and Stéphan Thomassé is in process about star packing and K-crowns. A paper is in construction.
