Hybridising plant propagation and local search for uncapacitated exam scheduling problems

Meryem Cheraitia, Salim Haddadi and Abdellah Salhi

International Journal of Services and Operations Management, 2019, vol. 32, issue 4, 450-467

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. (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=99477 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijsoma:v:32:y:2019:i:4:p:450-467

Access Statistics for this article

More articles in International Journal of Services and Operations Management from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().