blogpost

Algo répartition - Comment les maths nous ont aidés à avoir une meilleure UI ?

Nereo Congés est un logiciel de gestion des congés et absences pour les entreprises. C'est notre bébé.

Le principe de base du logiciel est très simple : un salarié peut choisir une période dans son calendrier et effectuer une demande d'absence à son supérieur. Son manager reçoit alors un mail de notification lui demandant de valider, refuser ou commenter cette demande d'absence.

L'action qui est effectuée le plus souvent dans Nereo Congés est sans surprise la demande d'absence. Il nous fallait donc designer le logiciel pour que la demande d'absence puisse être faite de manière la plus simple et la plus claire possible.

Challenge UI pure

Nereo Congés est capable de gérer plusieurs types d'absences. Par exemple, des congés payés, des RTT, des absences pour maladie, congés sans solde, etc.

Donc lorsqu'un salarié souhaite partir en vacances entre 2 dates, il peut très bien utiliser ses droits aux congés payés et aux RTT pour cette même période d'absence. Une solution serait d'obliger l'utilisateur à poser l'absence en plusieurs fois, une fois pour les congés payés et une fois pour les RTT, mais ce serait une très mauvaise interface utilisateur. Faire une demande d'absence est quelque chose que le salarié doit pouvoir faire avec la plus grande simplicité.

La solution est donc de proposer à l'utilisateur comment il souhaite répartir ses jours d'absence parmi les différents types d'absence auquel il a droit :

Ici l'utilisateur a choisi les dates du lundi 25 Août au vendredi 29 Août, en deux clics. Il peut maintenant cliquer sur "Valider" pour effectuer la demande d'absence, ou modifier la répartition qui lui est proposée en cliquant sur les boutons + et -.

Challenge programmation

Ici nous avons un petit challenge. La répartition parmi les types d'absence proposée par le logiciel doit être faite "intelligement". En effet, le logiciel doit proposer de prendre autant de jours qu'il peut sur chaque type d'absence en prennant en compte... le futur.

Dans l'exemple précédent, le logiciel a proposé de prendre 3 RTT.
Ceci est possible car le logiciel est capable de donner le solde de chaque type d'absence à n'importe quelle date. Il peut bien évidemment dire le solde dans le passé, le solde actuel, mais il peut aussi et surtout faire une estimation du solde dans le futur, en prennant en compte:

  • les acquisitions de droit (par exemple si le salarié gagne 1 jour par mois)
  • les consommations (si le salarié a pris des jours de RTT entre le jour où il fait la demande et le 25 Août)
  • les pertes de droit : par exemple si la consommation de RTT doit se faire sur une période minimale ou sur une période de consommation précise

 

Pour pouvoir calculer ces estimations, Nereo Congés utilise un système de scripting des règles internes des entreprises clientes. Il peut donc donner une date en entrée à ces scripts et recevoir une projection de l'état dans le futur des compteurs en fonction de ces règles internes.

Ainsi, si des jours de RTT ont été déjà posés entre le jour où il fait la demande et le 25 Août, le logiciel aurait proposé de prendre moins de jours de RTT et plus de jours de congés payés.

Challenge maths

Il y a un challenge un peu plus intéressant. Supposons que l'utilisateur a validé la répartition des jours d'absence parmi les types d'absences, en ayant éventuellement modifié celle proposée par le logiciel.

Comment déterminer quels jours d'absences doivent correspondre à quels types d'absence?

Supposons que l'utilisateur veuille la répartition suivante :

RTT : 3
CP  : 2 

Une possibilité est d'affecter comme suit:

Lundi      : RTT
Mardi      : RTT
Mercredi   : RTT
Jeudi      : CP
Vendredi   : CP

 

Mais il est également possible d'affecter comme ceci:

Lundi      : RTT
Mardi      : RTT
Mercredi   : CP
Jeudi      : CP
Vendredi   : RTT

 

