外文文献：
Arrangement system
University teachers arrangement system is a combination of 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.
外文文献,排课系统
