Contents

• What is TOGA?
• Licence
• Before you read this guide...
• Describing the Problem
  • Tier 0 tables
  • Tier 1 tables
  • Tier 2 tables
  • Tier 3 tables
  • Tier 4 tables
• Producing the Timetable
• How TOGA works
• The Objective Function
• References

What is TOGA?

TOGA stands for "Timetables Optimised with Genetic Algorithms". It is an application to help with the development of school, college and university timetables.

TOGA is intended for the use of teachers and administrators. It requires them to supply information such as staff commitments, room sizes, and course enrolment data. Once these are defined, the timetable will be generated automatically.

Licence

I am releasing the code under the GNU Public License. I believe this is the best way to maximise the user base, and encourage involvement from other developers. Also, I'd like to support the use of Free and Open Source Software in public institutions. The program is written in Python, whose community has a reputation for openness and altruism.

Before you read this guide...

This is a very early version of TOGA, and there is a lot to do before it becomes a complete solution to the task of automated timetabling. It has been released in this state for the following reasons:

• Designing school timetables is a seasonal activity, and a release now might benefit UK schools working on the schedule for 2003-2004.
• User feedback is essential for continuing development, and I would like to implement your suggestions in future releases.
• Automated scheduling is still a topic of mathematical research, and I'm hoping to develop TOGA to reflect best academic practice. I don't have a PhD in Maths, so I'm seeking critique and advice from other workers in this area.

TOGA is currently run from the command line, and only available as source code. This may present a difficulty to you if you are not used to using software this way. If this is the case, please send me an email, and I'll try to help. I'm happy to do this because TOGA's future user base will mostly be a non-technical bunch, and I need to understand the issues that are likely to arise.

For those who are able to work from the command line, I have implemented a help system which should be adequate to get you started. A key thing to realise is that TOGA's data model is structured like a Relational Database. This means tables of records, in third normal form. These tables are saved to file as comma separated values.

This guide explains some of the key concepts. However...

• If you'd like to read up on databases a bit more, I can recommend the book by Connolly and Begg ¹.
• For information on installing TOGA, consult the TOGA Installation Guide.
• To see how TOGA will develop, see the TOGA Roadmap.

Describing the Problem

To use TOGA you are going to have to describe the circumstances under which your school operates. TOGA uses a Data Model of a typical school or institution. It organises this data in memory as twelve tables.

You input the data to TOGA as twelve files, one for each of TOGA's tables. These files may be created in a standard spreadsheet application, such as OpenOffice.org Calc or Microsoft Excel. Together, they describe all the relationships which TOGA needs to build the timetable.

I'll explain more about the tables below. Some of the tables contain references to data in other tables. This means that the tables have to be defined in a certain order. In fact, the tables fall into five groups, and all of the tables in the first group have to be complete before defining those in the second group, and so on. I call these groups tiers, and I label them 0 to 4.

Producing the Timetable

Obtaining an optimised timetable is an iterative process. First you create your .csv files. At this point, you should not try to include too much information in your model. In particular, restrict staff commitments to their core competencies only. If you forget the syntax of the tables, use the TOGA Help Pages as a guide to creating your twelve files.

Once this is done, you use other command line options to read the files into TOGA's in-memory database. There is a command to check the data for integrity, and another to begin creating an optimised timetable.

TOGA saves session information as it goes. This means that if you are unhappy with the results after an optimisation run, you may run it again from where it left off. You may also make changes to your table files, say, to add a staff commitment, and use the previous solutions as a basis for the new timetable. Alternatively, you can instruct TOGA to delete its session, and start again from scratch.

TOGA can output its timetable as a set of simple web pages. These are generated for every member of staff. The Booking Table may be saved to file as a permanent record of the TOGA database.

TOGA also has a batch mode, so that you can repeat the whole process with one command only. This is a great help when the initial timetable is infeasible, and changes must be made to the data files.

How TOGA works

TOGA uses a Genetic Algorithm to optimise a population of potential solutions. At first, these solutions are generated at random. However, individual solutions may be mated to produce offspring in a manner which imitates nature. By using the processes of Crossover and Mutation, the offspring of two solutions may inherit features of their parents, but may also develop new ones.

Solutions are evaluated for their fitness by an Objective Function. We use this function to pick the best mating pairs, so that offspring solutions have the best chance of being more favourable than their parents.

TOGA's objective function actually checks the fitness of a solution against many criteria. This is called Multi- Objective Evolutionary Optimisation.

Generation after generation, the solution population will get better. Eventually it will reach a state of Pareto-Optimality where no solution is measurably better than another, although all are different. From then on, the algorithm ensures that the solutions are as diverse as possible, and a final choice is made according to soft constraints which may make some solutions more preferable than others.

TOGA's genetic optimiser uses an algorithm called NSGA II ³. The NSGA2 module is still under development, but currently enables solutions to be coded as Haploid individuals, of which simple animals like amoeba are an example, or as Diploid individuals, which mimic the mechanisms of more complex life.

The Objective Function

TOGA's Objective function measures a number of properties of each Candidate timetable. This function maintains separation amongst the criteria, rather than trying to create a single metric from a weighted sum. This means that in principle any number of parameters may be minimised.

The parameters currently minimised by TOGA are:

clash

A measure of the number of times a candidate timetable commits a pupil to two lessons in the same slot.

squeeze

The number of times a lesson is scheduled for a room which is too small for the class.

unfit

The number of times a lesson is scheduled for a room which does not have the resources the lesson requires.

References