计算机外文翻译---定义，建模和求解一个真正的大学课程表问题.doc

苏州大学本科生毕业设计（论文）附件：外文文献资料外文文献资料（外文文件名：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 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 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 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 2006-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, constraints, 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 totaling 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 products. in particular the software course planner (cp) is used 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 tries 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 definition problem easier.constraintsin 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 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 meaning, they will be referred to as constraining factors and 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 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 rollover 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 of the process is not discussed here. in the following sections, each 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 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 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 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 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. 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 electronically, 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 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 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 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 must 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 connect 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 timetabling 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 courses 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 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 schedule 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 infeasible 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 be 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 curriculum 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 would 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 schedule 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, listed 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 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 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 methods 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 promising 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. constraints 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 solution, 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 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 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 developed 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 out 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, incremental 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 accustomed 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 cannot 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. courses held by members of a certain unit must not clash with courses held by other members of the same unit.an offering typically consists of two lectures and a tutorial per week. there should be a day break between the lectures of an offering. the tutorial should not take place on a day, on which a lecture of the same offering takes place. all courses should be scheduled between9 a.m.and6 p.m. no lectures should be scheduled for friday afternoon. no tutorials should be scheduled for late friday afternoon.only few of the courses are mandatory for and dedicated to students of a certain term, while most courses are optional and open to all students. for each term of the undergraduate studies there is a set of mandatory courses, the attendance of which is highly recommended. courses of the graduate studies only rely on the knowledge provided by courses of the undergraduate studies. there is no recommended order of attendance. undergraduate courses of a term must not clash, while undergraduate courses of different terms are allowed to clash. graduate courses should not clash. first observations made clear that existing timetables do not meet the requirements stated, e.g., courses of a unit or graduate courses clash or a lecture of an offering and a tutorial of the same offering are scheduled for the same day. furthermore, considering the number of graduate courses offered over the years, it became clear that there is too little space to schedule all graduate courses without clashes. this is due to the following reason. as mentioned before, undergraduate courses are mandatory and there is a recommended order of attendance. this way it is possible to distinguish students of the first term from students of the third term and students of the second term from students of the fourth term, which makes it possible to allow clashing of undergraduate courses of different terms. the graduate courses only rely on the knowledge provided by the undergraduate courses. there is no recommended order of attendance, thus making it impossible to distinguish students of the fifth term from students of the seventh term, which makes it necessary to disallow clashing of graduate courses in some way. so we faced two problems: the demand for incremental scheduling by basing the new timetable on the timetable of the previous year and changing as little as possible made it necessary to handle old timetables, which do not meet the requirements stated. from a schedulers point of view, the graduate studies lack structure taking freedom and leading to over constrained timetable specifications.tackling the second problem by removing selected no-clash constraints turned out to be laborious and time-consuming and, therefore, impractical. classifying graduate courses by contents and expected number of students and allowing clashing of courses of different categories won back some freedom, but it was not possible to identify enough categorie