Evènements dépendants

Un peu de théorie

La plupart des contraintes d'emploi du temps peuvent être satisfaites de plusieurs façons. Imaginez un problème d'emploi du temps qui utilise seulement le module sametime.so avec l'option mandatory . Ce problème peut avoir des millions de solutions qui satisfont toutes les contraintes définies par le sametime.so . Mais, d'un autre côté, le nombre de toutes les combinaisons d'un tel emploi du temps (c'est à dire l'espace qui doit être parcouru pour trouver une de ces solutions) est des millions, ou des milliards, de fois plus grand que le nombre de solutions. Il n'existe pas de façon simple pour trouver une solution que de parcourir toutes les combinaisons possibles.

Le problème d'emploi du temps décrit est un parfait candidat pour être résolu avec un algorithme génétique. La plupart des contraintes d'emploi du temps entrent dans cette catégorie; cependant nous rencontrons parfois une contrainte qui est à l'exacte opposé : elle a seulement une ou seulement très peu de solutions et la solution est triviale si nous connaissons la nature du problème.

Il est très difficile pour un algorithme génétique de trouver une solution pour un tel problème puisque la seule connaissance que l'algorithme a de la nature du problème est l'allure de la fonction d'ajustage. Cela signifie que la fonction d'ajustage doit être soigneusement choisie pour qu'elle "guide" l'algorithme vers la solution unique.

Ce serait cependant du gaspillage que d'utiliser l'algorithme génétique compliqué pour résoudre un problème qui a une solution triviale. Pour cela, Tablix apporte les fonctions updater depuis la version 0.3.1 . Ces fonctions permettent à l'auteur du module de mixer son propre algorithme avec l'algorithme génétique qui fonctionne en arrière-plan.

A propos des fonctions updater

Comme vous savez, l'algorithme génétique du noyau assigne des ressources variables aux évènements tandis que l'assignation des ressources constantes ne change pas et sont fixés dans le fichier de configuration du problème. En définissant des fonctions "updater", un module peut assigner quelques ou toutes les ressources variables pour des évènements, sans passer par le noyau, et sous son propre contrôle.

Chaque fonction "updater" a un évènement source (indépendant) et une destination (dépendante). Les ressources variables de l'évènement source sont assignées soit par l'algorithme génétique, ou comme nous le verrons plus loin, par une autre fonction "updater".La fonction "updater" lit alors ces assignations (depuis les structures chromosomiques appropriées) et assigne les ressources variables correctes à l'évènement destination.

Résolution des dépendances

Comme vous pouvez le voir, une fonction "Updater" peut "mettre à jour" un seul évènement. Pour cette raison, un module définira typiquement beaucoup de fonctions. Aussi, une description de problème d'emploi du temps peut utiliser plus d'un module qui emploie les fonctions "Updater". Cela signifie qu'il est crucial que les fonctions "Updater" soient appelées dans le bon ordre. Par exemple : les premières fonctions à être appelées doivent être celles dont les évènements sources sont pris en charge par l'algorithme génétique. Ensuite, peuvent être appelées les fonctions dont les évènements sources sont les évènements destination du premier groupe de fonctions.

Heureusement, vous n'avez pas à vous préoccuper de ces détails puisque le noyau de Tablix résoud automatiquement les conflits de dépendance avant de démarrer la boucle principale de l'algorithme. Cependant, vous devez garder en tête de ne pas créer de dépendances circulaires avec vos fonctions. Voici un exemple de dépendance circulaire :

• Fonction Updater 1: évènement source 1, destination event 2

• Fonction Updater 2: évènement source 2, évènement destination 3

• Fonction Updater 3: évènement source 3, évènement destination 1

Le résolveur de dépendances du noyau détectera ça et reportera une erreur

Module consecutive.so

Le module consecutive.so est utilisé pour forcer la programmation de certains évènements par groupes de deux ou plus. Il nécessite l'existence d'un type de ressource "time" et qu'il soit une matrice.

Puisque'il utilise des fonctions "Updater", il ne contient pas de fonction d'ajustage. Par conséquent, il ignore les paramètres weight et mandatory (ndt: qui doivent néanmoins être présents).

