Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
178 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Trouver un roulement pour une équipe

Envoyé par waramiral 
Trouver un roulement pour une équipe
il y a cinq mois
Bonjour,
Pour une application professionnelle, je désirerais trouver une solution afin d’effectuer une rotation de personnel sur un planning.
Les bases sont simples :
- il y a 8 personnes (A,B,C,D,E,F,G et H)
- elles travaillent chaque semaine par groupe de quatre, soit le « Matin », soit le « Soir » (4 le matin et 4 le soir).
Comment faire un roulement par semaine, afin que chaque personne soit autant de fois le Matin et le Soir et qu’elle travaille autant de fois avec chaque personne.
Merci d’avance.



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Avec la covid il vaut mieux garder les mêmes équipes car dans le cas contraire un seul cas positif et tout le personnel doit rester une semaine au minimum à domicile.grinning smiley
Je dis cela en blaguant mais c’est exactement ce qui s’est passé dans mon service où notre chef avait voulu faire ce genre de roulement...



Edité 2 fois. La dernière correction date de il y a cinq mois et a été effectuée par biely.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Déjà, il faut déterminer la longueur du cycle.
L'individu A va être associé à 3 collègues pendant chaque semaine. Et il a 7 collègues. Il faut donc un cycle de 7 semaines, pour qu'il voit le même nombre de fois chacun de ses collègues.
Mais au bout de 7 semaines, on ne peut pas avoir d'équilibre entre les matins et les soirs.
Il faut donc un cycle de 14 semaines.



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par AD.
Re: Trouver un roulement pour une équipe
il y a cinq mois
Bonjour,
Il est en effet nécessaire d'adopter un cycle de deux semaines .
Tu peux, les semaines $a$, organiser les groupes de la manière suivante: $$ \begin{array}{cc} DFGH&&ABCE\\ ACDF&&EGHB\\FHBC&&ADEG\\AEFH&&GBCD\\HCDE&&AFGB\\ AGBC&&BDEF\\ AHBD&& CEFG\\\end{array}

$$ puis, les semaines $b$, en conservant les équipes, permuter les vacations journalières.
Ainsi, pendant chaque période de $14$ jours, chaque individu aura travaillé $7$ fois le matin et $7$ fois l'après-midi, et exactement $6$ fois avec chacun de ses collègues.

Ces sept $"\text{partitions} \:4-4 "$ de l'ensemble $\{A,B,C,D,E,F,G,H\}$ ont été obtenues en faisant subir à la partition $\Big\{\{A,B,C,E\}; \{D,F,G,H\}\Big\}$ six fois la permutation circulaire $B\to C \to D \to E \to F\to G\to H\to B, \quad A \to A.$



Edité 4 fois. La dernière correction date de il y a cinq mois et a été effectuée par LOU16.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Salut.
@waramiral, j'espère que ton personnel augmentera un jour !
D'une manière plus général, pour un personnel de $2n$ individus, il faut adopter un cycle de $2\times\binom{2n - 1}{n - 1}$ jours et adopter la stratégie de @LOU16, sur les deux moitiés du cycle, pour avoir ce que tu veux.

Remarque : si $\binom{2n - 1}{n - 1}$ est pair, on peut adopter un cycle de $\binom{2n - 1}{n - 1}$ jours.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par babsgueye.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Oui, mais Lou16 a choisi une position initiale ({A,B,C,E},{D,F,G,H}) qui n'est pas n'importe laquelle. La recette magique ne marche plus sans cet ingrédient secret.
Re: Trouver un roulement pour une équipe
il y a cinq mois
Note pour l'an prochain : demander à les-mathematiques.net de faire mon colloscope.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
@lourrran, il n'y a aucun élément particulier dans le groupe ; je ne vois alors pas en quoi ce choix initial est important, si on maitrise le raisonnement de @LOU16.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
La mise en place proposée par Lou16 dit :
1ère position '{ABCE},{DFGH}
Bien. Effectivement, si on commençait avec {ABCD},{EFGH}, on voit bien que C serait toujours accompagné soit de B, soit de D ... et quasiment jamais avec G ... problème.

Maintenant, on recommence, mais avec 10 personnes.
A est fixe, et on fait des permutations circulaires entre les 9 autres B -> C -> D -> E -> F -> G -> H -> I -> J -> B
En première position, on va prendre une position inspirée de celle proposée par Lou16 : {ABCEF}{DGHIJ} ou peut-être {ABCFG}{DEHIJ} ? ou bien même {ABCDF}[EGHIJ} ?
Peut-être que les 3 solutions marchent, ou 2, ou une seule, ou peut-être aucune ?
Je n'ai pas vérifié.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
La permutation à faire n'est pas définie à priori. Tu choisis la position initiale d'abord avant de savoir quelle permutation circulaire il faut faire.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Bon, dialogue de sourds, mais ce n'est pas grave, Waramiral a eu sa réponse,
Re: Trouver un roulement pour une équipe
il y a cinq mois
Bonjour,

