1、苏州大学本科生毕业设计（论文）附件：外文文献资料 1 外文文献资料 （外文文件名： Defining,Modeling,and Solving a Real University Course Timetabling Problem） Introduction As with many real life problems, the university course timetabling problem can be messy and complicated. Solving the university course timetabling problem involves many
2、people communicating to try to achieve a timetable that meets a set of requirements and goals. As explained in Chapter 3, the literature on automated timetabling often takes a given timetabling problem and reduces it to a mathematical definition, which can then be solved. In reality, there is a lot
3、more to a real world timetabling problem than what is represented in such a definition. The timetabling process is long and consists of many stages before that of actually placing courses into timeslots. The first stage of solving a problem in OR involves a detailed study of the system, identifying
4、specific problems, system constraints, and objective functions. This chapter looks, in detail, at the timetabling problem at the faculty of applied science and engineering at the University of Toronto (APSC). The process described is the one that took place in order to create the timetable for the 2
5、006-2007 school year. This process shows how real world problems are actually much more complicated than what appears in a mathematical model. As well, a detailed analysis of a given problem is a step towards creating a problem definition. It allows one to identify all of the process issues, constra
6、ints, restrictions, and goals, thereby providing a base of information that may be included in a problem definition. The undergraduate program at APSC consists of four years of study. There are 4000 students, over 1200 of which are first years. There are seven departments and nine degree programs to
7、taling 79 POSts1. There are 219 faculty members, 12 buildings, and 80 lab rooms that are managed internally. The faculty uses a software scheduling package that is part of the Syllabus Plus suite of scheduling 苏州大学本科生毕业设计（论文）附件：外文文献资料 2 products. In particular the software Course Planner (CP) is use
8、d to schedule, identify issues, and support decisions. CP is a software package that uses several heuristics when scheduling. 75% of timetables are delivered to the individual student conflict- free, based on program structure. In the following sections, we describe the goals that the timetable trie
9、s to achieve, the constraints involved, and the strategy, the process, used when creating the timetable. We then outline some problematic areas existing in the current process and highlight the areas where IT could be helpful. Identifying areas where IT could be helpful should make the problem defin
10、ition problem easier. Constraints In the timetabling domain, there are two types of constraints. Hard constraints are constraints that cannot be violated because if they were, the schedule would be infeasible. Soft constraints, otherwise known as preferences, are there to make the timetable as good
11、as possible. Fewer soft constraint violations mean that the schedule is better. In addition, in the University of Toronto example, there are certain situations that arise, due to the nature of the program, that seriously constrain the schedule. Although these are constraints in a slightly different
12、meaning, they will be referred to as constraining factors and they will be listed in this section as well. Strategy There is no written protocol that is followed when creating the timetable. This is because every year is unique and different than the previous one. There is, however, a general strate
13、gy that is used. The basic steps that make up the scheduling process are the same each year. First is data acquisition. Second is deciding on the rollover strategy. The rollover strategy is deciding what part of the previous years schedule is kept and rolled over for the following year. After the ro
14、llover strategy is determined, each years timetable is scheduled, one at a time, starting with the first year program and finishing off with the fourth year. The scheduling process really begins before the data acquisition stage, with the creation of the curriculum and calendar. However, this part o
15、f the process is not discussed here. In the following sections, each step in the above scheduling process will be looked at in more detail. 苏州大学本科生毕业设计（论文）附件：外文文献资料 3 Problems in the Process There are many areas of the process where there is a need for improvement. These problems range from technica
16、l issues such as there being too much data being entered manually, to communication issues, to political issues within the faculty. Some can benefit from an IT solution, and some cannot. IT Solutions There are several instances during the process where automation would be helpful. The obvious one is
17、 that of the creation of the timetable. Software is currently used, but that software requires a lot of interaction and in a way it is merely a database that holds data and notifies the user when conflicts exist, while the timetable is actually created manually. The CP software can schedule automati
18、cally, but from experience, the created schedules are often quite far from ideal. CP often has a lot of difficulty finding a timetable that doesnt violate constraints. CP does, after all, use heuristics to make its scheduling decisions, which may not be the best option. Using mathematical programmin
19、g, a model could be created to solve the APSC timetabling problem. Such a model might not require as much interaction. It would take the data and create a timetable, which could then be modified by the user. There are other areas, earlier in the APSC process that could also benefit from automation.
20、The director of scheduling has identified these areas as well as the proposed solution. One such area is the step of verifying the CP and calendar data. This is currently a manual, two-person process involving cross-checking data from three different sources. If these data were connected electronica
21、lly, a lot of time would be saved. Also, during the data acquisition phase, data is collected through spreadsheets. The process involves passing back and forth information that gets changed slightly each time. This process is currently done manually, creating many opportunities for miscommunication
22、and errors. Errors include filling out forms incorrectly as well as missing information. A third area where automation would be helpful is that of updating the CP data after the spreadsheets are completed. This is done manually. The proposed solution, from the director of scheduling, is to make the process of verifying, collecting, and updating data electronic. A database could be created from which the calendar data could be uploaded electronically to CP. Also, data