Voici la partie importante du code source du module consecutive.so . La totalité du code est disponible dans la distribution.

/* Cette structure décrit un seul bloc d'évènements consécutifs */
struct cons_t {
        /* Tableau d'indentifiants de tuples */
        int *tupleid;
        /* Nombre d'identidiants de tuples dans le tableau */
        int tupleidnum;

        struct cons_t *next;
};

/* Liste chaînée décrivant tous les blocs d'évènements consécutifs */
static struct cons_t *cons=NULL;

static int time;

static int periods, days;

/* C'est la fonction Updater. Elle vérifie qu'un évènement dépendant est bien programmé un créneau après l'évènement dépendant. */
int updater(int src, int dst, int typeid, int resid)
{
        return(resid+1);
}

/* C'est la fonction de précalcul. Elle est appelée après tous les gestionnaires de restrictions. Nous définissons les fonctions Updater ici. */
int module_precalc(moduleoption *opt)
{
        int n, tupleid;
        struct cons_t *cur;

        int *residlist;
        int residnum;

        if(cons==NULL) {
                /* La liste chaînée est vide*/
                info(_("Le module '%s' a été chargé, mais n'est pas utilisé"),
                                                        "consecutive.so");
        }

        /* Nous utiliserons ce tampon plus tard pour la fonction domain_and() */
        residlist=malloc(sizeof(*residlist)*periods*days);
        if(residlist==NULL) {
                error(_("Impossible d'allouer suffisamment de mémoire."));
                return(-1);
        }

        /* Nous parcourons tous les groupes d'évènements définis. */
        cur=cons;
        while(cur!=NULL) {

                /* Pour chaque évènement, excepté le premier, nous définissons une fonction Updater. */

                for(n=1;n<cur->tupleidnum;n++) {
                        tupleid=cur->tupleid[n];

                        /* Nous devons vérifier si cet évènement est déjà dépendant.
                         * S'il l'est, nous rapportons une erreur. */

                        if(updater_check(tupleid, time)) {
                                error(_("L'évènement '%s' dépend déjà d'un autre"
                                        " event"), dat_tuplemap[tupleid].name);
                                free(residlist);
                                return(-1);
                        }

                        /* Le premier évènement du groupe est clairement indépendant
                         * (au moins pour ce qui concerne ce module).
                         * Le second dépend du premier. Le troisième du second, etc... */


                        updater_new(cur->tupleid[n-1], tupleid, time, updater);
                }

                /* Maintenant, nous devons nous assurer que le premier évènement du groupe
                 * sera programmé suffisamment tôt pour que tout le groupe
                 * soit dans la même journée. */

                /* Cela signifie que nous devons éliminer les derniers créneaux tupleidnum
                 * pour chaque jour de son domaine de temps (time domain). */

                residnum=0;
                for(n=0;n<days*periods;n++) {
                        if(n%periods<(periods-cur->tupleidnum)) {
                                residlist[residnum]=n;
                                residnum++;
                        }
                }

                tupleid=cur->tupleid[0];
                domain_and(dat_tuplemap[tupleid].dom[time],residlist,residnum);

                cur=cur->next;
        }

        free(residlist);
        return(0);
}

La fonction d'initialisation, le gestionnaire de restriction et d'autres fonctions utilitaires manquent dans le code ci-dessus. En résumé, la fonction d'initialisation initialise les variables globales et enregistre le gestionnaire de restriction et la fonction de précalcul dans le noyau, de façon semblable à ce que nous avons déjà vu plus tôt. Le gestionnaire de restriction créé une liste chaînée de structures cons_t . Chacune de ces structures maintient une liste d'identifiants de tuple (le champ tupleid) des évènements qui doivent être consécutifs.

Enregistrer les fonctions "updater"

Les fonctions "updater" sont enregistrées dans le noyau de Tablix avec la fonction updater_new. Cette fonction prend 4 arguments : le premier est l'identifiant du tuple de l'évènement source, le second l'identifiant de tuple de l'évènement destination, le troisième est l'identifiant du type de ressource et le quatrième est le pointeur vers la fonction "updater".

