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.

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

Avella, Pasquale
;
Boccia, Maurizio;Mele, Michele;Viglione, Sandro
2025-01-01

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.
2025
Cut-and-branch
Scheduling
Separation algorithm
Valid inequalities
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12070/78367
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact