Timetabling through a deductive database: A case study

摘要

Timetabling and Constraint Satisfaction are very hard problems and a general polynomial time deterministic algorithm is not known. An Artificial Intelligence approach, in a logic programming environment may be useful for such problems. The decomposition and classification of constraints and the constraint ordering to obtain the minimization of the backtracking and the maximization of the parallelism are illustrated. The timetabling problem is discussed in detail as a case study: a PROLOG system and a PARLOG system which solve the problem are described and their performances in significant tests are assessed. Finally, a General Constraint Solver is proposed that may be useful for several Resource Allocation, Engineering, DBMS, Decision Support Systems.