The Timetable Program

written 2000 being revised May 2006
Google site search


1   Introduction

Hopefully the Timetable program is an example of a linear programming model. This section looks at the problem and attempts to determine if this is the case.

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 (S1) with an achievement vector of A1=( 1, 2, 0) and goal vector of G1=(4, 4, 0)
Student 2 (S2) with an achievement vector of A2=( 1, 0, 2) and goal vector of G2=(4, 0, 4)
Student 3 (S3) with an achievement vector of A3=( 0, 1, 2) and goal vector of G3=(0, 4, 4)

What classes should be held to complete these goals?

A first answer appears to be ( max over i of Gi1-Ai1, max over i of Gi2-Ai2,....), 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. S1 and S2 have to attend 3 periods of class1 together, in the meantime S3 can do one period of class 2. The achievement vectors are now A1=( 4, 2, 0) , A2=( 4, 0, 2), A3=( 0, 2, 2). S3 still has 4 classes to complete which S1 and S2 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 S3 could do 3 periods of class 2 while the others are doing class 1. Now the achievement vectors are A1=( 4, 2, 0) , A2=( 4, 0, 2), A3=( 0, 4, 2), Now S2 and S3 can do 2 periods of class 3 while S1 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)

2   Is this a Linear Programming Problem?

The answer to the question is Yes and No. The basic constraints are linear and we can even allow for a cost factor to be added to each class stream. But we have three different functions which we wish to minimise, so there will be up to three "right" answers depending on whether we choose: This linear model will resemble a kind of three cornered hat, but the reality will probably be that none of the three peaks can be realised due to resource constraints. In this case achieving the maximum level of achievement will become the determining constraint. This is not a happy situation because it means that some students will be pushed forwards at the expense of others. One wonders whether this does not already happen in our schools. Using this timetable program may just highlight who misses out and by how much - no school with resource problems and systemic underachievement wants to be confronted by this reality.

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.

©2000 - 2006 WEBSCOOL This page last updated 20 May 2006. All rights reserved - including copying or distribution of any portion of this document in any form or on any medium without authorisation. For more regarding the copyright.