@Babsgueye,
Lorsque $n=4$ comme dans le cas proposé par l'initiateur de ce fil, on a : $\:\: 2\binom {2n-1}{n-1} = 70$ et je ne vois pas trop de quel cycle de $70$ jours il s'agit.

Les choses ne me paraissent pas si simples et, hormis quelques banalités, je suis pour ma part incapable de généraliser quoi que ce soit.
Pour un personnel dont l'effectif est $2n$, une période de $2k(2n-1), \:\:(k\in \N^*)\:$ journées est nécessaire pour organiser le travail avec les contraintes imposées.
Mais, ainsi que l'a suggéré Lourran, il n'est pas possible, pour toute valeur de $n$, de le faire avec $k=1$ comme il l'a été fait avec $n=4$.

Par exemple, dans le cas où $n=3$, il est impossible d'obtenir un ensemble de $5$ partitions de type $\{\bullet \bullet\bullet\:
|\:\bullet\bullet\; \bullet \}$ de l'ensemble $\mathcal E =\{A,B,C,D,E,F\}$ dans lequel chaque élément de $\mathcal E$ est associé exactement $2$ fois avec tout autre élément de $\mathcal E.$

Une permutation circulaire du type de celle que j'ai effectuée ne fonctionne pas pour $n=5$, mais est réalisable pour $n=6$.


Tout ce que j'ai trouvé d'un peu général, c'est la jolie construction suivante, applicable lorsque $2n -1$ est un nombre premier congru à $3 \mod4.$
$2n-1 =p, \quad \mathcal E = \Z/p\Z \cup\{\infty\},\quad A=\Big\{x^2 \mid x\in \Z/p\Z\Big\}, \quad B= \mathcal E\setminus
A.\qquad \text{Card}\mathcal E =2n, \quad \text{Card}A=\text{Card}B =n.$

Alors l'ensemble $\mathcal P$ des $p =2n-1$ partitions de $\mathcal E$ défini par $\mathcal P:=\Big\{ \{A+t ;B+t\}\mid t\in \Z/p\Z \Big\}$ organise le travail des $2n$ employés pendant $2n-1$ journées, chaque élément de $ \mathcal E$ étant associé exactement $n-1$ fois avec tout autre élément de $\mathcal E.$



Edité 1 fois. La dernière correction date de il y a cinq mois et a été effectuée par LOU16.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Je n'étais pas trop inquiet sur ma compréhension du sujet, mais merci pour cette réponse.
Re: Trouver un roulement pour une équipe
il y a cinq mois
avatar
Bonjour.

En fait ce que j'ai dit à @Lourrran, c'est simplement que quel que soit la partition $4 - 4$ initiale choisie, il correspond une permutation qui engendre un bon résultat (qui vérifie les contraintes). Il suffit de bien noter les positions des différents agents et d'appliquer selon ces positions la méthode que tu as exposée.
C'est dire qu'à la partition $\{(1, 2, 3, 4)\,;\,(5, 6, 7, 8)\}$ correspond une permutation qui engendre un bon résultat, et on peut faire une correspondance bijective quelconque entre $\{1, 2 ,3, 4, 5, 6, 7, 8\}\,\textrm{et}\,\{A, B, C, D, E, F, G, H\}$.
C'est lui dans sa réponse, par incompréhension de ce que je voulais dire et qui est très simple, qui a voulu généraliser pour d'autres valeurs de n. J'ai pas encore assez saisi ton intuition pour m'aventurer dans ce terrain.
J'ai parler de généralisation à n quelconque avec ma méthode, qui est différente de la tienne et certainement plus brutale.
Moi, par exemple dans les cas où $n = 4$, j'ai isolé un agent et j'ai pris chaque combinaison de $3$ agents parmi les $7$ qui restent que j'associe à l'agent isolé pour formé le groupe du matin par exemple, et les $4$ restants le groupe du soir. C'est alors sur que tous les agents se voient autant de fois les uns que les autres ; ça forme les groupes de la première moitié de cycle. Et pour que chaque agent travaille autant de fois le matin que le soir, je permute ces équipes dans la deuxième moitié du cycle, exactement comme tu as fait.
Par exemple pour $n = 3$, (avec $\{A, B, C, D, E, F\}$), ça donne : $$ \begin{array}{cc}
ABC&&DEF\\
ABD&&CEF\\ABE&&CDF\\ABF&&CDE\\ACD&&BEF\\
ACE&&BDF\\ ACF&& BDE\\ ADE&& BCF\\ ADF&& BCE\\ AEF&& BCD\\\end{array}$$
pour la première moitié du cycle (je peux ici permuter n'importe quelle équipe du matin avec l'équipe du soir correspondant).

