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(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
- 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!).
1.6
Liens
3
Links
3.1 Researchers
3.2
Groups
3.3
Misc