Ou encore une autre possibilité:

Lundi      : CP
Mardi      : RTT
Mercredi   : RTT
Jeudi      : CP
Vendredi   : RTT

 

Quelle affectation devons nous choisir? La réponse est classique : ça dépend. Ça dépend de quoi? Nous avons comme contrainte de ne pas faire passer le salarié en solde négatif et choisir l'affectation en fonction de cette contrainte.

Supposons que le salarié a un solde de RTT de 2 le lundi matin et qu'il gagne un jour de RTT le vendredi. Si nous faisons l'affectation suivante:

Jour         type absence     solde RTT    
---------------------------------------
Dimanche:                         2
Lundi :      RTT                  1          
Mardi :      RTT                  0        
Mercredi :   RTT                 -1          
Jeudi :      CP                  -1              
Vendredi :   CP                   0         

son solde de RTT va passer dans le négatif mercredi et jeudi, avant de revenir à 0 le vendredi. Or, si on avait choisi l'affectation suivante :

Jour         type absence     solde RTT    
---------------------------------------
Dimanche:                         2
Lundi :      RTT                  1          
Mardi :      RTT                  0        
Mercredi :   CP                   0          
Jeudi :      CP                   0           
Vendredi :   RTT                  0    // car +1 -1  

il n'y aurait pas ce problème.

Pour autant, il ne faut pas essayer d'affecter les RTT en dernier. D'une part parce que nous pouvons très bien avoir le même problème avec les congés payés cette fois ci, d'autre part il peut y avoir des règles voulues par l'entreprise du salarié qui font que les RTT doivent être consommés avant une certaine date.

Supposons que le salarié a un solde de RTT de 3 le lundi matin et qu'une règle interne dit que tout RTT non consommé le mercedi 27 Août va être perdu. Si nous faisions l'affectation suivante:

Jour         type absence     solde RTT    
---------------------------------------
Dimanche:                         3
Lundi :      RTT                  2          
Mardi :      RTT                  1        
Mercredi :   CP                   0     // RTT non consommé -> solde passe à 0         
Jeudi :      CP                   0           
Vendredi :   RTT                 -1      

on se trouve avec un solde négatif qui aurait pu être évité avec l'affectation suivante :

Jour         type absence     solde RTT    
---------------------------------------
Dimanche:                         3
Lundi :      RTT                  2          
Mardi :      RTT                  1        
Mercredi :   RTT                  0          
Jeudi :      CP                   0           
Vendredi :   CP                   0  

Cette situation arrive très souvent. Notamment dès qu'un salarié souhaite faire une demande d'absence à cheval sur deux mois, des acquisitions ou des pertes de droit à absence interviennent en plein milieu de la période de l'absence souhaitée.

Nous devons donc trouver un algo sympa pour répondre à ce besoin.

Captain TTU to the rescue

Le problème d'affecter des éléments d'un ensemble à des éléments d'un autre ensemble est un problème largement connu en maths combinatoires.

Nous pouvons schématiser le problème comme suit :

A gauche, ce sont les jours d'absence, à droite, ce sont les types d'absences. Nous voulons affecter toute la période d'absence souhaitée par l'utilisateur, ici une semaine entière du lundi au vendredi, aux types d'absences qui sont en nombre souhaité également par l'utilisateur : 3 RTT et 2 Congés payés.

Pour avoir une affectation valide, on doit connecter chaque noeud de gauche à un noeud de droite et chaque noeud de droite à un noeud de gauche.

Voici une possibilité :

et son équivalent en terme d'absences de congés est :

Lundi      : RTT
Mardi      : RTT
Mercredi   : RTT
Jeudi      : CP
Vendredi   : CP

 

Voici une autre possibilité:

et son équivalent en terme d'absences de congés est :

Lundi      : RTT
Mardi      : RTT
Mercredi   : CP
Jeudi      : CP
Vendredi   : RTT

 

