La slist est une représentation spéciale de l'emploi du temps qui peut être demandée par la fonction module_init() . Dans ce cas, elle est calculée par le noyau et passée à la fonction d'ajustage du module.
Une fonction d'ajustage doit souvent calculer une liste d'évènements qui utilisent une certaine ressource d'un type particulier de type de ressources (l'exemple le plus commun étant de vérifier si deux évènements utilisent une même ressource). Cette vérification peut être très chronophage si elle est faite sur une forme chromosomique de l'emploi du temps, mais peut être faite plus rapidement si vous passez de la forme chromosomique à la forme de slist. Pour éviter de gaspiller du temps processeur et de la mémoire inutilement en faisant cette transformation au niveau du module, c'est le noyau qui calcule une slist une fois pour toutes, et passe un pointeur vers cette structure à chaque module qui l'utilisent.
Si vous jetez un oeil dans le manuel de référence de l'API, vous verrez que la structure slist est composée de tableaux varnum , chaque tableau comportant 0 ou plusieurs identifiants de tuples. varnum est égal au nombre de la ressource pour le type de ressource choisi (son identifiant est stocké dans le champ var_typeid).
Le Nième tableau contient les identifiants de tuples de tous les évènements qui utilisent la ressource dont l'identifiant est N et dont l'identifiant du type de ressource est égal à var_typeid.
Note: Comme vous pouvez le constater, le nombre d'slists possibles qui peuvent être générées pour un emploi du temps donné est égal au nombre de types de ressources variables définies dans le problème. En pratique, seulement une ou deux slists sont nécessaires. Notez qu'il est possible de générer une slist pour un type de ressources constant, et que n'y a aucune application pratique pour de une telle slist.
Contrairement aux chromosomes, les slists prennent du temps à être générées. Cependant, une fois qu'elle est générée (pour un certain type de ressources), il ne faut presque pas de temps processeur pour passer le pointeur la slist à deux ou plusieurs modules. Utilisez donc une slist si vous savez que la même structure sera utilisée par d'autres modules dans la résolution du problème, et que son utilisation permettra un traitement plus rapide de la fonction d'ajustage. Si la slist n'est calculée que pour un seul module, mais que cela permet un traitement en O(n) au lieu de O(n²), alors utilisez la.
L'utilisation des conflits dépend en partie de l'accord des auteurs d'un certain groupe de modules. Le noyau fournit un mécanisme qui permet de marquer quelle ressource entre en conflit avec telle autre en exportant deux fonctions :
res_set_conflict() et res_get_conflict(). La seule partie du noyau de Tablix qui utilise cette information est la génération d'extensions d'emploi du temps.
Note: Une ressource entre toujours en conflit avec elle-même. Par défaut, aucune ressource entre en conflit. Les modules peuvent définir des conflits entre des ressources, mais pas en annuler.
Par exemple, dans la planification scolaire, les conflits sont utilisés avec des types de ressources constants (dans ce cas, des groupes d'étudiants et des professeurs). Deux évènements mettant en jeu deux groupes d'étudiants conflictuels ne peuvent jamais être programmés en même temps. Idem pour deux professeurs en conflit.
Le noyau traite les conflits de façon asymétrique. Cela signifie que la ressource 1 peut entrer avec la ressource 2, alors que la ressource 2 n'entre pas en conflit avec la ressource 1. La plupart des problèmes d'emplois du temps ont néanmoins besoin de conflits symétriques (par exemple la planification scolaire). Cela signifie que lorsque vous définissez un conflit entre 2 ressources, vous devez appeler la fonction res_set_conflict() deux fois (la deuxième avec les arguments en ordre inverse).
Les conflits sont traités sans transitivité dans le noyau. Si la ressource 1 entre en conflit avec la ressource 2 et que la ressource 2 entre en conflit avec la ressource 3, cela ne signifie pas que la ressource 1 entre en conflit avec la ressource 3. Cependant, certains modules peuvent traiter les conflits de manière transitive.
Ce qui suit est la partie importante du code source du module sametime.so (la totalité du code peut être trouvée dans la distribution). Vous devriez maintenant être familiarisé avec la plupart des appels de fonctions.
Si vous ne connaissez pas bien la fonctionnalité de ce module (il est l'un des modules standards utilisés dans la planification scolaire), reportez-vous au manuel de référence des modules.
int getconflict(char *restriction, char *cont, resource *res1)
{
resource *res2;
res2=res_find(res1->restype, cont);
if(res2==NULL) {
error(_("ressource invalide dans la restriction conflicts-with "));
error(_("ressource: %s type de ressource: %s"), cont, res1->restype);
return(-1);
}
res_set_conflict(res1, res2);
res_set_conflict(res2, res1);
return 0;
}
int module_fitness(chromo **c, ext **e, slist **s)
{
int a,b,m;
int n;
int sum;
slist *list;
chromo *time, *room, *class, *teacher;
resourcetype *teacher_type, *class_type;
list=s[0];
room=c[0];
time=c[1];
class=c[2];
teacher=c[3];
teacher_type=teacher->restype;
class_type=class->restype;
sum=0;
for(m=0;m<time->gennum;m++) {
a=time->gen[m];
for(n=0;n<list->tuplenum[a];n++) if(list->tupleid[a][n]<m) {
b=list->tupleid[a][n];
if (room->gen[m]!=room->gen[b]) {
if(res_get_conflict(teacher_type,
teacher->gen[m],
teacher->gen[b])) {
sum++;
}
if(res_get_conflict(class_type,
class->gen[m],
class->gen[b])) {
sum++;
}
}
}
}
return(sum);
}
int module_precalc(moduleoption *opt)
{
...
}
int module_init(moduleoption *opt)
{
fitnessfunc *fitness;
handler_res_new("class", "conflicts-with", getconflict);
handler_res_new("teacher", "conflicts-with", getconflict);
precalc_new(module_precalc);
fitness=fitness_new("same time",
option_int(opt, "weight"),
option_int(opt, "mandatory"),
module_fitness);
if(fitness==NULL) return -1;
if(fitness_request_chromo(fitness, "room")) return -1;
if(fitness_request_chromo(fitness, "time")) return -1;
if(fitness_request_chromo(fitness, "class")) return -1;
if(fitness_request_chromo(fitness, "teacher")) return -1;
fitness_request_slist(fitness, "time");
return(0);
}
Il y a trois appels de fonctions dans module_init() que nous n'avons pas encore abordés.
La première est l'appel à handler_res_new(), qui enregistre un nouveau gestionnaire de restriction de ressource dans le noyau. Elle peut être utilisée un peu de la même manière que handler_tup_new():
le premier argument est le nom du type de ressource pour lequel cette restriction doit être appliquée. Le second argument est le nom de la restriction et le troisième est un pointeur vers la fonction de gestion (handler).
Note: Vous pouvez passer un pointeur NULL au lieu du nom du type de la ressource comme premier argument de
handler_res_new()function. Dans ce cas, la restriction sera appliquée pour tous les types de ressources.
La deuxième nouvelle fonction est precalc_new().
Elle enregistre simplement une fonction, dans le module, qui sera appelée après tous les gestionnaires de restrictions. Cette fonction sera utilisée par exemple pour faire une vérification des structures de données (sanity check) utilisées par le module et avertir l'utilisateur si le problème semble impossible à résoudre. Elle peut également servir à précalculer les "look-up tables" qui pourraient être utiles à la fonction d'ajustage (comme les "look-up tables" sont calculées une seule fois, il est souvent sensé de déplacer une partie du code de la fonction d'ajustage vers la fonction de précalcul).
Note: Le prototype de la fonction de précalcul est exactement le même que celui de la fonction
module_init(). Cependant, l'argumentmoduleoption*optest toujours NULL. Le pointeur vers la liste chaînée des options du module est seulement passé à la fonctionmodule_init().
La fonction de précalcul obéit à la même règle que la plupart des autres fonctions de Tablix : retourne 0 en cas de succès et -1 en cas d'erreur.
Finalement, il y a un appel à la fonction fitness_request_slist() qui demande une slist. Le premier argument est un pointeur vers la structure de fonction d'ajustage et le second est le nom du type de ressources variable pour lequel la slist doit être générée. Si vous demandez plus d'une slist pour une seule fonction d'ajustage, alors les slists seront passées dans le même ordre que les appels fitness_request_slist() .
La fonction getconflict() est assez simple. Elle réunit deux identifiants de ressources : l'identifiant de la ressource pour laquelle l'appel a été fait (le pointeur res1 pointe vers sa structure resource ) et l'identifiant de la ressource dont le nom a été passé en argument. Elle utilise ensuite la fonction res_set_conflict() deux fois pour marquer ces deux ressources comme conflictuelles.
Cette fonction d'ajustage vérifie si deux professeurs en conflit ou deux groupes d'étudiants en conflit sont programmés pour le même cours (évènement) en même temps. Comme une ressource entre toujours en conflit avec elle-même, cela signifie aussi que la fonction d'ajustage vérifie si un groupe ou un professeur doivent être au même moment dans deux cours différents.
En premier, nous enregistrons tous les pointeurs vers les chromosomes demandés et une slist dans des variables locales. Comme une seule slist a été demandée, elle est en première place dans le tableau s .
La première boucle parcourt tous les évènements définis (l'identifiant du tuple courant est enregistré dans m). Pour chaque évènement, nous obtenons le créneau horaire qu'il utilise et enregistrons son identifiant de ressource dans a.
La seconde boucle parcourt le aième tableau de la slist. Nous avons demandé une slist pour le type de ressource "time", cela signifie donc que cette boucle parcourt tous les identifiants de tuples des évènements qui utilisent le même créneau horaire que l'évènement contenu dans m. L'identifiant de tuple du second évènement est enregistré dans b.
La condition du "if" est nécessaire pour sauter les comparaisons d'évènements qui ont déjà été faites (sans cela, tous les évènements seraient comparés deux fois).
Le code dans la boucle interne incrémente le compteur d'erreurs sum si deux professeurs ou deux groupes d'étudiants en conflit sont programmés dans deux salles différentes au même moment.
res_get_conflict() est une macro. Le premier argument doit être un pointeur vers la structure de type de ressource. Le second et le troisième argument sont les identifiants des ressources qui doivent être vérifier pour un conflit. La macro vaut 1 si la première ressource entre en conflit avec la seconde ou 0 autrement.
| Précédent | Sommaire | Suivant |
| Matrices, domaines | Niveau supérieur | Extensions d'emplois du temps |