Timetable extensions

About extensions

Timetable extension is the third form of the timetable that can be passed to the fitness function. Its structure resembles a human-readable form of the timetable, like for example the output of the htmlcss export module. Because of that it is often the most convenient form to check for errors in timetables for human resources.

If you take another look at the API reference manual you can see that a timetable extension is defined by one constant resource type and one variable resource type (stored in con_typeid and var_typeid respectively). In comparison, slist is defined by only one variable resource type. Timetable data is stored in a two dimensional array of tuple IDs in the tupleid field. The first dimension goes from 0 to N-1, where N is the number of defined resources of the variable resource type var_typeid and the second dimension goes from 0 to M-1, where M is the number of defined resources of the constant resource type con_typeid.

If an event is using a resource n of type var_typeid and a resource m of type con_typeid at the same time, then its tuple ID will be stored in the e->tupleid[n][m], where e is a pointer to the extension struct. If no event is using this combination of resources, then the value stored in the array will be -1.

To better visualize this array of tuple IDs consider the following example from school scheduling. Let's say that we choose teachers as the constant resource type and time slots as the variable resource type. Also, since we are looking at a school timetable, time slots are in a form of a matrix with five days and three time slots per day.

Tuple IDs stored in the array represent events (in this case lectures) that are scheduled for this teacher at the specified time. If no event is scheduled for a certain teacher at a certain time slot then the value in the array will be -1.

It should be obvious now that an extension only represents a whole timetable if there is a one-to-one mapping of events to constant-resource/variable-resource pairs (i.e. no two events are using the same combination of the constant resource and variable resource of the chosen types). If this is not true than some events lost when converting a timetable from the chromosome format to the extension since only one tuple ID can be stored at one position in the tupleid array. In this case a random event will be chosen from the group of conflicting events and its tuple ID will be stored in the array.

Because of this limitation almost all modules that are using timetable extensions only work correctly when they are used together with a module (set to mandatory) that prevents this loss of events from happening. In school scheduling this is the role of the sametime.so module.

It was mentioned above that extensions are the only part of the kernel that is using the information about resource conflicts. Conflicting constant resources are handled as a single resource in this case. Conflicts in variable resources are ignored. This means that if a constant resource m1 conflicts with a constant resource m2 then events for both m1 and m2 will show in e->tupleid[x][m1]. On the other hand only events for m2 will show in tupleid[x][m2] (kernel treats conflicts asymmetrically, remember?).

holes.so module source code

holes.so fitness module is used in school scheduling and similar timetabling problems and searches for so called holes in the timetable. A hole in a timetable for a certain constant resource is defined as one or more free time slots in a day (time slots that aren't used by any event that uses this constant resource) surrounded on both sides (before and after on the same day) with non-free time slots.

Example 1: Timetable with three lectures in the middle of the day is considered without holes. Example 2: Timetable with one lecture in the morning, then a pause for two time slots and then two lectures is considered to have one hole that is two time slots wide.

Holes are in most cases annoying since they mean that for example a teacher or a group of students must wait for an hour between lectures. In some cases they are even forbidden by various regulations.

Following is an excerpt of the holes.so module. Full source code is included in the 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);
}

Module initialization

Since this module is intended for use in school scheduling, we expect the "time" resource type to be a matrix (width of the matrix is equal to the number of days in a week and height is equal to the number of time slots per day). We store the dimensions in days and periods global variables (we will use them later in the fitness function).

The "while" loop that follows iterates through all module options with name "resourcetype". With this option user can specify constant resource types that will have their timetables checked for holes (for example teacher, classes, etc.)

First we try to find the pointer to the first option by using the option_find() function (option_str() function can't be used if you expect more than one option with the same name - see API documentation). If we can't find even one option with this name (option_find() returns NULL), then this module isn't affecting the timetable solution and we can report a warning.

From the standpoint of the kernel we define a new fitness function for each such option. In reality we define a single fitness() function multiple times. Each time with a new name that includes the name of the resource type and each time we request a different timetable extension with fitness_request_ext(). This means that for each timetable evaluation our fitness() function will get called one or more times, depending on the number of "resourcetype" options the user supplied.

fitness_request_ext() is used in much the same way as fitness_request_slist() or fitness_request_chromo(). First argument must be a pointer to the fitness function structure, the second and the third argument are the names of the constant and the variable resource types respectively. Here, we request an extension with a constant resource type supplied by the user and "time" variable resource type.

Fitness function

Fitness function of this module is a bit more complicated than the previous ones. Our requested extension is stored in e and the number of defined resource of the chosen constant resource type is stored in connum (we obtain this number from the extension structure, since we don't know for which constant resource type this instance of fitness() was called for).

The outer most loop iterates con_resid through IDs of all defined constant resources. Since holes in the timetable are determined on a day basis, we also have a second loop that iterates through all days. var_resid holds resource ID of the current time slot.

The inner most loop iterates through all time slots in a day and determines: 1) period (y coordinate in the matrix) of the first non-free time slot first on this day, 2) period of the last non-free time slot last and 3) number of non-free time slots on this day.

If there are no non-free time slots (last is equal to -1), then by definition there are also no holes in the timetable for this day. If there are non-free time slots then the number of holes can be calculated by a simple formula: number of time slots between the first and the last time slot minus the number of non-free time slots equals the number of holes. The calculated number of holes for the current day is added to the error sum sum

Discussion

Timetable extensions are very computationally expensive. In most cases they are more expensive than slists. The discussion about slists is therefore also applicable for extensions.

The time required to calculate the extension depends on the number of defined constant and variable resources. It also depends on the use of conflicts in the specified constant resource type. If the timetable has non-trivial conflicts defined in the constant resource type (if any resource conflicts with a resource other than itself) then extensions take longer to compute.