Formule à créér

[cheromi]

Bonjour à tous,

Je n'arrive pas à générer une formule et j'ai besoin de votre aide. Voici la problematique ramenée à du concret virtuel pour mieux visualiser.
Imaginons que je sois chef d'une equipe de ligne de production. J'ai 6 postes de travail differents et 6 salaries .
Tous les salaries ne sont pas habilités sur les memes postes. ( certains ne font que le poste 1 et 2, d'autres que le 1 et 4, d'autres les 6 etc)


Il faut trouver une ou plusieurs formules permettant de placer tous les jours chaque salarié afin que chaque poste soit occupé mais egalement en respectant que chaque salarié puisse tourner equitablement sur les postes dont il est habilité.

En vous remerciant

Cheromi

[zorg]

Intéressant comme problème.

Plutôt qu'une formule, il s'agirait de concevoir un algorithme.

A première vue, une simple permuation circulaire ne suffirait-elle pas ?

[cheromi]

Merci de ta reponse

N'etant pas mathematicien du tout, je ne sais pas ce qu'est tout ca :) Si tu peux m'aiguiller

[zorg]

Un algorithme est un programme c'est-à-dire un ensemble de règles qui attribuent à chaque salarié son poste.

Pour la permuation circulaire si par exemple les salariés s1,s2,s3 sont affectés aux postes p1,p2,p3, au tour suivant on aura s2,s3,s1 affecté aux postes p1,p2,p3. On a fait tourner les salariés.

Ici, bien sûr, il faudrait tenir compte des contraintes. Si par exemple s1 ne peut pas aller sur p2 et bien il prend le prochain poste sur lequel il est compétent ie par exemple p3. s2 qui était sur p2 devrait aller sur p3 mais c'est déjà occupé donc il va sur le prochain libre et sur lequel il est compétent ie par exemple p1.


Bon il faut regarder en détails si ça marche.

[cheromi]

Si j'applique en langage informatique ce que tu me dis, je dois passer par des boucles. Cela risque de me generer une lenteur car pour 6 salaries , ca irait mais pour 20... car en plus, en arriavnt au dernier, il n'est pas sur qu'il soit habilité et il faudra remonter les boucles en arriere etc
Au moins c'est deja une solution mais n'y a til pas une maniere mathematique ou informatique plus rapide pour arriver au resultat ?

[zorg]

Je ne suis pas assez compétent en la matière. Mais je crois qu'il faut chercher plutôt de côté de l'informatique théorique que des mathématiques.
Je ne pense pas qu'il y ait une formule toute faite qui puisse attribuer à chaque salarié son poste au jour j.
Je penche plutôt pour un algorithme. Oui en effet ça peut être long.

il faudrait être sûr à l'avance que le problème ait une solution avant de se lancer dans la recherche d'un algorithme. Je viens d'essayer un exemple avec 6 salariés chacun étant compétent sur 2 postes. Ca bloque au premier tour car un salarié se retrouve sans poste....

Dur dur ton problème

[cheromi]

Voila toute l'etendue de mon probleme :)

[zorg]

Si jamais tu as du nouveau sur ton problème, fais nous en part. Ca nous intéresse.

As tu essayé les groupes de discussion fr.sci.maths ?

[cheromi]

Ca y est , jeviens de poser le probleme au groupe
Merci

[petr0]

