Cyril BRIAND

 

 1 - Research interests

2 -Research projects

3 -Enseignement (in french)

 4 -Links

 

 Based on Nvu version 1.0 - Updated Fev-2012
Document made with Nvu
UPS Briand's publications LAAS-CNRS

Cyril Briand
Associate Professor (HDR) at
 Université Paul Sabatier

Researcher at  LAAS-CNRSMOGISA Group

LAAS-CNRS
7, av. du Colonel Roche
F-31077 Toulouse Cedex 4

mailto       briand_at_ laas.fr telto

    tel :{0} 561 337 818
    fax :{0} 561 336 936




1 Research interests

1.1 Robust scheduling

A schedule is said robust when it gets the capacity to face the disruptions that occur during the schedule implementation while keeping the performance as close to the initial one as possible.

With respect to this definition, a static scheduling method that is able to characterize a set of solutions (instead of a unique one), the worst performance being  bounded, can be said robust since it allows to switch from on solution to another, according to the real time events, while keeping the performance under control.

 A part of the works developed in the  LAAS-CNRS fit in this class of approach. Regarding single machine scheduling  and two-machine flowshop problems, dominance conditions have been put in evidence that allow to characterize a very large set of solutions for those problems. Moreover, the worst performance of this set can be computed in polynomial time with respect to a set of perturbations.

Since the 1st of Juanary 2009, a french ANR project named ROBOCOOP has been launched on the thema of robust and cooperative scheduling. It involves four partners : the MOGISA group of the LAAS-CNRS of TOULOUSE, the LITIS of LE HAVRE,  the LI of TOURS and collaborators from the ILOG-IBM software company located in Paris. The goal of the ROBOCOOP project is twofold. On the one hand, it aims at designing and implementing original cooperative approaches for robust scheduling which can be used in distributed and perturbed environments. On the other hand, it takes an interest in developing a set of evaluation tools, aiming at analyzing the effectiveness of robust scheduling approaches with respect to several robustness indicators. For more details on this project, please visit the web site of ROBOCOOP.

In the context of project scheduling with uncertainties, where activity durations are modelled as intervals, we also took an interest in computing the minimum float of each activity over all duration
scenarios. For solving this NP-hard problem, we established new structural properties of optimal
solutions, as well as a new lower bound, which is used for designing an ecient branch-and-bound procedure. Two original mixed integer programming formulations were also proposed. Computational experimentations have been conducted on a large variety of randomly generated problem instances. The results show that the proposed branch-and-bound procedure is very fast and consistently outperforms the MIP formulations and the path enumeration algorithm (proposed by Dubois et al.).

References



1.2    Resource-Constrained Project Scheduling Problems

Resource Constrained Project Scheduling Problem are quite generic since they take under consideration a large variety of temporal and resource constraints. They belong to the class of combinatorial optimization problems that are very hard to solve and which  concentrate a lot of interest from the scientist community for many years. In 2004, considering the classic RCPSP with precedence constraints, a new O(n3) Schedule Generation Scheme (SGS) was proposed intending to build up near optimal solutions in a reasonnable amount of time. This SGS, named any-order, considers one by one the project activities and insert them inside a partial schedule (using the insertion procedure proposed by C. Artigues) so that the makespan increase is each time optimal. While this new SGS is more complex than other ones, it allows to reach a larger and a more interesting solution space. The problem of inserting an activity in an existing for a RCPSP with minimum and maximum time lags, fundamental for both reactive scheduling and neigborhood search, has also been tackled and proved to be NP-hard. We also design an insertion procedure that works when only minimum time lages are taken into account. This procedure generalizes previouly established results.

References

1.3   Cooperative scheduling

In production or service management,  firms have to cooperate together in order to build up a consistent and efficient global organization. While basic approaches usually assume that all the constraints and data are known and that an efficient organization can be found in a centralized way using specific optimization softwares, cooperative scheduling methods supose that it is unrealistic to do so, and favor a distributed decision approach where decisions and constraints have to be negociated between decision-makers.

In a Supply-Chain context, a method has been proposed that organizes the production process  by a set of cooperations between pairs of actors of the companies network. We study in particular customer/supplier relationship for which the cooperation process concerns the attributes of the orders shared by the customer and the supplier. Using an aggregated production model and constraint propagation mechanisms, a decision-aid tool has been proposed that allows each decision-maker to understand and evaluate the impacts of any decision.

Considering the job shop environment, we also propose a dynamic and distributed scheduling approach.  Each machine manages its own local schedule and the global schedule is obtained by point-to-point negotiations between the various machines. The local schedules are flexible since several alternative job sequences are allowed on each machine. This flexibility is the key feature that allows each resource, on the one hand, to negotiate with the others and, on the other hand, to react to unexpected events. The cooperative approach aims at ensuring the coherence between the local schedules while keeping a given level of flexibility on each resource.

