Algo affectation d'employé à des taches

**ninjaja** · 16/10/2007, 10h10

Bonjours tout le monde.

Je doit trouver pour demain un algo qui permette de trouver le meilleur planning possible pour un type de graphe particulier.

J'ai 4 types de taches différentes (etude, programmation, decoupage, assemblage) et pour chaque tache un type d'employé (Analiste, programmeur, decoupeur, assembleur) et une durée.
Chaque tache à besoin d'un et un seul employé.

Les graphes sont de la forme :
Etude-->Etude1-->Prog11-->Decoup11-->Assemblage1-->Assemblage
_____________-->Prog1a-->Decoup1a-->
_____-->EtudeN-->ProgN1-->DecoupN1-->AssemblageN-->
_____________-->ProgNb-->DecoupNb-->

N,a,b sont des variables en entrée
Le nombre d'employé de chaque type est aussi en entré

Si vous avez une idée, une piste...

édit:
Finalement il sembleré qu'un graph de la forme ci dessous soit suffisant

Etude-->Prog1-->Decoup1-->Assemblage
_____-->ProgN-->DecoupN-->

et aussi que cet algo fait parti des quelques algo non solutionné à ce jour

**pseudocode** · 16/10/2007, 17h21

Envoyé par ninjaja

et aussi que cet algo fait parti des quelques algo non solutionné à ce jour

yes, tout a fait: c'est du "Job Shop Scheduling".

Il y a tout de meme des algo pour résoudre ce genre de problème, meme si la solution optimale n'est pas en temps polynomial.

**ninjaja** · 17/10/2007, 09h37

Merci Pseudocode. Je vais de ce pas me renseigné sur "Job Shop Scheduling"

**FrancisSourd** · 17/10/2007, 11h50

Envoyé par ninjaja

et aussi que cet algo fait parti des quelques algo non solutionné à ce jour

C'est surtout le problème qui est mal résolu. D'après ce que je comprend, c'est surtout du RCPSP (resource constraint project scheduling problem).
Il faudra bien clarifier ton objectif (ce qu'est une bonne solution) et les contraintes d'affectation des employés (est-ce que chaque employé peut faire toutes les tâches?)

**ninjaja** · 17/10/2007, 12h27

Une bonne solution est d'avoir le projet terminé en un minimum de temp.
Que les employé ai le méme temps de travail serai un plus mais ce n'est pas obligatoir.

Chaque employé a un type de tache définie: un analiste peut faire les études, un programmeur peut faire les programations, etc...

**FrancisSourd** · 17/10/2007, 16h17

Si au départ il n'y a qu'un seul Analiste, un seul programmeur, un seul decoupeur, un seul assembleur c'est effectivement un job-shop (même un flow-shop) car on sait déjà qui va faire quoi. S'il y a plusieurs programmeur par exemple, il faut donc affecter les tâches de programmation aux différents programmeurs et cela devient un flow-shop hybride.

**sidahmed** · 17/10/2007, 17h45

Envoyé par ninjaja

Une bonne solution est d'avoir le projet terminé en un minimum de temp.
Que les employé ai le méme temps de travail serai un plus mais ce n'est pas obligatoir.

Chaque employé a un type de tache définie: un analiste peut faire les études, un programmeur peut faire les programations, etc...

Bonsoir,

si je ne me trompe pas, ta fonction objectif à minimiser est bien la durée du projet devant être minimale, notée Cmax (Completion Time) en ordonnancement et gestion de projets.

Je pense que ton problème est de type Open shop et revient à résoudre le système : Om | pij = 1| Cmax où :
m : représente le nombre de poste (analyste, ...),
pij : signifie que le temps opératoire est identique pour tous les postes,
Cmax : la durée du projet à optimiser (cf. à minimaliser).

Les règles d'ordonnancement JLNO-MLNO ou bien MLNO-JLNO donnent une solution optimale !

Bon courage !

Cordialement,
Sidahmed.

**sidahmed** · 18/10/2007, 02h43

Envoyé par ninjaja

Bonjours tout le monde.

Je doit trouver pour demain un algo qui permette de trouver le meilleur planning possible pour un type de graphe particulier.

J'ai 4 types de taches différentes (etude, programmation, decoupage, assemblage) et pour chaque tache un type d'employé (Analiste, programmeur, decoupeur, assembleur) et une durée.
Chaque tache à besoin d'un et un seul employé.

Les graphes sont de la forme :
Etude-->Etude1-->Prog11-->Decoup11-->Assemblage1-->Assemblage
_____________-->Prog1a-->Decoup1a-->
_____-->EtudeN-->ProgN1-->DecoupN1-->AssemblageN-->
_____________-->ProgNb-->DecoupNb-->

N,a,b sont des variables en entrée
Le nombre d'employé de chaque type est aussi en entré

Si vous avez une idée, une piste...

édit:
Finalement il sembleré qu'un graph de la forme ci dessous soit suffisant

Etude-->Prog1-->Decoup1-->Assemblage
_____-->ProgN-->DecoupN-->

et aussi que cet algo fait parti des quelques algo non solutionné à ce jour

Bonjour,

aujourd'hui, je suis de bonne humeur

, donc je pense que nous sommes tous passé à coté du problème, il s'agit d'un simple problème d'affectation dont la résolution est donnée par la méthode Hongroise, des deux mathématiciens hongrois, Eger Vary et König en 1916.

Je te demande juste de me confirmer deux choses :
1 - le nombre de tâches est égal au nombre d'employés,
2 - Chaque tâche est exécutée par un et un seul employé (tu as dit ça, mais je me répète

)
Sinon, cette méthode ne fonctionne pas tout simplement !

J'espère que c'est la solution à ton problème ! En retard, mais bon ... J'ai lu ton message à la va-vite.

Cordialement,
Sidahmed.

**pseudocode** · 18/10/2007, 10h00

Envoyé par sidahmed

Je te demande juste de me confirmer deux choses :
1 - le nombre de tâches est égal au nombre d'employés,
2 - Chaque tâche est exécutée par un et un seul employé (tu as dit ça, mais je me répète

)

hum... ca ne me semble pas très réaliste. Le PO dit:

J'ai 4 types de taches différentes (...) et pour chaque tache un type d'employé (...) et une durée.

Chaque tache à besoin d'un et un seul employé.

**sidahmed** · 18/10/2007, 12h46

Envoyé par pseudocode

hum... ca ne me semble pas très réaliste. Le PO dit:

Franchement là, j'arrive pas à te comprendre : l'auteur du message a dit qu'il disposait de 04 tâches et 04 postes (employeurs), donc où est le problème ? Une simple matrice de coût 4×4 contenant les durées respectives, ensuite application de la recette sus-mentionnée (c'est une vraie recette) et le tour est joué !