Désolée pour la fausse joie mais ce n'est pas une réponse :triste: , c'est juste pour te demander de nous faire part de la solution (qui pourrait dans un autre contexte m'intéresser). Par contre, je suis d'accord avec zorg, ce n'est pas une formule mais un algorithme à mon avis.
Tu auras une boucle i sur le numéro du salarié (S(i,j) avec i son numéro et j variant de 1 à 2 contenant le numéro du poste auquel il peut être attribué). Et à l'intérieur deux boucles "if", une pour signifier si oui ou non il peut travailler au poste j et une autre pour savoir si il n'est pas déjà occupé. Dans le cas où le programme n'aboutirait pas il te faut un retour au i=1 et le démarrage avec j=2 (en y réfléchissant bien tu peux faire beaucoup plus compliqué et testé toutes les possibilités).
Et tout ça seulement pour une journée donc après il faut que tu définisses le "partage équitable des postes" de manière plus mathématique.
Tu n'es pas plus avancé, mais bon j'espère t'avoir montré que tu ne trouveras pas le résultat avec des formules. Bonne chance.

[mln]

C'est un problème d'ordonnancement à contraintes de ressources, je n'ai trouver de théorie ou d'algorithme efficace pour ce problème, cependant je vous donne une idée pour un algo possible (?)

classement par ordre décroissant de contraintes et ensuite permuter :
je l'illustre par un exemple.
s1 peut travailler au poste p1 p2 p3 p6. 4 postes possibles
s2 peut travailler au poste p2. 1 poste possible
s3 peut travailler au poste p4 p5. 2 postes possibles
s4 peut travailler au poste p4 p5 . 2 postes possibles
s5 peut travailler au poste p1 p2 p3 p4. 4 postes possibles
s6 peut travailler au poste p2 p4 p5 p6. 4 postes possibles
au poste p1, on peut affecter s1 s5 2salariés possibles
au poste p2, on peut affecter s1 s2 s5 s6 4salariés possibles
au poste p3, on peut affecter s1 s5 2salariés possibles
au poste p4, on peut affecter s3 s4 s5 s6 4salariés possibles
au poste p5, on peut affecter s3 s4 s6 3salariés possibles
au poste p6, on peut affecter s1 s6 2salariés possibles


on classe tout ca par ordre croissant de possiblités:
s2
s3
s4
p3
p6
p5
s1
s5
s6
p2
p4

Chaque salarié ou poste possède une permutation.
Selon le choix du poste ou du salarié dans la permutation, on refait un classement du meme type.

ici s2 = p2
on refait un classement :
s1 peut travailler au poste p1 p3 p6. 3 postes possibles
s3 peut travailler au poste p4 p5. 2 postes possibles
s4 peut travailler au poste p4 p5 . 2 postes possibles
s5 peut travailler au poste p1 p3 p4. 3 postes possibles
s6 peut travailler au poste p4 p5 p6. 3 postes possibles
au poste p1, on peut affecter s1 s5 2salariés possibles
au poste p3, on peut affecter s1 s5 2salariés possibles
au poste p4, on peut affecter s3 s4 s5 s6 4salariés possibles
au poste p5, on peut affecter s3 s4 s6 3salariés possibles
au poste p6, on peut affecter s1 s6 2salariés possibles
le nouveau classement est:
s3
s4
p4
...
- on affecte s3 au poste p4 par exemple
s1 peut travailler au poste p1 p3 p6. 3 postes possibles
s4 peut travailler au poste p5 . 1 postes possibles
s5 peut travailler au poste p1 p3 . 2 postes possibles
s6 peut travailler au poste p5 p6. 3 postes possibles
au poste p1, on peut affecter s1 s5 2salariés possibles
au poste p3, on peut affecter s1 s5 2salariés possibles
au poste p5, on peut affecter s4 s6 2salariés possibles
au poste p6, on peut affecter s1 s6 2salariés possibles

- s4 = p5
s1 peut travailler au poste p1 p3 p6. 3 postes possibles
s5 peut travailler au poste p1 p3 . 2 postes possibles
s6 peut travailler au poste p6. 3 postes possibles
au poste p1, on peut affecter s1 s5 2salariés possibles
au poste p3, on peut affecter s1 s5 2salariés possibles
au poste p6, on peut affecter s1 s6 2salariés possibles

- s6=p6
s1 peut travailler au poste p1 p3. 2 postes possibles
s5 peut travailler au poste p1 p3. 2 postes possibles
au poste p1, on peut affecter s1 s5 2salariés possibles
au poste p3, on peut affecter s1 s5 2salariés possibles
...

et on fait avec toutes les permutations possibles

a mon avis si le système de départ a au moins une solution(cad tout salariés peut etre affecté à un poste. Par exemple le cas s1=p1; s2=p1,p2; s3 =p1,p2 n'est pas possible), cet algorithme recouvrent uniquement toute les combinaisons possibles (cependant je ne l'ai pas démontré) et pourra donner un ordre dans les permutations (cependant il se peut que 1 salarié travaille "2 fois de suite" sur le meme poste, dans certains cas initiaux on ne peut pas faire autrement)

En tout cas, c'est un sujet très intéressant.
J'espère avoir été compréhensible :)

[cheromi]

Pas de probleme, tu as ete tres explicite.
Je vais essayer de realiser mon programme mais le WE etant la, pas avant la semaine prochaine :)
Merci et tres bon WE

