Discussion :

[CedricMocquillon]

Bonjour à tous,

J'ai un problème algorithmique qui peut s'enoncer comme un problème de production: j'ai n tâches à exéctuer sur m machines (m=n). Chaque tâche a une date de début et une date de fin connue. Mon but est de les affecter aux machines de sorte à minimiser le nombre de machines utilisées. Mon algo actuel consite à trier les tâches par date de début d'exécution croissante et à les placer sur la machine compatible (qui est disponible avant la date de début de la tâche courante) disponible au plus tard. J'ai l'impression que ce problème est polynomial mais je n'arrive pas à le ramener à un problème "classique". Si vous avez des idées de pistes... je suis preneur

[pseudocode]

A mon avis, ton problème doit être un "Job Shop Scheduling" mais de la manière dont tu l'as expliqué, je ne comprend pas: si les dates de début et de fin des tâches sont imposées, je ne vois pas trop comment on peut minimiser quoi que ce soit.

[CedricMocquillon]

Justement, le truc c'est qu'ici je ne cherche pas à minimiser la date de fin de la dernière tâche mais le nombre de machines utilisées: si par exemple j'ai n tâches unitaires telles que la tâche i se commence en i et se termine en i+1, je peux très bien décider d'affecter chaque tâche à chaque machine (j'ai donc utilisé n machines) mais dans mon cas je préfèrerais qu'elles soient toutes affectées à la première machine (j'aurais donc utilisé une seule machine). Avec cet exemple c'est effectivement possible de toutes les affecter à la machine 1 mais si j'ai une tâche k qui commence en k et se termine en k+3, je serai alors obligé d'utiliser deux machines. Et je voudrais donc déterminer un algo optimal (si le problème est polynomial ou pseudo-polynomial) ou alors une bonne heuristique (si le problème est NP-difficile) pour le cas général où on connait pour chaque tâche sa date de début et sa date de fin.

[pseudocode]

... Je comprend toujours pas.

Si la date de début de la tâche est est imposée, il faut nécessairement affecter cette tâche à une machine disponible. N'importe laquelle.

[CedricMocquillon]

Ben... non... pas n'importe laquelle, je pense qu'un exemple vaut mieux qu'un long discours:
n = 3 (le nombre de tâches)
T1 [0,1], T2 [1,2], T3[2,3] (les dates de début et de fin des tâches)
Première possibilité d'affectation:
M1 |[T1][T2][T3]
M2 |___________
M3 |___________
Nombre de machines utilisées : 1

Deuxième possibilité d'affectation:
M1 |[T1]________
M2 |____[T2]____
M3 |________[T3]
Nombre de machines utilisées : 3

Donc il faut pas affecter une tâche à n'importe quelle machine puisque je veux minimiser le nombre de machines utilisées (et donc avec l'exemple être dans le cas de la première possibilité). Voilà, je sais pas si c'est plus clair maintenant. En fait il faudrait donc un algorithme pour le cas général et si possible que j'arrive à identifier quel type de problème c'est (genre si j'arrive à dire "c'est un problème de recherche de plus court chemin dans un graphe" c'est cool c'est polynomial ou encore "c'est un problème de sac à dos" bon c'est moins cool c'est pseudo polynomial ou enfin "c'est un problème de voyageur de commerce" et là c'est NP-Difficile mais au moins j'aurais accès à de bonnes heuristiques)

[pseudocode]

Ahhhhh.... je comprend mieux.

Tu veux minimiser le nombre de machines différentes nécessaires au scheduling.

Dans ce cas, au lieu de prendre "n'importe quelle" machine, il faut prendre en priorité celles qui ont déjà été utilisées. non ?