Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques AutreForum traitant des mathématiques, un peu moins scolaires AlgorithmiqueForum consacré aux algorithme [tout]Lister tous les topics de mathématiques
Niveau algorithmique
Partager :

Définition d'un nombre de tâches maximal

Posté par
Tochiro 02-02-13 à 15:52

Bonjour à tous

Je m'oriente vers ce forum après avoir tenté ma chance sans succès sur un forum spécialisé Excel. Le fond du problème étant de définir un algorithme, je m'oriente donc maintenant vers des "matheux" pour essayer de résoudre mon problème que voici:

J'ai réalisé un outil sous Excel me permettant de visualiser un plan de charges. Maintenant, je voudrais y ajouter un indicateur me permettant de dire, en fonction de tâches déjà planifiées, si je peux accepter tel ou tel type de tâche supplémentaire.

Pour chaque type de tâche, que j'appelle TA (tâche A), TB, TC, TD, etc... il me faut à chaque fois un chef d'équipe et deux équipiers. Jusque là, rien de compliqué.

Seulement, les personnels sont formés à plusieurs types de tâches, et là ça se complique pour moi ! Je n'affecte pas les personnels aux tâches, mais j'ai leur planning de présence à partir duquel je dois seulement savoir si je peux demander l'exécution de tâches supplémentaires.

Dans mon "tableau" ci-dessous, j'ai une liste de personnels et leurs compétences appelées CE (chef d'équipe) ou E (équipier):

-------------Tâche A------------Tâche B---------Tâche C-------Tâche D
Mr A---------   E   --------------------------------   CE  -------------------
Mr B----------------------------   CE  -------------   E   -------   E  ------
Mr C--------    E   ----------------------------------------------   E  ------
Mr D----------------------------    E  -----------------------------------
Mr E----------------------------   CE  ----------------------------  E   -----
Mr F--------   CE   ---------------------------------   CE   -------  E   -----
Mr G--------    E   ---------------------------------   CE   -------  CE  -----
Mr H--------   CE   ------------    E  --------------    E   -------  CE  -----
Mr I--------    E   ------------    E  --------------    E   ------------------

Autant il est simple "sur papier" de définir si, par exemple, à telle date j'ai déjà 1 tâche B et 1 tâche C de planifiées, est-ce que je peux ajouter une tâche D et une tâche E, autant trouver un algorithme permettant de lé définir me semble compliqué.

Mes souvenirs de maths sont loin, déjà que je n'excellais pas :-p

Je fais donc appel à vous pour m'orienter vers un algorithme qui puisse définir à un moment donné, quels quantité de tâches on peut planifier en même temps en fonction des personnels présents.

J'espère que mon problème est bien défini.

Merci d'avance de vos contributions.

Posté par
Tochirore : Définition d'un nombre de tâches maximal 02-02-13 à 16:26

Je suppose que l'utilisation de dénombrement et proba devrait aider, mais comment...

Posté par
Surbre : Définition d'un nombre de tâches maximal 03-02-13 à 18:30

Bonjour,

Est-ce qu'il est possible pour une personne d'effectuer plusieurs tâches en même temps?

J'imagine qu'un chef d'équipe peut aussi jouer le rôle d'équipier en cas de besoins.

Par exemple, si messieurs F,G et H sont présents. Peut-on dire qu'alors ils effectuent les tâches A,C et D.

Quand on parle de "quantité de tâches", qu'est-ce que ça veut dire? C'est combien de fois une tâche est accomplie (mais ça pourrait être 18 fois la même) ou combien de tâches différentes peuvent être accomplies?

Est-ce qu'on pourrait reformuler le but de l'algorithme comme suit:
Sachant exactement qui est là, trouver toutes les tâches différentes qu'il est possibles de faire.
Si c'est le cas, alors l'algorithme est très simple. Sinon j'ai pas tout compris...

Posté par
Tochirore : Définition d'un nombre de tâches maximal 03-02-13 à 19:23

Bonsoir,

Pour répondre à ces questions:

- une personne ne peut pas être affectée à plusieurs tâches en même temps;
- un chef d'équipe peut être employé comme équipier pour une tâche sur laquelle il est qualifié chef d'équipe;
- la quantité de tâche est le nombre total de tâches simultanées, sachant que celles-ci ne sont pas forcément différentes les unes des autres, ça pourrait être 3 tâches A, comme une tâche A, une B et une C;

Citation :
Est-ce qu'on pourrait reformuler le but de l'algorithme comme suit:
Sachant exactement qui est là, trouver toutes les tâches différentes qu'il est possibles de faire.


