Une méthode hybride pour la résolution du problème d'ordonnancement de tâches multiprocesseur sur deux processeurs dédiés - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année :

Une méthode hybride pour la résolution du problème d'ordonnancement de tâches multiprocesseur sur deux processeurs dédiés

(1) , (1) , (2)
1
2

Résumé

Dans ce résumé, nous avons proposé une stratégie de look-ahead combinée au path-relinking pour résoudre le problème d'ordonnancement de tâches multiprocesseurs sur deux processeurs dédiés. Une instance du problème est constituée de trois sous-ensembles de tâches et de deux processeurs, où certaines tâches peuvent être exécutées soit sur un des processeurs, soit sur les deux processeurs simultanément. Le but du problème est de trouver le meilleur ordre d'exécution de tâches afin de minimiser le temps d'exécution de la dernière tâche. Tout d'abord, la méthode proposée commence par une solution réalisable par une méthode glouton constructive adaptée. Deuxièmement, une série d'opérateurs de recherche locale sont ajoutés afin de conduire le processus de recherche autour d'une série de voisinages. Troisièmement, une première stratégie de diversification basée sur des opérateurs destruction et de reconstruction est appliquée. La deuxième stratégie de diversification/intensification est utilisée pour mettre en évidence la performance de la méthode ; elle incorpore une stratégie de look-ahead combinée avec le path-relinking. Enfin, la performance de la méthode proposée est analysée expérimentalement sur un ensemble d'instances de référence de la littérature, où les résultats fournis sont comparés à ceux obtenus par des méthodes plus récentes disponibles dans la littérature.
Fichier principal
Vignette du fichier
BAATOUT_ROADEF2022_Hifi_version2.pdf (318.75 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03595442 , version 1 (03-03-2022)

Identifiants

  • HAL Id : hal-03595442 , version 1

Citer

Méziane Aïder, Fatma Zohra Baatout, Mhand Hifi. Une méthode hybride pour la résolution du problème d'ordonnancement de tâches multiprocesseur sur deux processeurs dédiés. 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595442⟩
38 Consultations
10 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More