Scheduling Tutors in the Math Study Center: An Undergraduate Research Project

The Math Study Center (MSC) at UW is a tutoring facility for freshmen and sophomores taking mathematics classes. Each quarter Dr. Patrick Perkins, the director of the MSC, is faced with the problem of creating work schedules for about 25 tutors and desk assistants. The employees are all students at the UW and the times they work must fit in with their classes. Beyond these rigid constraints, Dr. Perkins tries to optimize more complicated employee preferences which include the following: (1) employees prefer not to enter and leave the MSC more than twice a day, (2) they prefer not to work isolated hours, (3) they prefer not to work more than a certain number of hours in a row and (4) they usually prefer to work during a free hour between two classes. This is a complicated optimization problem for which an optimal solution is not apparent. Over the years, Dr. Perkins has written an ad-hoc program in C++ that finds ``good'' schedules for his workers.

In Spring 2003, Professor Rekha Thomas offered the MSC scheduling problem as an optional project to her undergraduate class on Discrete Optimization. Three students took on this project: Youngbae Lee, an undergraduate student in Applied and Computational Mathematical Sciences; Yoonsoo Kim, a graduate student from the Department of Aeronautics and Astronautics; and Caleb Z. White, an undergraduate Economics major. The two undergraduates were supported by the UW VIGRE grant during the summer. The three students met frequently with Thomas and Perkins during the Spring and Summer quarters and designed a sophisticated model of the problem as an integer program. They then solved the problem using CPLEX, which is a state-of-the-art commercial software package for integer and linear programming. The resulting schedules were computed in just a few seconds and were of very high quality.

Youngbae, Yoonsoo and Caleb have created a mathematically sound and computationally viable solution method that can be used by Dr. Perkins in the future. In fact, Caleb computed the Fall 2003 schedule at the beginning of this academic year. It took CPLEX less than seven seconds to produce the optimal schedule. This work resulted in a paper by the five collaborators: Caleb Z. White, Youngbae Lee, Yoonsoo Kim, Rekha R. Thomas and Patrick Perkins, ``Creating Weekly Timetables for Maximizing Employee Preferences,'' 18 pages, August 2003, available here.

Patrick Perkins & Rekha Thomas