Titre : |
La théorie des graphes en ordonnancement d’atelier |
Type de document : |
texte imprimé |
Auteurs : |
Chennaf ,Souad, Auteur ; Benhocine,A, Directeur de thèse |
Editeur : |
Setif:UFA |
Année de publication : |
2018 |
Importance : |
1 vol (56 f .) |
Format : |
29 cm |
Langues : |
Français (fre) Langues originales : Français (fre) |
Catégories : |
Thèses & Mémoires:Mathématique
|
Mots-clés : |
la théorie des graphe
Ordonnancement d’atelier
Contraintes
les graphes sans circuit
Algorithme de Bellman |
Index. décimale : |
510 Mathématique |
Résumé : |
Ce mémoire s’intéresse à l’étude de la théorie des graphes en ordonnancement d’atelier.
La partie théorique est consacrée à la description des problèmes d’ordonnancement à partir de quelques définitions et heuristiques, et la modélisation graphique des différentes contraintes.
Dans la partie pratique, notre attention est portée sur les graphes sans circuit et l’application de l’algorithme de Bellman, sous l’utilisation du logiciel scilab |
Note de contenu : |
Sommaire
Table des matières
Dédicace...................................................................................................................................
Remerciement...........................................................................................................................
Table des matières………………………………………………………………………........
Liste des figures……………………………………………………………………………...
Liste des tableaux…………………………………………………………………………....
Liste des abréviations………………………………………………………………………..
Notation…………………………………………………………………………………...…
Introduction Générale…………………………………………………………………..
Chapitre 1 : Terminologie de la théorie des graphes…………………………...
1.1Introduction………………………………………………………………………………..
1.2 Graphe orienté…………………………………………………………………………….
1.2.1 Les éléments de base d’un graphe orienté…………………………………………….
1.2.2 Notion de degré……………………………………………………………………….
1.3 Graphe non orienté………………………………………………………………………...
1.3.1 Les éléments de base d’un GNO………………………………………………………
1.3.2 Relation entre d+, d-, d, m……………………………………………………………..
1.4 Les différents types d’un graphe………………………………………………………....
1.4.1 Graphe complet……………………………………………………………………….
1.4.2 Graphe biparti…………………………………………………………………………
1.4.3 Graphe pondéré…………………………………………………………………….....
1.4.4 Graphe partiel et sous graphe………………………………………………………....
1.5 Chemin, chaine, cycle, circuit…………………………………………………………...
1.5.1 Chemin, chaine, cycle et circuit hamiltoniens………………………………………..
1.5.2 Chemin, chaine, cycle et circuit euleriens…………………………………………….
1.6 Connexité et forte connexité…………………………………………………………….
1.7 Les graphes sans circuit………………………………………………………………….
1.8 Les graphe avec circuit…………………………………………………………….........
1.9 Représentation des graphes…………………………………………………………......
1.9.1 Liste de succession…………………………………………………………………...
1.9.2 Matrice d’adjacence……………………………………………………………….....
1.9.3 Matrice d’incidence………………………………………………………………......
1.10 Conclusion…………………………………………………………………...................
Chapitre 2 : Les problèmes d’ordonnancement………………………………...
2.1 Introduction………………………………………………………………………………
2.2 Description générale des problèmes d’ordonnancement…………………………………
iv2.2.1 Les tâches…………………………………………………………………………...
2.2.2 Les ressources……………………………………………………………………….
2.2.3 Les contraintes………………………………………………………………………
2.2.4 Les critères………………………………………………………………………….
2.3 Typologie des problèmes d’ordonnancement…………………………………………....
2.3.1 Le problème à une machine unique……………………………………………….....
2.3.2 Les problèmes à machines parallèles…………………………………………...…...
2.3.3 Problème d’atelier multi-machine……………………………………………….......
2.4 Modélisation et représentation du problème d’ordonnancement………………………...
2.4.1 Graphe disjonctif……………………………………………………………………..
2.4.2 Diagramme de Gantt…………………………………………………………………
2.4.3 Les représentations par graphes les ateliers Flow-Shop……………………………...
2.4.4 Les représentations par graphes les ateliers Job-Shop……………………………….
2.4.5 Atelier de type Open- Shop………………………………………………………….
2.5 Les algorithmes en ordonnancement d’atelier …………………………………………..
2.5.1 Ordonnancement de n tâches sur une machine…………………………………........
2.5.2 Ordonnancement de n tâches sur 2 machines, Algorithme de Johnson……………...
2.6 Les heuristiques…………………………………………………………………………..
2.6.1 Les heuristique Flow -Shop…………………………………………………………..
2.6.2 Heuristique de palmer………………………………………………………………..
2.6.3 Heuristique CDS……………………………………………………………………..
2.6.4 Heuristique de Dannenbring…………………………………………………………
2.6.5 Heuristique de NEH…………………………………………………………………
2.7 Algorithme de Bellman………………………………………………………………….
2.7.1 Algorithme de Bellman dans le cas où les niveaux ne sont pas déterminés…………
2.7.2 Algorithme de Bellman dans les cas où les niveaux sont déterminés………………..
2.8 Conclusion……………………………………………………………………………….
Chapitre 3 : Les systèmes de production avec différentes contraintes........
3.1Introduction……………………………………………………………………………….
3.2 Système de production de type Flow Shop………………………………………………
3.2.1 Flow Shop classique…………………………………………………………………..
3.2.2 Flow Shop hybride……………………………………………………………………
3.3 Système de production de type Job Shop………………………………………………...
3.3.1 Job Shop classique……………………………………………………………….........
3.3.2 Job Shop hybride…………………………………………………………………….
3.4 Description des contraintes de blocage…………………………………………………...
3.4.1 Contrainte de blocage de type RSb…………………………………………………..
3.4.2 Contrainte de blocage de type RCb…………………………………………………..
3.5 Job Shop avec contrainte de transport…………………………………………………….
3.5.1 Le problème de Job Shop avec transport et plusieurs robots…………………………
3.5.2 Les différentes contraintes de job-shop avec transport………………………………
3.6 La contrainte no-idle ………………………………………………………………….....
v3.6.1 Présentation de problème Flow Shop Avec contrainte no-idle………………………
3.7 Conclusion……………………………………………………………………………….
Chapitre 4 : Application………………………………………………………………
Conclusion générale …………………………………………………………………………
Références……………………………………………………………………………………
Annexe………………………………………………………………………………………………………………………………………………………………………………..
Résumé……………………………………………………………………………………….
Abstra |
Côte titre : |
MAM/0283 |
En ligne : |
https://drive.google.com/file/d/1offA9QDj19YYBZD4rUZPOr3sA9z3Dsnd/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
La théorie des graphes en ordonnancement d’atelier [texte imprimé] / Chennaf ,Souad, Auteur ; Benhocine,A, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (56 f .) ; 29 cm. Langues : Français ( fre) Langues originales : Français ( fre)
Catégories : |
Thèses & Mémoires:Mathématique
|
Mots-clés : |
la théorie des graphe
Ordonnancement d’atelier
Contraintes
les graphes sans circuit
Algorithme de Bellman |
Index. décimale : |
510 Mathématique |
Résumé : |
Ce mémoire s’intéresse à l’étude de la théorie des graphes en ordonnancement d’atelier.
La partie théorique est consacrée à la description des problèmes d’ordonnancement à partir de quelques définitions et heuristiques, et la modélisation graphique des différentes contraintes.
Dans la partie pratique, notre attention est portée sur les graphes sans circuit et l’application de l’algorithme de Bellman, sous l’utilisation du logiciel scilab |
Note de contenu : |
Sommaire
Table des matières
Dédicace...................................................................................................................................
Remerciement...........................................................................................................................
Table des matières………………………………………………………………………........
Liste des figures……………………………………………………………………………...
Liste des tableaux…………………………………………………………………………....
Liste des abréviations………………………………………………………………………..
Notation…………………………………………………………………………………...…
Introduction Générale…………………………………………………………………..
Chapitre 1 : Terminologie de la théorie des graphes…………………………...
1.1Introduction………………………………………………………………………………..
1.2 Graphe orienté…………………………………………………………………………….
1.2.1 Les éléments de base d’un graphe orienté…………………………………………….
1.2.2 Notion de degré……………………………………………………………………….
1.3 Graphe non orienté………………………………………………………………………...
1.3.1 Les éléments de base d’un GNO………………………………………………………
1.3.2 Relation entre d+, d-, d, m……………………………………………………………..
1.4 Les différents types d’un graphe………………………………………………………....
1.4.1 Graphe complet……………………………………………………………………….
1.4.2 Graphe biparti…………………………………………………………………………
1.4.3 Graphe pondéré…………………………………………………………………….....
1.4.4 Graphe partiel et sous graphe………………………………………………………....
1.5 Chemin, chaine, cycle, circuit…………………………………………………………...
1.5.1 Chemin, chaine, cycle et circuit hamiltoniens………………………………………..
1.5.2 Chemin, chaine, cycle et circuit euleriens…………………………………………….
1.6 Connexité et forte connexité…………………………………………………………….
1.7 Les graphes sans circuit………………………………………………………………….
1.8 Les graphe avec circuit…………………………………………………………….........
1.9 Représentation des graphes…………………………………………………………......
1.9.1 Liste de succession…………………………………………………………………...
1.9.2 Matrice d’adjacence……………………………………………………………….....
1.9.3 Matrice d’incidence………………………………………………………………......
1.10 Conclusion…………………………………………………………………...................
Chapitre 2 : Les problèmes d’ordonnancement………………………………...
2.1 Introduction………………………………………………………………………………
2.2 Description générale des problèmes d’ordonnancement…………………………………
iv2.2.1 Les tâches…………………………………………………………………………...
2.2.2 Les ressources……………………………………………………………………….
2.2.3 Les contraintes………………………………………………………………………
2.2.4 Les critères………………………………………………………………………….
2.3 Typologie des problèmes d’ordonnancement…………………………………………....
2.3.1 Le problème à une machine unique……………………………………………….....
2.3.2 Les problèmes à machines parallèles…………………………………………...…...
2.3.3 Problème d’atelier multi-machine……………………………………………….......
2.4 Modélisation et représentation du problème d’ordonnancement………………………...
2.4.1 Graphe disjonctif……………………………………………………………………..
2.4.2 Diagramme de Gantt…………………………………………………………………
2.4.3 Les représentations par graphes les ateliers Flow-Shop……………………………...
2.4.4 Les représentations par graphes les ateliers Job-Shop……………………………….
2.4.5 Atelier de type Open- Shop………………………………………………………….
2.5 Les algorithmes en ordonnancement d’atelier …………………………………………..
2.5.1 Ordonnancement de n tâches sur une machine…………………………………........
2.5.2 Ordonnancement de n tâches sur 2 machines, Algorithme de Johnson……………...
2.6 Les heuristiques…………………………………………………………………………..
2.6.1 Les heuristique Flow -Shop…………………………………………………………..
2.6.2 Heuristique de palmer………………………………………………………………..
2.6.3 Heuristique CDS……………………………………………………………………..
2.6.4 Heuristique de Dannenbring…………………………………………………………
2.6.5 Heuristique de NEH…………………………………………………………………
2.7 Algorithme de Bellman………………………………………………………………….
2.7.1 Algorithme de Bellman dans le cas où les niveaux ne sont pas déterminés…………
2.7.2 Algorithme de Bellman dans les cas où les niveaux sont déterminés………………..
2.8 Conclusion……………………………………………………………………………….
Chapitre 3 : Les systèmes de production avec différentes contraintes........
3.1Introduction……………………………………………………………………………….
3.2 Système de production de type Flow Shop………………………………………………
3.2.1 Flow Shop classique…………………………………………………………………..
3.2.2 Flow Shop hybride……………………………………………………………………
3.3 Système de production de type Job Shop………………………………………………...
3.3.1 Job Shop classique……………………………………………………………….........
3.3.2 Job Shop hybride…………………………………………………………………….
3.4 Description des contraintes de blocage…………………………………………………...
3.4.1 Contrainte de blocage de type RSb…………………………………………………..
3.4.2 Contrainte de blocage de type RCb…………………………………………………..
3.5 Job Shop avec contrainte de transport…………………………………………………….
3.5.1 Le problème de Job Shop avec transport et plusieurs robots…………………………
3.5.2 Les différentes contraintes de job-shop avec transport………………………………
3.6 La contrainte no-idle ………………………………………………………………….....
v3.6.1 Présentation de problème Flow Shop Avec contrainte no-idle………………………
3.7 Conclusion……………………………………………………………………………….
Chapitre 4 : Application………………………………………………………………
Conclusion générale …………………………………………………………………………
Références……………………………………………………………………………………
Annexe………………………………………………………………………………………………………………………………………………………………………………..
Résumé……………………………………………………………………………………….
Abstra |
Côte titre : |
MAM/0283 |
En ligne : |
https://drive.google.com/file/d/1offA9QDj19YYBZD4rUZPOr3sA9z3Dsnd/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
|