- Title
- A hybrid simulated annealing with kempe chain neighborhood for the university timetabling problem
- Creator
- Tuga, Mauritsius; Berretta, Regina; Mendes, Alexandre
- Relation
- 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007). Proceedings of the 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007) (Melbourne 11 - 13 July, 2007) p. 400-405
- Publisher Link
- http://dx.doi.org/10.1109/ICIS.2007.25
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2007
- Description
- This paper addresses the problem of finding a feasible solution for the university course timetabling problem (UCTP), i.e. a solution that satisfies all the so-called hard constraints. The problem is reformulated through relaxing one of its hard constraints and then creating a soft constraint to address the relaxed constraint. The relaxed problem is solved in two steps. First, a graph-based heuristic is used to construct a feasible solution of the relaxed problem, and then, a simulated annealing (SA)-based approach is utilized to minimize the violation of the soft constraint. In order to strengthen the diversification ability of the method in the SA phase, a heuristic based on Kempe chain neighborhood is embedded into the standard approach. This strategy is tested on a well-known data set, and the results are very competitive compared to the current state of the art of the UCTP.
- Subject
- Kempe chain neighborhood; graph-based heuristic; simulated annealing; university course timetabling problem
- Identifier
- http://hdl.handle.net/1959.13/921178
- Identifier
- uon:9260
- Identifier
- ISBN:0769528414
- Rights
- Copyright © 2007 IEEE. Reprinted from the Proceedings of the 6th IEEE/ACIS International Conference on Computer and Information Science (ICIS 2007). This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of University of Newcastle's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.
- Language
- eng
- Full Text
- Reviewed
- Hits: 1098
- Visitors: 2089
- Downloads: 514
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 158 KB | Adobe Acrobat PDF | View Details Download |