Iterated local and very-large-scale neighborhood search for a novel uncapacitated exam scheduling model

Abstract

We consider a novel uncapacitated exam scheduling model where the soft constraint stipulates that the exams should be spread over the periods so as to avoid adjacent conflicts as much as possible. The proposed method starts by constructing an initial feasible timetable. A two-phase method is then iterated. The first phase is a local search (LS) heuristic where two neighborhoods, ExamShift and KempeSwap, are searched using the token-ring strategy. The second phase takes as input the local optimum obtained during the first phase and performs a very-large-scale neighborhood (VLSN) search. We prove that searching the exponential neighborhood is NP-hard. Hence a polynomial-time heuristic based on reordering the periods is proposed for exploring a polynomial sized part of the neighborhood. The incumbent of the VLSN search is then perturbed and the method iterated. The practicability and effectiveness of our approach is studied by testing it on the university of Toronto benchmark instances and comparing it to an established method adapted to the new model.

Keywords:

• Uncapacitated exam scheduling
• iterated local search
• very-large-scale neighborhood
• minimum length Hamiltonian path
• consecutive block maximization

JEL Classifications:

• 90B35
• 90B40
• 90C27
• 90C59

Acknowledgements

We thank the anonymous reviewers for their thorough review and highly appreciate their comments and suggestions, which significantly contributed to improving the quality of the article.

Notes

No potential conflict of interest was reported by the authors.