Slist is a special representation of the timetable that can be requested by module_init() function. In that case it is calculated by the kernel and passed to that module's fitness function.
Often a fitness function must calculate a list of events that are using a certain resource of a certain resource type (the most common example is to check if two events are using the same resource). This check can be very time consuming if performed on a chromosome form of the timetable but can be performed an order of the magnitude faster if you first translate the timetable from a chromosome form to a slist form. Because it would be a waste CPU cycles and memory if each module would preform this translation by itself, the kernel calculates a slist only once and then passes a pointer to all modules that requested this slist.
If you take a look at the API reference manual, you will see that a slist structure consists of varnum arrays, each array holding zero or more tuple IDs. varnum is equal to the number of resource in the chosen resource type (its ID is stored in var_typeid). The Nth array holds the tuple IDs of all events that are using the resource with resource ID equal to N and resource type ID equal to var_typeid.
Note: As you can see, the number of possible slists that can be generated for a certain timetable is equal to the number of defined variable resource types in that timetabling problem. In practice only one or two slists need to be generated. Also note that it is possible to generate a slist for a constant resource type, however there are no practical uses for such slists.
Unlike chromosomes, slists take some time to generate. However once a slist is generated (for a certain resource type) then almost no additional processor time is required to pass the pointer to the generated slist to two or more modules. So, use a slist if you know that this same slist will be requested by another module used by the timetabling problem and that its use will result in a small speed-up of your fitness function. On the other hand if the use of the slist will result in a major speed-up (for example from O(n^2) to O(n) time) then use the slist in any case.
The use of conflicts somewhat depends on the agreement of authors of a certain group of modules. The kernel merely provides a mechanism of tagging which resource conflicts with which by exporting two functions: res_set_conflict() and res_get_conflict(). The only part of the Tablix kernel that uses this information is the generation of timetable extensions.
Note: A resource always conflicts with itself. By default no resources conflict. Modules can then only set conflicts between resources and can not unset them.
For example in school scheduling conflicts are used with constant resource types (in this case groups of students and teachers). Two events that are attended by two conflicting groups of students can never be scheduled at two places at the same time. Same with two conflicting teachers.
The kernel treats conflicts asymmetrically. This means that resource 1 can conflict with resource 2 while at the same time resource 2 does not conflict with resource 1. Most timetabling problems however need symmetrical conflicts (for example school scheduling). This means that when setting a conflict between two resources, you must call res_set_conflict() twice (second time with reversed order of the arguments).
Conflicts are treated as not transitive in the kernel, which means that if resource 1 conflicts with resource 2 and resource 2 conflicts with resource 3, this does not mean that resource 1 conflicts with resource 3. Some modules can however treat conflicts are transitive.
Following is the important part of the sametime.so module source code (full source is available in the distribution). You should be familiar with most of of the function calls in it by now.
If you are not familiar with the function of this module (it is one of the standard modules used in school scheduling) have a look at the Module reference documentation.
int getconflict(char *restriction, char *cont, resource *res1)
{
resource *res2;
res2=res_find(res1->restype, cont);
if(res2==NULL) {
error(_("invalid resource in conflicts-with restriction"));
error(_("resource: %s resource type: %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);
}
There are three function calls in the module_init() function that we haven't discussed yet. First one is the call to handler_res_new(), which registers a new resource restriction handler in the kernel. It can be used in much the same way as handler_tup_new(): first argument is the name of the resource type to which this restriction can be applied. Second argument is the name of the restriction and the third argument is a pointer to the handler function.
Note: You can pass a NULL pointer instead of the resource type name in the first argument of the
handler_res_new()function. In that case the restriction will be registered for all resource types.
The second new function call is precalc_new(). This simply registers a function in the module that will be called after all restriction handlers. This function can be used for example to perform a sanity check on any data structures used by the module and give a warning to the user if the problem looks unsolvable. It can also be used to precalculate any look-up tables that may be needed by the fitness function (since look-up tables are calculated only once, it often makes sense to move as much code from the fitness function to the precalculate function).
Note: The prototype of the precalculate function is exactly the same as that of the
module_init(). However themoduleoption*optargument is always NULL. Pointer to the module options linked list is only passed to themodule_init()function.
Precalculate functions obey the same rule as most other functions in Tablix: return 0 if successful, or -1 on error.
Finally there is a call to fitness_request_slist() function that requests a slist. The first argument is a pointer to the fitness function structure and the second argument is the name of the variable resource type for which the slist should be generated. If you request more that one slist for a single fitness function then slists will be passed to it in the same order as the fitness_request_slist() functions were called.
The getconflict() function is quite simple. It gathers two resource IDs: ID of the resource it was called for (pointer res1 points to its resource structure) and the ID of the resource whose name was passed to it as an argument. Then it uses the res_set_conflict() function two times to tag these two resources as conflicting.
This fitness function checks whether two conflicting teachers or two conflicting groups of students are scheduled to have a lecture (event) at the same time. Since a resource always conflicts with itself, this also means that the same fitness function checks whether a group or a teacher must be at the same time at two different lectures.
First, we store all pointers to requested chromosomes and a slist to local variables. Since only one slist was requested the pointer to it is in the first place in the s array.
The first loop goes through all defined events (current tuple ID is stored in m). For each event we get the time slot it is using and store its resource ID in a.
The second loop iterates through the ath array in the slist. We requested a slist for the "time" resource type, so this means that this for-loop iterates through all tuple IDs of events that are using the same time slot as the event in m. The tuple ID of the second event is stored in b. The if conditional is required to skip those event comparisons that were already made (without it all events would be compared twice).
The code in the inner loop then increments the error counter sum if two conflicting teachers or student groups are scheduled at different rooms at the same time.
res_get_conflict() is a macro. The first argument must be a pointer to the resource type structure. The second and the third argument are resource IDs of resources that should be checked for a conflict. The macro evaluates to 1 if the first resource conflicts with the second or 0 otherwise.