AMPL in Action

Teacher Scheduling

Anders Peterson
Optimatika, Stockholm, Sweden

Reprinted from Compass News, number 3, fall 1996

The Maxwell project, involving the city of Linkoping and Cambridge Technology Partners, aims to develop a high school resource management system for the city. It is named after the physicist James Clerk Maxwell who proposed a way of gaining energy by violating the second law of thermodynamics with the aid of a demon. Like this demon, the system is expected to free resources.

In Sweden, most schools -- from kindergartens to universities -- are public. Traditionally students entered the high school system by applying to take part in one of several largely, but not completely, fixed programs. Although the basic structure remains, the system is currently being reformed to better imitate higher forms of education, which means increased flexibility. With the reformed system, each student's study plan theoretically constitutes a unique set of at least 30 courses. Along with this reform, each school has been forced to cut costs. Altogether this has made the task of managing and scheduling the schools' activities much more difficult.

Most municipalities manage their own high schools, each of which must educate a fixed number of students as cost-effectively as possible within the limits of their budget. The two main resources to be managed are teachers and classrooms. The city of Linkoping decided to develop its own high school management system. The idea is not only to aid the schools in managing their resources, but also to allow them to share resources. The city has 5 high schools with roughly 500 teachers and 5000 students. With the new system each school still manages its own teachers, students and classrooms, but has access to those of the other schools.

Having all the data in a single database which is accessible to staff at all schools will be a great advantage. But the real gain will be to provide the means to enable the schools to effectively plan their activities. A structure for the planning process has therefore been developed. The assignment of teachers to classes is one step in this process, and the actual scheduling of classes (when and where) is another. Theoretically, the system should handle different schedules for each teacher, student, classroom and day. There are repetitions, but they are not consistent in any way that would allow the database or an optimization model to be scaled down. It was decided that to automate the entire process would not be feasible. To automatically assign teachers, however, would be relatively easy. Since the teachers represent the single most costly resource, it was decided that this should be optimized.

AMPL and CPLEX are used to carry out the optimization. The Maxwell system is a client/server solution. The server is a Sun machine running an Oracle database as well as the optimization software. The clients are PCs running Windows 95, and client applications developed using SQL Windows, except for a few complex graphical components developed with C++. To tie it all together, the city has a 10Mbit network.

The optimization model, largely developed with the student edition of AMPL, contains two sets of variables: one real that describes how many hours the teachers are employed to teach (e.g. full-time or not), and another binary that tells whether or not a teacher is assigned to a specific group. Each school has about 100 teachers and 10,000 possible assignments. The objective is primarily to employ as few teachers as possible, and secondly, to use more experienced teachers. Optimization is triggered by the user directly from the software specifically developed for this task. It is possible to manually do some assignments, optimize, lock or re-do part of the result and then optimize again. A typical problem is solved in less than 2 minutes.

The project started at the beginning of 1996 and is in its final stages. There will be a pilot installation at one of the schools this fall, and by the spring semester next year all high schools in the city will be using the system. Part of the system will be extended to support other levels of education within the city. Cambridge and the city of Linkoping have agreed to jointly market Maxwell to other municipalities. All high schools in Sweden are facing the same reality and we believe that Maxwell will suit many of them.

Anders Peterson graduated in 1993 from the Royal Institute of Technology in Stockholm with a Master of Science degree in Engineering, and majors in Naval Architecture and Operations Research. He is one of the founders of Optimatika. Specific questions regarding the optimization model or this article can be sent to him at peterson@optimatika.se.

For general information regarding Cambridge Technology Partners and the Maxwell project, contact Håkan Arpfors at harpf@ctp.com.



Comments or questions?
Write to info@ampl.com or use our comment form.

Return to the AMPL cases index.

Return to the AMPL home page.


LAST MODIFIED 2 JUNE 1997 BY 4er.