Extension d'emplois du temps

A propos des extensions

L'extension d'emploi du temps est la troisième forme qui peut être passée au fonction d'ajustage. Sa structure ressemble à une forme d'emploi du temps lisible pour l'humain, comme par exemple la sortie du module d'exportation htmlcss . Pour cette raison, c'est la forme la plus pratique pour vérifier les erreurs pour les emplois du temps pour les ressources humaines.

Si vous regardez le manuel de référence de l'API, vous pourrez constater qu'une extension d'emploi du temps est définie par un type de ressource constante et un type de ressource variable (enregistrés respectivement dans con_typeid et var_typeid) . En comparaison, une slist est définie par un seul type de ressource variable. Les données de l'emploi du temps sont enregistrées dans un tableau à 2 dimensions d'identifiants de tuples dans le champ tupleid . La première dimension va de 0 à N-1, où N est le nombre de ressources du type de ressource variable var_typeid et la seconde dimension va de 0 à M-1, où M est le nombre de ressources du type de ressource constante con_typeid.

Si un évènement utilise une ressource n de type var_typeid et une ressource m de type con_typeid en même temps, alors son identifiant de tuple sera enregistré dans e->tupleid[n][m], où e est un pointeur vers la structure de l'extension. Si aucun évènement n'utilise cette combinaison de ressources, alors la valeur enregistrée dans le tableau sera -1.

Pour mieux visualiser ce tableau d'identifiant de tuples, considérons l'exemple suivant de planification scolaire. Disons que nous choisissons les professeurs comme type de ressource constante et les créneaux horaires comme type de ressource variable. Les créneaux sont sont forme de matrice, de 5 jours et 3 tranches par jour.

Les identifiants de tuple du tableau représentent les évènements (dans ce cas, les cours) qui sont planifiés pour ce professeur, pour le créneau spécifié. Si aucun cours n'est planifié pour ce professeur, la valeur est de -1.