Plutôt: "Sachant exactement qui est là, trouver les tâches qu'il est possible de faire." puisque les tâches pourraient être identiques éventuellement, mais l'idée est bien celle là.

La finalité sera dans mon plan de charge, d'ajouter un indicateur qui dira "BON" ou "PAS BON" si je lui ajoute une tâche à celles déjà planifiées, et sachant qui est là et qui n'est pas là.

Ca me fait plaisir que l'algorithme semble simple, car pour moi non !! :-p

Posté par
Surbre : Définition d'un nombre de tâches maximal 05-02-13 à 00:09

Bonsoir,

Merci pour ces précisions. Ci-dessous vous trouverez un algorithme qui pour un ensemble de tâches et un ensemble de gens présent donnés trouve toutes les répartition (s'il en existe au moins une) de ces gens pour rendre l'execution des tâches possible.

Quelques petites précisions d'abord:

1)

Citation :
J'ai réalisé un outil sous Excel...

Ma connaissance d'Excel est extrêmement limitée (si ce n'est nulle). L'algorithme ci-dessous est donné en pseudo-code . Je me tiens naturellement à votre disposition (dans ce topic) pour toutes questions concernant la conceptualisation. Concernant l'implémentation je vous conseille soit de retourner sur le forum Excel dont vous faites référence soit de trouver un gentil mathîlien qui saurait le faire.

2)
J'ai fais l'hypothèse qu'il a exactement 3 fois plus de gens présents que de tâches à exécuter. Je peux volontiers adapter l'algorithme pour les cas où il y a plus que 3 fois plus de présents que de tâches. Cependant, il me semble pédagogique de commencer par le cas simple et de le compliquer ensuite.

3)
Citation :
Ca me fait plaisir que l'algorithme semble simple, car pour moi non !! :-p

Effectivement l'algorithme est moins simple que ce que je pensais qu'il serait possible de faire...

4)
Pour des soucis de notations, à la place de Mr A, Mr B, ... je noterai Mr 1, Mr 2,... de même qu'à la place de TA, TB,... je noterai T1, T2,...


Initialisation:

Commençons par définir une matrice (un ) MR définie comme suit pour
1 \leq i \leq (\text{nombre total de personnes}) =: NTP et
1 \leq j \leq (\text{nombre total de tâches différentes}) =: NTD .

