Algorithme de répartion

Bonjour,

Mon objectif est de mettre en place un code qui permettrait une répartition équitable du nombre d’enfants par adulte.

Dans mon exemple, j’ai deux tableaux.

Dans le premier tableau se trouvent des données. On y trouve des personnes intervenant quelques heures par semaine sur différents groupes.

Dans le deuxième tableau, en tenant compte des horaires du premier tableau, les effectifs groupes doivent se répartir au prorata.

J’ai mis en place un code itératif pour simuler la répartition. Vous allez tout de suite constater qu’il est préférable d’être en fin de liste plutôt qu’en début. Gros travail pour les premiers et vacances pour les derniers

J’ai inclus un coefficient de charge en colonne AF qui doit permettre l’allègement de la charge pour certains personnels ciblés. Il doit être pris en considération dans le calcul de répartition.

Si certains d’entre vous ont travaillé sur ce type de problème je suis fortement intéressé de savoir comment vous avez procédé.

Dans mon exemple, cliquez sur le bouton « Repartition » afin d’illustrer mes propos.

Merci pour vos conseils avertis.

ddetp88

Bonjour,

Pour ne pas trop me fatiguer en cette journée consacrée au repos j'ai utilisé ton algo de répartition...

Une solution qui n'évite pas les "vacanciers" : Les lignes sont résolues de manière aléatoire.

Si tout le monde a un coef à 100%, on a un effet d'aubaine pour 2 ou 3 qui seront toujours libres.

On peut y remédier en mettant tout le monde à 0.90 dans ce cas on arrive à "occuper" tout le monde.

Si en plus, il y en a quelques uns à 50% par exemple, il n'y a plus de problème.

S'il y en trop qui ont des coefs réduits il devient difficile de remplir le tableau du 1er coup :

Il faudrait utiliser une variable de contrôle qui déclancherait plusieurs tirages successifs jusqu'à ce que le résultat soit Ok

Je me suis contenté d'une coloration conditionnelle (colonne BM et ligne 7) pour signaler les anomalies : Dans ce cas il suffit de faire un ou plusieurs tirages supplémentaires jusqu'à ce que le résultat soit satisfaisant...

A+

Bonjour Galopin01,

Déjà merci d'avoir étudié mon problème en ce premier jour d'été

Ton idée est intéressante mais comme tu le dis: certains bénéficient d'un effet d'aubaine.

Je ne peux pas me permettre de proposer une répartition aléatoire. Si je lance le code x fois, il faut que le résultat soit toujours le même.

Je vais de mon coté continuer à mener une réflexion. Si tu penses à autre chose ou si d'autres veulent intervenir sur le fil, ils sont les bienvenus.

A te relire,

ddetp88

Je n'ai fait que quelques centaines de test... Il en faudrait bien plus pour maitriser complètement l'imbrication de toutes les conditions.

Ce que j'ai cru comprendre :

La répartition est étroitement dépendante de l'ordre des personnes et plus précisément du ratio :

Nbre de groupes par personne / Quantité d'heures totales par personne (AD)

Plus le ratio est important (classé en ordre décroissant) , plus les risques d'avoir des "vacanciers" est importante.

De plus l'effet coef est négligeable quand le ratio est important. donc on a un "saupoudrage" plus important dans ce cas, -au point de rendre inefficace ta formule de NbrSuivi- (si j'ai bien compris l'intention du coef...)

Si le ratio est classé en ordre croissant, plus les risques d'impossibilités (et l'effet vacanciers) augmentent.

Nota : (De mémoire) le ratio évolue dans une fourchette de 1 à 50 environ ; même avec la méthode aléatoire on n'a que 4% de chance (environ) de trouver une solution satisfaisante (n'excluant personne mais sans saupoudrage excessif...) : je ne vois pas bien comment on y échappe compte tenu que les très petits ratios sont incontournables ! Un personnel qui n'a qu'un groupe possible ira forcément dans ce groupe...

A+

La répartition est étroitement dépendante de l'ordre des personnes et plus précisément du ratio

Dans la réalité, le classement est en fait un classement alphabétique croissant. Le jeu du coefficient, tu as raison, n'est que très peu influant. Pourtant son objectif serait d'atténuer la tache pour certains(es) car très pris(es) par ailleurs.

Encore merci pour ton implication sur ma question.

Ne sait-on jamais peut-être que d'autres auront été confrontés à ce type de réflexion et auront des éléments à communiquer pour nous mettre sur la piste d'une solution.

Bonne journée à toi.

ddetp

Bonjour

On peut découper les petits n'enfants ?

Une proposition je pense équitable.

Je n'ai rien repris de ta méthode. Principe choisi :

Passe 1 :

- chaque personnel présent reçoit un nombre proportionnel à son temps, arrondi à l'entier le plus proche

- chaque personnel présent a au moins 1 enfant

- on note le déficit ou le surplus décimal de chaque personnel

Passe 2 :

- comptage des déficit ou surplus des groupes

Passe 3 :

