 Cyril
Briand
Associate Professor (HDR) 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 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
- T. GARAIX, C. ARTIGUES,
C. BRIAND, Fast minimum float computation in activity networks under interval
uncertainty, to be published, Journal of Scheduling, 2012 [pdf]
- 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, 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 fi nish 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
- 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].
-
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].
-
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].
- 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 effi cient
ILP formulation for the single machine scheduling problem "
- RAIRO - Operations
Research, Vol.44, N°1, pp.61-71, 2010 [pdf]
- C. BRIAND, S. OURARI, "Minimizing the number of tardy jobs
for the single machine scheduling problem: MIP-based lower and upper
bounds", submitted to RAIRO - Operations Research, dec 2011 [pdf].
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
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 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
4
Links
Researchers
Groups
Misc
