University Sétif 1 FERHAT ABBAS Faculty of Sciences
Catégories
Ajouter le résultat dans votre panier Affiner la recherche
Elaboration d’une métaheuristique pour résoudre un problème d’ordonnancement des tâches sur machines parallèles identiques avec périodes d’indisponibilité / Omar Selt
Titre : Elaboration d’une métaheuristique pour résoudre un problème d’ordonnancement des tâches sur machines parallèles identiques avec périodes d’indisponibilité Type de document : texte imprimé Auteurs : Omar Selt, Auteur ; Rachid Zitouni, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (80 f.) Format : 29 cm Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement
Machines paralléles identiques
Périodes d'indisponibilité
Métaheuristique
Recherche tabouIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, nous proposons une nouvelle élaboration polynômiale d’un algorithme
métaheuristique (recherche tabou) pour résoudre un problème d'ordonnancement de tâches
sur machines parallèles identiques avec périodes d’indisponibilité (avec ). Afin de
résoudre ce problème qui est NP-difficile, nous avons proposé une heuristique basée sur le
choix de la machine la plus disponible. Pour améliorer les coûts initiaux obtenus par notre
heuristique, nous avons appliqué une recherche tabou en utilisant d’une part, deux techniques
de voisinage (voisinage par swapping et voisinage par insertion) et d’autre part, une stratégie
de diversification dans le but d'explorer le maximum des régions des solutions admissibles.
Notons que le mouvement de tâches peut être effectué sur une machine ou sur différentes
machines. Le critère de performance pour optimiser ce problème est la somme pondérée des
dates de fin de tâches.Note de contenu : Table des matiËres
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I G…N…RALIT…S SUR LE PROBL»ME DÃORDONNANCEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 GÈnÈralitÈs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 T‚ches . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Ressources . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 CritËre dÃoptimisation rÈguliËre . . . . . . . . . . . . . . 14
1.3.2 CaractÈristiques gÈnÈrales des ordonnancements . . . . 15
1.4 ReprÈsentation des problËmes dÃordonnancement . . . . . . . . 16
1.4.1 Ordonnancement dans les di§Èrents types dÃateliers manufacturiers . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Machine unique . . . . . . . . . . . . . . . . . . . . . . 17
1.4.3 Machines parallËles identiques . . . . . . . . . . . . . . 18
1.4.4 Atelier ‡ cheminement unique (Flow Shop) . . . . . . . 18
1.4.5 Atelier ‡ cheminement multiple (Job Shop) . . . . . . . 19
1.4.6 Notion de dominance . . . . . . . . . . . . . . . . . . . 20
1.5 Quelques notions sur la complexitÈ des problËmes et des algorithmes . . . . . . . . . . . . . . . . . . . . . . 20
II M…THODES DE R…SOLUTION . . . . . . . . . . . . . . . . . 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 MÈthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 MÈthode dÃÈnumÈration complËte . . . . . . . . . . . . 25
2.2.2 MÈthode de programmation dynamique . . . . . . . . . 26
2.2.3 MÈthode par sÈparation et Èvaluation [branch and bound] 26
2.3 MÈthodes approchÈes . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 MÈthodes de voisinage . . . . . . . . . . . . . . . . . . . 33
2.3.2 Algorithmes Èvolutifs . . . . . . . . . . . . . . . . . . . 33
2.3.3 MÈtaheuristique recherche Taboue . . . . . . . . . . . . 38
2.4 MÈthodes hybrides . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1 MÈthode de descente . . . . . . . . . . . . . . . . . . . 44
2.4.2 Recuit simulÈ . . . . . . . . . . . . . . . . . . . . . . . 46
III R…SOLUTION DÃUN PROBL»ME DÃORDONNANCEMENT
SUR MACHINES PARALL»LES IDENTIQUES PAR M…-
TAHEURISTIQUE RECHERCHE TABOUE . . . . . . . . . 49
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 PrÈsentation du problËme (Pg) . . . . . . . . . . . . . . . . . . 52
3.3 Structure de voisinage . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Voisinage par swapping . . . . . . . . . . . . . . . . . . 54
3.3.2 Voisinage par insertion . . . . . . . . . . . . . . . . . . 55
3.4 Structure de la liste Taboue . . . . . . . . . . . . . . . . . . . . 56
3.5 RÈsolution du problËme (Pg) . . . . . . . . . . . . . . . . . . . 58
3.6 Algorithme gÈnÈral pour le problËme (Pg) . . . . . . . . . . . . 60
3.7 Algorithme dÈtaillÈ pour le problËmePn;m_2. . . . . . . . . 62
3.8 Tests numÈriques . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9 Tableau rÈcapitulatif . . . . . . . . . . . . . . . . . . . . . . . 70
3.10 RÈsultats et commentaires . . . . . . . . . . . . . . . . . . . . 74
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Côte titre : DM/0111 En ligne : https://drive.google.com/file/d/1Dp2-fc2P1tLNkZXaIX3LffcKlfuI7wGh/view?usp=shari [...] Format de la ressource électronique : Elaboration d’une métaheuristique pour résoudre un problème d’ordonnancement des tâches sur machines parallèles identiques avec périodes d’indisponibilité [texte imprimé] / Omar Selt, Auteur ; Rachid Zitouni, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (80 f.) ; 29 cm.
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Ordonnancement
Machines paralléles identiques
Périodes d'indisponibilité
Métaheuristique
Recherche tabouIndex. décimale : 510 Mathématique Résumé : Résumé
Dans cette thèse, nous proposons une nouvelle élaboration polynômiale d’un algorithme
métaheuristique (recherche tabou) pour résoudre un problème d'ordonnancement de tâches
sur machines parallèles identiques avec périodes d’indisponibilité (avec ). Afin de
résoudre ce problème qui est NP-difficile, nous avons proposé une heuristique basée sur le
choix de la machine la plus disponible. Pour améliorer les coûts initiaux obtenus par notre
heuristique, nous avons appliqué une recherche tabou en utilisant d’une part, deux techniques
de voisinage (voisinage par swapping et voisinage par insertion) et d’autre part, une stratégie
de diversification dans le but d'explorer le maximum des régions des solutions admissibles.
Notons que le mouvement de tâches peut être effectué sur une machine ou sur différentes
machines. Le critère de performance pour optimiser ce problème est la somme pondérée des
dates de fin de tâches.Note de contenu : Table des matiËres
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I G…N…RALIT…S SUR LE PROBL»ME DÃORDONNANCEMENT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 GÈnÈralitÈs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 T‚ches . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Contraintes . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Ressources . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Objectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.1 CritËre dÃoptimisation rÈguliËre . . . . . . . . . . . . . . 14
1.3.2 CaractÈristiques gÈnÈrales des ordonnancements . . . . 15
1.4 ReprÈsentation des problËmes dÃordonnancement . . . . . . . . 16
1.4.1 Ordonnancement dans les di§Èrents types dÃateliers manufacturiers . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.2 Machine unique . . . . . . . . . . . . . . . . . . . . . . 17
1.4.3 Machines parallËles identiques . . . . . . . . . . . . . . 18
1.4.4 Atelier ‡ cheminement unique (Flow Shop) . . . . . . . 18
1.4.5 Atelier ‡ cheminement multiple (Job Shop) . . . . . . . 19
1.4.6 Notion de dominance . . . . . . . . . . . . . . . . . . . 20
1.5 Quelques notions sur la complexitÈ des problËmes et des algorithmes . . . . . . . . . . . . . . . . . . . . . . 20
II M…THODES DE R…SOLUTION . . . . . . . . . . . . . . . . . 24
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 MÈthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 MÈthode dÃÈnumÈration complËte . . . . . . . . . . . . 25
2.2.2 MÈthode de programmation dynamique . . . . . . . . . 26
2.2.3 MÈthode par sÈparation et Èvaluation [branch and bound] 26
2.3 MÈthodes approchÈes . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 MÈthodes de voisinage . . . . . . . . . . . . . . . . . . . 33
2.3.2 Algorithmes Èvolutifs . . . . . . . . . . . . . . . . . . . 33
2.3.3 MÈtaheuristique recherche Taboue . . . . . . . . . . . . 38
2.4 MÈthodes hybrides . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.1 MÈthode de descente . . . . . . . . . . . . . . . . . . . 44
2.4.2 Recuit simulÈ . . . . . . . . . . . . . . . . . . . . . . . 46
III R…SOLUTION DÃUN PROBL»ME DÃORDONNANCEMENT
SUR MACHINES PARALL»LES IDENTIQUES PAR M…-
TAHEURISTIQUE RECHERCHE TABOUE . . . . . . . . . 49
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 PrÈsentation du problËme (Pg) . . . . . . . . . . . . . . . . . . 52
3.3 Structure de voisinage . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Voisinage par swapping . . . . . . . . . . . . . . . . . . 54
3.3.2 Voisinage par insertion . . . . . . . . . . . . . . . . . . 55
3.4 Structure de la liste Taboue . . . . . . . . . . . . . . . . . . . . 56
3.5 RÈsolution du problËme (Pg) . . . . . . . . . . . . . . . . . . . 58
3.6 Algorithme gÈnÈral pour le problËme (Pg) . . . . . . . . . . . . 60
3.7 Algorithme dÈtaillÈ pour le problËmePn;m_2. . . . . . . . . 62
3.8 Tests numÈriques . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.9 Tableau rÈcapitulatif . . . . . . . . . . . . . . . . . . . . . . . 70
3.10 RÈsultats et commentaires . . . . . . . . . . . . . . . . . . . . 74
Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Côte titre : DM/0111 En ligne : https://drive.google.com/file/d/1Dp2-fc2P1tLNkZXaIX3LffcKlfuI7wGh/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DM/0111 DM/0111 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : Eléments finis en dimension 1et 2 et implémentation en matlab Type de document : texte imprimé Auteurs : Nawel Boudjellal ; Selmani, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (58 f.) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématiques appliquées Côte titre : MAM/0165 En ligne : https://drive.google.com/file/d/13jfMevLh93zB7_9DcC5XU37m9EgpxuF8/view?usp=shari [...] Format de la ressource électronique : Eléments finis en dimension 1et 2 et implémentation en matlab [texte imprimé] / Nawel Boudjellal ; Selmani, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (58 f.).
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Mathématiques appliquées Côte titre : MAM/0165 En ligne : https://drive.google.com/file/d/13jfMevLh93zB7_9DcC5XU37m9EgpxuF8/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0165 MAM/0165 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEnveloppe d'une famille de droites / Moufida Benhanniche
Titre : Enveloppe d'une famille de droites Type de document : texte imprimé Auteurs : Moufida Benhanniche ; Mezaghcha, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (35 f.) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Algèbre et géométrie Côte titre : MAM/0150 Enveloppe d'une famille de droites [texte imprimé] / Moufida Benhanniche ; Mezaghcha, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (35 f.).
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Algèbre et géométrie Côte titre : MAM/0150 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0150 MAM/0150 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Enveloppe d'une famille de droites. Application à l’ellipse Type de document : texte imprimé Auteurs : Daas ,Mouna, Auteur ; Messaoud Hannachi, Directeur de thèse Editeur : Setif:UFA Année de publication : 2019 Importance : 1 vol (32 f .) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : les coniques
Approche non standard
Enveloppe d’une famille des droitesIndex. décimale : 510 Mathématique Résumé :
La présente étude a pour objectif d’étudier les coniques d’une nouvelle manière avec l’analyse non standard.
En principe, on travaille sur l’ellipse et notre étude est décomposée en deux chapitres.
Dans le premier chapitre, on a donné un rappel sur la définition algébrique et géométrique d’une ellipse, les éléments caractéristiques et l’équation réduite de l’ellipse.
Finalement, j’ai conclu cette étude avec un algorithme en C++, qui aide à donner la nature de la conique avec ses éléments caractéristiques.Note de contenu :
Sommaire
Introduction 1
1 Approche classique 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Dé…nition géométrique (par foyer et directrice) . . . . . . . . . . . . . . . 3
1.3 Dé…nition algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Coniques à centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Dé…nition de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 L’équation réduite de l’éllipse . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Les propriétées de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Approche non standard de la théorie des enveloppes 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Enveloppe dÂ’une famille de droites du plan . . . . . . . . . . . . . . . . . 10
2.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Paramétrisation de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Calcul de la courbure en chaque point de lÂ’ellipse . . . . . . . . . . . . . 17
2.6 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Algorithme en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Côte titre : MAM/0358 En ligne : https://drive.google.com/file/d/1UQmreNb7-x20o79CBomSGQzSxy8vQIGO/view?usp=shari [...] Format de la ressource électronique : Enveloppe d'une famille de droites. Application à l’ellipse [texte imprimé] / Daas ,Mouna, Auteur ; Messaoud Hannachi, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (32 f .) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : les coniques
Approche non standard
Enveloppe d’une famille des droitesIndex. décimale : 510 Mathématique Résumé :
La présente étude a pour objectif d’étudier les coniques d’une nouvelle manière avec l’analyse non standard.
En principe, on travaille sur l’ellipse et notre étude est décomposée en deux chapitres.
Dans le premier chapitre, on a donné un rappel sur la définition algébrique et géométrique d’une ellipse, les éléments caractéristiques et l’équation réduite de l’ellipse.
Finalement, j’ai conclu cette étude avec un algorithme en C++, qui aide à donner la nature de la conique avec ses éléments caractéristiques.Note de contenu :
Sommaire
Introduction 1
1 Approche classique 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Dé…nition géométrique (par foyer et directrice) . . . . . . . . . . . . . . . 3
1.3 Dé…nition algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Coniques à centre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Dé…nition de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 L’équation réduite de l’éllipse . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Les propriétées de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Approche non standard de la théorie des enveloppes 10
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Enveloppe dÂ’une famille de droites du plan . . . . . . . . . . . . . . . . . 10
2.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Paramétrisation de l’ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Calcul de la courbure en chaque point de lÂ’ellipse . . . . . . . . . . . . . 17
2.6 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7 Algorithme en C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Côte titre : MAM/0358 En ligne : https://drive.google.com/file/d/1UQmreNb7-x20o79CBomSGQzSxy8vQIGO/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0358 MAM/0358 Mémoire Bibliothéque des sciences Français Disponible
DisponibleEquation aux dérivées partielle déterministes et stochastiques avec opérateurs fractionnaires / DIBBI, Latifa
Titre : Equation aux dérivées partielle déterministes et stochastiques avec opérateurs fractionnaires Type de document : texte imprimé Auteurs : DIBBI, Latifa, Auteur ; L Abbaoui, Directeur de thèse Editeur : Setif:UFA Année de publication : 2006 Importance : 1 vol (53 f.) Format : 29 cm Catégories : Thèses & Mémoires:Mathématique Mots-clés : Equation aux dérivées partielle
Déterministes
Stochastiques
Opérateurs fractionnaires
SFDPEsIndex. décimale : 510 Mathématique Côte titre : DM/0024-0028 Equation aux dérivées partielle déterministes et stochastiques avec opérateurs fractionnaires [texte imprimé] / DIBBI, Latifa, Auteur ; L Abbaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2006 . - 1 vol (53 f.) ; 29 cm.
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Equation aux dérivées partielle
Déterministes
Stochastiques
Opérateurs fractionnaires
SFDPEsIndex. décimale : 510 Mathématique Côte titre : DM/0024-0028 Exemplaires (5)
Code-barres Cote Support Localisation Section Disponibilité DM/0024 DM/0024-0028 Thèse Bibliothéque des sciences Français Disponible
DisponibleDM/0025 DM/0024-0028 Thèse Bibliothéque des sciences Français Disponible
DisponibleDM/0026 DM/0024-0028 Thèse Bibliothéque des sciences Français Disponible
DisponibleDM/0027 DM/0024-0028 Thèse Bibliothéque des sciences Français Disponible
DisponibleDM/0028 DM/0024-0028 Thèse Bibliothéque des sciences Français Disponible
DisponiblePermalinkPermalinkEquation de transport, méthodes de résolution / Abdelouahab Kadem
PermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalinkPermalink