Constraints

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.

Fundamental Constraints

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.

Simultaneous Activities

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.

Double Booking

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.

Times of Unavailability

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.

Fixated Cells

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.

Optimizational Constraints

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".

Gaps

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.

Late Starts

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).

Consecutive Cells

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.

Period Range

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.

Occupied Periods

This constraint sums up the number of periods (horizontally) on which any cell is scheduled. For example, if an activity has 5 cells, two of which are scheduled on the 1st period (say on Tuesday and Thursday), two of which are scheduled on the 3rd period, and 1 is scheduled on the 4 period, the activity is said to occupy 3 periods: 1st, 3rd and 4th:

The most common use case for this constraint is for limiting all the occurrences of an activity to be scheduled on the same period. For example, if we want all the cells of an activity to occupy the same period number (no matter which, but all should be on the same), we will set the maximal value of this constraint for that activity to be "1" (meaning it should occupy only one period).

Occupied Days

This constraint sums up the number of days (vertically) on which anything is scheduled in any resource's or activity's timetable. For example, if a teacher has 8 cells, 3 of which are scheduled on Monday, 3 on Wednesday and 2 on Thursday, it is said that there are 3 occupied days in that teacher's timetable: Monday, Wednesday and Thursday.

This constraint is usually used to limit the number of work days in teacher timetables. For example, when a teacher needs to have one day off in a 5-day timetable (and it does not matter which one), setting the maximal number of occupied days for that teacher to "4" basically tells the program to leave one day free.

Gap of Days

This constraint controls the number of free days (on which nothing is scheduled) between any two occupied days in any resource's of activity's timetable. In other words, it's the gap (of days) between any two work days. For example, suppose that a group has two Astronomy cells during the week. If our objective is to make sure those two cells are scheduled at least two days apart, we will set the minimal gap of days for that activity to "2". By doing so, we are telling the program that it is required to leave at least two days between the two occurrences of the astronomy activity.

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.

Practical Examples

In this section we will provide examples of how the constraints we have listed above are usually used to make sure the timetable fits a wide range of common real life requirements and limitations. In each example we will first describe the use case, and then explain which constraints should be entered in order to achieve the desired effect in the timetable.

How to prevent a subject from being scheduled more than once a day?

In many cases, we do not want the same subject to appear more than once a day in a group's timetable. For example, we may not want History to be scheduled twice (occupying two different periods) on Monday in the timetable of the group 1-A.

To convey this requirement to the program, we will be using the Cells per Day constraint for subjects. In the Constraints pane, we will select "Cells per Day" at the top, and then click the Subject icon. In the list of subjects, we will type "1" in the "Max." column next to the History subject. This tells the program that History should not have more than one cell on any day in any group's timetable. Since History is currently scheduled twice on Monday (in this example) the program displays a value in the "Violation" column, and the violation is "+1": meaning that there is one extra cell scheduled on some day (Monday in this case):

We will do the same thing with other subjects too. However, subjects such as Writing, in this example, which have 6 or more planned cells per week (in a 5-day week), will naturally have a maximum of "2" allowed cells per day.

After defining the above constraints, we click the "Solve All" button at the bottom so that the program will resolve the violations:

How to spread the cells of a group evenly across the week?

When a group has less activities planned than the total number of vacant cells in its timetable (i.e. the number of periods multiplied by the number of days), some cells will naturally remain empty when the timetable is complete. For example, in a 6-day timetable with 7 periods a day, there are 42 potential cells to schedule activities. If a group has only 37 activities planned, 5 cells will obviously remain empty. It is theoretically possible, in this situation, that the program will schedule 5 days with 7 periods in each, and on the 6th day there will only be 2 activities scheduled. This situation is usually unacceptable.

In order to prevent such an uneven distribution of activities, we will also be using the Cells per Day constraint, only now instead of subjects we will define it for groups. We will simply define a minimum of 5 (or 6) cells per day for the group and this will prevent the scenario we have just described of a group having a day with only 2 activities scheduled.

To do this, we will select "Cells per Day" at the top of the Constraints pane and then click the Group icon. Finally, we will type "5" in the "Min." column next to the group's name:

After defining the above, we click the "Solve All" button at the bottom right corner of the workspace, and the program resolves the violation:

How to prevent gaps in the timetables of groups?

As you recall, Gaps are empty cells in the middle of the day. It is often OK for teachers to have them (up to a certain limit of course), but it's usually a big no-no for groups and students. To define this constraint, we will be using the Gaps per Day constraint (yes, we can alternatively use the Gaps per Week too). We will simply define a maximal value of "0" for all the groups.

To do this, we select "Gaps per Day" at the top of the Constraints pane, click the Group icon and type "0" next to the first group. We can duplicate this value for all the other groups by pressing Ctrl+C while the zero value is selected, then selecting the Max. column's cells of the other groups and pressing Ctrl+V:

To fill in the gaps, we click the Solve All button and the timetable is rearranged accordingly:

How to make sure a group's activities start on the 1st period?

Just like gaps, which are empty cells in the middle of the day, a timetable can have empty cells at the beginning of a day. Imagine, for example, that the program has scheduled the activities of a group so that the first period on Monday was left empty, and the first scheduled cell is on the 2nd period. We call that a late start. In most schools, late starts is something that is forbidden for groups, but is allowed (up to a certain extent) for teachers. In order to define this requirement, we will be using (as expected) the "Late Starts per Week" constraint.

What we will do, is simply put a maximum limit of zero on the number of late starts per week for all groups. To accomplish that, we select "Late Starts per Week" at the top of the Constraints pane, click the Group icon at the top and enter "0" in the "Max." column for all the groups:

