---

University Introduction
Course scheduling for secondary and post-secondary institutions consists of building a timetable and building student schedules. In most post-secondary institutions these two activities are separated by necessity; the timetable is established, usually with regard to faculty constraints, and then the students build their schedules. In many secondary institutions, student choices of courses are known before the timetable is constructed. In each case, the overall goal is to minimize the number of conflicts in students' schedules, where a conflict is any course chosen by a student but scheduled at the same time as another course taken by the student. Separate or joint, the process of constructing timetables and determining student schedules is NP-Complete [Even, Itai and Shamir 76, Lewandowski 94].
Goals and Purpose
Our project had several goals related to this problem. We wanted to investigate the quality of solutions for the course scheduling problem derived from a bipartite matching heuristic devised by Dr. Lewandowski. We wanted to investigate the distribution of courses selected by students to learn more about the structure of the problem. We wanted to build a web interface to allow students to interact with the heuristic on Xavier's timetable.
Methods and Process
At the beginning of the school year we worked together on the background of the course scheduling problem, reading several papers about approaches to solving it. We met once a week to discuss the papers. The next stage of the project involved each student selecting a part of the problem for specialization. Jen Wanner chose to work on the simulation portion of the project which would be used to test Dr. Lewandowski's heuristic. Jennifer Levins chose to work on the distribution of courses problem, and Christy Lohrer chose to work on the web interface portion of the project. The project then moved into an evolution stage as each student worked out the particulars of their project section. At this point we realized that the key issue involved in testing the heuristic was having data with a known solution. Jen Wanner's work focused on this aspect of the problem. The other two portions of the project remained much the same as the original proposal. At this point we continued meeting once a week as a whole group, and also added one or more meetings a week individually with Dr. Lewandowski. We discovered that the process of working on the projects varied for the students. Jen Wanner preferred a holistic approach, working out her ideas before coming to weekly meetings and using the group to critique her ideas and suggest new avenues. Eventually this turned into her implementation, where some group-debugging would occur during the meetings. Christy Lohrer preferred to work on a smaller scale, setting small goals for the next several weeks as she built her interface. This approach was better suited to her task because she needed to learn about Perl and client-server technology as she worked on the project. By meeting several times a week and having concrete problems to solve she could be sure she was progressing towards her goal. Unfortunately, Jennifer Levins needed to leave the university after our first semester. The investigation of course distributions remains an open problem for our team.
Conclusions and Results
We have developed a method for constructing random timetables and random student course selections such that the existence of an optimal (zero conflict) solution exists. The random construction can be used to create many data sets. The construction takes in parameters indicating how many courses should be in the timetable, and the number of sections per course. It then generates a timetable and uses backtracking to generate plausible schedules. While we were not able to run detailed simulations of our heuristic in the time we had for the project, we intend to continue this work over Summer 2000. We have also developed a web interface that allows students to enter the courses they are interested in and returns a list of open sections of those courses. This process is much faster than the current method of watching a monitor by the Registrar's office flash closed courses. The next step is to output this information into a file format compatible with the scheduling heuristic so that it can offer an actual schedule for the student. Our work has already been presented as a poster at Xavier University's Celebration of Student Research, and we intend to also present the work at the Consortium for Computing in Small Colleges: Midwest Conference at Valparaiso University in October 2000.
Students and Mentor
Jennifer Wanner and Christy Lohrer will be senior computer science majors at Xavier University in Fall 2000. Gary Lewandowski is an Associate Professor of Mathematics and Computer Science at Xavier University; he will be a Visiting Professor of Computer Science at Hope College during the 2000-2001 academic year.