Couverture de chemins avec chemins non triviaux minimums et son application à l'ordonnancement flow-shop à deux machines avec un graphe de conflit

Résumé :

La couverture de chemins est un problème bien connu et difficile à résoudre qui consiste à trouver un nombre minimum de chemins disjoints dans un graphe donné pour couvrir tous les sommets. Nous montrons qu'une variante, dans laquelle l'objectif est de minimiser le nombre de chemins de longueur 0, est soluble en temps polynomial. Nous montrons également qu'une autre variante, visant à minimiser le nombre total de chemins de longueur 0 et de longueur 1, est également soluble en temps polynomial. Les deux variantes trouvent des applications dans l'approximation du problème d'ordonnancement de l'atelier de flux à deux machines dans lequel le traitement des tâches a des contraintes qui sont formulées comme un graphe de conflit. Pour les tâches unitaires, nous présentons une approximation 4/3 pour le problème d'ordonnancement avec un graphe de conflit arbitraire, basée sur l'algorithme exact pour la deuxième variante du problème de couverture de chemin ci-dessus. Pour les tâches arbitraires où le graphe de conflit est l'union de deux cliques disjointes, nous présentons un algorithme simple d'approximation 3/2.