The classroom assignment problem: Complexity, size reduction and heuristics
This paper treats essentially an important compound of the exam timetabling. The NP hardness proof of the problem is deduced by reduction from the numerical matching with target sum problems. Two reduction procedures are proposed in order to reduce the size of the problem. To finalize the assignment procedure, we have used the VNS metaheuristic in order to obtain a good quality complete solution.
classroom assignment complexity size reduction exam timetabling variable neighbourhood search