• on ajuste les groupes : le personnel ayant le plus fort déficit en reçoit 1 de plus (ou l'inverse pour les surplus) et voit son compteur corrigé, on recommence jusqu'à épuisement.
• j'ai conservé toujours mini un enfant (si on peut), on peut modifier.

Il y a quand même un peu d'alea. Si tu as 6 enfants pour 7 personnels, pas de raison que les vacances soient toujours pour le même (groupe 24 par exemple).

Tu l'aurais eu plus tôt sans les pièges qui donnent des prises de tête inutiles :

8 au lieu de 4 en BC5, somme de contrôle qui ne prend pas en compte la dernière ligne.

Regarde si ça va et ce que tu en penses.

eric

PS: j'ai vu le coeff un peu tard.

Essaie de voir pour l'intégrer, ça doit se passer en passe 1.

ouha!

Je travaillais dans ce sens avec les parties décimales mais sans y parvenir pour le moment.

Tu l'aurais eu plus tôt sans les pièges qui donnent des prises de tête inutiles :

8 au lieu de 4 en BC5, somme de contrôle qui ne prend pas en compte la dernière ligne.

Une erreur de ma part mais complétement involontaire tu penses bien! J'en suis désolé

Je vais regarder pour ajouter les coefficients sinon le dernier de la bande avec un suivi de 19 enfants va tomber malade.

MERCI pour cette proposition très cartésienne. C'est du carré! J'apprécie.

ddetp

Re,

Je viens de regarder d'un peu plus prés le résultat de l'algorithme.

J'ai ajouté en colonne BM la somme des enfants suivis.

J'ai ajouté en colonne AD un calcul théorique du nombre d'enfants à suivre en fonction du service hebdomadaire.

Exemple:

pour le professeur n°13 on a donc: 21 heures x 321 enfants / 660 heures soit 9.91 enfants à suivre en colonne AD et on a 19 enfants en colonne BM: résultat de l'algorithme.

Je me perds dans les tableaux (le code) que tu me proposes.

Saurais-tu me dire comment m'approcher au plus près des calculs théoriques? Que faudrait-il modifier au code?

Merci encore du temps que tu accordes à ce casse tête.

ddetp

Je ne vois pas trop comment tu pourrais concilier ça.

Pour répartir les enfants par prof au prorata de leurs heures il faut traiter colonne par colonne.

Tu n'as ton total par prof qu'à la fin, quand toutes les colonnes on été traitées. Trop tard pour influencer.

Et si tu prends en compte pour les profs le total d'heure au lieu des heures par groupe tu pourras avoir 8 élèves pour 1h et 1 pour 5h.

Ceci dit on pourrait imaginer que dans l'ajustement passe 3 tu ajoutes à ceux qui sont en retard sur le théorique et que tu retranches à ceux qui en ont trop. Ca permettra de t'approcher un peu plus du théorique

eric

dans l'ajustement passe 3 tu ajoutes à ceux qui sont en retard sur le théorique

je ne vois pas où il faut agir dans la passe 3

Ce code n'est pas trop prévu pour ça.

Tu rajoutes une contrainte non annoncée au départ, il faut repenser le truc.

Là il va avoir tendance à te ramener toujours vers des groupes corrects, comme un élastique.

Et ne pas oublier que tu travailles avec des entiers. Vouloir jouer avec 0.014254 alors qu'il y a des arrondis n'est pas évident.

eric

Ok, je comprends mais néanmoins je ne me vois pas présenter cette répartition. L’élastique je vais le prendre sur les doigts .

Pas grave, je vais continuer à réfléchir de mon coté. Si tu as une autre idée tu peux faire signe. Elle sera bien accueillie.

MERCI encore à toi et à Galopin01 de m'avoir accordé du temps.

ddetp

Je viens d'avoir une idée...

Ajouter une 4ème passe : par colonne, relever ceux qui ont un écart par rapport au théorique <=1 et >=1 et enlever un enfant pour le donner à l'autre.

Tu s'approcheras un peu plus du théorique sans modifier le total des groupes.

Ca va déséquilibrer le nombre d'enfant/h pour un prof mais bon, faut choisir... Je te conseille de faire un seul échange par colonne, et recommencer si besoin pour minimiser ce déséquilibre.

Je vois bien aussi un arrondi sur le théorique pour augmenter le nombre d'échanges possibles.

Et reste à savoir si mettre 0 enfants est autorisé ou pas.

Pour l'instant je n'ai pas trop le temps mais si ça t'inspire.

eric

Pour ma présentation de lundi prochain et en attendant d'avoir trouvé un algorithme adapté, j'ai fait la quatrième passe manuellement.

En attendant j'ai supprimé tous les codes et j'ai mis une formule en place avec un arrondi.

Ensuite je retouche manuellement.

Tu verras dans le fichier joint, j'ai mis en évidence les retouches. Les cases avec un encadré rouge ont été retouchées (formule supprimée)

Comme tu pourras aussi le constater, certaines cellules encadrées en rouge n'ont plus de valeur. le zéro est donc accepté. En revanche et tu l'as bien compris, le nombre global d'enfants suivis par professeur doit s'approcher du nombre théorique.

La règle à respecter pour se sortir de ce casse tête me conduit à dire que le nombre global doit primer sur le nombre d'élèves suivis par classe.

Exemple pour le professeur 1 dans le fichier joint.

Il suit 9 élèves au total:

2 élèves de 1AEM

2 élèves de 2AEM

5 élèves de 2LOG

Pour rééquilibrage (4ème passe) il pourrait très bien suivre:

1 élève de 1AEM

3 élèves de 2AEM

5 élèves de 2LOG

Pour la 4ème passe, le rééquilibrage, faut-il travailler en colonne ou en ligne? Je ne sais plus

Au plaisir de te relire.

ddetp