《计算机外文翻译定义建模和求解一个真正的大学课程表问题.doc》由会员分享，可在线阅读，更多相关《计算机外文翻译定义建模和求解一个真正的大学课程表问题.doc（16页珍藏版）》请在三一办公上搜索。
1、外文文献资料（外文文件名：Defining,Modeling,and Solving a Real University Course Timetabling Problem）IntroductionAs with many real life problems, the university course timetabling problem can be messy and complicated. Solving the university course timetabling problem involves many people communicating to try to
2、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 more to a real world timetablin
3、g 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 specific problems, system const
4、raints, 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 2006-2007 school year. This proce
5、ss 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, constraints, restrictions, and goals, t
6、hereby 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 totaling 79 POSts1. There are 219 f
7、aculty 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 products. In particular the software Course Planner (CP) is used to schedule, identify issues, and support decisions. CP is
8、 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 tries to achieve, the constraints involved, and the strategy, th
9、e 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 definition problem easier.ConstraintsIn the timetabling domain, t
10、here 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 as possible. Fewer soft constraint violations mean that the sc
11、hedule 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 meaning, they will be referred to as constraining factors and
12、they will be listed in this section as well.StrategyThere 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 strategy that is used. The basic steps that make up the scheduling pro
13、cess 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 rollover strategy is determined, each years timetable is scheduled
14、, 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 of the process is not discussed here. In the following sections, e
15、ach step in the above scheduling process will be looked at in more detail.Problems in the ProcessThere are many areas of the process where there is a need for improvement. These problems range from technical issues such as there being too much data being entered manually, to communication issues, to
16、 political issues within the faculty. Some can benefit from an IT solution, and some cannot.IT SolutionsThere are several instances during the process where automation would be helpful. The obvious one is that of the creation of the timetable. Software is currently used, but that software requires a
17、 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 automatically, but from experience, the created schedules are often quite far from ideal. CP often has a
18、 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 programming, a model could be created to solve the APSC timetabling problem. Such a model might not requir
19、e 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. The director of scheduling has identified these areas as well as the proposed solution. One such
20、 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 electronically, a lot of time would be saved. Also, during the data acquisition phase, data is collected th
21、rough 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 and errors. Errors include filling out forms incorrectly as well as missing information. A third
22、 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
23、which the calendar data could be uploaded electronically to CP. Also, data collection could be done through online forms, where there could be input restrictions so that the counselors would not be allowed to fill out the forms incorrectly and blank slots would not be permitted. The data from these
24、forms could then be uploaded electronically into CP. Such a solution would save a lot of time as well as prevent many errors.Another area where an IT solution would be useful is that of the disconnect between the systems used for the schedule. When a change is made to the schedule, three systems mus
25、t be updated: CP, ROSI, and the Room Reservation System (RRS). Often, there are different people updating the different systems and if it is not done simultaneously, someone may work on one of the systems assuming it is up to date when it is not. This can cause problems. It would be useful to connec
26、t the systems so that when one is updated, so are the others.Non-IT SolutionsThere are two reasons why an IT solution may not be possible: there is no IT solution that applies to the specific problem, or the IT solution that applies is not feasible.The biggest issue existing in the current timetabli
27、ng process is that of communication during the data acquisition phase. During this phase, the counselors are supposed to get all the requirements from the faculty in regards to their schedule preferences and necessities. Faculty are supposed to supply their departments with the delivery of the cours
28、es they will be teaching. Delivery refers to the number of sections the course should have and the number and length of all meetings of the course. Faculty members are also supposed to supply their rooming requirements. It is very common in the current process that faculty members do not supply much
29、 data during the data acquisition phase. In such cases, it is assumed that there are no strict constraints and that the delivery is the same as what is written in the calendar. It is also very common for such faculty members to come to the scheduling office with demands or complaints once the schedu
30、le is completed and uploaded. These demands range from wanting different rooms to wanting to change a one-hour lab to be a three-hour lab.Although it may be possible to have an IT solution where faculty members could enter their data online, instead of going through the counselor, it is likely infea
31、sible to expect buy in from all the faculty members. A more realistic solution would be to develop a written policy that includes a date by which the departments must have all their teaching assignments done, a date by which the faculty members must submit their scheduling data, and what data must b
32、e included. The scheduling office would then be required to approve any deviations from the faculty members requests and there would be no changes made once the schedule is uploaded. A similar policy would be useful in regards to the development of curriculum. There should be no changes to curriculu
33、m made past a certain date. Implementing such a strict set of rules would not be a simple task. Ideally, the curriculum committee would be a year ahead of where they are now. Adjusting to that timeline would take time and effort and although it would be nice for scheduling, it would mean that it wou
34、ld take a year longer for curriculum changes to take effect. Another issue that can be resolved without an IT solution is that of scheduling without known class sizes for first year. Since the admission numbers are not known until after classes start, it is impossible to schedule the first year sche
35、dule with known class sizes. However, the later on in the summer the first year is scheduled, the more accurate the estimate of the class sizes. It would be a good idea to change the scheduling order and schedule first year last, after all the other years are completed. There were several reasons, l
36、isted earlier in the chapter for scheduling first year first. However, when the first year schedule has to be changed last minute due to unknown class sizes, it ends up being scheduled last anyway. The only difference is that time was wasted by scheduling it the first time. The scheduling department
37、 intends to try scheduling first year last in the upcoming year.ConclusionUniversity course timetabling problems are combinatorial problems, which consist of scheduling a set of courses within a given number of rooms and time periods. Solving a real world timetabling problem manually often requires
38、a significant amount of time, sometimes several days or even weeks. Therefore, a lot of research has been invested in order to provide automated support for human timetablers. Contributions come from the fields of operations research and artificial Intelligence. This paper refers to terms and method
39、s from constraint satisfaction. The methods presented were developed using constraint logic programming. Constraint logic programming combines the declarativity of logic programming with the efficiency of methods from operations research and artificial intelligence. It has recently become a promisin
40、g approach for solving timetabling problems. Applying classical methods from constraint satisfaction requires to model the problem as a constraint satisfaction problem, a set of variables, each associated with a domain of values it can take on, and a set of constraints among the variables. Constrain
41、ts are relations that specify the space of solutions by forbidding combinations of values.Methods include search, heuristics, and constraint propagation. Typically, systematic search assigns values to variables sequentially following some search order. If the procedure fails to extend a partial solu
42、tion, decisions are undone and alternatives explored. Systematic search often relies on heuristics, which define the order in which variables and values are chosen. Constraint propagation is complementary; it simplifies a problem by identifying values that cannot participate in a solution. This way
43、the search space gets pruned and search becomes easier. In practice, most constraint-based timetabling systems either do not support soft constraints or use a branch and bound search instead of chronological backtracking. Branch and bound starts out from a solution and requires the next solution to
44、be better. Quality is measured by a suitable cost function that depends on the set of violated soft constraints. With this approach, however, soft constraints play no role in selecting variables and values.After collecting wishes of teacher and information on the new courses, a first proposal is dev
45、eloped with the timetable of the previous year as a starting point. This is done by using free slots in the timetable left by courses not taking place again for new courses offered by the same people, whereas wishes of teachers take precedence over the timetable of the previous year. After handing o
46、ut the proposal to all teachers, evaluations and new wishes are collected. With the current proposal as a starting point, a new proposal is developed incorporating the responses on the current proposal, again changing as little as possible, and so on. Creating a new timetable is thus a multistage, i
47、ncremental process. Relying on the timetable of the previous year and changing as little as possible by incremental scheduling drastically reduces the amount of work necessary for creating a new timetable and ensures acceptance of the new timetable by keeping the weekly course of events people are a
48、ccustomed to. Note that the assignment of rooms is done elsewhere. Nevertheless, conflicting requirements for space or certain equipment may be a cause for changing the timetable. The general constraints are due to physical laws, academic reasons, and personal preferences of teachers: A teacher cann
49、ot be in two places at the same time, so avoid clashing the courses of a teacher. There should be at least a one hour break between two courses of a teacher.Some teachers prefer certain times or days for teaching.Monday afternoon is reserved for professors meetings: Do not schedule professors courses for Monday afternoon. The department consists of five units, each dedicated to a certain area of research. Most courses are held by members of a single unit while only a few courses are held by members of different units.