Il faut peut-être dire sur ma remarque, que si on veut prendre $\binom{2n - 1}{n - 1}$ comme longueur du cycle, le problème n'est pas de suite tout à fait réglé, parce qu'il va falloir encore bien choisir les équipes du matin pour que chaque agent travaille autant de fois le matin que le soir. et je ne vois pas encore de méthode standards pour faire ce choix... Si on multiplie par $2$ ce problème est vite réglé.

Si on reste avec ces seules deux contraintes, la méthode de calcul que je donne peux s'appliquer mème à un nombre d'agents $N$ impair et des équipes du matin et du soir de nombres d'agents $s$ ou $N - s$.

Remarque : Encore plus brutalement on peut considérer toutes les combinaisons de $n$ agents parmi les $2n$. Mais là pour respecter la deuxième contrainte assez facilement, il faut un cycle encore plus long : $2\times\binom{2n}{n}$.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''
Re: Trouver un roulement pour une équipe
il y a quatre mois
Bonjour,

Cette histoire rappelle le problème des 15 écolières ou encore le planning d'équipe qu'on peut fabriquer avec le plan projectif d'ordre 2. Comme toujours la difficulté consiste à prouver l'existence de tels objets.
Même si ces histoires débutent au 19 ème siècle chez les statististiciens anglais qui s'attaquent à des problèmes d'assurance il me semble, encore et comme presque toujours, Euler s'est intéressé à ces questions avec peu de succès, une fois n'est pas coutume. A sa décharge même avec la puissance des ordinateurs on ne sait toujours presque rien sur l'existence de ces objets (on collectionne les cas particuliers, ou alors on obtient des preuves d'existence non constructives via le calcul des probabilités).

Extrait Wikipedia
« Quinze écolières se promènent sept jours de suite par groupes de trois ; il est requis de les grouper par jour de telle sorte que deux écolières ne se promènent jamais deux fois ensemble. »
Une solution que j'ai oubliée utilise de l'arithmétique modulaire.
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Salut.
Ne faut-il pas compléter ton problème de Wikipedia par ''...de telle sorte que deux écolières ne se promènent jamais deux fois ensemble, mais au moins une fois. » ?
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Salut.
J'ai un peu regardé le ''problème des 15 écolières'' de wikipedia dont tu parles. Je note qu'il appartient à des problèmes plus généraux appelés les ''systèmes de Steiner'' et que ce problème particulier est un système triple Steiner noté $S(2, 3, 15)$.
Jai fait un comptage plutôt élémentaire des possibles solutions du problème $S(2, 3, n)$ par analogie au cas particulier $n = 15$.

Pour $n = 15$ je dis que le nombre de triplets convenables est : $$N_{15} = \binom{15}{3} - 2(12 + 2\times 11 + 3\times 10 + 4\times 9 + 5\times 8 + 6\times 7) +13 +1 = 105.

$$ Puis je me suis dit que dans le cas plus général avec $n$ impair : $$N_n = \binom{n}{3} - 2\big((p-3) + 2(p-4) +\cdots +\dfrac{(n-3)(n-2)}{4}\big) + n - 1.

$$ Mais le caractère exponentielle de la manière dont le nombre de possibilités augmente m'intrigue ?
Cordialement.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''



Edité 3 fois. La dernière correction date de il y a trois mois et a été effectuée par babsgueye.
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Les écolières sont au nombre de 15.
Chaque jour l'écolière A se promène avec 2 camarades. Au bout de 7 jours, elle s'est promenée avec 7x2 camarades.
Si les camarades sont nouvelles à chaque fois, s'il n'y a pas de doublon, elle s'est donc promenée avec 14 camarades différentes.

On a donc l'assurance qu'elle s'est promenée au moins une fois avec chacune de ses camarades, puisqu'elles ne sont que 15 en tout.
Et inversement. Si l'écolière A est sortie au moins une fois avec chacune de ses 2 camarades, ceci nous assure qu'elle ne s'est pas promenée 2 fois avec une de ses camarades.

