KTS is not a school administration system. It does not print timetables for individual students, it does not produce reports summarising the total number of hours that students take different subjects for. It merely solves timetabling problems. There is an assumption that finding timetables is a hard problem, hard enough to make it worth your while to wear the cost of linking KTS to your school administration system, for example by hand entering a KTS timetable into it.
KTS is not a general timetabling system. It is specific to high school timetabling, and even then it does not handle every type of requirement found in high school timetabling. This page explains what KTS can do. The topics are listed in the order you would typically follow when using KTS to construct and solve your own problem instances.
Becoming a KTS user
Archives
Instances and solutions
Times
Resources
Detailed examples of resources
Meetings
Detailed examples of meetings
Being realistic
How the solver works
Stage 1: Column layout
Stage 2: Submeeting timetabling
Stage 3: Tile construction
Stage 4: Time assignment
Stage 5: Time adjustment
Stage 6: Resource assignment
Support for high school timetabling research
Security and availability
About KTS and its author
Glossary
Back to KTS home page
You may snoop around the Visitor account of the KTS web site without becoming a user, but when you decide to actually make a timetable, you need to become a signed-up KTS user with your own account name and password, so that other KTS users cannot access your data. It's free.
The KTS home page offers you the option of becoming a KTS user. If you take it, you will be asked to enter your name and an initial password. An account name will be allocated to you. You may then enter the site again, using your account name and password to access your KTS account.
Within your account you may create any number of archives: collections of instances that you want to solve. Most users would need to create only one archive, named after their high school. There may well be more than one instance in the archive, however, since as time passes new timetabling problems arise for the one school; they should all be stored in the one archive.
A timetabling problem for a particular institution in a particular year (or semester etc.) is called an instance of the timetabling problem. You may store any number of instances in each archive within your account. You may select any of these instances to work on, or you may ask to start work on a new instance.
When creating an instance you need to specify three main kinds of things: times, resources, and meetings. These are explained in detail below. Entering all the information describing your instance will take several hours, although you don't have to do it all in one session, because everything you enter is stored permanently by KTS unless you specifically delete it. Furthermore, there are some shortcuts that reduce repetitive work. You can get a fresh copy of any meeting at the click of a button, make a few changes, and have another meeting finished in a few moments. And as you move to a new year or semester, there is a button for making a complete copy of an old instance, ready to use as the basis for a new one.
When your instance is all entered, you can request the KTS solver to find a timetable for it. On our tests, KTS takes about 10 seconds to solve a typical one-week timetable, and about 50 seconds to solve a typical two-week timetable. You may have to wait longer if the solver encounters something unusually difficult, or the network connection is slow, or the server that hosts KTS is busy doing other things besides solving your instance.
Once you have a solution, you can ask KTS to evaluate it for you. It will check the solution for the various kinds of defects (poor layout of times through the week, teacher slots not assigned, and so on) and display summary tables showing how many of each of these there are. You can also examine detailed lists of defects if you wish.
KTS also offers many ways to view your solution. You can ask to see the timetables of individual resources, or large planning timetables, or faculty timetables; you can view these tables in HTML, PDF, or PostScript; and you can fine-tune their appearance with many options. You can also download the instance and solution as a text file in a simple format that you can read.
After viewing the solution, you can change your requirements, or make suggestions to the solver, and run the solver again. The system keeps the most recent solution on file, so you can safely return at a later session and continue from where you left off.
KTS is not able to adapt an existing solution to a change (even a very small change) in requirements. If you change any part of your requirements, the affected part of any current solution is thrown away. If you then ask for a new solution, the new solution is created without any reference to the old one. Adapting solutions to changing requirements is a very interesting problem, but one that is not currently within the scope of the KTS system. On the other hand, there is no randomness in the solutions that KTS produces: a given collection of requirements will always lead to exactly the same solution. For example, if you add some requirements and subsequently take them away again, the solver will produce the same solution you had before.
Timetables generally cycle (repeat themselves) once per week (or two weeks etc.). Within one cycle, time is divided into intervals called times (or periods). One major restriction of KTS is that all times must have the same duration (though see below for double and triple times). Another is that it can only handle timetables that are exactly the same in each cycle. For example, it can't produce a timetable for two semesters in which some of the meetings occur in both semesters and others only in one. On the other hand, there may be any number of times, spread over any number of days or weeks, and the number of times per day may vary.
Times are ordered chronologically. A time may be marked as being immediately adjacent to the following time, or as being separated from it by a meal break (or end of day, etc.). You may request that some of the times assigned to meetings be double times, triple times, etc. (two or more times not separated by any breaks). In fact, you may ask for an arbitrary block structure, as described under Meetings below.
Resources are participants in meetings. Resources are usually either teachers, rooms, or groups of students. Although there are differences in the detailed handling of these different kinds of resources, fundamentally they all attend meetings and they all want no clashes (a clash occurs when a resource is timetabled to attend two meetings at the same time, or to attend a meeting at a time when it is unavailable). You may create any number of resources of these three kinds, or other kinds.
KTS cannot handle instances where the students are free to choose any courses they wish (as occurs in university timetabling). Instead, the students must be grouped together into student resources, one resource representing an entire group of students. It is the student resources that are timetabled, not individual students. A modest degree of student choice is obtainable using electives: sets of meetings constrained to run simultaneously, from which each student chooses one.
There may be any number of teachers, each with an individual daily and weekly workload limit, and a set of unavailable times (so teachers may be part-time). Teachers may be partitioned into faculties (or departments). Any number of capabilities, such as the capability of teaching English, or Junior Science, may be created and granted to any number of teachers. A teacher may have many capabilities, not just one. Meetings may request that a teacher with a particular capability be assigned to them.
Everything just said about teachers also applies to rooms and any other types of resources you may need. Room capabilities may be used to say, for example, that a room is both a Science laboratory and also usable as an ordinary classroom. Rooms may follow teacher or student resources, i.e. be assigned to meetings containing those teachers or student resources whenever possible.
Click here for some detailed examples of resources, or click here to see these detailed examples in a separate window.
A meeting is a collection of times and resources. The meaning is that all of the resources meet together at all of the times, and so are unavailable to attend other meetings at those times.
You may request that the times chosen for a meeting conform to a certain block structure. For example, you may ask that the six times of a meeting occur as two double times and two single times. These blocks of time may also be required to spread evenly through the cycle, spread evenly between morning and afternoon times, and obey other similar conditions. You may also request that certain times be preassigned to the meeting, in which case the meeting will always contain those times.
A meeting may contain any number of resources of any kind. Some resources may be preassigned, meaning that they must attend the meeting; others may be preferred, meaning that they are good choices to attend the meeting if available; and others may be left for the solver to choose.
Student group resources are usually preassigned, because meetings are created for the benefit of particular groups of students. For example, student resource 07A would be preassigned to meeting 07A-Science, the meeting created to describe their Science lessons.
For teachers and rooms it is more usual to let the solver choose a resource with the desired capability: a Science teacher, a Science laboratory, or whatever. Teachers and rooms may be preassigned too, but the solver will perform very poorly if this is done for more than, say, the senior meetings and a few other key meetings. On the other hand, it is quite safe to have preferred teachers and rooms in any meeting. These will always be chosen by the solver if available.
It is very desirable for the same teacher to attend a meeting at all of its times. The alternative is for two qualified teachers to share the meeting between them. This is called a split assignment, and it is usually only allowed as a last resort. On the other hand, the meeting may not need to be held in the same room at all of its times, although the same room should be used throughout any double or triple times. KTS gives you all these options.
Submeetings are meetings contained within larger meetings. They allow for electives, hand-crafted runarounds, and other kinds of more complex meetings. KTS also allows staff meetings and other non-student meetings. Click here for some detailed examples of meetings, or click here to see these detailed examples in a separate window.
It's important to be realistic and intelligent in your requirements. Requesting things that you could never achieve by hand will only lead to disappointment.
For example, many people want to preassign teachers as well as student resources. It is usually not practical to preassign all teachers, unless you work out the entire timetable at the same time, because it puts too many constraints on possible solutions. It's better to preassign teachers to just those meetings where there is a real requirement for it (senior meetings, typically, plus a few other key meetings), leaving the other teachers for the solver to choose. You can specify preferred teachers for those if you wish, which the solver will assign whenever it can.
In a similar vein, if the timetable KTS makes is not good enough, it usually does not help to try to force matters by putting in more and more preassignments. Often, tightening up in one place only causes something bad to pop up in another. It's better to loosen things by making more resources qualified for more capabilities, breaking large meetings up into smaller ones, and requesting part-form tiling in the solve profile. KTS considers an unsuitable room to be just as serious as an unsuitable teacher, so loosening room requirements can improve your results with teachers.
If you can do much better by hand than KTS, the author of KTS would love to hear all the details, because they are the best inspiration for improving KTS.
Timetabling is one of what Computer Scientists call the NP-complete problems. There are thousands of these problems, but they all have the same basic flavour of looking for a needle in a haystack: when you find it, you know you've got it, but there is nothing to guide you to where it is hidden. Timetabling is like that: it is easy enough to recognise a good timetable when you have one (just carry out the obvious checks that all the meetings have the times and resources they need, that there are no clashes, etc.), but finding it to begin with seems to be a lot harder.
Unlike routine problems such as searching a database, sorting a pile of student assignments into alphabetical order, and so on, the NP-complete problems apparently don't have fast and certain methods of solution. Amazingly enough, if someone does ever find a fast and certain method of solving any one of these thousands of problems, that method can be used to solve all of the problems. Since no such methods have been found despite many attempts over many years, it seems likely that they don't exist. Of course, you can always try every possible timetable and choose the best, but that is totally impractical because of the unimaginably vast number of different solutions that are out there. For example, there are 3,838,380 ways to choose 6 times for a meeting out of a cycle of 40 times, and that is just one of hundreds of choices to be made.
If anyone ever tells you that they have a fast and certain method of finding the best possible timetable, you are either talking to someone who has made a scientific breakthrough worthy of an Einstein, or else they are exaggerating.
Rather than spending a long time looking for the perfect timetable, the method used by the KTS solver takes only a moderate amount of time, and it returns a timetable that usually has some defects. You can ask KTS to list the defects for you. With this approach you get to see solutions quickly, and their defects might help you to spot problems with the information you have entered, or inspire you to simplify or make suggestions to the solver that will overcome the problems.
If you are waiting much longer than 10 seconds for a solution to a one-week instance, or 60 seconds for a solution to a two-week instance, that may be because your instance contains something particularly troublesome to the solver, or it may just be that the network is running slowly, or that the server on which the solver is running is handling other jobs as well and cannot give its full attention to yours.
It's important to know something about how the solver works, so that you can work with it rather than against it. The solver uses a tiling method, in which meetings are grouped together into small, regular clumps called tiles, and then the tiles are timetabled. This method has the great advantage of producing comprehensible timetables. There are six stages, carried out sequentially.
As part of your instance you are asked to specify a division of your cycle into columns. For example, given a cycle of 40 times you might choose to have 6 columns of 6 times each plus one column of 4 times. (You get to specify a block structure for each column as well as a number of times.) You need to choose these columns so that they have the same number of times as far as possible, and so that meetings fit neatly into them (again, as far as possible). For example, if many meetings have 6 times each, then the columns just suggested would be a good choice. There is no requirement that all the meetings have to fit neatly into the columns you choose. Meetings that don't fit neatly will be split across two or more columns.
The first stage of the tiling method used by the solver is column layout. It assigns particular times to the columns you request. The result of column layout might be something like this:
| Monday | Tuesday | Wednesday | Thursday | Friday | |
| Time 1 | Column 1 | Column 6 | Column 2 | Column 4 | Column 4 |
| Time 2 | Column 1 | Column 6 | Column 2 | Column 4 | Column 4 |
| Time 3 | Column 6 | Column 3 | Column 5 | Column 3 | Column 3 |
| Time 4 | Column 6 | Column 3 | Column 5 | Column 3 | Column 2 |
| Time 5 | Column 5 | Column 2 | Column 1 | Column 2 | Column 1 |
| Time 6 | Column 5 | Column 5 | Column 1 | Column 2 | Column 7 |
| Time 7 | Column 4 | Column 4 | Column 6 | Column 1 | Column 7 |
| Time 8 | Column 3 | Column 7 | Column 5 | Column 6 | Column 7 |
This is just an example: KTS is not limited to any particular number of weeks, days, or times per day. The columns give a basic structure to the timetable layout, that meetings follow whenever possible. For example, a meeting requiring six times might be placed in Column 1, which means that it would be assigned Times 1 and 2 on Mondays, Times 5 and 6 on Wednesdays, Time 7 on Thursdays, and Time 5 on Fridays.
In this particular instance KTS was told to spread the time blocks of each column evenly through the days of the week, with at most one time in each column being the last in its day, except that Column 7 was preassigned to the times shown. It has done all this quite well, but not perfectly. Many users would want to tell KTS to spread the times of each column evenly between morning and afternoon as well, and that can be done. If you wish, you may tell KTS exactly what you want, by preassigning some or all of the times of the columns.
The solver takes breaks between times into account, to ensure that each column's times fulfil the block structure that you requested. If two times are preassigned to one meeting, the solver tries to ensure that those two times appear in the same column, so that the meeting does not have to be split across two columns. It also tries to ensure that every day has some single times as well as doubles and triples, since daily workload limits can be awkward on days when there are no singles.
In this stage the solver timetables submeetings into their enclosing meetings. Even a complicated meeting with several sets of submeetings presents quite a small, simple problem to KTS, and many meetings don't have submeetings at all, or only full-width ones, so in practice this stage always runs very quickly and never gives any trouble.
As already mentioned, the solver groups meetings together into small, regular clumps called tiles. A typical tile will contain meetings for all the resources of one form in one or more subjects. For example, suppose there is a student form called Year 7 containing five student resources, called 07A, 07B, 07C, 07D, and 07E. Suppose that student resource 07A attends a meeting called 7A-Science for five times each week, and a meeting called 7A-Music for one time each week, and that the other four student resources attend corresponding meetings of their own. Then KTS is quite likely to construct this tile:
| Time 1 | Time 2 | Time 3 | Time 4 | Time 5 | Time 6 | |
| 07A | 7A-Science | 7A-Science | 7A-Science | 7A-Science | 7A-Science | 7A-Music |
| 07B | 7B-Science | 7B-Science | 7B-Science | 7B-Science | 7B-Music | 7B-Science |
| 07C | 7C-Science | 7C-Science | 7C-Science | 7C-Music | 7C-Science | 7C-Science |
| 07D | 7D-Science | 7D-Science | 7D-Music | 7D-Science | 7D-Science | 7D-Science |
| 07E | 7E-Science | 7E-Music | 7E-Science | 7E-Science | 7E-Science | 7E-Science |
Each column of this table represents what is happening at one time. For example, the Time 3 column says that student resource 07D is attending 7D-Music while the other student resources are attending their Science meetings. This does not mean that the exact times when these meetings are on has been decided. What has been decided is that they will be on at the same time.
In this example the solver apparently discovered that there were not enough Music teachers and rooms to allow five Music meetings to run simultaneously, so it staggered them among the other meetings in the tile so that only one Music meeting occurs at any given time. This arrangement, called a runaround, is well known to manual timetablers. KTS finds runarounds automatically during tile construction, based on its knowledge (communicated previously by you) of how many resources of each kind there are, and how many resources of each kind each meeting requires.
Although the typical tile contains meetings from one form, some meetings, called composite classes, contain student resources from several forms, and then so do the tiles containing these meetings. On the other hand, it might be desirable to break up some forms into part-forms for timetabling, to produce smaller tiles whose chances of being timetabled well are greater. For example, you might choose to treat student resources 07A and 70B as one part-form, and 07C, 07D, and 70E as another, producing two separate tiles:
| Time 1 | Time 2 | Time 3 | Time 4 | Time 5 | Time 6 | |
| 07A | 7A-Science | 7A-Science | 7A-Science | 7A-Science | 7A-Science | 7A-Music |
| 07B | 7B-Science | 7B-Science | 7B-Science | 7B-Science | 7B-Music | 7B-Science |
| Time 1 | Time 2 | Time 3 | Time 4 | Time 5 | Time 6 | |
| 07C | 7C-Science | 7C-Science | 7C-Science | 7C-Science | 7C-Science | 7C-Music |
| 07D | 7D-Science | 7D-Science | 7D-Science | 7D-Science | 7D-Music | 7D-Science |
| 07E | 7E-Science | 7E-Science | 7E-Science | 7E-Music | 7E-Science | 7E-Science |
The difference here is that the two tiles might end up in completely different columns. There is a way to suggest this to the solver, on the solve profile page.
The solver tries to make tiles whose widths match the column widths, and it tries to timetable each tile into exactly one column. If the meetings of one form contain awkward numbers of times with respect to the columns, the tiles made out of these meetings will have to be split across two or more columns. For example, if the columns contain six times each, and the form contains three sets of meetings, each containing four times, then it is likely (depending on what else the form contains) that one of these three sets of meetings will end up with two of its four times in one column and two in another.
Such splitting of meetings across two columns tends to degrade the quality of the solution. The split meetings' times may not be spread through the cycle as evenly as is desired, and there is a greater chance of split assignments occurring. So try to choose the number of times in your meetings and columns to minimize the need to split meetings across two columns.
In this stage the tiles constructed in Stage 3 are timetabled against each other, producing an assignment of times to all the meetings.
The solver ensures that, as far as possible, the meetings assigned to each time do not demand more resources of each kind than are available at that time. In checking this condition it is not correct to merely add up (for example) the total number of English teachers demanded, make sure that it does not exceed the total number of English teachers available, then separately add up the total number of History teachers demanded and so on. This is wrong, because some of the English teachers may also be History teachers. KTS does not make this mistake. How it does it right is very interesting (it uses bipartite matching) but beyond the scope of this overview.
The solver carries out the main timetabling by adding the tiles of each form in turn to the growing solution. You can tell the solver which order to insert the forms in, or leave it to the solver to estimate which forms are the hardest to timetable, and insert those first. This usually turns out to mean starting with the senior forms and finishing with the junior ones. For each form, the solver finds and uses the assignment of tiles to columns that produces the smallest possible number of problems, again using bipartite matching. It tries to keep tiles neatly aligned in columns, but it will split a tile across two or more columns if it needs to. The result is not necessarily the best possible way to timetable a given set of tiles, because a decision made when timetabling the first few forms, although best for them, could turn out to be a mistake when viewed in the light of the later forms. However it is likely to be very close to the best.
Despite its best efforts, the solver may not be able to assign all the tiles and keep within resource limits. Rather than failing, it produces a timetable with as few problems as it can. Some or all of these overload defects may be removed by the next stage.
By the end of Stage 4, every meeting's times have been assigned. At some times there may be overload defects: demands for resources in excess of what can be supplied. This stage tries to find simple swaps among the times assigned to meetings that remove these defects.
These swaps do not worry about keeping within tiles and columns. If you see fragments of meetings at peculiar times unrelated to the tiles and columns, that will be because this stage moved them there to fix overload defects.
In this final stage, resources are assigned to meetings in accordance with the required capabilities, and respecting any workload limits. The solver has two quite different methods of assigning resources: a simple method and a complicated method.
The simple method is used if you specify (on the resource group page) that you need the same resource to be assigned throughout double and triple times, but not throughout entire meetings. This is typically what is required when assigning rooms: it does not matter if a meeting takes place in different rooms on different days. The method straightforwardly assigns resources to each block of each meeting in turn, taking the larger blocks first, and using the same resource throughout the meeting when it can easily do so, which is usually most of the time. It runs very quickly and works very well.
The complicated method is used if you specify that you want as few split assignments as possible. This is typically needed when assigning teachers. It runs more slowly than the simple method, and although it tries very hard to avoid split assignments, especially assignments split among three or more resources, it is usually obliged to include some. A full description of this method is beyond the scope of this overview. It has several stages of its own, and will even swap the times of meetings around if that helps.
Both methods have the desirable property of assigning resources to all resource selections; in other words, everything gets covered. Of course, if the instance has problems such as not enough Mathematics teachers to cover the Mathematics classes, or if the time assignment stage introduces similar problems, for example by scheduling six simultaneous Science meetings even though the school has only five Science laboratories, then someone has to miss out. The methods also occasionally miss an assignment when a resource selection is marked unsplittable or has a special workload. So the precise statement is this: when there are no unsplittable slots and no special workloads, these methods will assign everything that could possibly be assigned, taking the time assignment as given.
It would be wonderful if KTS could also claim that its solutions contain the smallest possible number of split assignments. Sadly, minimizing split assignments is a very hard problem, and all that KTS is able to claim in this department is that their number cannot be reduced by making small adjustments to the solutions it produces. This follows from the fact that the complicated method tries several kinds of small adjustments itself. For example, it tries taking each pair of resources involved in a split assignment, deassigning everything those two resources are currently assigned, then reassigning all those things avoiding the split assignment, usually exploring every possible way to do this. It also tries swapping the assigned times of one block from each of two meetings, one of which has a split assignment, to see if this opens the way to removing the split assignment.
KTS supports high school timetabling research by allowing account holders to add sets of solutions to their archives as well as instances. KTS will evaluate the solutions against the instances and produce tables reporting the quality of the solutions. For more information, click here.
The KTS web site is not secure against malicious attacks based on observing network traffic. All data including your password are transmitted unencrypted. On the other hand, your data are stored on a secure server which guarantees that only you and the server administrator have access, and your password is stored there in encrypted form, so there is no possibility of an attack based on obtaining access to your stored data. Your password is transmitted only once, when you log on. Thereafter your session is authenticated by a session identifier (constructed randomly from your encrypted password and time of login) which accompanies every transmission but is current only until you end your session. Your next session will use a different session identifier. The session identifier is also used to prevent two people who share an account from inadvertently using it simultaneously.
KTS does not promise continuous availability of your data or protection against loss. However the server it runs on is operated in a professional manner, including nightly backups and less frequent off-site backups. If you wish you may make your own backups by downloading a text file version of your instance to your own computer which can if necessary be uploaded again later.
KTS was written between February and October 2004 by computer scientist Jeffrey H. Kingston, and released on 11 October 2004. The solver was a complete rewrite of an experimental version written between August and December 2003. Various enhancements including a more general version of the solver were added between August 2005 and October 2006. Further improvements (mainly to resource assignment) were made between September 2007 and January 2008, leading to the release of Version 1.7 in February 2008, and in July and August 2008.
Dr. Jeffrey H. Kingston is an Honorary Associate and former Associate Professor of the School of Information Technologies at the University of Sydney, Australia. He has been investigating timetabling problems since 1991, and is a founding member of the Steering Committee of the Practice and Theory of Automated Timetabling conference series (the only international conference series devoted to timetabling). For further information, including links to some of Dr. Kingston's papers, visit his home page.