Constraints

From Lantiv User's Guide

Jump to: navigation, search

The quality of a constructed timetable is measured by how suitable it is for the affected 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. Each kind constrains a different aspect of the timetable. For example, the "Gaps" constraint controls the number of vacant cells before and after which there are scheduled cells.

File:constraint_types.png

Basically, every constraint is 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 are defining separate values per each resource.

Since every constraint's formula produces a number, what is left for us to do is to put a limitation on that number. Once we do, the program will aspire to generate a timetable in which all these limitations are satisfied. We can define 3 types of limitations: Minimum, Maximum and a Desirable value. The Minimum and Maximum values are "hard" limitations whereas the Desirable value is a "soft" limitation, meaning that the Min/Max values have a higher priority. It is not required to enter all the 3 values if not necessary.

Contents

Entering Constraints

To switch to the Constraints entry window, click on "Constraints" at the bottom left corner of the workspace.

File:constraints_tab.png

The Constraints entry window has a navigation pane at the top. The first button in the navigation pane is where you select the type of the Constraint. The rest of the buttons allow you to select the type of resources for which to enter the constraint limitation values.

File:constraints_navigation_pane.png

Once you select a constraint type, you will see a list of all the resources with three additional columns: "Min.", "Max." and "Desr." ("Desirable"). 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.

File:constraints_min_max_desr.png

Constraint Types

Let's go over the available types of constraints and understand their use cases.

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 a 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 the number of consecutive free cells (in case there is more than one).

The most common use case for limiting Gaps is to prevent too much idle time in between activities for teachers or 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 (just like a gap) or a series of 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 constraints here: "Late Starts per Week" which sums the number of free cells a resource has at the beginning of a day throughout the entire week, and "Late Start Size" which sums the number of these consecutive free cells.

Consecutive Cells

This constraint sums up the number of consecutive periods on which any activity is scheduled on the same day. 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 "Max" 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 this case the program would be forced to leave a free period after the 3rd cell.

Cells per Day

This constraint 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 number of scheduled cells evenly across the week. For example, suppose a teacher has 10 cells to be scheduled; by setting the "Max" value of this constraint 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 activities scheduled.

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 notified to the program by setting the "Max" value for the subject "Physical Education" to "1".

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 inform the program that an activity should be scheduled only on periods 1-3, you can type "1" in the "Min" value for that activity and "3" in the "Max" value.

Note that if your periods start from "0" or are named differently than "1", "2", etc., you still need to enter positive numbers in the Min/Max/Desirable values. After you enter a number, the program will translate the number "1" to the first period's name, "2" to the second's and so on.

Desirable Constraints

The "Desr." column allows you to enter a desirable value. A desirable value has less importance than the Min/Max range. This means that if the program considers a "move" to improve the timetable in order to reach a desirable value on account of breaking another constraint's Min or Max value, the option will not be applied. However, the desirable values do allow you to tweak the timetable's quality to a greater precision by providing you with a way to enter "nice to have" limitations.

File:desirable_values.png

The program supports not only a single desirable value, but also a range of values. You can use 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".

Critical Constraints

There are 3 constraints' 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 in the database. 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 "Desr." 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 first priority to take care of that constraint – even in a higher priority than scheduling any remaining activity. In a way, it affects the decision making process of the program during the automatic phase because then 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 end of the value in the "Min." or "Max." column.

File:critical_values.png

Violation Indication

If you click on the Constraints tab while being in the Automatic mode of timetable construction, you will see an additional column next to the Min/Max/Desr columns, named "Viol.". This column contains a value only for the unfulfilled constraints. In those cases the value in this column shows a negative or a positive number which indicates the difference between what is currently the value of the constraint in the timetable and the nearest required value.

For instance, assuming the Max number of Gaps per Week was set to "3" for some resource, yet the current timetable having 5 gaps, the Violation column for that resource will have the value "+2" (yes, with a plus sign) – meaning that there are 2 gaps over what is required. Another example – if the Min number of Cells per Day for a resource was set to "5" but the current timetable of it has only 1 cell on each day of the 5-day week, the violation column will contain the accumulated value of "-20" (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 red color. If it's a violation of the desirable value, it will be written in an orange color.

Modifying Constraints "On the Fly"

Even if the timetable is partially or fully constructed, you always have the option to modify the existing constraints and then run the automation again from that point. The program knows how to take the existing timetable as a starting position and automatically make the necessary adjustments to make it fulfill the new constraints.

In fact, this ability can be used as a technique to construct the timetable gradually because you can run the automation 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 and fixate it, and then run the automatic solver again. Following this process several times is actually the recommended method of achieving the highest quality timetable.

Over Constraining

One last thing which is important to understand about Constraints is how to not misuse 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 it faces a "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 range constraints, i.e. both are required), the program will refrain from making that change. If both constraints are indeed required, that is certainly the desired behavior. If, however, one isn't, 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 and use the "Desirable" field for the "nice to have" constraints.