Ces 3 énoncés sont équivalents :
« Quinze écolières se promènent sept jours de suite par groupes de trois ; il est requis de les grouper par jour de telle sorte que deux écolières ne se promènent jamais deux fois ensemble. »
« Quinze écolières se promènent sept jours de suite par groupes de trois ; il est requis de les grouper par jour de telle sorte que chaque écolière se soit promenée au moins une fois avec chacune de ses camarades. »
« Quinze écolières se promènent sept jours de suite par groupes de trois ; il est requis de les grouper par jour de telle sorte que deux écolières ne se promènent jamais deux fois ensemble mais au moins une fois. »
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Je reconnais que je n'avais pas compris sept jour de suite comme une semaine exactement.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
C'est le fait que la page Wikipedia, dise que ''le nombre de possibilité augmente exponentiellement avec $n$'' de telle sorte qu'on passe de 7 possibilités pour $n =15$ à plus de 11 millards pour $ n = 19$ qui 'intrigue.
En plus on dit sur la page que un des critères d'existence de solution est que $n$ divise 3, et ensuite elle donne l'exemple de $n = 19$ qui fait plus de onze milliards de possibilités...

J'ai des doutes sur ce que dit cette page.

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Pour 19 écolières, en groupes de 3, sur n jours , comment choisir n pour que le problème ait au moins une solution ?

En tout, on doit avoir 19*18/2=171 rencontres ; quand A, B et C se promènent ensemble, ça compte comme 3 rencontres (AB, AC et BC)

19 n'est pas un multiple de 3. Chaque jour je peux par exemple faire 6 groupes de 3, et une des écolières est privée de sortie.
J'ai donc 18 rencontres par jour ... et je ne peux pas arriver à 171.

Je peux aussi dire que chaque jour, 5 groupes sortent, et 4 écolières ne sortent pas, mais là encore, je ne peux pas arriver à 171 rencontres.
Idem si chaque jour , 4 groupes sortent.
Par contre, si chaque jour, 3 groupes sortent, alors au bout de 19 jours, j'arrive bien à 171 rencontres. Reste à trouver les bonnes dispositions pour que les autres contraintes soient vérifiées.

Pour moi, pour que le problème ait un sens avec 19 écolières, il faut donc le lire ainsi :
chaque jour 3 groupes de 3 écolières sortent en promenade.
Au bout de 19 jours, on veut que chaque écolière se soit promenée une fois et une seule avec chacune de ses camarades.
Quelle autre interprétation du problème aurait un sens ?

On peut envisager une variante de cette proposition.
Pendant 9 jours, il y a 6 groupes de 3 écolières qui sortent. Et le 10ème jour, il y a 3 groupes de 3 écolières.

En tout cas, avant de compter le nombre de solutions, ou de critiquer le nombre de solutions trouvées par untel ou untel, il faut que le problème soit clairement défini.

Dans ces 2 schémas que je propose on a beaucoup de 'marge de manoeuvre' ; surtout dans la première proposition. Difficile d'estimer si on a plusieurs milliards de solutions, ou même plus ?
Re: Trouver un roulement pour une équipe
il y a quatre mois
avatar
Mais ils ont clairement dit que pour qu'il y ait des solutions il faut que $n$ soit divisible par $3$. C'est du français et on est en maths.
Pourquoi tu veux faire tes propres interprétations ? Pour sauver quoi ?

''Dans un point, il n'y a pas de matière, donc il y a de l'esprit, et que de l'esprit.''
Re: Trouver un roulement pour une équipe
il y a trois mois
avatar
Bonsoir
Pour n = 18 qui est bien un multiple de 3,on trouve 153 triplets, et donc toutes les élèves ne pourront se promener l'un avec l'autre qu'au bout de 9 jours. 9 des élèves verront toute autre pendant les 8 jours, et les 9 autres se verront le neuvième jour.

En fait pour $n = 2p'$ pair j'obtiens la formule :
$N_n = \binom{2p'}{3} - 2\big(\sum_{i=1}^{p'-2}i(2p' - 2 - i)\big) - p'^{2} + 4p' - 2$

Pour ce qui est du nombre de possibilités, je pense qu'il y a erreur lorsqu'elle dit qu'il y en a 7 pour le cas des 15 écolières ou bien j'ai du mal à saisir ce qu'il appelle possibilité. Mais 7 pour n = 15 et des milliards pour n = 19 c'est un peu aberrant.



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par babsgueye.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 148 604, Messages: 1 497 690, Utilisateurs: 28 280.
Notre dernier utilisateur inscrit Section Paloise.


Ce forum
Discussions: 886, Messages: 7 497.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page