Rat-Inspired Algorithm Tackles the Chaos of University Exam Scheduling

Every semester, universities around the world face a computational puzzle that looks deceptively simple on paper but can quickly spiral into a combinatorial nightmare: deciding which examinations go into which timeslots so that no student is forced to sit two exams at once, while keeping the overall burden on students as light as possible. A new study published in Neural Computing and Applications by Mohammad Abu Setteh, Mohammed Azmi Al-Betar, and Mirna Nachouki of Ajman University’s Artificial Intelligence Research Center takes aim at this classic scheduling problem with an unusual weapon: a hybrid optimization algorithm inspired by the foraging behavior of rats, supercharged with two of the most venerable techniques in the metaheuristics toolbox.

The problem the researchers tackle, known as examination timetabling, belongs to a family of combinatorial optimization challenges that are computationally intractable at scale. The goal is to assign each exam to a timeslot without creating conflicts, meaning no student should be scheduled for two exams in the same period. Beyond hard constraints, there are soft constraints that translate into penalties: spreading exams out so students are not crammed with back-to-back tests, for example. Because the number of possible timetables grows explosively with the number of exams and students, finding the best possible schedule by brute force is out of the question for real institutions. Instead, researchers rely on metaheuristics, intelligent search strategies that explore the vast space of possible schedules in search of very good, if not provably optimal, solutions.

The core engine of the new approach is the Rat Optimization Algorithm, or ROA, a relatively recent nature-inspired method introduced in 2024 that mimics the swarming and foraging dynamics of rats. In its original form, ROA is designed for continuous optimization, where solutions are points in a smooth numerical landscape. Examination timetabling, however, is a discrete problem: an exam either sits in timeslot three or it does not, and there is no meaningful in-between. The researchers therefore reformulated ROA’s operators so that the algorithm’s search moves operate directly on discrete timeslot assignments, a necessary adaptation that preserves the spirit of the rat-inspired search while making it compatible with the structure of the problem.

Two further ingredients round out the hybrid. The first is the Lévy Flight, a mathematical description of a movement pattern observed across nature, from albatross foraging paths to human hunter-gatherer travel, in which mostly short, local steps are punctuated by occasional long jumps. In optimization terms, Lévy Flights allow an algorithm to escape the gravitational pull of a local optimum by occasionally making dramatic, far-reaching changes to a solution. The second ingredient is simulated annealing, a technique dating back to 1983 that borrows its logic from the cooling of molten metal: it accepts most improvements outright, but also tolerates some worsening moves with a probability that gradually decreases as the search matures, giving the algorithm a controlled way to explore early on and to refine later.

Crucially, the authors did not simply bolt these components together. They describe three main adaptations that coordinate the pieces. ROA’s operators were rewritten for discrete timeslots, as noted. The Lévy Flight mechanism was designed to apply selective perturbations with feasibility checking, so that a long jump does not wreck the hard constraint that no student has conflicting exams; if a perturbation breaks feasibility, it is checked and handled rather than blindly accepted. And simulated annealing’s acceptance criterion was synchronized with ROA’s search phases, so that the willingness to accept worse solutions ebbs and flows in harmony with the underlying swarm dynamics rather than running on an independent schedule. On top of this coordination layer, the team incorporated Kempe chain operators, a neighborhood structure borrowed from graph coloring in which an entire chain of interdependent exam assignments is moved at once, providing a powerful local refinement mechanism that can untangle stubborn scheduling knots.

To find out whether all this engineering actually pays off, the researchers ran a rigorous evaluation on twelve benchmark instances from the well-known Toronto dataset, a standard proving ground for examination timetabling research hosted via the University of Nottingham’s public repository. The evaluation had two prongs: ablation studies, which systematically strip away components to measure each one’s individual contribution, and comparisons against eleven state-of-the-art methods from the literature. The ablation results are striking. The full hybrid configuration improved on a basic ROA implementation by 38.4 percent, with the Lévy Flight component contributing 13.0 percent of that gain and simulated annealing contributing 10.5 percent. These numbers suggest that the hybridization is not decorative; each added mechanism earns its place in the pipeline.

In the head-to-head comparisons, the hybrid algorithm achieved a Friedman rank of 4.59, placing it third overall among the methods tested. Statistical rigor was a priority: the authors applied the Wilcoxon, Friedman, Nemenyi, and Holm tests to the results, and this analysis confirmed that there was no statistically significant difference between the top two methods in the comparison. In other words, while the new hybrid did not claim the crown, it sits firmly within the leading pack, and its performance is statistically indistinguishable from the best performers. For a newly adapted algorithm competing against mature, heavily tuned methods, that is a notable result.

Perhaps just as important as raw solution quality is consistency, and here the algorithm shines. Across all twelve instances, the method demonstrated strong repeatability, with a coefficient of variation as low as 0.01 percent between runs. Stochastic algorithms can sometimes produce wildly different schedules from one run to the next, which is a practical headache for administrators who need to trust that the tool will deliver a comparable result every time. A coefficient of variation in the hundredths of a percent range indicates that the hybrid’s search is remarkably stable, likely a benefit of the coordinated acceptance mechanism that keeps the exploration-exploitation balance steady throughout the run.

The study arrives amid a long and active research tradition. Examination timetabling has been studied algorithmically since at least the mid-1990s, when Carter, Laporte, and Lee laid out foundational strategies, and simulated annealing itself was applied to the problem as early as 1998 by Thompson and Dowsland. Since then, the field has seen tabu search, ant algorithms, artificial bee colonies, genetic algorithms, harmony search, intelligent water drops, firefly algorithms, and cellular memetic approaches, among many others. Surveys published in 2009 and again in 2024 chart the steady evolution of solution methodologies, and the persistence of the problem in the literature reflects its real-world stakes: poorly balanced exam schedules translate directly into student stress and institutional friction.

What the Ajman University team’s work illustrates is a broader lesson in modern metaheuristic design: single algorithms rarely dominate, and the most competitive systems are often carefully orchestrated hybrids in which each component compensates for the weaknesses of the others. The rat-inspired swarm provides the population-level exploration, the Lévy Flight injects the occasional bold leap out of stagnation, simulated annealing governs the tolerance for temporary setbacks, and Kempe chains perform the surgical fine-tuning. The result, published in Neural Computing and Applications as volume 38, article 735, is a system that lifts a young optimization method into contention with the state of the art, while offering a template for how discrete scheduling problems can benefit from disciplined hybridization rather than novelty for its own sake.

Subject of Research: A hybrid metaheuristic combining the rat optimization algorithm, Lévy Flights, and simulated annealing for solving the examination timetabling problem.

Article Title: Hybridizing rat optimization algorithm with Lévy Flights and simulated annealing for examination timetabling

Article References: Setteh, M. A., Al-Betar, M. A., & Nachouki, M. (2026). Hybridizing rat optimization algorithm with Lévy Flights and simulated annealing for examination timetabling. Neural Computing and Applications, 38(17), Article 735. https://doi.org/10.1007/s00521-026-12466-5

Image Credits: AI Generated

DOI: 10.1007/s00521-026-12466-5

Keywords: examination timetabling, rat optimization algorithm, Lévy Flight, simulated annealing, hybrid metaheuristic, combinatorial optimization, Kempe chains, Toronto benchmarks, scheduling, swarm intelligence, Neural Computing and Applications, discrete optimization