US331L

Modèles et algorithmes en ordonnancement


2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

Notions de base en algorithmique, complexité et programmation mathématique

Objectifs pédagogiques

Le cours vise à découvrir la théorie de l'ordonnancement à travers l'étude et l'analyse de différents modèles et algorithmes du domaine. Il permet également d'assimiler les concepts fondamentaux à la démonstration des propriétés des méthodes de résolution.

Compétences

  • Connaître les résultats fondamentaux en théorie de l'ordonnancement (complexité, modèles et algorithmes).

  • Savoir identifier les problèmes dans la typologie usuelle en ordonnancement.

  • Savoir analyser la complexité des problèmes d'ordonnancement.

  • Maîtriser les techniques de preuve utilisées en ordonnancement.

Contenu

  • Introduction à l'ordonnancement, critère minmax (problème central, ordonnancement à une machine): Introduction sur la nature des ressources, des contraintes et des critères d'ordonnancement. Présentation de la typologie à 3 champs utilisée en ordonnancement. Etude du problème central ainsi que quelques variantes.

  • Ordonnancement à une machine (critère minsum): Etude de problèmes de base polynomiaux ou difficiles (minimisation des temps de séjours ou des retards). Ouverture sur les problèmes à critère irrégulier (avance-retard).

  • Ordonnancement à machines parallèles: Présentation de quelques problèmes polynomiaux pour certaines classes de problèmes et analyse d'algorithmes de liste.

  • Applications en production: Ordonnancement d'atelier: Analyse de quelques problèmes rencontrés en production tels que les problèmes de flowshop, de jobshop ou le RCPSP.

  • Applications en informatique: Ordonnancement avec délais de communication: Analyse de quelques problèmes rencontrés en informatique tels que les problèmes avec délais de communication ou des problèmes avec contraintes énergétiques.

Modalités de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003