Algorithmes d'approximation sur un problème de planification avec contraintes de connectivité

Nous proposons un nouveau problème de planification avec des contraintes de connectivité. Ce problème définit un graphe connexe Formule : voir le texte, où chaque arête Formule : voir le texte est associée à un temps de traitement Formule : voir le texte et un coût Formule : voir le texte, c'est-à-dire, Formule : voir le texte, où Formule : voir le texte est l'ensemble des nombres réels positifs. L'objectif est de sélectionner un chemin Formule : voir le texte dans Formule : voir le texte pour établir la connectivité entre deux sommets donnés et de programmer en outre les arêtes correspondantes sur Formule : voir le texte machines parallèles pour minimiser la somme du makespan et du coût total. Ce problème est fortement NP-difficile, combinant des éléments de la théorie des graphes et de la planification sur des machines parallèles. Dans cet article, nous nous concentrons sur l'environnement des machines parallèles uniformes, pour lequel nous développons des algorithmes d'approximation et fournissons une analyse du pire cas. Nos résultats contribuent à la théorie de la planification dans l'optimisation combinatoire et offrent de nouvelles perspectives sur la restauration des réseaux sous contraintes de ressources.