A Fast Threshold Acceptance Algorithm for the Examination Timetabling Problem

Nuno Leite (), Fernando Melício () and Agostinho C. Rosa ()
Additional contact information
Nuno Leite: Instituto Politécnico de Lisboa
Fernando Melício: Instituto Politécnico de Lisboa
Agostinho C. Rosa: Universidade de Lisboa

Chapter Chapter 11 in Handbook of Operations Research and Management Science in Higher Education, 2021, pp 323-363 from Springer

Abstract: Abstract In this chapter, an accelerated variant of the threshold acceptance (TA) metaheuristic, named FastTA, is proposed for solving the examination timetabling problem. FastTA executes a lower number of evaluations compared to TA while not worsening the solution cost in a significant way. Each exam selected for scheduling is only moved if that exam had any accepted moves in the immediately preceding threshold bin; otherwise, the exam is fixed and is not evaluated anymore. If an exam had zero accepted movements in the preceding threshold bin, it is likely to have few or zero accepted movements in the future, as it is becoming crystallised. The FastTA and TA were tested on the Toronto and Second International Timetabling Competition benchmark (ITC 2007) sets. Compared to TA, the FastTA uses 38% and 22% less evaluations, on average, on the Toronto and ITC 2007 sets, respectively. On the ITC 2007 set, the FastTA is competitive with TA attaining the best average solution cost value in four out of twelve instances while requiring less time to execute. Compared with the state-of-the-art approaches, the FastTA is able to achieve competitive results. The main contribution/value of this chapter is the proposal of a new acceptance criterion for the TA metaheuristic, which leads to a significantly faster variant (FastTA), and its application to solve public examination timetabling benchmark sets.

Keywords: Examination timetabling; Hybrid algorithm; ITC 2007 benchmark set; Local search; Threshold acceptance; Timetabling; Toronto benchmark set (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:isochp:978-3-030-74051-1_11

Ordering information: This item can be ordered from
http://www.springer.com/9783030740511

DOI: 10.1007/978-3-030-74051-1_11

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().