Iterated local and very-large-scale neighborhood search for a novel uncapacitated exam scheduling model. Issue 4 (2nd October 2018)

• Record Type: Journal Article
• Authors: Haddadi, Salim; Cheraitia, Meryem
• Is Part Of: International journal of management science and engineering management. Volume 13:Issue 4(2018)
• Page Start: 286
• Page End: 294
• Publication Date: 2018-10-02
• Subjects: Uncapacitated exam scheduling -- iterated local search -- very-large-scale neighborhood -- minimum length Hamiltonian path -- consecutive block maximization; 90B35 -- 90B40 -- 90C27 -- 90C59; Management science -- Periodicals; Engineering -- Management -- Periodicals; Engineering -- Management; Management science; Periodicals; 658.005
• DOI: 10.1080/17509653.2018.1445045
• Languages: English
• ISSNs: 1750-9661

Abstract

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.