On peut considérer le coût d'associer un noeud de gauche à un noeud de droite, ainsi notre problème revient à trouver une affectation valide en minimisant le coût global. En maths, ça se formule de façon plus formelle par :

f(i, j) = le cout de relier le noeud i au noeud j
x_ij = variable de décision : vaut 1 si le noeud i doit etre relié au noeud j, 0 sinon.

 

Bonne nouvelle
Il se trouve que la matrice définie par les contraintes ici est une matrice totalement unimodulaire. Derrière ce nom trop classe se cache en fait une bonne nouvelle. Cela veut dire que nous pouvons faire cette optimisation en temps polynomial en balançant la résolution à un algorithme de type simplex. En "temps polynomial" veut dire que vu la taille des données, on va pouvoir résoudre ce système en un clin d'oeil.

 

Par contre, selon les souhaits des entreprises clientes, nous pouvons avoir des règles plus "tordues". Ainsi, le coût d'affecter le noeud i au noeud j peut ne pas dépendre uniquement de i et j mais de l'état de l'affectation actuelle, par exemple : certaines entreprises ne souhaitent pas que deux types d'absences soient accolées si le nombre de jours pris dépasse un certain seuil. Dans ce cas, le coût d'associer le noeud i au noeud j ne dépend plus que du noeud i et j mais aussi de ce qui a été mis dans le noeud j-1.

Qu'est-ce qui se passe dans ce cas là? Dans ce cas on n'a plus la bonne nouvelle de résolution polynomial. Nous devons tester toutes les affectations possibles. Mais intuitivement, on sent qu'il y en aura peut-être pas tant que ça à calculer, notamment parce qu'il y a plein de cas où les affectations sont équivalentes. Considérez par exemple ces deux affectations possibles, elles sont équivalentes :

Mais est-ce qu'il va y en avoir beaucoup? Comptons les !

Nombre de combinaisons
Prennons un exemple et comptons le nombre d'affectations possibles.

Supposons qu'on souhaite prendre 15 jours, dont 5 RTT et 7 Congés payés et 3 congés sans solde.

Rappelez vous de vos cours de terminal: pour les RTT, nous avons C(15,5) possibilités. (rappel sur Cnk). Pour chacune de ces possibilités, il reste encore 10 jours à affecter aux congés payés et aux congés sans solde. Donc pour chacune de ces possibilités, nous avons C(10, 7) possibilités pour les congés payés, et il reste encore 3 jours à affecter aux 3 congés sans solde: soit C(3,3) (qui vaut 1 car il y a une seule façon d'affecter 3 jours de congés sans solde à 3 jours d'absence).

Cela fait donc nombre d'affectations = C(15, 5) * C(10, 7) * C(3, 3)

en réecrivant avec la formule de C (n, k) : nombre d'affectations = 15! / ( 5! 10! ) * 10! / (7! 3!) * 3! / 3! nombre d'affectations = 15! / ( 5! 7! 3! ) = 360360

Le logiciel doit donc calculer 360360 combinaisons d'affectations. Ce nombre peut paraitre beaucoup mais pour un ordinateur de nos jours calculer autant de combinaisons est instantané.

Bon ...

Respirons un peu et regardons à nouveau le schéma global. On est parti d'une question très bête : comment peut-on améliorer l'UI de cette page du logiciel? Et on se retrouve tête à tête avec les matrices totalement unimodulaires et des coefficients binomiaux.

Qu'est-ce qu'on a fait ici?

Nous avons trouvé une façon d'éviter des dizaines de clics à chaque utilisateur pour une action primordiale du logiciel, tout en lui laissant la main sur la manière dont il veut procéder.

Ça c'est la magie d'une bonne UI : une interface super simple qui ne laisse rien paraitre des calculs qui sont faits derrière pour le bonheur de l'utilisateur. Et pour une fois, les maths sont au service de l'UI !