MR_{i,1} = \left\{ \begin{array}{l l} 1 & \text{si Mr } i \text{ est présent,} \\ \\ 0 & \text{sinon} \end{array} \right.

MR_{i,2j+1} =  \left\{ \begin{array}{l l} 1 & \text{si Mr } i \text{ est chef d'équipe pour T}j \\ \\ 0 & \text{sinon} \end{array} \right. \\

MR_{i,2j} =  \left\{ \begin{array}{l l} 1 & \text{si Mr } i \text{ est équipier pour T}j \\ \\ 0 & \text{sinon} \end{array} \right.

Soit encore \tau_1, \tau_2, \ldots, \tau_{nt} \in \{1,2,\ldots,NTD\} la liste des tâches devant être exécutées.

On notera np le nombre total de personnes présentes.
Remarque: D'après la précision 2) on a alors np = 3nt.

Posons finalement P=(P_1,P_2,\ldots,P_{np}) le vecteur (tableau d'une seule ligne ) contenant les indexes dans l'ordre croissant des gens présents, i.e.
P_1 < P_2 < \ldots < P_{np} et MR_{P_1,1} = MR_{P_2,1} = \ldots = MR_{P_{np},1} = 1

Algorithme:

\begin{tabular}{l} \\ Si $np / nt < 3$: $\rightarrow $ PAS OK; fin Si \\ \\ Si $np / nt > 3$: cas restant à traiter; fin Si\\ \\ Si $np / nt = 3$: faire: \\ \\ $\quad k = 1 $\\ \\ $\quad$ Tant que $k \neq 0$ faire: \\ \\ $\quad \quad$ Pour $i$ allant de $1$ à $np-1$ faire: \\ \\ $\quad \quad \quad$ Si $P_i < P_{i+1}$: $k = i$; fin Si \\ \\ $\quad \quad$ fin Pour \\ $\quad$ $l = 0$ \\ \\ $\quad$ Si $k \neq 0$  faire: \\ \\ $\quad \quad$ Pour $i$ allant de $1$ à $k+1$ faire: \\ \\ $\quad \quad \quad$ Si $P_k < P_i$: $l = i$ ; fin Si \\ \\ $\quad \quad$ fin Pour \\ \\ $\quad$ $a= P_k$ \\ \\ $\quad$ $P_k = P_l$ \\ \\ $\quad$ $P_l = a$ \\ \\ $\quad$ Si $np-k > 1$: faire: \\ \\ $\quad \quad$ $\tilde{P} = (P_{k+1},P_{k+2},\ldots,P_{np})$\\ \\ $\quad \quad$ Pour $i$ allant de $1$ à $np-k$ faire: \\ \\ $\quad \quad \quad$ $P_{k+i} = \tilde{P}_{np-k+1-i}$\\ \\ $\quad \quad$ fin Pour \\ \\ $\quad$ $\nu = 1$ \\ \\ $\quad$ Pour $i$ allant de $1$ à $nt$ faire: \\ \\ $\quad \quad$ Si $ MR_{P_{3(i-1)+1},\tau_i} = 0$: $\nu =0$; fin Si \\ \\ $\quad \quad$ Si $ MR_{P_{3(i-1)+2},\tau_i + 1} = 0$: $\nu =0$; fin Si \\ \\ $\quad \quad$ Si $ MR_{P_{3(i-1)+3},\tau_i + 1} = 0$: $\nu =0$; fin Si \\ \\ $\quad$ fin Pour \\ \\ $\quad$ Si $\nu = 1$: $\rightarrow$ OK et la répartition des tâches se trouve dans le vecteur $P$; fin Si \\ \\ fin Si \\ \end{tabular}

Et la répartition finale des tâches se fait comme suit:
On assigne
Mr P_1 \quad (CE), Mr P_2 \quad (E), Mr P_3 \quad (E) à la tâche T\tau_1
Mr P_4 \quad (CE), Mr P_5 \quad (E), Mr P_6 \quad (E) à la tâche T\tau_2 \\
...
Mr P_{3(i-1)+1} \quad (CE), Mr P_{3(i-1)+2} \quad (E),Mr P_{3(i-1)+3} \quad (E) à la tâche T\tau_i
...
Mr P_{nt-2} \quad (CE), Mr P_{nt-1} \quad (E),Mr P_{nt} \quad (E) à la tâche T\tau_{nt}

Je me rends bien compte que si on n'y est pas habitué cela peut être difficile à comprendre. C'est pourquoi je posterai un exemple d'application se basant sur votre exemple normalement demain.

Posté par
Surbre : Définition d'un nombre de tâches maximal 05-02-13 à 13:46

Bonjour,

Partons de votre exemple et supposons que Messieurs A,C,E,F,G,H sont présents. De plus on voudrait exécuter les tâches A et C. Alors
\\ MR = \left[ \begin{array}{c c c c c c c c c} \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1\\ \\ 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0\\ \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1\\ \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1\\ \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0\\ \\ 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0\\ \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ \end{array} \right]

\tau_1 = 1, \tau_2 = 3

nt = 2, np = 6, NTD = 4, NTP = 9

P = [1,3,5,6,7,8]

J'ai implémenté une version de l'algorithme sur Matlab (ou Octave dans sa version gratuite) ce matin en prenant l'avion. Si vous la désirez, je vous prie d'ajouter un e-mail dans votre profile.

Posté par
Tochirore : Définition d'un nombre de tâches maximal 05-02-13 à 20:38

Bonsoir,

Merci beaucoup pour ces éléments que je vais tenter de:

1 - comprendre;
2 - mettre en pratique sous mon plan de charge (VBA Excel)

Je suis également preneur de la version MATLAB, même si là encore c'est loin pour moi. Cela dit, heureusement que j'avais MATLAB et Mapple, parce que sinon j'aurais très certainement sombré en maths !!

Bref, je ne manquerai pas de faire un retour sur la mise en application de cet algorithme.

Posté par
Tochirore : Définition d'un nombre de tâches maximal 06-02-13 à 00:43

Re bonsoir,

Dans ma phase compréhension, avant d'attaquer "le dur" de votre algorithme, j'observe une incohérence dans la matrice proposée en exemple par rapport à sa définition.
A priori c'est une simple inversion de définitions de la matrice entre chef d'équipe et équipier.

J'attribue donc les colonnes paires (2j) à la qualification chef d'équipe, et les impaires (2j+1) à la qualification équipier.

J'obtiendrais alors la même matrice que vous à la ligne 3 près (Mr C), et je suppose donc alors une erreur par rapport à l'exemple que j'avais donné au départ.

Au final voici la troisième ligne de la matrice corrigée, ou alors j'ai tout faux !

Au lieu de: 1 0 1 1 0 0 1 0 0
Je mets:    1 0 1 0 0 0 0 0 1

Voilà, je poursuis donc l'analyse de votre proposition en espérant que je ne me suis pas trompé


PS: désolé, je ne maîtrise pas Latex, je ferai un effort si je ne suis pas compréhensible

Posté par
Surbre : Définition d'un nombre de tâches maximal 06-02-13 à 12:59

Bonjour,

Citation :
Au final voici la troisième ligne de la matrice corrigée, ou alors j'ai tout faux !

Au lieu de: 1 0 1 1 0 0 1 0 0
Je mets:    1 0 1 0 0 0 0 0 1


Vous avez tout à fait raison.

Citation :
je vais tenter de:

1 - comprendre;


En gros, l'algorithme ci-dessus marche comme suit:
Pour une liste d'entier naturels A=\{a_1,\ldots,a_n\}, on considère
l'ensemble de vecteurs \alpha (A) contenant toutes les permutations des éléments de A ().
Par exemple si A = \{1,5,9\} alors \sigma(A) = \{(1,5,9),(1,9,5),(5,1,9),(5,9,1),(9,1,5),(9,5,1)\}.
Une telle liste se génère en utilisant un algorithme établit par Narayana Pandita au 14ème siècle en Inde (voir ).
Ainsi si P est la liste des indexes des gens présents (qui, par hypothèse, a exactement 3 fois le nombre de tâches à exécuter de composantes), alors pour chaque vecteur dans \sigma(P) on vérifie si c'est une répartition possible.

J'ai réussi à trouver un moyen d'extraire les données d'une feuille Excel (enregistrée en .xls) et de coller la solution dans un fichier Excel (.csv). Je vous laisse télécharger le dossier suivant et lire le README pour savoir comment exécuter l'algorithme.

Posté par
Tochirore : Définition d'un nombre de tâches maximal 06-02-13 à 23:08

Bonsoir,

Merci pour les fichiers, je regarderai dès que possible.

J'avance lentement faute de temps, mais déjà sur la première partie de l'algorithme, je ne saisis pas l'utilité de la première boucle (mais je lis l'algorithme pas à pas donc n'ai pas la vision d'ensemble). En effet vous introduisez la boucle:

Citation :
Pour i allant de 1 à np -1 faire:
  Si Pi<Pi+1 : k=i; fin si
fin Pour


Or, d'après la définition du vecteur P, P1<P2<...<Pnp
Donc nécessairement, Pi<Pi+1

Par conséquent, la boucle ira au bout, soit jusqu'à i=np-1, et on aura alors Pnp-1<Pnp
Donc en sortie de cette première boucle, nous aurons toujours k=i=np-1

Quelle est donc l'utilité de cette première boucle, sachant qu'une boucle est gourmande en temps, je pourrais m'en passer et fixer directement k, non ?


De même pour la seconde boucle:
Citation :
Pour i allant de 1 à k+1 faire:
  Si Pk<Pi : l=i; fin si
fin Pour


Si mon raisonnement de la première boucle tient:
k+1=np-1+1=np
et
Pk=Pnp-1

Donc, toujours d'après la définition du vecteur P, nécessairement on a:
Pk=Pnp-1<Pi VRAI uniquement si i=np=k+1, donc si on est en fin de boucle...

A nouveau, cette seconde boucle serait inutile, et on pourrait de suite fixer l=np, non ?


Avant d'aller plus loin, est-ce que je fais une erreur de raisonnement, ou n'ai-je pas compris la notation de l'algorithme ?

Posté par
Surbre : Définition d'un nombre de tâches maximal 07-02-13 à 09:55

Bonsoir,

Citation :
(mais je lis l'algorithme pas à pas donc n'ai pas la vision d'ensemble)


cf. poste du 06-02-13 à 12:59

Citation :
Quelle est donc l'utilité de cette première boucle, sachant qu'une boucle est gourmande en temps, je pourrais m'en passer et fixer directement k, non ?


Attention vos raisonnements sont correctes que lors de la première itération de la boucle:

\begin{tabular}{l} \\ Tant que $k\neq 0$ faire: \\ \end{tabular}

A chaque itération de cette boucle (qui en fait exécute l'algorithme de Pandita, cf. plus haut) le vecteur P change. Donc lors de l'entrée dans la boucle, ce que vous dites est juste mais P est changé dès la première exécution ainsi ces conditions ont du sens.
Je vous conseille dans tous les cas d'aller voir le lien (introduction et chapitre sur l'ordre lexicographique):


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !