algorithme pour les événements/éléments d'empilage

Question

Je cherche à créer un diagramme pseudo diagramme de Gantt, sauf un où les événements peuvent être sur la même ligne que tant qu'ils ne se chevauchent pas, quelque chose comme ceci:

   M T W R F S U M T W R F S U M T W R F S U 
Category 1: |Event 1|  |Event 2| |------Event 3--| 
       |---------Event 4-----------| |-Event 5-| 

Je cherche un algorithme pour emballer efficacement ces événements. Je sais que je peux utiliser la longueur de l'événement et la date de début pour déterminer le chevauchement, mais j'aimerais avoir un point de départ. Pour les curieux, je cherche à contourner les limitations de l'affichage du calendrier de Gantt dans SharePoint 2007. Nos utilisateurs aiment cette vue, mais ne veulent pas une tâche par ligne.

Answer 1

Ma première tentative serait de trier les tâches par heure de début/date. Ensuite, je les place un à la fois sur la première ligne sur laquelle leur heure de départ n'était pas déjà occupée. Je ne suis pas (du tout) sûr que cela donne des résultats optimaux (c'est-à-dire, utilise toujours le plus petit nombre de lignes possible), mais il devrait au moins être raisonnable à mi-chemin.

Plus je pense à cela, plus je pense que cela pourrait être optimal. Les problèmes d'optimisation sont généralement difficiles car le nombre de combinaisons augmente extrêmement rapidement par rapport au nombre d'éléments. Dans ce cas, cependant, vous n'obtenez pas vraiment une telle explosion combinatoire parce que vous ne pouvez pas réorganiser les éléments - au moins je suppose que leurs heures de début sont toutes préréglées, donc ils ne peuvent pas être réarrangés. Edit: juste pour être clair: ici, je suppose que la question ne concerne que affichant un calendrier d'événements pour lesquels les heures de début et les durées sont déjà connus, donc l'optimisation signifie simplement afficher les données comme "compact "Comme possible. Je suis pas en parlant de tenter de créer le calendrier lui-même (c'est-à-dire, essayer de comprendre quels événements à planifier quand). En fonction des contraintes, c'est normalement un problème beaucoup plus difficile. C'est assez facile tant que vos seules contraintes sont des dépendances inter-tâches, mais quand vous ajoutez des choses comme l'utilisation maximum de la main-d'œuvre et les ressources contraintes (par exemple, la tâche X peut uniquement être effectuée par la personne A, B ou C , C ou D, etc.), la situation devient beaucoup plus difficile très rapidement.