<  Back to the Polytechnique Montréal portal

Problème d'affectation et d'ordonnancement sur un réseau muni d'une relation de précédence

Tom De Pauw and Benjamin Thomas Smith

Technical Report (1980)

[img] Published Version
Terms of Use: All rights reserved.
Restricted to:
Registered users or access from Polytechnique onlyLog in using your matricule if you are not accessing this document from Polytechnique Montréal's buildings or VPN.

Request a copy
Cite this document: De Pauw, T. & Smith, B. T. (1980). Problème d'affectation et d'ordonnancement sur un réseau muni d'une relation de précédence (Technical Report n° EP-R-80-33).
Show abstract Hide abstract

Abstract

Le problème considéré -- Le problème d'ordonnancement -- La classe des problèmes NP-complets -- Description formelle -- Contraintes d'affectation -- Contraintes de précédence -- Contraintes d'échance -- Contraintes de non-interférence -- Fonction-objectif -- Résolution du problème -- Solution optimale -- Définition du problème PD -- Énoncé du problème PD -- Utilité du problème PD -- Introduction théorique à l'énumératioon ordonnée -- Définitions -- Démonstration -- Aspects pratique des méthodes de résolution -- L'énumération complète -- L'énumération progressive -- L'énumération ordonnée -- L'énumération ordonnée partielle -- Complexité de l'algorithme d'énumération ordonnée partielle -- Résolution du problème PD -- Explosion du réseau -- Influence de la configuration du réseau -- Explosion progressive du réseau -- Principe de l'alogorithme -- Introduction d'une contrainte dans le réseau de précédence -- Complexité de l'algorithme -- Algorithme de chemin le plus long.

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Date Deposited: 15 Apr 2021 15:12
Last Modified: 15 Jul 2021 17:00
PolyPublie URL: https://publications.polymtl.ca/6204/
Document issued by the official publisher
Report number: EP-R-80-33

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only