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  

Public ISBD 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 tabou Index. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Côte titre : DM/0111 En ligne : https://drive.google.com/file/d/1Dp2-fc2P1tLNkZXaIX3LffcKlfuI7wGh/view?usp=shari [...] Format de la ressource électronique : pdf 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 tabou Index. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 Côte titre : DM/0111 En ligne : https://drive.google.com/file/d/1Dp2-fc2P1tLNkZXaIX3LffcKlfuI7wGh/view?usp=shari [...] Format de la ressource électronique : pdf

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
DM/0111	DM/0111	Thèse	Bibliothéque des sciences	Français	Disponible Disponible

---

1 (1 - 1 / 1)