For the classical project scheduling context (PERT), we consider  cooperative projects that involve a set of agents, each one being in charge of a part of the project. Any agent is assumed to be able to control the duration of its activities by leveling, at a given cost, the usage of extra resources. The outcome of an agent depends on his strategy, but also on the strategies of the others and on the satisfaction of the customer, which depends on the project makespan: rewards are offered  in case agents manage to finish the project earlier than expected. For this framework, we analyze the problem of finding strategies that i) are fair and allow to maximize the agents' profit; ii) are stable and allow to minimize the project makespan.

References

1.4   ILP formulations for Single Machine Scheduling Problems


Another important research axis concerns the study of analytical and numerical dominance conditions for the single-machine scheduling problem (SMSP). Using new dominance conditions, we propose a powerful IP formulation that permits to solve SMSP instances having several thousands of jobs. This formulation has been extended to tackle the problem of minimizing the number of tardy jobs.

References

1.5   PhD Offer

Subject                             Solving multiagent combinatorial  optimization problems:
                                          centralized and decentralized approaches

Duration                            September 2012 - September 2015

Deadline for Application   23 March 2012

General context
This thesis is funded by the EDSYS Doctoral School on the basis of a Doctoral contract (from 1374,21€ to 1651,90 € per month net)

How to Apply
Please send a CV, a covering letter, your scores and ranking during the last two years of academic studies, and a letter(s) of recommendation
to briand@laas.fr and huguet@laas.fr.

Description
In many applicative fields, decision processes involve a set of agents; each one having their own decision autonomy and managing their own constraints and objectives. Agents need to cooperate together to fulfil a global objective, providing their local objective is also optimized or, at least, kept close to a given satisfying value. In the literature, such a decision framework is often referred as “multiagent combinatorial optimization”. In the context of multiobjective optimization, seeking a "fair" strategy that satisfies agents' objectives and, which also remains acceptable in a global viewpoint, has been considered in several papers (e.g. [1]). In the context of game theory, some authors also take an interest in finding a stable strategy (Nash equilibrium), which optimizes the global objective (e.g.  [2, 3]), aiming at measuring the so-called price of stability.
The selected applicant will investigate the complexity of such problems for various classical OR problems, and propose centralized or decentralized algorithms for solving them. Concerning decentralized algorithms, he/she will take benefit from some already existing approaches connected to the field of Distributed Constraint Optimization (see [3, 4, 5]).

Required skills
Applicants should have an outstanding academic record and a master’s degree in computer science. They should have good programming skills, an interest in, as well as a good understanding of, Combinatorial Optimization, and should be knowledgeable in at least some of the methods that will be investigated: Constraint Programming, Integer Programming, and Game Theory. Prior knowledge of French is an advantage, although not mandatory.