À bientôt.

**pseudocode** · 18/10/2007, 14h57

Tel que je vois le problème, cela ressemble a ca:

On dispose de:

1 Analiste, 2 programmeurs, 3 decoupeurs, 2 assembleurs

En on a 2 projets a faire qui sont modelisés par les graphes suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
            -->Prog1-->Decoup1--
          /                      \
        /                          \
Etude1-+------>Prog2-->Decoup2------+-> Assemblage1
        \                          /
          \                      /
            -->Prog3-->Decoup3--
 
 
Etude2-------->Prog4-->Decoup4--------> Assemblage2

Sachant que les les charges par taches (en jour) sont:

Etude1:1j, Etude2:2j
Prog1:3j, Prog2:2j, Prog3:2j, Prog4:1j
Decoup1:1j, Decoup2:2j, Decoup1:3j, Decoup4:2j
Assemblage1:2j, Assemblage2:3j

Le but est de trouver le planning (= sequence + affectations) optimum, c-a-d la plus petite date de fin pour la réalisation des 2 projets.

Envoyé par sidahmed

Franchement là, j'arrive pas à te comprendre : l'auteur du message a dit qu'il disposait de 04 tâches et 04 postes (employeurs), donc où est le problème ? Une simple matrice de coût 4×4 contenant les durées respectives, ensuite application de la recette sus-mentionnée (c'est une vraie recette) et le tour est joué !

Si je comprend bien, tu vas construire une matrice 4x4 comme cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
              | Analiste | programmeur | decoupeur | assembleur |
-----------------------------------------------------------------
etude         |          |             |           |            |
-----------------------------------------------------------------
programmation |          |             |           |            |
-----------------------------------------------------------------
decoupage     |          |             |           |            |
-----------------------------------------------------------------
assemblage    |          |             |           |            |
-----------------------------------------------------------------

Question 1: Que mets tu dans les cases ?
Question 2: comment trouves tu le planning optimum ?

**sidahmed** · 18/10/2007, 15h22

Envoyé par pseudocode

Tel que je vois le problème, cela ressemble a ca:

On dispose de:

1 Analiste, 2 programmeurs, 3 decoupeurs, 2 assembleurs

En on a 2 projets a faire qui sont modelisés par les graphes suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
            -->Prog1-->Decoup1--
          /                      \
        /                          \
Etude1-+------>Prog2-->Decoup2------+-> Assemblage1
        \                          /
          \                      /
            -->Prog3-->Decoup3--
 
 
Etude2-------->Prog4-->Decoup4--------> Assemblage2

Sachant que les les charges par taches (en jour) sont:

Etude1:1j, Etude2:2j
Prog1:3j, Prog2:2j, Prog3:2j, Prog4:1j
Decoup1:1j, Decoup2:2j, Decoup1:3j, Decoup4:2j
Assemblage1:2j, Assemblage2:3j

Le but est de trouver le planning (= sequence + affectations) optimum, c-a-d la plus petite date de fin pour la réalisation des 2 projets.

Si je comprend bien, tu vas construire une matrice 4x4 comme cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
              | Analiste | programmeur | decoupeur | assembleur |
-----------------------------------------------------------------
etude         |          |             |           |            |
-----------------------------------------------------------------
programmation |          |             |           |            |
-----------------------------------------------------------------
decoupage     |          |             |           |            |
-----------------------------------------------------------------
assemblage    |          |             |           |            |
-----------------------------------------------------------------

Question 1: Que mets tu dans les cases ?
Question 2: comment trouves tu le planning optimum ?

Bonjour pseudocode,

je vais lire attentivement et à tête reposée ce que tu vient de le décrire ci-dessus, sinon les réponses à tes deux questions sont :

Réponse 1 :
Remplir la matrice de coût par les durée des tâches.

Réponse 2 :
Énumérer toutes les combinaisons possibles : 4! = 24 affectation et choisir la (les) meilleure(s) qui donne(ent) un coût optimum (minimum).
Si la taille de la matrice >= 10 => 10! affectation => explosion combinatoire, donc on fait recours à la méthode Hongroise qui nous donne gentillement la solution optimale en un temps record, même avec une taille de matrice suffisamment grande !

Cordialement,
Sidahmed.

**sidahmed** · 18/10/2007, 14h08

Envoyé par sidahmed

Je te demande juste de me confirmer deux choses :
1 - le nombre de tâches est égal au nombre d'employés,
2 - Chaque tâche est exécutée par un et un seul employé (tu as dit ça, mais je me répète

)

Logiquement, la deuxième contrainte entraîne la première !

Cordialement,
Sidahmed.

Algo affectation d'employé à des taches

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager