## The Timetable Programwritten 2000 being revised May 2006 |

Each student can be represented by a vector of the class streams offered by the school. The student will have a current achievement vector which will typically have nonzero values in 6 or more subjects. The student will have a goal vector which will have upper bound values higher than the achievement vector in 5 or 6 subjects. Let us take a simple example involving only three subjects:

Student 1 (S^{1}) with an achievement vector of A^{1}=( 1, 2, 0) and goal vector of G^{1}=(4, 4, 0)

Student 2 (S^{2}) with an achievement vector of A^{2}=( 1, 0, 2) and goal vector of G^{2}=(4, 0, 4)

Student 3 (S^{3}) with an achievement vector of A^{3}=( 0, 1, 2) and goal vector of G^{3}=(0, 4, 4)

What classes should be held to complete these goals?

A first answer appears to be ( max over i of G^{i}_{1}-A^{i}_{1}, max over i of G^{i}_{2}-A^{i}_{2},....), in other words, however many classes it takes to complete each course for the student furthest from his goal, in this example (3,3,2).

The number of student attendances is the number of students enrolled for the subject (non-zero goal times the number of classes, in this case (6,6,4). The achievement total is the sum of the individual achievements (6,5,4). In this example there is only one "wasted" student class period.

If there are 2 teachers, how many periods are required? One might assume it is the total number of classes divided by 2, this being 4, but each student has to attend 5 classes, so how many teachers are required for how many periods? This question requires more careful thought. S^{1} and S^{2} have to attend 3 periods of class1 together, in the meantime S^{3} can do one period of class 2. The achievement vectors are now A^{1}=( 4, 2, 0) , A^{2}=( 4, 0, 2), A^{3}=( 0, 2, 2). S^{3} still has 4 classes to complete which S^{1} and S^{2} can attend as required. This means it will take 7 periods and all students will have 2 free periods and the second teacher is only required for 1 period. In other words the students spend 2/7ths of their time not working towards their goals. Is this such a surprising result from such a simple example? This solution has minimised the number of teacher periods.

As an alternative S^{3} could do 3 periods of class 2 while the others are doing class 1. Now the achievement vectors are A^{1}=( 4, 2, 0) , A^{2}=( 4, 0, 2), A^{3}=( 0, 4, 2), Now S^{2} and S^{3} can do 2 periods of class 3 while S^{1} completes 2 periods of class 2. In this case all student courses are completed in 5 periods instead of 7, with no empty periods and both teachers are fully employed though they only work for a total of 10 periods compared to the 8 previously. This is not a great increase in cost compared to the savings in time, specially as it allows for smaller classes and therefore more individual attention.

It can be seen that the 2 teacher solution is optimal and that it would not help to have 3 teachers. Having only 1 teacher would require 3 periods with students doing nothing for 3 of the 8 periods. This is education at its least optimal level. But it is interesting to note that the best result is given by having a teacher effectively repeat the same classes for different students. (I wonder how often this timetabling technique is used in schools to gain efficiency.) Note also that in both solutions students attending each class are all at the same achievement level.

How would this translate into a school timetable? The 3 "classes" in the example could respresent Science, Arts/Language and Technology streams. Students elect to do 2 of these 3 streams and may be starting from different levels of achievement as a result of coming from different schools prior to this. So each "student" may represent a student profile of 10 to 15 students. Although the students have 3 very different profiles in terms of their streaming goals, they can be kept together for 2 of the 3 streams. The third stream is broken into 2. Probably due to its resource intensive requirements the technology stream would be split. As far as the students are concerned there are only 2 streams. All the students taking science classes do them all together, and the same with the language/arts classes. During science classes the students not doing science do their tech course. During language/arts classes the students not doing that do a parallel tech course. This also means that the tech courses have smaller class sizes which is handy if there is limited machinery. Also the two tech courses can cover different ranges of material tailoring the course more closely to the appitude of the students in that stream. The school may also have a core component of English, Maths and Social Studies that everone does.

(I also wonder if at least a quarter of a students time in class is wasted, and what would happen if it was productive instead.)

This simple example is surprising enough to justify building a timetable laboratory.

The following tclet calculates some basic statistics.

Next we decide how many teachers we wish to provide and work out several timetable solutions which maximise certain constraints. Candidates criteria are - minimum number of teacher classes - minimum number of empty student periods, minimum numer of periods in time frame.

The algorithm used is the "brute force" algorithm. Namely to consider all possible first steps to a solution and then rephrase the problem at this point. Reject any solutions that cannot meet any of the maximal criteria. Proceed to solve the resulting set of solutions.

We start by finding the first vacant period in the teacher/period timetable. We assign to this a class which meets the goals of the maximum number of students still available for that period. The Teacher/period array t(i,p) holds the class number, or 0 for a free period if no students are available to be taught. The student/period array s(i,p) holds the achievement goal for that students period in class t(i,p)

- Minimum number of teacher classes
- Minimum number of empty student periods
- Minimum number of periods in timeframe

So the overall answer is to solve all four linear programming problems and then look at the policy issues. Maybe a timetable that projects significant underachievement can justify a call for emergency resources.