Cyril Briand Assistant Professor at Université Paul Sabatier Researcher at LAAS-CNRS - MOGISA Group LAAS-CNRS 7, av. du Colonel Roche F-31077 Toulouse Cedex 4
briand_at_ laas.fr	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 which is able to characterize a priori a set of solutions (instead of a unique one) having a known worst performance is robust, since it allows to switch from on solution to another, according to the real time events, while keeping the performance under control. The works developed in LAAS-CNRS fit in this class of approach. Regarding single machine scheduling problem 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 given 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.

References

C. BRIAND, H.T. LA, J. ERSCHLER « A robust approach for the single machine scheduling problem », Journal of Scheduling,Vol. 10, No. 3, pp.209-221, 2007 [pdf].
C. BRIAND, H.T. LA, J. ERSCHLER « A new sufficient condition of optimality for the two-machine flowshop problem » , European Journal of Operational Research, 169 pp 712-722, 2006 [pdf].
H.T. LA, J.-L. SANTAMARIA, C. BRIAND "Une aide à la décision pour l'ordonnancement robuste en contexte mono-ressource : un compromis flexibilité/performance, 6ème Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'05), Tours (France), 14-16 Février 2005, pp 101-116. [pdf]

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(n³) 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

C. BRIAND , " A new Any-Order schedule generation scheme for resourceconstrained project scheduling " - RAIRO - Operations Research, Vol. 43 No. 3, pp 297-308, 2009 [pdf].
C. ARTIGUES, C. BRIAND , " The resource-constrained activity insertion problem with minimum and maximum time lags " - Journal of Scheduling, Vol. 12, No 5, pp 447-460, 2009 [pdf].

1.3 Cooperative scheduling

In production or service management, it is required that firms 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.

References

E. DESPONTIN, C.BRIAND, P. ESQUIROL « Aide à la décision pour une coopération interentreprise» - Journal Européen des Systèmes Automatisés, 39/2005, pp 797-816 [pdf]
C. BRIAND, S. OURARI, B. BOUZOUIA, "A cooperative approach for job shop scheduling under uncertainties", International Conference on Collaborative Decision Making (CDM'08), Toulouse (France), 1-4 juillet 2008, p5-15 [pdf].

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

C. BRIAND, S. OURARI, B. BOUZOUIA , " An efficient ILP formulation for the single machine scheduling problem " - RAIRO - Operations Research, à paraître en 2010 [pdf]
S. OURARI, C. BRIAND, B. BOUZOUIA, "A mathematical programming approach to minimize the number of late jobs for the single machine scheduling problem", in revision for the Journal of Mathematical Modelling and Algorithms, mai 2009 [pdf].

2 Enseignement

2.1 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).

2.2 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.

2.3 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.

2.4 Méthodes et modèles pour l'aide à la décision

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.

2.5 Projet de Grande Envergure (PGE) de l'IUP 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!).