After defining the constraints, we click the Solve All button at the bottom right corner of the workspace for the program to resolve the violations:

How to minimize the number of gaps in teachers' timetables?

To make the best use of their time, most teachers like it when their timetable has only a few or no gaps at all. To accommodate this requirement, we will be using the Gaps per Week constraint. We will define two values for each teacher: the first is a maximal value which serves as an "upper boundary" which has a higher priority; the second is a desirable value which has lesser priority but will cause the program to strive to minimize the number of gaps even further if that is possible.

As usual, we start by selecting "Gaps per Week" at the top of the Constraints pane. Then, we click the Teacher icon. What we'll do next are two things:

• In the "Max." column near each teacher we type our strong maximal value, in this case it's "4" gaps per week.
• In the "Desr." column, however, we type the value "0-3" (0 dash 3). Why are we using a dash? Because this tells the program that we are OK with zero, one, two or three gaps. If we only entered a single value of "3" as the exact desirable value, it would have meant that when a teacher had 2 gaps in his/her timetable, the program would have considered it as a less desirable situation than him/her having 3 gaps - which is not our intention. As a result, we enter a range of 0-3 as the desirable range (by the way, we could also type "0,1,2,3" as the desirable value because this field accepts both commas and dashes).

After clicking Solve All and letting the program run for one minute, we have received the following result:

How to leave a day off for a teacher?

There are two ways to make sure a teacher has one or more days off (days without anything scheduled) in his/her timetable:

• If the exact day off is known in advance, all we need to do is block out that day's cells in the teacher's timetable, and nothing will be scheduled on that day. As you recall, blocking cells is a function which is available in the Interactive mode by selecting the relevant cells and choosing "Edit", "Block" in the main menu.
• On the other hand, if it's not important which day is going to be the day off for a teacher (just as long as there will be one) we will prefer to use the "Occupied Days" constraint (instead of blocking out a random day), because that leaves more freedom to the program during the automatic construction. The "Occupied Days" constraint allows us to control how many days in a teacher's timetable have something scheduled in them. Subsequently, this gives us the control over how many days don't have anything scheduled in them, i.e. the number of days off for that teacher. For example, in a 5-day week, if we want a teacher to have 1 day off, we will set a maximum of 4 occupied days for that teacher, which will leave 1 day free. If we wanted 2 days off, we would set the maximum to 3 and so on.

In order to define the number of occupied days for teachers, we select "Occupied Days" at the top of the Constraints pane and then we click the Teacher icon. Finally, we type the maximal number of work days (occupied days) for a teacher in the "Max." column, so that the number of weekdays minus the work days gives us the number of days off:

After clicking Solve All we can see that the program has moved the activities of the teacher from one of the work days to the other days so that one day has become free:

How to force an activity to be scheduled only on certain days or periods?

When there is an activity (or a subject) that needs to be scheduled only on specific days or at specific times, we can use blocks to limit the availability of that activity to only those specific cells. Remember that just like there is a timetable of a group or a teacher, there is also a timetable of an activity and a subject. You can see them by clicking the Activity or the Subject icon in the navigation pane. If you click the Activity icon, you can select any activity in the Activities pane and see its timetable. The timetable of an activity consists only of the cells of that activity. And just like you can block out cells in a timetable of a group or a teacher, you can just as easily block out cells in the timetable of an activity. This tells the program that the activity cannot be scheduled at those cells, and thus forces it to be scheduled only at the other unblocked cells.

Let's look at an example. Suppose we have an activity which we would only like to be scheduled on the days Monday, Wednesday and Friday, after the 5th period. In such case, we will block out all the other activity's cells, namely Tuesday and Thursday and all the cells until the 5th period. That way, when we run the automatic solver, the program will be forced to schedule the activity only at the cells we have left unblocked:

Reminder: To block out cells you need to be in the Interactive mode because blocks apply both to interactive timetabling and to automatic timetabling.

How to schedule an activity on the same period?

Sometimes we don't mind on which period exactly an activity is scheduled, as long as it is the same one across all the days on which it is scheduled. For example, we may want the Band class, which is open to visitors, to be scheduled at the same time every day so that the visitors would have a constant time for hearing the band playing.

What we will do in this case, is use the "Occupied Periods" constraint to limit the number of periods this activity occupies to a maximum of 1. By doing so, we are telling the program that all the cells of this activity must be on the same period number (because otherwise it would occupy more than one period horizontally).

To enter this requirement, we select "Occupied Periods" at the top of the Constraints pane, and then click the Activity icon. Now we find the band activity in the list and type "1!" in the "Max." column (we use the exclamation mark in "1!" in order to tell the program that this constraint is a must):

After clicking Solve All, the program has rearranged the timetable so that the activity is now at the exact same time every day:

How to make sure a subject is not scheduled on consecutive days?

Especially when a certain subject has only 2 or 3 cells during the week, we may not want these cells to appear on consecutive days. Instead, we would like them to be spread at least one or two days apart. For example, when a group has 2 Physical Education activities during the week, we would probably like them to be scheduled on Monday and Thursday or perhaps Tuesday and Friday, as long as they are 2 days apart. To define this requirement, we will be using the "Gap of Days" constraint for subjects.

First, we select "Gap of Days" at the top of the Constraints pane. Then, we click the Subject icon to display a list of subjects. Now, near the relevant subject (Physical Education in this case), we will type "2" in the "Min." column. This tells the program that the minimal number of free days (on which Physical Education is not scheduled) between two occupied days (on which Physical Education is scheduled) should be at least 2:

We can see that after clicking Solve All the program rearranges the timetable so that the cells are now two days apart as we have requested:

The next chapter: Changes.