VB+SQL Server智能排课系统 第15页
University 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 scheduler’s point of view, the graduate studies lack structure taking
<< 上一页 [11] [12] [13] [14] [15] [16] 下一页