Paper Info
Title
Constraint programming approach for school timetabling
Abstract
In this paper, the timetabling problem for a typical high school environment was modeled and solved using a constraint programming (CP) approach. In addition, operations research (OR) models and local search techniques were also used in order to assist the CP search process by effectively reducing the solution search space. Relaxed models that can be solved using minimum cost matching algorithms were used in order to calculate problem lower bounds at various instances of the solution process. These bounds were in turn used to prioritize the search options of the CP process. The use of minimum cost matching model in the search process is an economical and efficient mechanism for the creation of effective search strategies and it is a competitive manner of introducing problem domain information in the CP environment. By including in the solution process a sequence of local search steps, the solution quality was further improved. Several large problems were solved and actual computational results for specific problem instances are presented.
Year
DOI
Venue
2003
10.1016/S0305-0548(02)00083-7
Computers & Operations Research
Keywords
DocType
Volume
Constraint programming,Timetabling,Combinatorial optimization,Minimum cost matching,Local search
Journal
30
Issue
ISSN
Citations 
10
0305-0548
38
PageRank 
References 
Authors
1.56
4
2
Name
Order
Citations
PageRank
Christos Valouxis1855.88
Efthymios Housos221914.71