GILLES SIMONIN's website
Research
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.
