The quality of an automatically constructed timetable is measured by how convenient it is for the involved individuals and by how well it utilizes the available resources. The parameters which define these criteria are called Constraints.
There are many kinds of constraints which the program supports and we have, in fact, already seen some of them in the previous chapters. That's because some constraints are fundamental and are taken under account even during the interactive timetabling process whereas others are optimizational constraints and are considered by the software only during the automatic construction.
But before we get to the new type of constraints, let's go over the ones we have learned about in the previous chapters so that we have a clear list of all the constraints which are considered during automation in one place.
All the constraints in this chapter are considered during automation, but the ones that are listed in this section were entered in the "Timetable" tab (as explained in previous chapters) and not in the "Constraints" tab. Let's get a reminder of what they were.
Note: All the constraints described in this section are considered as mandatory constraints by the software in the Automatic mode. The program will never suggest a timetable in which any of these requirements is not met.
Length Of Activity
As you remember, each activity can be assigned a Length attribute in the activities' list:
The length is the number of periods the activity should occupy consecutively each time it is scheduled. In the Interactive mode, when you drag-and-drop an activity with a length of "2", for example, into the timetable, you will be dragging a two-cell activity. In the Automatic mode, the program does exactly the same thing - it always schedules such an activity on 2 consecutive periods.
Multiple Resources Per Activity
Another important reminder: each activity can involve multiple resources of the same type (by placing a check mark near all these resources when you are filling in the activity's properties):
For example, one activity can involve two teachers; or three groups; or two teachers and three groups. Such an activity will appear in all the involved resources' timetables and will only be scheduled at a time slot when they are all free.
Sets make it possible to bundle together several separate activities which need to be scheduled at the same time. Sets are created in the activities' list and stand out from the rest of the activities by having a color and a folder-like shape:
Each activity in a Set can involve different resources such as groups and teachers, yet when they are united into a Set, they become one inseparable unit and are always scheduled simultaneously by the automatic engine.
Multiple Possible Rooms Per Activity
Naturally, when an activity can be scheduled in several possible rooms, it gives the program more flexibility during the automatic timetabling. As described before, the potential rooms in which an activity can be scheduled can be listed in the activity's Room property, while changing the inscription at the bottom of the list from "All the selected resources" to "Any of the selected resources":
When an activity has several possible rooms as above, the program will automatically choose one of them during the timetable construction. Note that different cells of the same activity may be scheduled in different rooms.
Distances Between Rooms and Buildings
When the time that is needed to travel from one room (or building) to another is significant, the program is required to leave a gap of one period (or more; depending on the travel time) between two consecutive activities that belong to the same person (teacher or student) or group, and that are scheduled in those two rooms. As described in the "Resources" chapter, the distances between rooms and buildings are set in the Properties pane:
When the room distances are specified, the program will always check the start and end times of periods to make sure that no two activities are scheduled one after the other so that there is not enough time to travel from the first activity's room to the second, given the gap between the end time of the first activity's period and the start time of the second activity's period.
Quantity Of Equipment In Stock
As you remember, the total number of items of a certain kind of equipment in stock is defined in the equipment's properties:
This quantity creates a limit on the number of activities which use that equipment that can be scheduled at the same time slot. For example, suppose an activity requires a single projector:
In such case when there are only 2 projectors available in stock, the program will never be able to schedule 3 activities which require a single projector at the same time slot.
Needless to say, that teachers, students and groups cannot be double booked (that is unless they are intentionally part of a Set). This may sound obvious, but we are reminding this because it is actually one of the most constraining aspects of timetabling.
As explained in the Interactive Timetabling chapter, the days and periods at which a resource (or an activity) are not available for scheduling can be blocked out by selecting the relevant cells and choosing "Edit", "Block" in the main menu. A resource's blocked cell prevents the program from scheduling any activities which involve that resource at that cell.
An activity that is scheduled in the interactive mode and fixated (by selecting "Edit", "Fixate" in the main menu), will not be "touched" during the automation. This is very useful when you know in advance that a certain activity must take place at a certain day and period or when you think that would be the best way to schedule it.
Now that we got a reminder of the software's fundamental constraints, we can explore the constraints which are used to optimize the timetable. Each kind of constraint is responsible for a different aspect of the timetable. Let's go over their types and understand what each one means.
Cells Per Day
The constraint Cells per day sums up the number of scheduled cells on one day in some resource's timetable:
There are two common use cases for this constraint. One, it allows you to spread the activities evenly across the week. For example, suppose a teacher has 10 activities to be scheduled; by setting the maximal cells per day to "2", you can force the program to schedule the teacher's activities on all 5 days because no day would be permitted to have more than 2 scheduled activities.
The second use case is related to subjects. It allows you to make sure a subject is not scheduled too many times on the same day in any group's timetable. For example, given that "Physical Education" needs to be scheduled 3 times a week, we don't want it to be scheduled more than once a day. This is accomplished by setting the maximal cells per day for the subject "Physical Education" to "1".
A Gap is a free cell in the middle of the day, before which there is some activity scheduled and after which there is also some activity scheduled:
The number of gaps on any single day is summed up by the "Gaps per Day" constraint and the total number of gaps during the entire week is summed by the "Gaps per Week" constraint. There is one additional constraint related to gaps which is called "Gap Size" which sums up the number of consecutive free cells and allows to limit that number.
The most common use case for constraining the number of gaps is to prevent idle time in between activities for teachers, groups and students. For example, if a teacher is scheduled on the 1st period and then only on the 7th period, he/she has 5 gaps (5 idle periods). On many occasions this may be uncomfortable for the teacher. In such cases, by setting the maximal number of gaps per day to 2, for example, the program will be encouraged to schedule all the teacher's activities no more than 2 idle periods apart.
A Late Start is a free cell or a series of several free cells at the beginning of the day. There are no scheduled activities before a late start but there are activities scheduled after it. For example, if a teacher does not teach anything on the 1st period, but has an activity scheduled on the 2nd period, he/she has a "Late Start".
We have two types of constraints here: "Late Starts per Week" which sums up the number of free cells a resource has at the beginning of a day throughout the entire week, and "Late Start Size" which sums up the number of consecutive free cells at the beginning of any day. The first constraint makes it possible to limit the number of times a resource starts his/her day later than the 1st period (e.g. no more than 3 late starts per week) and the second one to limit the length of the allowed late start (e.g. no more than 2 periods).
This constraint allows you to specify the range of periods on which a resource or an activity should be scheduled. For example, to tell the program that a resource's activities should be scheduled only on periods 1-4, you can enter "1" as the minimal value for that constraint and "4" as the maximal value.
Note: If the periods in your school start from "0" or are named differently than "1", "2", etc., you still need to enter positive numbers as the constraint minimum/maximum values. That's because after you enter a number, the program maps that number to the relative period's number. For example, "1" is mapped to the first period in the list, "2" to the second period and so on.
This constraint sums up the number of consecutive periods at which any activity is scheduled:
The most common use case for this constraint is to limit the maximal length of a series of activities in some resource's timetable. For example, by setting the maximal value of some teacher to "3" you can ask the program that the teacher is not scheduled for more than 3 consecutive periods in a row. In such case the program would be forced to leave a free period after the 3rd cell.
Entry of Constraints
In order to enter optimizational constraints, first you need to switch to the Automatic mode by clicking the button named "Automatic" at the bottom right corner of the screen:
Once you are in the Automatic mode, you will see a tab named "Constraints" at the right hand side of the workspace (near the "Violations" tab).
Clicking the "Constraints" tab will display the constraints entry pane:
How to select the type of the constraint?
The Constraints pane also has a "navigational pane" at the top. The first selector there is where you choose the type of the constraint, while the rest of the buttons allow you to select the type of the resources for which you will be entering the constraint values:
After selecting the type of the constraint, you will see a list of all the resources of the selected type with 4 additional columns at the left hand side of the list: "Min.", "Max.", "Desr." (i.e. "Desirable") and "Viol." (i.e. "Violation"):
What are the Min, Max and Desirable columns?
As we have seen above, a constraint is basically a mathematical formula which counts something. That's why if we look at any resource's timetable from the point of view of a specific kind of constraint, that formula always produces a single number. For example, if we are counting the number of weekly gaps in some resource's timetable we will come up with a number. Of course, each resource's timetable will produce a different number. That's why when we are defining the constraints, we will be defining different limits for each resource.
Since every constraint's formula produces a number, what is left for us to do is to put a limit on that number. Once we do, the program will aspire to generate a timetable in which all these limits are satisfied. We can define 3 types of limitations: minimum, maximum and a desirable value (or several desirable values). The minimum and maximum values are hard limitations (have higher priority) whereas the desirable value is a soft limitation (has lesser priority). It is not required to enter all the 3 values if not necessary.
To enter a value, just type it in one of these fields. All fields are optional so you can type only a minimum, or only a maximum or minimum and desirable etc.:
How to enter several Desirable values?
The Desirable ("Desr.") column allows you to enter one or more desirable values. A desirable value has a lesser priority than the values defined by the Min/Max range. This means that if the program considers a way to improve the timetable in order to reach a desirable value on the account of breaking another constraint's Min or Max value, this option will not be applied. However, the desirable values do allow you to tweak the timetable's quality to a greater extent by providing you with a way to enter "nice to have" requirements.
The program supports not only a single desirable value, but also a range of values. This is accomplished by using a comma or a dash to specify multiple values. For example, suppose a certain subject should only be scheduled on periods 2-8, but the preferred periods are 3, 4, 5 and 7. To define this you can set the "Period Range" constraint for that subject to have a Min value of "2" and a Max value of "8", and in the Desirable field type: "3-5,7":
How to prioritize critical constraints?
There are 3 constraint priorities: "critical", "required" and "desirable". By default, the critical constraint is only the "scheduling" constraint, meaning that it is considered critical for the program to schedule 100% of the activities. The required constraints are the Min/Max values that you enter in the constraints list and the desirable are the values that you enter in the Desirable column in that list.
There is, however, a way to turn any "required" constraint into a "critical" constraint. This makes it clear to the program that it is absolutely vital to take care of that constraint – even in a higher priority than scheduling any other remaining activities. In a way, this affects the decision making process of the program during the automatic phase because the program does not even consider solutions in which that critical constraint is violated. In order to turn a "required" constraint into a "critical" constraint, you need to append the "!" symbol to the value in the Min or Max columns:
What does the Violation column mean?
If you click the Constraints tab while being in the Automatic mode, you will see an additional column next to the Min/Max/Desirable columns, named Violation ("Viol."). A value will appear in this column only for constraints which are unfulfilled (violated) in the current timetable. In such cases the value in this column will show either a negative or a positive number which indicates the difference between the value of the constraint in the current timetable and the nearest required (or desirable) value.
For example, if we set the maximal number of gaps per week to "3" for some teacher, yet the current timetable has 5 gaps, the Violation column for that teacher will have the value "+2", meaning that there are 2 gaps more than what was required. Another example – if the minimal number of cells per day for a group was set to "5" but the current timetable of that group has only 1 cell on each day of the 5-day week, the violation column will contain the accumulated value of "-20" because on each of the 5 days 4 cells are currently missing.
In case the violation is of the min/max range, it will be shown in a red color. If it's a violation of the desirable value, it will be displayed in an orange color:
Is it possible to modify constraints later?
It's important to emphasize that even if the timetable is already partially or almost fully constructed, you always have the option to modify the existing constraints (or add new ones) and then run the automation from that point. The program knows how to take the existing timetable as a starting point and automatically make the necessary adjustments to have it fulfill the constraints that you have modified.
In fact, this ability can be used as a useful technique to construct the timetable gradually because you can run the automatic engine multiple times. The reason this can be useful is because it is often very difficult to enter all the constraints correctly from the beginning. You may well find yourself looking at the resulting timetable after the first phase and saying something like "Oh, this also needs to be like this and that". In such cases you can always go back to the constraints entry and enter the additional constraints; or, you can make a manual change in the interactive mode, fixate it, and then run the automatic solver again. Doing these steps several times until completion is actually the recommended method of achieving the highest quality timetable.
How to prevent over constraining?
One last thing which is important to understand about constraints is how to avoid misusing them. You see, constraints are really a very delicate matter. Imagine that you have entered plenty of constraints into the program, and some are indeed important to you yet some are negligible or worse yet – totally unrealistic. If it were you constructing the timetable manually and gradually, you would have undoubtedly made the right decisions as you went along in order to satisfy the critical constraints as first priority. The automatic solver, on the other hand, does not possess your judgment logic. Its process of decision making is 100% based on the constraints that you have entered. If the solver faces a logical "junction" in which it needs to decide whether to make a change in the timetable in order to satisfy one constraint, but that change breaks another constraint (and they are both defined as Min/Max constraints, i.e. both have the same priority), the program will refrain from making that change (because it would seem disadvantageous to the program). If both constraints are indeed required, that is certainly the desired behavior. If, however, one of them isn't really necessary, we have a case of over constraining here which damages the program's ability to make the right decisions for you. So when you are entering constraints, please make sure to enter only the required and realistic constraints in the Min/Max values while using the Desirable value for the lesser priority "nice to have" constraints.
The next chapter: Automatic Timetabling.