Il est maintenant évident qu'une extension représente un emploi du temps en entier seulement s'il existe une association un-à-un des évènements en paires ressource constante / ressource variable (c'est à dire qu'il n'y a pas deux évènements qui utilisent la même combinaison de ressource constante et ressource variable). Si ce n'est pas le cas, certains évènements seront perdus lors de la conversion de la forme chromosomique à la forme étendue puisqu'il ne peut y avoir qu'un seul identifiant de tuple enregistré dans une case du tableau tupleid . Dans ce cas, un évènement est choisi au hasard parmi le groupe d'évènements en conflit et son identifiant est enregistré dans le tableau.

A cause de cette limitation, la plupart des modules qui utilisent les extensions ne fonctionnent correctement que s'ils sont associés à un module (obligatoire) qui empêche ces pertes d'arriver. Dans la planification scolaire, c'est le rôle du module sametime.so .

Il est écrit plus haut que les extensions sont les seules parties du noyau qui utilisent des informations concernant les conflits de ressources. Les ressources constantes en conflit sont considérées dans ce cas comme une seule ressource. Les conflits pour les ressources variables sont ignorés. Cela signifie que si une ressource constante m1 est en conflit avec une ressource m2 alors les évènements pour m1 et m2 seront dans e->tupleid[x][m1]. En revanche, seuls les évènements pour m2 seront dans tupleid[x][m2] (le noyau traite les conflits de façon asymétrique, vous souvenez-vous ?).

Code source du module holes.so

Le module d'ajustage holes.so est utilisé dans la planification scolaire et les problèmes similaires, et recherche les trous dans les emplois du temps. Un trou dans un emploi du temps pour une certaine ressource constante est défini comme un ou plusieurs créneaux dans une journée (créneaux qui ne sont pas utilisés par cette ressource constante) entourés (avant et après, le même jour) de créneaux occupés.

Exemple 1: un emploi du temps avec 3 cours au milieu de la journée est considéré sans trou. Exemple 2: une emploi du temps, avec 1 cours le matin, puis une pause de 2 créneaux et ensuite 2 cours est considéré comme ayant un trou d'une durée de deux créneaux.

Les trous sont le plus souvent ennuyeux car cela signifie qu'un professeur ou une classe doît attendre en deux cours. Dans certains cas, ils sont même interdits.

Ci-dessous, un extrait du code du module holes.so . Le code complet est fourni avec la distribution.

static int periods, days;

int fitness(chromo **c, ext **e, slist **s)
{
        int first,last;
        int free,nonfree;
        int sum;

        ext *timext;
        int connum, con_resid;
        int day, period, var_resid;

        timext=e[0];

        connum=timext->connum;

        sum=0;

        for(con_resid=0;con_resid<connum;con_resid++) {
                var_resid=0;
                for(day=0;day<days;day++) {
                        first=-1;
                        last=-1;
                        free=0;
                        nonfree=0;

                        for(period=0;period<periods;period++) {
                                if(timext->tupleid[var_resid][con_resid]==-1) {
                                        free++;
                                } else {
                                        nonfree++;
                                        last=period;
                                        if (first==-1) first=period;
                                }
                                var_resid++;
                        }

                        if (last!=-1) {
                                sum=sum+(periods-nonfree-first-(periods-1-last));
                        }
                }
        };
        return(sum);
}

int module_init(moduleoption *opt)
{
        fitnessfunc *f;
        moduleoption *result;

        char *type;
        char fitnessname[256];
        int n;

        resourcetype *time;

        time=restype_find("time");
        if(time==NULL) {
                error(_("Resource type '%s' not found"), "time");
                return -1;
        }

        n=res_get_matrix(time, &days, &periods);
        if(n) {
                error(_("Resource type %s is not a matrix"), "time");
                return -1;
        }

        result=option_find(opt, "resourcetype");
        if(result==NULL) {
                error(_("module '%s' has been loaded, but not used"), "holes.so");
        }
        while(result!=NULL) {
                type=result->content_s;

                snprintf(fitnessname, 256, "holes-%s", type);

                f=fitness_new(fitnessname,
                        option_int(opt, "weight"),
                        option_int(opt, "mandatory"),
                        fitness);

                if(f==NULL) return -1;

                n=fitness_request_ext(f, type, "time");
                if(n) return -1;

                result=option_find(result->next, "resourcetype");
        }

        return(0);
}

Initialisation du module

Puisque ce module est conçu pour la planification scolaire, nous nous attendons à ce que la ressource "time" soit de type matriciel (la largeur étant le nombre de jours de la semaine et la hauteur le nombre de créneaux horaires par jour). Nous enregistrons ces dimensions dans les variables globales days et periods (nous les utiliserons plus tard dans la fonction d'ajustage).

La boucle "while" qui suit parcourt les options du module nommées "resourcetype". Avec cette option, l'utilisateur peut spécifier les types de ressources constantes qui devront avoir leurs emplois du temps vérifiés, à la recherche de trous (par exemple professeur, classes, etc...)

En premier, nous essayons de trouver le pointeur vers la première option en utilisant la fonction option_find() (la fonction option_str() ne peut pas être utilisée si vous attendez plus d'une option portant le même nom - voir la document de l'API ). Si nous ne trouvons même pas trouver une option avec ce nom (option_find() retourne NULL), alors le module ne touche pas à l'emploi du temps soumis et nous pouvons écrire un avertissement.

Du point de vue du noyau, nous définissons une nouvelle fonction d'ajustage pour chaque option de ce nom. En réalité, nous définissons une seule fonction fitness() plusieurs fois. Chaque fois avec un nouveau nom qui inclut le nom du type de ressource et à chaque fois, nous demandons une extension différente avec fitness_request_ext(). Cela signifie que pour chaque évaluation d'emploi du temps notre fonction fitness() sera appelée une ou plusieurs fois, suivant le nombre d'options "resourcetype" fournies par l'utilisateur.

La fonction fitness_request_ext() est utilisée pratiquement de la même manière que fitness_request_slist() ou fitness_request_chromo(). Le premier argument doit être un pointeur vers la structure de la fonction d'ajustage, les second et troisième sont les noms respectifs des types pour les ressources constante et variable. Ici, nous demandons une extension avec un type de ressource constante fourni par l'utilisateur et le type de ressource variable "time".

Fonction d'ajustage

La fonction d'ajustage de ce module est un peu plus compliquée que les précédentes. Notre extension demandée est enregistrée dans e et le nombre de ressources définies du type de ressource constante est enregistré dans connum (nous obtenons ce nombre depuis la structure de l'extension, puisque nous ne savons pas pour quel type de resssource constante cette instance de fitness() a été appelée).

La boucle la plus exterieure parcourt, dans con_resid, les identifiants de toutes les ressources constantes définies. Puisque les trous dans l'emploi du temps sont déterminés par journée, nous avons une seconde boucle qui parcourt les jours. La variable var_resid contient l'identifiant de la ressource pour le créneau courant.

La boucle la plus interne parcourt les créneaux d'une journée et détermine :
1) horaire (ordonnée de la matrice) du premier créneau non-libre first du jour,
2) horaire du dernier créneau non-libre last
3) le nombre de créneaux non-libres de la journée.

S'il n'y a pas de créneaux non-libres (class="varname">last est égal à -1), alors, par définition, il n'y a pas de trou dans l'emploi du temps pour la journée.
S'il y a des créneaux non-libres, alors le nombre de trous peut être calculé par une formule simple : le nombre de créneaux entre first et last moins le nombre de créneaux non-libres égal le nombre de trous. Le nombre de trous calculés du jour courant est ajouté à la somme d'erreurs sum .

Discussion

Les extensions d'emploi du temps sont gourmandes en ressource de calcul. Dans la plupart des cas, elles sont moins performantes que les slists. La discussion à propos des slists est aussi applicable pour les extensions.

Le temps nécessaire pour calculer l'extension dépend du nombre de ressources constantes définies et des ressources variables. Il dépend aussi de l'utilisation de conflits dans le type de ressources constantes spécifiés. Si l'emploi du temps utilise des conflits non-triviaux définis dans le type de ressources constantes (si chaque ressource entre en conflit avec une autre ressource qu'elle-même), alors l'extension est plus longue à calculer.