A cut-and-branch algorithm for the external candidates examination scheduling problem

Pasquale Avella (), Maurizio Boccia (), Carlo Mannino (), Michele Mele () and Sandro Viglione ()
Additional contact information
Pasquale Avella: Università del Sannio
Maurizio Boccia: University of Naples
Carlo Mannino: SINTEF Digital and University of Oslo
Michele Mele: Università del Sannio
Sandro Viglione: Università del Sannio

Journal of Scheduling, 2025, vol. 28, issue 6, No 2, 577-584

Abstract: Abstract Twice a year, the regional school departments in Norway need to schedule examination sessions for external candidates in the region, which also involves reserving and assigning rooms, examiners and reviewers. We present a cut-and-branch algorithm to get provably good solutions to this problem, the external candidates examination scheduling problem (ExtSchedule). The algorithm relies on a new family of valid inequalities, effective in tightening the initial formulation and accelerating the solution process. We develop an efficient separation algorithm and embed it in a cut-and-branch framework to solve the problem. The algorithm has been validated on real-life instances arising from the Vestfold County school department in Norway.

Keywords: Valid inequalities; Cut-and-branch; Separation algorithm; Scheduling (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-024-00833-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jsched:v:28:y:2025:i:6:d:10.1007_s10951-024-00833-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-024-00833-w

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().