Modeling and Solution of a Complex University Course Timetabling Problem
The modeling and solution approaches being used to automate construction of course timetables at a large university are discussed. A course structure model is presented that allows this complex real-world problem to be described using a classical formulat
- PDF / 470,666 Bytes
- 21 Pages / 430 x 660 pts Page_size
- 73 Downloads / 201 Views
ace Management and Academic Scheduling, Purdue University 400 Centennial Mall Drive, West Lafayette, IN 47907-2016, USA {kmurray,muller}@purdue.edu 2 Faculty of Informatics, Masaryk University, Botanick´ a 68a, Brno 602 00, Czech Republic [email protected]
Abstract. The modeling and solution approaches being used to automate construction of course timetables at a large university are discussed. A course structure model is presented that allows this complex real-world problem to be described using a classical formulation. The problem is then tackled utilizing a course timetabling solver model that transforms it into a constraint satisfaction and optimization problem. The tiered structure of this approach provides flexibility that is helpful in solving the multiple subproblems that arise from decomposition of the university-wide problem. A production system has been partially implemented and results of early use are presented. Practical issues raised during the implementation of the automated timetabling system are also discussed.
1
Introduction
Timetabling is a widely studied area and many potentially useful algorithms have been offered for solving the university course timetabling problem, as evidenced by several recent surveys [7,16,19]. Unfortunately, much of the work in this area has been conducted using artificial data sets or based on actual problems that have been greatly simplified. Methods developed have also rarely been extended to the solution of actual university problems of any large scale. McCollum offers a good review of this situation in [11]. The major differences between many of the problems studied and their reallife counterparts are the additional complexity imposed by course structures, the variety of constraints imposed, and the distributed responsibility for information needed to solve such problems at a university-wide level. University timetabling problems may also involve the solution of multiple subproblems with very different characteristics. In practice, therefore, the solution process should not be specifically tailored to a single problem type. The work described here has been motivated by the need to create and modify course timetables at Purdue University that better meet student course demand and allow students to be assigned to the constituent course sections in a way E.K. Burke and H. Rudov´ a (Eds.): PATAT 2006, LNCS 3867, pp. 189–209, 2007. c Springer-Verlag Berlin Heidelberg 2007
190
K. Murray, T. M¨ uller, and H. Rudov´ a
that minimizes conflicts. Purdue is a large (39,000 students) public university with a broad spectrum of programs at the undergraduate and graduate levels. In a typical term there are 9,000 classes offered using 570 teaching spaces. Approximately 259,000 individual student class requests must be satisfied. The complete university timetabling problem is decomposed into a series of subproblems to be solved at the academic department level, where the resources required to provide instruction are controlled. Several other special problems, where shared resources or
Data Loading...
