VB+SQL Server智能排课系统 第16页
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 categories in such a way that courses spread evenly over categories, which would have been necessary to prevent conflicts. It became clear that we were in need of some kind of weighted constraints able to express weak and strong constraints that are not mandatory.
A Constraint Satisfaction Problem(CSP)consists of a finite set of variables, each associated with a finite domain and a finite set of constraints. A solution of a CSP maps each variable to a value of its domain such that all the constraints are satisfied. A partial constraint satisfaction problem(PCSP) is a CSP where each constraint is associated with a weight. A weight of a constraint expresses the importance of its fulfillment, allowing one to distinguish hard constraints from soft constraints. Hard constraints stand out due to infinite weights. The finite weights of soft constraints allow for the specification of preferences among constraints. A solution of a PCSP maps each variable to a value of its domain such that all hard constraints are satisfied and the total weight of the violated soft constraints is minimal.
Clearly, we only need one variable for each course holding the period, the starting time point, it has been scheduled for. Each variable’s domain consists of the whole week, the periods being numbered from0 to 167, for example,9 denotes
No-clash constraints demand that a course must not clash with another one.
Preassignment constraints and availability constraints are used to express teachers’ preferences and that a course must take place at a certain time.
Distribution constraints make sure that there is at least one day between a course and another, or that two courses are scheduled for different days.
Compactness constraints make sure that one course will be scheduled directly after another.
With respect to soft constraints, three grades of preferences were chosen: weakly preferred, preferred, and strongly preferred, which get translated to the integer weights1,3, and9.
The search procedure employed integrates the solver given above with chronological backtracking and heuristics for variable and value selection. For variable selection, the first fail principle was chosen, which dynamically orders variables by increasing cardinality of domains, the principle proposes to select one of the variables with the smallest domains with respect to the current state of computation. For value selection, a best-fit strategy was used choosing one of the best rated periods. From an optimistic point of view, this will be one of the periods violating a set of soft constraints with minimal total weight, but the estimate may be too good duet o the low propagation performance of the no–clash solver. Furthermore, the best assessment does not necessarily violate a minimum number of constraints: a strong personal preference may balance out 10 weak no –clash constraints. This approach yielded a good first solution to the problem. It was not necessary to search for a better solution.
The generation of a timetable runs as follows. Each course is associated with a domain constraint allowing for the whole week, the periods being numbered from 0 to 167. It is important to note that, for each course, the initial assessment for all periods is 0 indicating that no period is given preference initially. Then preassignment constraints and availability constraints will be translated into in and not in constraints. Adding in and not in constraints may narrow the domains of the courses using the rules presented above. Propagation continues until a fix point is reached, that is to say, when further rewriting does not change the store. Usually, our consistency-based finite domain solver is not powerful enough to determine that the constraints are satisfiable. In order to guarantee that a valid solution is found the search procedure is called. Addition of an in constraint may initiate propagation, and so on.
Now that we have discussed the details of creating a timetable, how does one create a new timetable based on a timetable of the previous year with this system? Central to our solution is the notion of fixing a timetable. Fixing a timetable consists in adding a soft preassignment constraint for each course that has been scheduled ensuring that all courses offered again will be scheduled for the same time.
The time necessary to compute a timetable depends on whether a previous timetable is reused or not. Scheduling 89 courses within 42 time periods from scratch took about five minutes. Considering an ‘‘almost good’’ previous timetable saved about two and a half minutes.
Constraint handling rules is a declarative high level language extension, especially designed for writing application－oriented constraint solvers. In this paper, it has been argued that CHR is a good vehicle for implementing a finite domain solver that performs hard and soft constraint propagation. The solver is powerful enough to serve as the core of a university timetabling system. The internet is relied on, and more specifically the World Wide Web(WWW) to enable teachers to enter new wishes and offerings into the specification by themselves. The Web front end is based on HTML; pages are also generated by a Prolog program. Developing the constraint solver and attaching it to a database of timetabling problems took about three weeks; developing the front end took an other two weeks. The solver takes only a few lines of code. The good execution times achieved and the very reasonable timetables generated demonstrate that CHR is able to reconcile efficient execution and declarative implementation. This very high level approach also means that the program can be easily maintained and modified.
<< 上一页 [11] [12] [13] [14] [15] [16]