Avant d'enregistrer une fonction "updater", vous devez vérifier si l'évènement destination n'est pas également l'évènement destination d'une autre fonction "updater" (d'un module différent, par exemple). Cela peut être fait soit avec la fonction updater_check ou en vérifiant la valeur retournée par updater_new. Toutefois, la première méthode est recommandée puisque la fonction updater_new peut échouer pour d'autres raisons (par exemple, par manque de mémoire), ce qui peut conduire à des messages d'erreur trompeurs.

Fonction Updater

La fonction "updater" est en elle-même très simple dans ce cas. Elle est appelée avec 3 arguments : l'identifiant de tuple de l'évènement source et de destination, et l'identifiant du type de ressource, comme spécifié dans la fonction updater_new et l'identifiant de la ressource assignée à l'évènement source. Elle doit retourner l'identifiant de ressource qui doit être assignée à l'évènement destination.

Puisque le module a été conçu ainsi, la fonction "updater", dans ce cas, se comporte de la même manière pour tous les évènements dépendants (elle ignore tous les arguments, excepté resid): elle leur assigne une ressource qui a l'identifiant de la ressource assignée à l'évènement source plus 1. Puisque nous travaillons avec le type de ressource "time" qui est une matrice, cela signifie que nous assignons à l'évènement destination un créneau horaire qui est juste après celui assigné à l'évènement source.

Les fonctions Updater et les domaines de ressources

Il est possible que, quand certaines ressources sont assignées à l'évènement source, une fonction "updater" essaie d'assigner une ressource à l'évènement destination qui n'est pas dans le domaine de ressources de ce dernier. Pour cette raison, le noyau évalue chaque fonction juste avant le démarrage de l'algorithme génétique et détermine pour quelles valeurs d'entrée une fonction "updater" peut être appelée. Les valeurs pour lesquelles une fonction "updater" retourne des assignations de ressources erronées sont enlevées des domaines de ressources appropriées des évènements sources.

Cela se déroule automatiquement, pendant la phase de résolution des dépendances. En d'autres termes, le noyau fera cette vérification pour vous et vous ne devez pas vous préoccuper des domaines de ressources lorsque vous écrivez une fonction "updater".

Porter les modules de la version 0.3.1 vers la version 0.3.2

Dans la plupart des cas, cela devrait être relativement simple. La fonction "updater" dans la version 0.3.2 ne modifie plus directement la structure table . Elle prend l'assignation de la ressource demandée de l'évènement source comme argument, et retourne l'identifiant de la ressource qui doit être assignée à l'évènement destination.

A cause de ce changement, une fonction "updater" ne peut affecter les assignations des ressources que d'une seul type. Les fonctions updater_check et updater_new ont maintenant un argument supplémentaire, en rapport avec ce changement.

Suivent les parties signatives du module consecutive.so avant le changement (comparez-les avec le listing ci-dessus) :

void updater(int src, int dst, table *tab)
{
        int src_time;

        src_time=tab->chr[time].gen[src];

        /* Cela devrait être toujours vrai si nous avons correctement initialisé le domaine de temps
         * pour le premier évènement de chaque groupe */

        /* Cela signifie que l'évènement indépendant n'est pas dans le dernier créneau du jour */


        assert(src_time%periods<(periods-1))

        /* L'évènement suivant du groupe est programmé le créneau d'après. */

        tab->chr[time].gen[dst]=src_time+1;
}

.
.
.

int module_precalc(moduleoption *opt)
{
                        .
                        .
                        .

                        /* Nous devons vérifier si cet évènement est déjà dépendant.
                         * Si c'est le cas, nous rapportons une erreur. */

                        if(updater_check(tupleid)) {
                                error(_("L'évènement '%s' dépend déjà d'un autre"
                                        " event"), dat_tuplemap[tupleid].name);
                                free(residlist);
                                return(-1);
                        }

                        /* Le premier évènement du groupe est vraiment indépendant
                         * (du moins pour ce qui concerne ce module).
                         * Le second dépend du premier, le troisième du second, etc...*/

                        updater_new(cur->tupleid[n-1], tupleid, updater);

                        .
                        .
                        .
}