Équipe : RO - Recherche Opérationnelle

Axes : TMC (👥👥), AID (👥), ASN (👥).

Responsable : Bruno Escoffier Campus Pierre et Marie Curie 26-00/419

Brève présentation

L'équipe de recherche opérationnelle étudie des problèmes d'optimisation combinatoires, avec des applications en ordonnancement, conception de réseaux, mais aussi en lot sizing et la gestion de la chaîne logistique et de production par exemple. Nous approchons les problèmes avec la théorie des jeux algorithmique, des algorithmes d'approximation, des algorithmes en ligne, des algorithmes à paramètre fixé, des algorithmes auto-stabilisant, des heuristiques de recherche, la complexité à boîte noire, la programmation mathématique, des processus de décision markoviens et l'optimisation stochastique. Notre recherche veut faire avancer la théorie et concevoir des solutions pour des problèmes pures ou des applications réelles.

ordonnancement, optimisation combinatoire, recherche opérationnelle, algorithme exact et approché, complexité.

Aucune manisfestation prévue actuellement.

Sélection de publications

Ch. Dürr, F. Guíñez, M. Matamala : “Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography”, SIAM Journal on Discrete Mathematics, vol. 26 (1), pp. 330-352, (ISBN: 0895-4801) [Dürr 2012a]
N. Absi, S. Dauzère‑Pérès, S. Kedad‑Sidhoum, B. Penz, Ch. Rapine : “Lot Sizing with Carbon Emission Constraints”, European Journal of Operational Research, vol. 227 (1), pp. 55-61, (ISBN: 0377-2217) [Absi 2013b]
S. Angelopoulos, P. Schweitzer : “Paging and list update under bijective analysis”, Journal of the ACM (JACM), vol. 60 (2), pp. 7, (ISBN: 0004-5411) [Angelopoulos 2013]
E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis : “On multiprocessor temperature-aware scheduling problems”, Journal of Scheduling, vol. 16 (5), pp. 529-538 [Bampis 2013c]
B. Doerr, C. Doerr, T. Kötzing : “The unbiased black-box complexity of partition is polynomial”, Artificial Intelligence, vol. 216, pp. 12, (Elsevier) [Doerr 2014g]
A. López‑Ortiz, S. Angelopoulos, A. Hamel : “Optimal Scheduling of Contract Algorithms for Anytime Problem-Solving”, Journal of Artificial Intelligence Research, vol. 51, pp. 533-554, (ISBN: 1076-9757) [López-Ortiz 2014]
Y. Seddik, Ch. Gonzales, S. Kedad‑Sidhoum : “Performance guarantees for a scheduling problem with common stepwise job payoffs”, Theoretical Computer Science, vol. 562, pp. 377-394, (ISBN: 0304-3975) [Seddik 2015]
É. Bonnet, B. Escoffier, Vangelis Th. Paschos, É. Tourniaire : “Multi-parameter Analysis for Local Graph Partitioning Problems: Using Greediness for Parameterization”, Algorithmica, vol. 71 (3), pp. 566-580, (ISBN: 0178-4617) [Bonnet 2015b]
É. Bonnet, B. Escoffier, E. Kim, Vangelis Th. Paschos : “On Subexponential and FPT-Time Inapproximability”, Algorithmica, vol. 71 (3), pp. 541-565, (ISBN: 0178-4617) [Bonnet 2015a]
B. Escoffier, J. Monnot, Vangelis Th. Paschos, M. Xiao : “New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set”, Theory of Computing Systems, vol. 56 (2), pp. 330-346, (ISBN: 1432-4350) [Escoffier 2015]
E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis : “From preemptive to non-preemptive speed-scaling scheduling”, Discrete Applied Mathematics, vol. 181, pp. 11-20, (Elsevier), (ISBN: 0166-218X) [Bampis 2015a]
E. Bampis, D. Letsios, G. Lucarelli : “Green scheduling, flows and matchings”, Theoretical Computer Science, vol. 579, pp. 126-136, (Elsevier) [Bampis 2015b]
P. Bendotti, P. Fouilhoux : “Feasibility recovery for the Unit-capacity Constrained Permutation Problem”, Discrete Optimization, vol. Volume 22, Part A, pp. 66-86, (Elsevier) [Bendotti 2016]
B. Doerr, C. Doerr, R. Spoehel, H. Thomas : “Playing Mastermind with Many Colors”, Journal of the ACM (JACM), vol. 63, (ACM) [Doerr 2016d]
S. Angelopoulos, D. Arsenio, Ch. Dürr, A. López‑Ortiz : “Multi-processor Search and Scheduling Problems with Setup Cost”, Theory of Computing Systems, (Springer Verlag) [Angelopoulos 2016d]
P. Bendotti, Ph. Chrétienne, P. Fouilhoux, A. Quilliot : “Anchored reactive and proactive solutions to the CPM-scheduling problem”, European Journal of Operational Research, vol. 261 (1), pp. 67-74, (Elsevier) [Bendotti 2017c]
L. Gourvès, J. Monnot, F. Pascual, D. Vanderpooten : “Bi-objective matchings with the triangle inequality”, Theoretical Computer Science, vol. 670, pp. 1-10, (Elsevier) [Gourvès 2017]
S. Kedad‑Sidhoum, F. Monna, G. Mounié, D. Trystram : “A Family of Scheduling Algorithms for Hybrid Parallel Platforms”, International Journal of Foundations of Computer Science, vol. 29 (1), pp. 63-90 [Kedad-Sidhoum 2018]
A. Carlier, C. Hanen, A. Munier‑Kordon : “The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays”, Journal of Scheduling, pp. 1-9, (Springer Verlag) [Carlier 2017]

Toutes…