Inscription / Connexion Nouveau Sujet
Des machines et des tâches (graphe)
J'ai un exercice à faire qui me parait assez difficile.
Voici l'énoncé :
Soit T={t1;t2;t3;t4;t5} un ensemble de cinq tâches et M={m1;m2;m3;m4;m5} un ensemble de cinq machines.
L'execution de t1 nécessite l'utilisation des machines m2,m3;m5 ; t2 nécessite l'utilisation de m1 et m2 ; t3 nécessite m2,m3,m5 ; t4 nécessite m2 et m4 et enfin t5 nécessite que la machine m5.
Chaque tâche requiert le même temps d'execution.
Une même machine ne peut être utilisée que pour une seule tâche à la fois.
1)Représenter ces contraintes à l'aide d'un graphe.
2)Utilisez une coloration convenable des sommets de ce graphe pour obtenir une planification des tâches permettant de minimiser le temps total d'exécution
Pourriez vous m'aider si possible pour cet exo s'il vous plait ? :S
Un grand merci d'avance 
Hello,
1)
les sommets du graphe sont les taches et tu relies par une arête les taches qui ne peuvent avoir lieu en même temps.
Cela donne...sauf erreur...
:
2)
tu dois maintenant colorier les sommets de manière que deux sommets adjacents n'aient pas la même couleur, couleur qui représente une plage horaire.
Bon ça je te laisse faire...je te corrigerai...éventuellement ....
Hello littleguy
Effectivement.......on n'est jamais assez concentré...même pour les choses les plus simples 
Bonjour, excusez moi du retard :S.
Merci beaucoup MisterJack & Littleguy . Je ne pensais pas que ca serait aussi simple
Pour la 2), y-a-t-il besoin de justifier le nombre chromatique que l'on va utiliser ? Ou si l'on doit mettre directement les couleurs sans justification ?
Tu peux colorier comme tu veux (en tenant compte des contraintes), mais si tu affirmes que c'est le nombre chromatique tu dois le justifier ...
Pour le "coloriage", cela donne :
Pour t1 : BLEU
Pour t2 et t5 : VERT
Pour t3 : VIOLET
Pour t4 : ROUGE.
Je pense que ca peut aller non ? :S
> Alain063
Il me semble que MisterJack en a tenu compte implicitement : on peut dresser un tableau sur les incompatibilités (si une tâche nécessite l'utilisation "simultanée" de machines) :
On peut y lire que T1 ne peut s'effectuer en même temps que T2 ni de T3 ni de T4 ni de T5
Mais peut-être avons-nous mal interprété le texte
Ca me semble bien oui mais d'autres eleves ont fait un graphe prennant en compte les machines ET les taches, cela m'a donc fait douter sur le coup. Mais je reste sur votre idee
Annuler
connectez vous