|
We chose to tackle the problem of trying to set up time tables of the first 5 years of UTC curriculum, for several reasons: (1) the problem has eluded Operational Research combinatorial techniques for over 6 years, and Artificial Intelligence techniques for over 4 years, despite an average of 2 attempts per year, (2) there is a large amount of data (teaching personal curriculum structure, available classrooms,...), (3) there is no clear optimizing criterion (one must need a maximum flexibility for a student population which has not decided yet which courses it will take), (4) if constraints are taken literally, then the problem has no solution, (5) the actual manual solution involves a consensus between several decision makers, (6) an expert was available and willing to participate in the project. The number of students and of options increasing over the years, the problem is more and more difficult to visualize and to solve efficiently. Several techniques have been tested to solve this problem, but none succeeded. We first tried combinatorial techniques, but the problem has no solution if one cannot violate some of the constraints, and it was not possible to succeed. We tried to use Relational Data Bases to store the several data (more than 5000), but it was not efficient enough. Then, an Object Oriented Data Base gave us the good answer for storing all these data. We tried to use Prolog to solve the problem, but we realized that Backtracking and Backward inferences were not a good solution. We needed an expert system with a forward strategy. Thus, we implemented an expert system integrated into an object oriented data base. The software architecture was correct, but we forgot an important factor: what was the human expert's knowledge? How was it possible to 'catch' that knowledge? In fact, the knowledge base that we used was inefficient, and the system failed one more time. It has good performances during experimental tests. But in fact, it was not able to find a solution when running in real conditions, with a lot of data and constraints. Today, a new project is being implemented. We kept the last software architecture (object oriented data base, and expert system with a forward strategy), and also added to it Operational Research combinatorial techniques. We have been working for 2 years with the human expert, to improve the knowledge base, and the system is starting to give good answers, even in real conditions of work. This paper will describe this planning and scheduling problem, how we have been failing for 10 years, and how we are now starting to find a good solution, based on both Operational Research combinatorial and
|
