Cyril BRIAND

 

 1 - Research interests

2 -Research projects

3 -Enseignement (in french)

 4 -Links


 

Document made with KompoZer

Last update: Sep-2012

 
UPS Briand's publication list
LAAS-CNRS

Cyril Briand
Professor 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

Sorry: no offer available at the moment!

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
J'aime MobiScience !

Go to Top of page