Discussion :

[Iori Yagami]

Bonjour,
Mon problème est comme suit :
J'ai une machine qui fait un ensemble d'opérations.
Chaque opération requiert un temps bien déterminé.
Chaque opération a une date de début au plus tôt.
J'ai un produit qui doit subir toutes les opérations.

Je voudrais savoir si je peut faire une optimisation d'ordonnancement en utilisant l'algorithme de la colonie de fourmis.
Merci.

[Iori Yagami]

Je crois qu'il s'agit du problème de flowshop
quelqu'un a une idée?

[pseudocode]

Je connais plutot ce problème sous le nom "Job Shop Scheduling".

Il y a un papier sur citeseer qui parle de l'utilisation de colonie de fourmis pour ce problème :

[Iori Yagami]

merci pseudo mais le site est "unvailable" apparemment..

[pseudocode]

merci pseudo mais le site est "unvailable" apparemment..

Oui, ca lui arrive de temps en temps. En attendant, tu peux te faire un peu de bibliographie grace a notre amis Google avec les mots clés "Ant Colony" et "Job Shop Scheduling".

Par exemple : Implementation of an Ant Colony Optimization technique for job shop scheduling problem

[Iori Yagami]

crois moi pseudo, je suis pas venu ici avant de consulter google, c juste que j'ai rien trouvé de pratique, en plus, la plupart des articles sont payants.
cet article parle du Job Shop, et qu'en est il du flow shop?

[CedricMocquillon]

Le problème de flow-shop dans l'absolu ça veut pas dire grand chose... il faut que tu précises ton environnement d'atelier (nombre de machines), les contraintes sur tes tâches (dates de début au plus tôt, contraintes de précédence...) et ton ou tes objectif (date de fin au plus tard du dernier travail, somme pondérée des avances/retard dans le cas de dates de fin souhaitée pour tes tâches...). Dans le cas de plusieurs objectifs, tu dois fixer si tu as un ordre sur ces objectifs (optimisation lexicographique) si tu veux une combinaison linéaire des objectifs ou si tu veux énumérer un front de Pareto.

Un fois que tu as ça, tu auras défini ton problème et tu pourras alors utiliser la notation de Graham ce qui te permettra de retrouver plus facilement des articles dans la littérature.

A titre d'exemple, le problème de flow-shop à deux machines avec minimisation de la date de fin du dernier travail (noté F_2||C_{max}) est polynomial...

Dernier point, tu pourras aller voir sur le site de Peter Brucker, il expose un certain nombre de problèmes avec leur complexité associée et les papiers correspondants.

[pseudocode]

crois moi pseudo, je suis pas venu ici avant de consulter google, c juste que j'ai rien trouvé de pratique, en plus, la plupart des articles sont payants.

hum... Google me trouve pourtant pas mal de choses.

cet article parle du Job Shop, et qu'en est il du flow shop?

Est-tu sur que c'est bien du flow shop (= cheminement unique), parce que ta phrase "J'ai une machine qui fait un ensemble d'opérations" laisse la place au doute.

[Iori Yagami]

Bonsoir,
Je m'excuse pour le retard.

Est-tu sur que c'est bien du flow shop(= cheminement unique), parce que ta phrase "J'ai une machine qui fait un ensemble d'opérations" laisse la place au doute.

oui, tu as raison pseudo. bon, on me demande pour le moment ceci :
une machine qui fait n opérations (i.e 10)
chaque opération a un temps d'exécution
chaque machine a une date d'exécution au plus tôt.
je dois trouver le makespan.

est ce que c'est possible de le retrouver en utilisant l'algorithme de la colonie de fourmis?
Si je suppose que
- les nœuds sont les opérations à effectuer.
- les arcs sont le temps passé entre deux opérations

Pour utiliser l'algorithme de la colonie de fourmis, il faut avoir un tableau à deux dimensions où sont stockés les arcs. Mais dans le cas cité dessus, ça peut pas se faire puisque le temps passé entre l'execution d'une opération i et une autre (i+1), depend de la date de l'execution de (i) qui n'est pas fixe.
J'espère que vous m'avez compris.
des idées?

[pseudocode]

bon, on me demande pour le moment ceci :
une machine qui fait n opérations (i.e 10)
chaque opération a un temps d'exécution
chaque machine a une date d'exécution au plus tôt.
je dois trouver le makespan.

une machine qui fait n opérations ? en meme temps ?

hum... Ta terminologie ne correspond pas a celle en vigueur. Un problème de "job scheduling" se pose habituellement en ces termes:

• Un nombre fini "n" de Jobs
• Chaque Job est composé d'une suite d'Opérations
• Un nombre fini "m" de Machines
• Chaque Machine fait (au plus) une Opération à la fois

Avec des variantes : ordre des opérations, similitude des jobs, contraintes sur les machines, ...

Si tu arrives a poser ton problème en ces termes, ca sera plus facile de trouver dans la littérature un algo qui te convient.

[Iori Yagami]

en meme temps ?

J'ai pas dit en même temps, mais plutot :
chaque opération a une date d'exécution au plutôt. bon, c'est vrai que ça a l'air bizarre, mais je parle de point de vue implémentation : est ce possible ou pas.

il s'agit surement pas de job shop, ni de flowshop. Je dirai un simple problème de voyageur de commerce.
les noeuds sont les opérations.
les arcs sont le temps passé entre le début effectif de l'opération "i" et le debut de l'opération "j".

Qu'est ce que vous en pensez?

[pseudocode]

J'ai pas dit en même temps, mais plutot :
chaque opération a une date d'exécution au plutôt. bon, c'est vrai que ça a l'air bizarre, mais je parle de point de vue implémentation : est ce possible ou pas.

il s'agit surement pas de job shop, ni de flowshop. Je dirai un simple problème de voyageur de commerce.
les noeuds sont les opérations.
les arcs sont le temps passé entre le début effectif de l'opération "i" et le debut de l'opération "j".

Qu'est ce que vous en pensez?

Ah. Effectivement ca ressemble plus à une recherche de "chemin critique". Du coup, je ne sais pas si les colonies fourmis sont la solution optimale. En adaptant un algo comme dijkstra ou A* ca devrait être possible, non ?

[Iori Yagami]

oui surement, mais on me demande d'adapter ACO, et la je me demande si c'est possible ou pas.
Je sais très bien que ACO peut résoudre le problème du voyageur de commerce. Mais ici, vu que la valeur des arcs défini le temps écoulé entre deux opérations (ce qui ne peut être trouvé que dynamiquement), je ne sais pas si c'est faisable ou pas.

[kniza]

slt les amis ,je voudrais savoir s'il existe des applications industrielles pour l'alogorithme des colonies de fourmies ,si oui dans kel site je peux les retrouver? merci

[bipame]

Bonsoir,
Est ce qu'il existe des codes sources en Matlab sur les algorithmes colonies de fourmis ,si oui est ce que vous pouvez me les indiquer, me les envoyer.
merci.