Title: Hybridising plant propagation and local search for uncapacitated exam scheduling problems

Authors: Meryem Cheraitia; Salim Haddadi; Abdellah Salhi

Addresses: LabSTIC, 8 Mai 1945 University, Guelma, Algeria ' LabSTIC, 8 Mai 1945 University, Guelma, Algeria ' Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, UK

Abstract: The uncapacitated exam scheduling problem (UESP) is a well-known computationally intractable combinatorial optimisation problem. It aims at assigning exams to a predefined number of periods, avoiding conflicts over the same period, and spreading exams as evenly as possible. Here, we suggest a new hybrid algorithm combining the plant propagation algorithm (PPA) and local search (LS) for it. PPA is a population-based metaheuristic that mimics the way plants propagate. To the best of our knowledge, this is the first time this idea is exploited in the context of UESP. Extensive testing on the University of Toronto benchmark dataset, and comparison against a large number of new as well as well-established methods shows that this new metaheuristic is competitive and represents a substantial addition to the arsenal of tools for solving the problem.

Keywords: uncapacitated exam scheduling; plant propagation algorithm; PPA; local search; hybridisation.

DOI: 10.1504/IJSOM.2019.099477

International Journal of Services and Operations Management, 2019 Vol.32 No.4, pp.450 - 467

Received: 15 Feb 2017
Accepted: 10 Apr 2017
Published online: 07 May 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article