FET FAQ:
--------
Q: What is the organization of FET input data?
A: - Students - organized into sets (years, containing groups, containing subgroups).
- Teachers.
- Subjects (the names of the possible courses, eg. Maths, Physics, etc.).
- Rooms (classrooms).
- Activities: a coupling of one or more teachers, a subject and one or more students set. This is usually named a course, a lecture, a laboratory and so on.
- Constraints. They can be: time constraints (referring to the allocated day and hour) or space constraints (referring to rooms allocation). They can also be compulsory or non-compulsory. ConstraintBasicCompulsoryTime and ConstraintBasicCompulsorySpace are two implicit constraints of any timetable. They are added automatically. Also automatically added are ConstraintActivityPreferredTime, added by FET when a new activity is inserted. Each constraint has a weight. The implicit constraints have the weight 1.0. You can choose the weight of the other constraints and you are encouraged to play with that. How to calculate the conflict factor of a constraint? Basically, the number of conflicts, multiplied with 1 for biweekly activities and with 2 for weekly activities, and then multiplied with the weight.
PS: Please try to work with integer weights, for now (between 1 and 100).
New adding: the FET data set also may contain a list of equipments and a list of subject tags.
-------------------------------------------------------------------------------
Q: How does FET work?
A: A really simple genetic algorithm. You can read my papers (available on my web site - http://lalescu.ro/liviu/fet/) about it.
The essence (hour allocation only): each possible timetable is represented by an array, say times[i], where i goes from 0 to the number of activities - 1. The location times[i] represents the allocated time for activity i. This is the representation.
Now, it applies a genetic algorithm (using notions like selection, crossover, mutation, etc.) to obtain a close to optimal solution (hopefully).
-------------------------------------------------------------------------------
Q: How can I obtain a good timetable and why do I get different results each time?
A: The generation of the timetable is a random process; please restart and try again if you are dissatisfied with the results. Also, you can increase the population number. For the moment, the population number is limited to 8192 but, if you have plenty of RAM, you can make it as big as you want (8192 means about 160 megabytes of memory). This variable is stored in the file src/engine/genetictimetable_defs.h and is named MAX_POPULATION_NUMBER.
NEW ADDING - 18 Oct. 2004: you can decrease the variable MAX_ACTIVITIES to the number of activities you have in your school, then increase MAX_POPULATION_NUMBER. I have achieved results with MAX_ACTIVITIES set to 400 and MAX_POPULATION_NUMBER set to 65536. These variables can be found in the file src/engine/genetictimetable_defs.h. Please run a "make clean" before running "make" (there is a bug in gcc, I think).
NEW ADDING - 14 Feb. 2005: The variable MAX_ACTIVITIES is now set by default to 1250, and MAX_POPULATION_NUMBER to 8192.
-------------------------------------------------------------------------------
Q: What is the structure of the students FET can handle?
A: FET was designed to allow any school structure:
- independent subgroups (non-overlapping);
- overlapping groups (several subgroups) and years (several groups).
-------------------------------------------------------------------------------
Q: How can one work with overlapping structures of students?
A: If you have overlapping groups, then you must define the smallest independent subgroup, which does not overlap with any other subgroup. Example: you have 1 group, subject sport (which must be taught to boys and girls separately) and subject physics, which is an optional subject and only some students would like to have this course (yes, FET can manage optional subjects). Then, you must define the subgroups: boys who want physics, boys who do not want physics, girls who want physics, girls who do not want physics. Now, it is very easy. Just define
group girls=subgroup girls who want physics + girls who do not want physics,
group boys=subgroup boys who want physics + boys who do not physics
group physics=boys who want physics + girls who want physics.
Then, you can add as many activities as you want to the corresponding groups:
Activity1: teacher A, group girls, subject sport;
Activity2: teacher B, group boys, subject sport;
Activity3: teacher C, group physics, subject optional physics.
-------------------------------------------------------------------------------
Q: Can you add more students sets or teachers to a single activity?
A: Yes, you can add several students sets (subgroups, groups or years) and several teachers per activity.
NEW ADDING - 18 Oct. 2004: The interface permits only 3 teachers and 4 students sets per activity. But you can edit by hand the input file and add there as more as 6 teachers per activity. Nobody asked me for more than 6 teachers and 4 students sets.
-------------------------------------------------------------------------------
Q: What represents the weight of the constraints?
A: The importance of the respective constraint, relative to other constraints. For the moment, please try to use integer weights (between 1 and 100). I never had to use different values than 1, but you might need that.
-------------------------------------------------------------------------------
Q: How can I increase the power of search?
A: You will have to increase the population number.
-------------------------------------------------------------------------------
Q: What means bi-weekly activity?
A: An activity which takes place once at two weeks (maybe this concept is not usual, but I considered it from the beginning because my faculty needed that).
-------------------------------------------------------------------------------
Q: Why are all the conflicts reported with double importance?
A: Because they are conflicts referring to weekly activities. For biweekly ones, they will appear with single importance.
-------------------------------------------------------------------------------
Q: How can I contribute to/support FET?
A: Please see the TODO file. Also, you can send any comment/suggestion to the author.
FET is free software and any donation would be great. Please contact the author for that.
-------------------------------------------------------------------------------
Q: What is the algorithm behind FET?
A: A simple genetic algorithm applied on a simple data representation.
In the future, I hope I will put here some real description of the algorithm. Until then,here are different tricks needed to understand the program:
- The genetic algorithm and representation behind the program looks very simple to me now and I think it can be explained in at most 2 hours. The engine is also not so hard to understand. The nightmare is the graphical user interface, data representation and loading/saving part.
- Time (hours) and space (rooms) allocations are 2 similar phases. You must read my paper to see the reasons why you can firstly allocate the hours and then the rooms.
- I use for the teachers, subjects, students (years, groups, subgroups), activities and constraints a QPtrList. Before starting the simulation, all this information is copied into some arrays, to speed up the computation. Now, the simulation works by considering each teacher, subject and activity an index in these new arrays (the timetables are represented as matrices, indexed by the the teacher (students, rooms), day and hour, and have integer values, which represent activity indices (indices in this second copied arrays).
- I used int16 sometimes just because of the memory consumption
- With 8192 maximum population and 2500 maximum activities, class GeneticTimetable has the size of about 160 megabytes (I hope I remember well). In fact, it contains an array of 2500*8192*2*2 of 16 bit integers, which is ~160Mb of memory.
Modification (21 Feb. 2005) - with 8192 population size and 1250 activities the class Rules has size of ~160Mb.
-------------------------------------------------------------------------------
Q: Could you please detail the use of weights in constraints?
A: The weight of any constraint can be a real number (double). BUT: I preferred that any return value of a constraint to be an integer, which is this real value rounded up to the nearest integer (reasons of speed). For the moment, please try to work with integer weights (between 1 and 100).
-------------------------------------------------------------------------------
Q: Could you please explain why FET works in two phases, first the time, then the space?
A: For reasons of speed. But in the two phase allocation the first phase might find solutions that are not compatible with the second phase (for example, working with the sample number 12, from Marek Jaszuk, will not yield perfect solutions for the second phase, although there exists a perfect solution, found manually.
There are two solutions: 1) FET to work in a single phase (but the time will be a bit longer) or 2) add some time constraints so as the solution to the first phase will always respect all the space constraints (very complicated: all the constraints might be compulsory or non-compulsory and the execution time is very long).
This is a research problem.
-------------------------------------------------------------------------------
Q: How does ConstraintActivitiesSameStartingTime work?
A: - for compulsory constraints, the solution candidate is repaired before evaluation (so all solutions will respect these constraints and there will be no conflicts reported). This is faster, as an input file from user Ian Fantom proved.
- for non-compulsory constraints, the method is conflict reporting (slower, worse than the above method).
-------------------------------------------------------------------------------
Q: How does ConstraintActivityPreferredTime work?
A: - for compulsory constraints, the solution candidate is repaired before evaluation (so all solutions will respect these constraints and there will be no conflicts reported). This is faster (proved practically, not theoretically).
- for non-compulsory constraints, the method is conflict reporting. The procedure reports a conflicts factor that is increasing with the distance to the desired period. This might generate worse solutions, if you are only interested in the exact placement. In this case, please use ConstraintActivityPreferredTimes with only one preferred time.
Example: 5 days per week
5 activities daily exclusive
activity 1 - preferred on monday
activity 2 - preferred on monday
activity 3 - preferred on tuesday
activity 4 - preferred on thursday
activity 5 - anytime
The best solution will contain 2 conflicts, and a possible solution would be:
act 1 - mon
act 2 - tue
act 3 - wed
act 4 - thu
act 5 - fri
If you use ConstraintActivityPreferredTimes, you will get only one conflict:
act 1 - mon
act 2 - wed
act 3 - tue
act 4 - thu
act 5 - fri
-------------------------------------------------------------------------------
Q: What advantages has FET over other applications?
A: - It is free software
- Supports weekly and biweekly activities (my university of Craiova, Romania, needed that);
- Independent subgroups, overlapping or independent groups, overlapping or independent years (flexible enough to permit any kind of students structure). FET can even be used to manage every individual student, if you really need that;
- Possibility of optional activities;
- Many kinds of constraints, possibility to add many more (please suggest!).
-------------------------------------------------------------------------------
Q: What are the disadvantages of FET, compared to other applications?
A: - Very unfriendly (no help, primitive graphical user interface);
- Potentially buggy. I do not have enough sample files for testing FET (and I hate testing :-)
-------------------------------------------------------------------------------
Q: Does FET compile on other operating systems than GNU/Linux?
A: FET can be compiled easily in operating systems which are similar to GNU/Linux. I will provide help to compile this program on any operating system. In particular, FET can be compiled on Microsoft Windows, if you install Qt from trolltech.com.
-------------------------------------------------------------------------------
Q: Does FET claim to be the best timetabling software in the world, like all the other timetabling applications?
A: I cannot pretend that, because I could not compare FET with other applications (if you could help me, that would be great). All I can say right now is that I did not see any application with as many kinds of constraints and such flexibility as FET, and besides being free software.
Is FET the first free timetabling software (GNU/GPL)? Hmmm... the first one was Tablix, as I found out after finishing FET. You can see links to this software if you look in the LINKS file or if you search it on the internet.
-------------------------------------------------------------------------------
Q: What is the difference between unallocated and random initialization? Which one is better?
A: This means the method of initializing the population of solution candidates. It seems (practical results) that unallocated initialization is better. I have not read about unallocated initialization anywhere, but it seems to me more natural and I have an empirical explanation somewhere on my thesis.
-------------------------------------------------------------------------------
Q: Help on ConstraintMinNDaysBetweenActivities.
A: It refers to a set of activities and involves a constant, N. For every pair of activities in the set, it does not allow the distance(in days) between them to be less than N. If you specify N=1, then this constraint means that no two activities can be scheduled in the same day. N=2 means that each two subactivities must be separated by at least one day
Example: 3 activities and N=2. Then, one can place them on Monday, Wednesday and Friday (5 days week).
Example2: 2 activities, N=3. Then, one can place them on Monday and Thursday, on Monday and Friday, then on Tuesday andFriday (5 days week).
-------------------------------------------------------------------------------
Q: Is it easy to add new constraints to FET?
A: It is very easy. I can say that I am able to implement a new constraint in a matter of hours. You can find a description of this procedure in file /.../fet-x.x.x/doc/how-to-implement-new-constraints
-------------------------------------------------------------------------------
Q: Help on ConstraintStudentsEarly.
A: It is a constraint that imposes the condition that all the students must begin their courses as early as possible. You have to be careful with this constraint: if any set of students begins the classes later than the first hour in a certain day, you
will get a conflict.
-------------------------------------------------------------------------------
Q: FET fails to solve my timetable.
A: Please try to use a greater population size. Then, try more simulations. If that does not solve your problem, please try to relax the conditions on the timetable. You can accomplish that by deleting compulsory constraints or by making them non-compulsory
-------------------------------------------------------------------------------
Q: Do the weights have any importance? What is the best way to choose them?
---The comment below was written when FET used only mutation which randomized an activity's starting time.
A: Yes, the weights are important, but unfortunately I cannot answer to the second question.
I can justify the first affirmation by an example: the considered file is named (for the moment) sample4. As it is right now, it is a good example of a very constraint timetable, difficult to schedule by FET. The weights are chosen such that the basic constraints have a smaller weight than the constraint avoiding the gaps for the students. I think that after about 4 tries, FET manages to find a clash-free timetable (I am only referring to compulsory constraints). There was no trial in which FET failed with more than 3 compulsory constraints conflicts (usually 1).
I wanted to impose the more important basic constraints, so I raised their importance (weight) and lowered the weight of the gaps constraints. The results came as a very unpleasant surprise for me: I never obtained less than 3 conflicts, with an average of 6. What conclusions can be derived: I am currently thinking and analysing this issue. Until someone will come up with a plausible explanation, I think that: the weights of the constraints are influencing the conflicts function. The function can have more or less local minima (which are a headache for genetic algorithms designers). You are encouraged to play with different weights.
New comment: FET-s algorithm favorises the one-mutation transitions, that is, from a candidate solution you obtain a new candidate solution with a single activity rescheduled. The old candidate solution and the new one must have a good fitness, to be preferred in the evolutionary process. Basic constraints are more likely to be respected by this mutation, whereas gaps constraints require more mutations and the intermediary candidate solutions are not so fit and therefore the chances are lower of finding the good solution.
---The comment below was written after I chosed to introduce also the second kind of mutation, a swapping of two random activities. This swapping was very benefical, and now the results are the same, regardless of the weights (I am only referring to the above example). The reason is that this random swap helps FET transform a candidate solution which does break gaps constraints into a candidate solution which does not.
-------------------------------------------------------------------------------
Q: Can I use FET to do interactive timetabling?
A: Yes, but this is not easy. All the part regarding data representation and gradually construction of the solution is working, only the interface has to be updated.
Anyway, when you add a compulsory ConstraintActivityPreferredTime, it means that you fixed that activity. You can use this feature for a semi-automatic or even manual timetabling, but it is not so convenient.
-------------------------------------------------------------------------------
Q: Help on ConstraintActivityPreferredTimes.
A: You can specify a set of time slots when this activity can be scheduled (a kind of OR of more ConstraintActivityPreferredTime).
Important: For only one non-compulsory preferred time, ConstraintActivityPreferredTimes might behave better than ConstraintActivityPreferredTime, depending on whether you are interested in minimizing the distance to this preferred time or only in reaching the exact preferred time. Please see the detailed observation in the explanation of ConstraintActivityPreferredTime
-------------------------------------------------------------------------------
Q: Help on ConstraintStudentsSetIntervalMaxDaysPerWeek.
A: Quite a difficult and long name. A user needed a constraint to disallow more than 2 afternoons per week for a students set. This constraint is more general. You can specify an interval (by the start and end hour), a students set and the maximum number of days in a week when it is permitted to have activities in this time interval.
-------------------------------------------------------------------------------
Q: Help on Constraint2ActivitiesConsecutive.
A: A user needed a timetable to respect the requirement that 2 activities follow one after the other (order is important). For compulsory and non-compulsory, normal error reporting is done. The conflicts are a difference in days + a difference in hours. The number of conflicts is multiplied with 2 if the first activity is weekly (not bi-weekly) and again multiplied with 2 if the second activity is weekly.
->added - 15 May 2004.
->modified - 20 February 2005.
-------------------------------------------------------------------------------
Q: Help on Constraint2ActivitiesGrouped.
A: A user needed a timetable to respect the requirement that 2 activities follow one after the other (order is not important).For compulsory and non-compulsory, normal error reporting is done. The conflicts reported are: the difference in days+: - the difference in hours if the activities are too far from each other
- a constant number if the activities overlap
- 0 if the hours are OK.
The number of conflicts is multiplied with 2 if the first activity is weekly (not bi-weekly) and again multiplied with 2 if the second activity is weekly.
->added - 15 May 2004.
-------------------------------------------------------------------------------
Q: Help on ConstraintActivitiesPreferredTimes.
A: A user suggested that ConstraintActivityPreferredTimes should be more general. Now, you can specify a teacher, the students and a subject as a filter to a set of activities that must be scheduled in certain intervals.
->added - 15 May 2004.
-------------------------------------------------------------------------------
Q: After finding the timetable of our school, suppose that a single teacher needs to modify his timetable and the rest would like to keep their timetable unchanged. Thus, it is needed to fix all the activities of the rest of the teachers and re-allocate the hours. Can FET deal with such a situation?
A: Yes, FET can deal with that. Just add many compulsory ConstraintActivityPreferredTime-s, one for each activity that you would like to be fixed (the preferred time will be the one from the previous allocation). This will not slow down the allocation, because compulsory constraints of this type are dealt with in a special way (repairing of the chromosomes, to be more specific).
->added - 17 November 2004.
-------------------------------------------------------------------------------
Q: What about introducing duplicate constraints in the timetable data?
A: It will slow down the automatic allocation, so please don't.
-> added - 12 February 2005.
-------------------------------------------------------------------------------
Q: What about the one phase and 2 phases automatic allocation?
A: If FET fails to solve your timetable in 2 phases (it has many broken space constraints), try a single phase allocation
-> added - 14 February 2005.
this documentation by Liviu Lalescu