Working environment
The student will work on this project in collaboration with Marie-José Huguet and Cyril Briand, and more generally with members of the MOGISA group (http://www.laas.fr/MOGISA-EN/) at LAAS. The scientific activities of the group are focused on scheduling, transportation, discrete optimization, and constraint satisfaction.

*References*
1.    Briand C., Lehaux T, “The multi-agent project scheduling problem : the fair share of stress”, 12th International Workshop devoted to Project Management and Scheduling (PMS 2010), Tours (France), 26-28 April 2010. [pdf]
2.    Briand C., Billaut J.-C, “Cooperative project scheduling with controllable processing times: a game theory framework”, Emerging Technologies and Factory Automation (ETFA 2011), Toulouse (France), 5-9 September 2011. [pdf]
3.    Briand, C., Agnetis, A., & Billaut, J.-C. (2011), 'The multiagent project scheduling problem: complexity of finding a minimum-makespan Nash equilibrium', to be presented to the 13th International Conference on Project Management and Scheduling, Leuven, Belgium.[pdf]
4.    Anton Chechetka and Katia Sycara, "An Any-space Algorithm for Distributed Constraint Optimization", Proceedings of AAAI Spring Symposium on Distributed Plan and Schedule Management, March", 2006.
5.    Jonathan Gaudreault, Jean-Marc Frayret, and Gilles Pesant. 2009. Distributed search for supply chain coordination. Comput. Ind. 60, 6 (August 2009), 441-451.
6.    William Yeoh, Ariel Felner, and Sven Koenig. 2008. BnB-ADOPT: an asynchronous branch-and-bound DCOP algorithm. In Proceedings of the 7th International Joint Conference on autonomous agents and multiagent systems - Volume 2 (AAMAS '08), Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 591-598.

2 Research projects

The ECO-INNOVERA Project EASY


The EASY project is concerned by Theme 2: Sustainable industrial processes and products of the Eco-Innovera Platform. It aims at promoting energy-aware practices for internal supply operations management, so enhancing the environmental performances of factories. One objective is to analyze the raw-material flows across the factory, from the warehouses to the assembly lines, focusing on energy consumption aspects. The feeding system of the assembly line of FAGOR Electrodomesticos, Mondragon, Spain, will particularly be studied under this viewpoint. Then, on the basis of a better modeling of the relationships between energy costs and tactical/operational decisions, aided-decision tools will be designed and implemented. These tools will involve simulation and optimization techniques intending to highlight best minimum energy-costing decisions and, beside, to favor energy awareness of decision makers.

 The ANR Project ROBOCOOP


The french ANR project named ROBOCOOP has been launched in 2009 on the theme of robust and cooperative scheduling. It ended in May 2012. It involved four partners : the MOGISA group of the LAAS-CNRS of TOULOUSE, the LITIS of LE HAVRE,  the LI of TOURS and collaborators from the ILOG-IBM software company located in Paris. The goal of the ROBOCOOP project was twofold. On the one hand, it aims at designing and implementing original cooperative approaches for robust scheduling which can be used in distributed and perturbed environments. On the other hand, it takes an interest in developing a set of evaluation tools, aiming at analyzing the effectiveness of robust scheduling approaches with respect to several robustness indicators. For more details on this project, please visit the web site of ROBOCOOP.


3 Enseignement

Formations


Mes enseignements se déroulent à l'Université Paul Sabatier de Toulouse. J'interviens principalement à l'IUP SI et au Master Recherche SAID (Systèmes  Automatique, Informatique et Décisionnels).

 Systèmes à événements discrets


Il s'agit de donner aux étudiants des outils et des méthodes permettant de passer d'une part, d'un cahier des charges (explicitant la commande d'un procédé équipés de capteurs/actionneurs tout-ou-rien) à une modélisation, et d'autre part, de la modélisation à une mise en oeuvre sur support matériel ou logiciel. Les modèles sont ceux des graphes d'états, des Statecharts, Grafcet et Réseaux de Petri. Les techniques de mises en oeuvre synchrones et asynchrones sont abordées. Les supports de réalisation envisagés sont les bascules, les mémoires, les FPGA, les automates programmables industriel, les micro-ordinateurs. 

 Ordonnancement de projet


Il s'agit d'un cours relativement théorique faisant un focus sur les méthodes de gestion des contraintes de ressources et de temps relatives aux tâches d'un projet (ordo RCPSP et Multi-Mode RCPSP). Le critère analysé est la durée du projet. On distingue l’ordonnancement hors ligne, de de l’ordonnancement réactif. Quelques méthodes de prise en compte des incertitudes sont décrites. 

 Optimisation et gestion des flux

Il s'agit de fournir un acquis théorique aux étudiants leur permettant d'appréhender, de formaliser, de modéliser, puis de résoudre les problèmes de gestion industrielle auxquels ils seront confrontés pendant leur thèse. Des techniques d'optimisation (PL,PLNE, PL-01, PD) sont sont étudiés dans ce cadre.  

  Projet de Grande Envergure (PGE) du Master 2 SI

 Le PGE a pour but principal d'illustrer les enseignements sur les systèmes interactifs et les systèmes de commande temps réel à travers la réalisation d'une application ambitieuse. Les étudiants sont autonomes et doivent prendre en charge la réalisation de l'application depuis sa spécification jusqu'à sa livraison effective. Le PGE leur donne donc l'occasion d'expérimenter les techniques de gestion de projet présentées dans la formation et de comprendre leur importance. Il constitue également une expérience humaine forte et enrichissante (pas seulement pour les étudiants!).

   Liens

Somme des entiers, carrés, inverses...
Thèses de Mathématiques
INFORMS OR/MS Resource Collection: Courses
Ressources ROSO en RO
Dictionary of Algorithms and Data Structures
GLPK - GNU Project - Free Software Foundation (FSF)




4 Links

Researchers


Christian Artigues
Philippe Baptiste
Jean-Charles Billaut
Peter Brucker
PhilippeClauss
Evelyne Contejean
Pierre Lopez
Mike Pinedo
Stephen F. Smith
Francis Sourd
Éric Taillard

   Groups

GdR Recherche Opérationnelle 
Sociedad de Estadística e Investigación Operativa
ESTADÍSTICA I INVESTIGACIÓ OPERATIVA
European Coordinating Committee for Artificial Intelligence (ECCAI)
EURO - What is OR?
ASAP Research Group
GOThA

   Misc

Jardiniers de la Lèze
Mon joli cinéma de Labarthe sur Lèze

Go to Top of page