[mln]

je te mets un algo pour compter le nombre de combinaison :
A, tableau (1..nbposte, 1..nbsalarié): A(i,j) = 1 si le salarié j peut travailler au poste i, 0 sinon.
nc: entier, nombre de combinaison
p : entier, numéro du poste
combinaison une fonction


nc = combinaison (p, A, nbposte, nbsalarié, nc )
{
Pour(1) j=1..nbsalarié

Si(1) A(p,j) = 1
B=A

Pour(2) i=1..nbposte
B(i,j)=0
finPour(2)

Si(2) (p+1) <= nbposte
nc=combinaison(p+1,B,nbposte,nsalarié,nc)
Sinon(2)
nc = nc+1
fin Si/sinon(2)

fin Si(1)

fin Pour(1)

retourne nc
}

Pour le problème, la fonction se lancerait :

Si nbposte>=1 & nbsalarié>=1
affiche(combinaison(1, A, 6, 6, 0))
fin Si

Pour avoir toutes les combinaisons, il suffit de les stocker au lieu de les compter.
l'algo avec le classement est aussi valable et se construit pareil (il faut juste rajouter le classement qui est tout bete(premier minimum de somme ligne, somme colonne ), retirer la ligne du poste pris par le salarié et la colonne du salarié et les retirer de nbposte et nbsalarié ds la récursion), je pense qu'il est plus rapide quand nbposte, nb de salarié et nb de contraintes sont grands mais c'est pas sur. La différence entre les 2 est qu'un passe seulement par les combinaisons possibles
voili voilou
Bon courage

[cheromi]

Merci Mln, cela fait plaisir de voir qu'il existe une solution :)

J'ai une question sur l'algo.

"Si(1) A(p,j) = 1
B=A"


Je ne vois pas evoluer la valeur de p
A et B seul a quoi correspondent-ils ?

Merci encore

Cheromi

[mln]

Bonjour,
p évolue dans la récursivité:
combinaison((p+1),B,nbposte,nsalarié,nc)

B = A, c'est copier le tableau A dans le tableau B : pour tout i,j, B(i,j) = A(i,j).

Un exemple, pour illustrer ce que fait l'algo
avc nbposte = 3
nbsalarié = 3


nc = combinaison(p=1,A,3,3,0)
{(1)
A(1,1)==1 donc

p+1=23 donc nc=nc+1 = 1
retourne nc
}(3)

A(2,3)==1 donc

p+1=33 donc nc=nc+1 = 2
retourne nc
}(3b)
retourne nc
}(2)
retourne nc
}(1)

nc==2
Bon courage

[cheromi]

Ok, c'est programmé en Dbase III en y ajoutant un tri sur les ecarts de presence des salaries a chaque poste afin de rendre equitable le dispatching journalier. J'ai fait un test avec 14 salariés et 9 postes . Cela peut etre tres rapide si les restrictions sont reduites et tres long pour des restrictions intermediaires. Des qu'une solution est trouvée, j'ai fait arreter les boucles pour afficher la solution. Pour avoir le nombre total de combinaisons possibles, il me suffirait de laisser tourner les boucles jusqu'a la fin.
PROBLEME
Dans le cas ou aucune solution n'est possible, le programme doit tourner jusqu'a la fin. Donc cela fait beaucoup d'attente pour pas de resultats. Comment faire pour savoir, avant de lancer les boucles, qu'au moins une solution est possible?

[mln]

C'est normal que soit long puisque si n salariés peuvent travailler sur n postes, le nombre de combinaison est égale à n!
Une solution pour que pour être a peu près sur qu'il ait une solution, ce serait de classer les lignes de A par nombre décroissant de 0.(dans la fonction principale)

Bon courage