Title | ||
---|---|---|
Investigating Ahuja-Orlin's Large Neighbourhood Search Approach for Examination Timetabling |
Abstract | ||
---|---|---|
Since the 1960's, automated approaches to examination timetabling have been explored and a wide variety of approaches have been investigated and developed. In this paper we build upon a recently presented, sequential solution improvement technique which searches efficiently over a very large set of 'adjacent' (neighbourhood) solutions. This solution search methodology, originally developed by Ahuja and Orlin, has been applied successfully in the past to a number of difficult combinatorial optimization problems. It is based on an improvement graph representation of solution adjacency and identifies improvement moves by finding cycle exchange operations using a modified shortest path label-correcting algorithm. We have drawn upon Ahuja-Orlin's basic methodology to develop an effective automated exam timetabling technique. We have evaluated our approach against the latest methodologies in the literature on standard benchmark problems. We demonstrate that our approach produces some of the best known. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/s00291-006-0034-7 | Or Spektrum |
Keywords | Field | DocType |
modified shortest path label-correcting algorithm. correspondence to: salwani abdullah,large neighbourhood,examination timetabling . large neighbourhood . improvement graph,examination timetabling,improvement graph,graph representation,shortest path | Adjacency list,Mathematical optimization,Shortest path problem,Computer science,Neighbourhood (mathematics),Graph (abstract data type) | Journal |
Volume | Issue | ISSN |
29 | 2 | 0171-6468 |
Citations | PageRank | References |
50 | 1.78 | 32 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Salwani Abdullah | 1 | 778 | 45.60 |
Samad Ahmadi | 2 | 220 | 15.61 |
Edmund K. Burke | 3 | 5593 | 363.80 |
Moshe Dror | 4 | 574 | 64.77 |