Proceedings

Airlines make thousands of interconnected decisions across different planning horizons, ranging from long-term fleet and network planning to real-time operational control. While each planning process has traditionally been optimized in isolation, increasing operational complexity and uncertainty call for a more integrated perspective on resilience.

Drawing on insights from an ongoing research collaboration, initiated through the Kickstart.AI program, between Air France-KLM, Utrecht University, and the University of Twente, this presentation places a series of research projects within the broader context of the airline planning process. Through practical case studies, it highlights three recurring themes: accounting for interdependencies across planning processes, explicitly incorporating uncertainty into planning models, and developing customized optimization methods tailored to the unique characteristics of airline planning.

Download PDF

We present a general local search framework for scenario-based two-stage combinatorial stochastic programming problems. The framework is based on Adaptive Large Neighborhood Search (ALNS), where an upper-level local search method operates on the first-stage decision variables, while a number of lower-level local search methods optimize the individual scenarios. As a demonstration of the Stochastic ALNS algorithm, the framework is tested on the two-stage stochastic Prize-collecting Vehicle Routing Problem, and stochastic Team Orienteering Problem. In all problems, the customers, demands and travel times can be stochastic as long as they can be represented by a number of scenarios. Computational experiments show that the algorithm scales well with the number of scenarios, making it possible to solve instances with up to 1000 customers in short time.

Download PDF

Metaheuristics serve as the primary building blocks for modern industrial solvers and complex optimization engines. While their flexibility allows for rapid integration into both academic frameworks and practical software, the pursuit of performance often leads to their over-engineered designs. Beyond that, we emphasize the idea of simplicity and simplification in algorithm design as the keys to generality and robustness. Drawing on a wide range of successful applications, we show how distilling algorithms to their core principles leads to better outcomes. We present case studies across several optimization challenges: implementing slack induction by string removals in vehicle routing, utilizing iterative forward search in course timetabling, and applying local search in grid scheduling and warehouse planning. Furthermore, we discuss how cross-domain hyper-heuristics benefit from this philosophy. With a focus on robust performance across diverse and complex domains, designing simple(r) algorithms can advance the current state of the art.

Download PDF

Designing high-performance heuristics is a complex task that requires both intuition and deep domain knowledge. Recent advances in deep reinforcement learning (DRL) and large language models (LLMs) have led to new ways of creating heuristics that rival the performance of state-of-the-art human-designed approaches. In this talk, I introduce these new mechanisms for heuristic design and describe their advantages and limitations, with a focus on routing and scheduling problems. The talk will include two methods: Neural Deconstruction Search, an approach harnessing DRL to learn policies for constructing routing and scheduling solutions, and VRPAgent, an evolutionary approach to generate novel routing heuristics.

Download PDF

Exact approaches to the Runway Sequencing Problem (RSP) rely on pruning rules to make optimisation tractable. However, these rules are typically proven manually, making it difficult to evaluate new candidates or reuse rules across problem variants. We propose the use of Satisfiability Modulo Theories to automatically verify pruning rules for the RSP. Our approach verifies several published pruning rules within a symbolic sequence abstraction, where correctness is established by refuting all counterexamples. This enables a more systematic workflow for pruning rule development, and provides a basis for future rule synthesis.

Download PDF

The Trigger Arc Travelling Salesman Problem (TATSP) is a recently introduced variant of the TSP in which arc costs depend dynamically on the traversal order: traversing a trigger arc before a target arc may change the target’s cost, with only the last trigger encountered being active. The problem arises in warehouse routing with compactable storage systems and has so far only been addressed by an integer linear programming formulation that fails to scale beyond approximately 25 nodes. We propose an Iterated Local Search (ILS) with a simulated annealing acceptance criterion, using first-improvement hill climbing over an Or-opt neighbourhood adapted for trigger-arc semantics via a delta cost evaluation scheme that traces trigger fan-out. Computational experiments on 55 benchmark instances from the MESS 2024 competition show that the approach achieves an average gap of 1.79% on the dense C1 instances (20–60 nodes) and 0.07% on the sparser C2 instances (18– 142 nodes), establishing 5 new best-known solutions on the latter family while scaling well beyond the reach of exact methods.

Download PDF

This paper addresses the train dispatching problem, which involves rescheduling and rerouting delayed trains on a shared railway network to minimize total delay and avoid resource conflicts. Dispatching optimization can reduce overall lateness, increase network throughput, and improve the utilization of railway infrastructure. We propose an iterative model reduction method that reduces the complexity of problem instances while ensuring that no optimal solution is eliminated from the search space. A series of model transformations are introduced that tighten operation start-time bounds, merge compatible operations, prune dominated subpaths, remove redundant resource requirements, and linearize train operation graphs. The proposed reduction method can be applied either as a preprocessing step or dynamically within other solution methods. In this paper, we apply the reduction as preprocessing and propose a compact constraint programming formulation based on the reformulated model. The solution method is evaluated on the DISPLIB 2025 benchmark library, which consists of instances derived from real-world use cases. The computational results show that the proposed model reduction method can substantially simplify large problem instances and improve performance. The complete solution method was able to find high-quality feasible solutions for most benchmark instances and achieved competitive performance in the DISPLIB 2025 competition.

Download PDF

University course timetabling is a dynamic optimization problem in which published schedules frequently require modification due to changes in enrolment, staffing, or resource availability. The Minimal Perturbation Problem (MPP) addresses this by seeking revised timetables that minimize deviation from an existing solution. However, standard formulations of MPP typically treat all timetable changes as equivalent, irrespective of their timing, type, or impact on end-users. This paper proposes a behaviorally informed extension to MPP that introduces a disruptiveness weighting for post-publication timetable changes. The proposed Minimally Disruptive Perturbation (MDP) model weights post-publication changes according to the week of occurrence, the type of change, and the number of students affected. This enables a more nuanced assessment of disruption in dynamic timetabling contexts. The model incorporates temporal weighting, change type and student reach to assess the behavioral cost, by way of a disruptiveness score, of timetable volatility. Using institutional data from a large UK university, the paper demonstrates how the disruptiveness score differentiates between changes that are operationally similar but behaviorally distinct. The approach is intended as a decision-support metric that can be incorporated into post-publication rescheduling processes and candidate solution evaluation, supporting more human-centric timetable optimization.

Download PDF

This paper addresses a real-world personnel rostering problem arising in a public university library. The roster covers Monday–Saturday operations and must satisfy shift-coverage and skill-mix requirements, while handling a set of undesirable duties (Friday evening and Saturdays) subject to rotation and adjacency rules. The main challenge is to reconcile these operational constraints with staff preferences on the undesirable duties and to do so equitably. We introduce a max–min fairness criterion that maximizes the minimum normalized happiness across employees, thereby protecting the least satisfied staff member with respect to the roster accomodating their preferences. We first investigate the effectiveness of a compact mixed-integer linear programming (MILP) formulation for this setting. We also propose an alternative, structure-exploiting solution workflow based on a two-stage decomposition: Stage 1 optimizes assignments on the undesirable days, and Stage 2 completes weekday evening duties using the fixed weekly availability patterns implied by the Stage 1 decisions. Since weeks with holidays may induce additional imbalance in days off, we further introduce a refinement model that balances worked days within holiday weeks by minimizing the range between the most- and least-loaded staff members. A real-world application shows that the proposed workflow produces equitable and transparent rosters, with high worst-case normalized satisfaction, and can be used routinely by non-technical personnel.

Download PDF

The optimal balance between exploitation and exploratory capabilities of optimization algorithms plays a vital role in convergence on combinatorial optimization problems. While hybridizing diversification and intensification has been proven effective in scheduling tasks, the mechanism for switching between them during different stages of the search remains less explored. In this study, a restart strategy based on Luby’s universal sequence is adopted as a neighborhood structure guidance to manage the transition between exploration and exploitation, guided by theoretical indications of its efficacy. To validate this, a diversification approach based on Random Search is hybridized with an intensification approach based on Hill Climbing. This methodology is applied to a university course timetabling with student sectioning benchmark as a proof of concept. When tested on the International Timetabling Competition 2019 dataset, the empirical results align with theoretical expectations and outperform the individual building blocks at a faster pace, finding 80% more feasible candidate solutions. Beyond this experiment, these findings are significant for balancing search algorithms within Operations Research in general and contribute to other optimization tasks.

Download PDF

This paper addresses the unrelated parallel-machine scheduling problem with non-resumable maintenance under a makespan minimization objective. Maintenance periods restrict machine availability and create a strong coupling between job assignment and sequencing decisions, making solution evaluation computationally expensive. We propose a decomposition-based hybrid genetic algorithm in which the evolutionary search determines the assignment of jobs to machines, thereby defining for each machine the subset of jobs it must process. Given this assignment, each machine-level subproblem is solved optimally using a pseudo-polynomial dynamic programming procedure formulated as a 0–1 knapsack problem. While this exact evaluation ensures accuracy, it constitutes the main computational bottleneck. To reduce this cost, we introduce a surrogate-assisted evaluation mechanism that approximates makespan values and selectively replaces exact computations during the search. The surrogate models are trained online and updated to reflect the evolving search region. Computational experiments on benchmark instances show that the proposed approach achieves substantial runtime reductions while preserving high solution quality. These results demonstrate the effectiveness of combining exact decomposition with data-driven approximation for maintenance-constrained unrelated parallel-machine scheduling.

Download PDF

The Radiotherapy Scheduling Problem (RTSP) concerns finding an optimal appointment schedule for patients undergoing radiation treatments. Given its considerable impact on clinical outcomes, this problem has been studied in previous research, relying on datasets obtained from various hospital settings; however, such real-world datasets are rarely made public--mainly for privacy reasons--while synthetic problem instances are rare and not standardised, which makes the comparison between scheduling algorithms harder. To address this gap, we propose a Benchmark Instance Management Tool that comprehends 1) a generator of new instances that samples from statistical distributions tuned on two real-world reference datasets from a big Belgian cancer centre and a small Italian radiotherapy unit, 2) a set of solvers, such as Mixed Integer Linear Programming, Simulated Annealing and two heuristics, and 3) a validator to check solution feasibility. Moreover, we propose a standardised input and output format. The generated instances are compared to real-world data by means of Instance Space Analysis on features extracted directly from instances. The results reveal two sharply separated clusters for the real-world reference datasets in the 2-dimensional feature space, while the newly generated instances not only populate those clusters but also fill the gap between them.

Download PDF

Clinic scheduling systems built on constraint programming offer powerful optimization, but adapting them to frequently changing operational rules remains a bottleneck: every new constraint, from staff availability changes to patient-specific restrictions, requires a developer to translate domain knowledge into solver code. We present an LLM-based agent that lets non-technical clinic staff add scheduling constraints by describing them in natural language. New constraints are injected as modular plugins with a standardized interface, preserving the integrity of the core scheduling model. The agent autonomously resolves entity references against the clinic database and verifies generated code through self-designed test scenarios before deployment. On a benchmark of 234 scheduling constraints across nine operationally relevant categories, the agent achieves 90.2% accuracy versus 70–82% for non-agentic alternatives. Ablation reveals that database search and iterative self-testing are complementary, with their combination (+20.1 pp) exceeding the sum of individual contributions (+16.2 pp). In a supplementary experiment, directly modifying the monolithic scheduling model achieved only 35.4% accuracy, indicating that constraint isolation helps when LLM-generated code must compose with existing scheduling logic.

Download PDF

University study regulations are legal documents which usually induce an enormous amount of valid study plans from which students can choose. And with several other works dealing with courses and/or examinations and not necessarily the regulations behind them, this work is part of an attempt to shift perspectives. Indeed, the combinatorial solution space induced by university study regulations is not at all reasonable for students to explore manually, let alone check for the satisfaction of certain desirable characteristics. Hence, building upon our foundational work, and as part of an effort in the digitalization of higher educational institutions, we hereby present four hard and soft constraints which students are able to apply on the solution space. We present an Answer Set Programming (ASP) approach for reasoning over the solution space induced by the modules in university study regulations, after laying a formal foundation of the constraints. An ASP-driven user interface prototypes our implementation allowing for user interactions with the constraints and solution space exploration.

Download PDF

Real-world scheduling problems frequently involve many, often conflicting objectives. Lexicographic optimization is a widely used approach for such many-objective problems, expressing the objectives' relative importance through a fixed priority order. However, as the number of objectives grows, configuring an effective order becomes challenging: optimizing certain objectives before others restricts the search space and the still obtainable values for remaining objectives in complex ways, and some objectives may dominate others or induce costly trade-offs. In this work, we present a data-driven framework for analyzing and supporting the configuration of lexicographic optimization in many-objective scheduling problems formulated as linear programs. We consider the space of all objective function permutations and compile an objective order graph that captures how the solution space and diverse quantitative measures evolve as objectives are fixed sequentially. Merging and pruning strategies recognize and remove symmetries, substantially reducing the graph. We demonstrate the framework on a smart electric vehicle charging scheduling problem with seven objectives deployed in a real-world setting. Results reveal strong asymmetries between objectives and show that only a small fraction of all possible objective orders lead to distinct solutions. We further present an interactive tool that allows users to explore objective orderings and their consequences.

Download PDF

University course timetabling is an NP-hard optimization problem defined by complex combinations of academic, pedagogical, and resource-related constraints. While recent advances in constraint pro gramming and hybrid optimization have improved model expressiveness, institutions still lack integrated tools that connect optimization, data collection, recommendation, and student-support capabilities within a unified platform. This paper presents MounouZinc, a tool for university timetabling, designed as a modular built on MiniZinc. It integrates a PostgreSQL backend, a Python automation layer, and a web-based in terface for collecting professor availability and timeslot preferences. The system integrates an AI-driven professor–course matching agent, which prioritizes professor assignments based on specialization and course de scriptions, and a conversational chatbot that supports both new ap plicants (FAQ services) and current students (iAdvisor-style course se lection and enrollment assistance). Experimental evaluations were con ducted on synthetically generated datasets designed to reflect real in stitutional scenarios demonstrate that MounouZinc produces feasible, high-quality timetables that align with diverse academic policies while providing end-to-end decision-support functionalities rarely found in ex isting UCTP systems. MounouZinc advances beyond basic solving to offer an integrated decision-support platform.

Download PDF

Despite significant research into nurse rostering problems, generating feasible solutions for large instances that include complex hard constraints as part of nurses' contracts, and proving their optimality, remains a challenge. The combination of long rostering periods and many shift types leads to enormous search trees that simply cannot be fathomed by current exact algorithms. In this paper we help close this gap by developing effective pruning strategies for dynamic programming approaches, drastically reducing the number of individual rosters that must be considered, as well as a heuristic that quickly identifies feasible rosters. We demonstrate how incorporating these strategies into state-of-the-art methods significantly speeds up the computation of optimal (partial) solutions. The strategies we suggest for rostering a single nurse in isolation can be embedded within a complete nurse rostering approach.

Download PDF

This study addresses the Home Health Care (HHC) problem with the goals of minimizing both the cost of hiring caregivers and the transportation cost incurred as caregivers travel between patients' residences, while satisfying patient-friendliness constraints. To achieve the aforementioned goals, this study proposes a new caregiver assignment and routing algorithm, called hiCH. Our algorithm does not require a set of caregivers to be given in advance, but instead hires caregivers one by one as the problem is addressed, thereby reducing hiring costs. Our algorithm hiCH adopts a hierarchical convex hull approach, considering the convex hull formed by unvisited patients and selecting a patient with the highest care level required on the convex hull to determine the employment level of the caregiver and serve as the starting point of the caregiver's visiting path, with the aim of reducing transportation cost. We improve hiCH by proposing D-hiCH, in which patients requests are further sorted according to their required service levels and time windows. To further improve solution quality, we also propose a genetic algorithm (GA) version of D-hiCH.

Download PDF

High school timetabling is a challenging combinatorial optimization problem involving numerous hard and soft constraints and competing stakeholder interests. In modular high schools, student course selections introduce additional complexity beyond standard time and resource constraints. Structural and regulatory differences between schools further increase instance variability, making it unlikely that a single solution approach performs best across all cases. To address this variability, identifying instance characteristics that explain differences in algorithm performance is essential for informed algorithm selection. In this paper, we apply Instance Space Analysis (ISA) to the modular extension of the Extended High School Timetabling format (XHSTT). We analyze two fundamentally different solution approaches: a construction heuristic, Simulated Annealing (SA), and an Adaptive Large Neighborhood Search (ALNS) method. Our study considers approximately 1500 diverse instances, including real-world modular XHSTT instances, existing instances extended with student course selections, and purely artificial modular instances. The modified and artificial instances represent novel contributions to the modular XHSTT benchmark set. Using ISA, we characterize the instance space and evaluate algorithm performance. The results provide insights into structural properties influencing solver behavior and demonstrate ISA’s potential for supporting algorithm selection in modular high school timetabling.

Download PDF

Academic timetabling remains one of the most complex and resource-sensitive functions in educational institutions worldwide. Although major advances have been made in automated timetabling and optimization techniques, many developing countries still face systemic challenges arising from decentralized scheduling practices, limited technical coordination, and uneven capacity among timetable coordinators. This paper presents the establishment and emerging role of the Forum for Tanzania Academic Timetable Coordinators (FTATC), a national technical platform created to strengthen coordination, capacity, and efficiency in academic timetabling across all education levels, from pre-primary to universities. The initiative represents one of the first structured national efforts in Sub-Saharan Africa to institutionalize collaboration among timetable coordinators. The paper examines the context that motivated the creation of FTATC, including resource constraints, scheduling conflicts, and inefficiencies associated with isolated timetabling practices. It then describes the Forum’s organizational model, capacity-building activities, and role in promoting best practices and the professionalization of academic timetabling. Using qualitative institutional observations and practitioner experiences, the paper highlights early outcomes, including improved technical awareness, stronger coordination among institutions, and increased recognition of timetabling as a strategic function. The study contributes to timetabling literature by presenting a national coordination framework that complements algorithmic and institutional approaches and discusses implications for developing countries seeking scalable, collaborative models to improve timetabling efficiency and institutional performance.

Download PDF

Surrogate-assisted genetic programming (SAGP) has become an effective approach for reducing the computational burden of automated heuristic design in dynamic scheduling, where fitness evaluation is typically dominated by repeated stochastic simulation. Its effectiveness, however, depends critically on the characterization used to represent GP individuals for surrogate modeling. Conventional top-1 phenotypic characterization (PC) retains only a top-1 signal from each decision situation, thereby discarding most of the induced preference ordering and yielding a coarse behavioral representation for distance-based surrogates. This paper proposes weighted Spearman phenotypic characterization (WSPC), which maps each individual to a fixed-length behavioral embedding by comparing the complete ranking it induces in each decision situation with that of a reference policy. WSPC introduces position-dependent weights into the Spearman correlation so that disagreements near the top of the ranking receive greater emphasis. The resulting characterization preserves richer behavioral information than conventional top-1 phenotypic characterization while remaining compatible with standard distance-based surrogates such as $k$-nearest neighbors. Experiments on dynamic container terminal truck scheduling show that, under the same training-time budget, WSPC generally provides stronger surrogate quality and characterization quality, and achieves the best average scheduling performance across the tested scenarios.

Download PDF

We introduce a transformer-based approach for generating nurse schedules. A constraint programming model with a randomized objective produces diverse feasible schedules used as training data. The transformer learns the underlying constraint structure and proposes complete assignments without any search procedure. We evaluate the model on three constraint configurations spanning 3 to 40 nurses and report per-family satisfaction rates across four constraint types. The results reveal a learnability hierarchy: local per-nurse rules (forbidden transitions, 80.8-99.3%) are captured reliably, bounded-window constraints (consecutive limits) reach 99-100% on small instances but fall to 30.7% on larger ones, and global cross-nurse constraints (coverage 14-86.7%, period limits 7.3-62%) remain the hardest to satisfy. Instance size is the dominant factor, as left-to-right generation cannot coordinate assignments across nurses. A violation analysis shows that even when constraints are not perfectly satisfied, the number of violations per schedule remains low (median 0-5.5), indicating that the model produces near-feasible schedules suitable as warm-start solutions for repair or local-search methods.

Download PDF

We consider the problem of reducing complexity from dynamic arrival routes (DARs). DARs entail an arrival tree that merges all arriving traffic during a given time period towards the runway, such that we can guarantee temporal separation and optimal descent profiles for all the arriving aircraft. With DARs, we aim to answer the need for reduced environmental impact while alleviating air-traffic-controller workload through the automated separation. While DARs provide a high degree of flexibility---they allow to accommodate even high-traffic scenarios without reducing capacity---the points in which the entry-point--runway paths merge along the tree, so-called merge points, can be located differently in the TMA during different time periods. However, switching these merge points often yields high complexity for air traffic controllers. In this paper, we propose a data-driven approach to select a candidate set of merge points, integrate the restriction to this candidate set into the mathematical framework for DARs, and demonstrate our approach on an example of a realistic high-traffic scenario at Stockholm Arlanda airport. We are able to obtain feasible solutions even for very few merge-point candidates, with a tradeoff of solution quality/performance in the TMA and the complexity induced by the number of merge-point candidates.

Download PDF

University timetabling is a critical operational challenge, with policy decisions directly impacting staff, students, and resources. This paper presents a new benchmark instance derived from real-world data. Using this instance alongside an existing timetabling model and solution methods, we demonstrate how four strategic policy questions can be assessed: curriculum restructuring, enforcement of core teaching hours, room capacity relaxation, and hybrid teaching under reduced physical capacity. For each problem, we identify and apply an appropriate technique from the literature, including sensitivity analysis, objective function modification, constraint relaxation, and model extension. Our results show that students remain highly interconnected regardless of curriculum changes, that intuitive scheduling improvements can have counterproductive effects, and that modest capacity relaxation yields meaningful gains. The benchmark instance and methodology provide a reusable framework for timetabling practitioners tackling similar strategic problems.

Download PDF

Permutation schedules in reentrant flow shops can be defined in several ways depending on job-passing and level-passing constraints across the sub-jobs. This gives rise to four permutation types. In this paper, we investigate the reentrant permutation flow shop with the objective of total completion time for the four permutation types. We show that allowing level passing is more effective at reducing the objective function value than allowing job passing. We conduct a systematic analysis of small instances to demonstrate this observation. We also address larger instances using the simulated annealing metaheuristic. The computational results demonstrate the strength of level passing with respect to the total completion time objective. In particular, the permutation type that allows level passing while prohibiting job passing offers a good trade-off for obtaining high-quality solutions in a reduced solution space.

Download PDF

This paper addresses the exam invigilator assignment problem with interaction-oriented objectives in a university with multiple departments. The problem consists of assigning invigilators to exams, where each exam requires a given number of invigilators, with each invigilator subject to availability and workload constraints. We consider two objective variants. Contact maximization seeks to maximize the number of unique interdepartmental contacts to stimulate interaction between departments. Contact reduction seeks to minimize the total number of unique contacts to limit health risks during pandemics or seasonal outbreaks. For both variants, we develop bounds on the objective value and propose a multi-neighborhood local search heuristic. Computational experiments on benchmark instances show that our proposed bounds improve or match almost all previously reported bounds. Moreover, the proposed heuristic improves upon all previously reported best-known solutions. For many contact-maximization instances, the best solution found matches the new bound, thereby proving optimality.

Download PDF

We study a surgical case planning problem in which patients must be selected and scheduled for surgery under uncertainty in both surgery durations and anaesthesiologist availability. To address this problem, we use a Predict-then-Optimize approach that combines a regression model for predicting surgery durations with a classification model for predicting staff absences, followed by an integer programming model for generating solutions. In a computational study on real hospital data, we investigate how prediction accuracy affects the quality of the resulting solutions by simulating varying levels of prediction accuracy. The evaluation of generated solutions considers rescheduling policies to handle realized uncertainties to provide a realistic approximation of operational costs. Our results provide insights into the interaction between multiple predictive models and optimization, highlighting that better predictions do not necessarily lead to better optimization outcomes.

Download PDF

The aircraft maintenance routing problem with a maintenance distribution objective (AMRP-D) considers a set of flight legs that have to be assigned to a set of available aircraft. While the start and end time of the flight legs are specified in advance, the aircraft are required to undergo various maintenance tasks in the planning horizon. Scheduling these maintenance tasks as evenly as possible is the objective of the AMRP-D, however, for most instances it is even difficult to find a feasible solution covering all maintenance requirements. In this work, we focus on different decompositions strategies in order to provide feasible solutions for the benchmark instances of this problem.

Download PDF

This paper presents ongoing work on a solver for nurse rostering which is oriented towards practice, in that it aims to find good solutions quickly for a wide range of instances. This abstract shows that the current version of the solver, KHE26, has improved significantly on the previous version on one important data set, of four-week instances from the Second International Timetabling Competition. The full paper will present results for this as well as several other data sets, and will explain how these improvements have been obtained without fundamental changes to the solver.

Download PDF

The University Course Timetabling Problem (UCTTP) often assumes that course enrollment is given a priori, though this is not always the case in practice. In this extended abstract, we outline our work to predict unconstrained course demand and student registration behavior using methods borrowed from airline revenue management, and to analyze the impact of these predictions within a timetabling optimization model.

Download PDF

In this work, we study novel neighborhood structures for incomplete round robin tournaments. We show that the proposed neighborhoods introduce non-isomorphic games into the schedule, thereby increasing the solution space connectivity over existing neighborhoods. We also embed the neighborhoods in a metaheuristic and obtain several new best solutions for some selected problems involving timetabling an incomplete round robin tournament.

Download PDF

This research develops an integrated optimization framework for monthly rostering of airport ground security personnel. The approach combines a Simulated Annealing metaheuristic with a Minimum Cost Flow based staffing assessment to efficiently evaluate coverage and guide the search. Using a real-world dataset from airport security operations, the framework addresses the practical complexity of simultaneously constructing shifts and assigning them to employees while satisfying labor regulations, contractual constraints and employee preferences. Initial rosters are generated through greedy construction heuristics and subsequently improved using neighborhood moves that modify assignments across multi-day blocks and refine shift characteristics such as timing, duration, and break placement. The Minimum Cost Flow formulation matches available employees to skill demand in each period, enabling fast evaluation of under- and overstaffing across the planning horizon.

Download PDF

This study addresses the Home Healthcare Routing and Scheduling Problem (HHCRSP), a complex extension of the Vehicle Routing Problem involving joint nurse–patient assignment, service scheduling, and route planning under synchronized multi-nurse constraints and strict time windows. To tackle the highly constrained search space, we propose a Hybrid Adaptive Metaheuristic-based Q-Learning (HAMQL). The approach utilizes a survival-selection mechanism to maintain population diversity while leveraging Q-learning as an adaptive memory scheme to guide local search operations. The proposed algorithm was evaluated on benchmark instances of varying scales (up to 100 patients) representing high-density routing scenarios. The results demonstrate promising scalability and high constraint-fulfillment ratios in medium- and large-scale instances, approaching MILP objective function values (or bounds) with faster CPU Time. Finally, we discuss computational trade-offs, particularly regarding convergence rates in large-scale scenarios, and outline paths for future algorithmic refinement.

Download PDF

First-Break-Then-Schedule (FBTS, cf. Nemhauser and Trick, 1998) is a method for optimizing sports tournament schedules that has gained widespread recognition in the literature for its effectiveness. The method decouples two core decisions: (i.) for each team, whether they play home or away in each round, i.e., the home-away pattern (HAP); and (ii.) which teams are meeting in which round. FBTS faces two critical challenges. First, the method relies on full enumeration of possible HAPs that can be exponential in size, or it considers heuristic approaches. Second, the method lacks a systematic backtracking mechanism when HAP assignments turn out infeasible. We provide an integer programming Branch-Price-and-Cut framework that implements FBTS in an effective and exact way. Rather than enumerating all possible HAPs, our framework starts with the most promising patterns and uses a variable pricing approach to generate missing ones. To organize backtracking, we integrate the Branch-and-Price approach with the traditional Benders' decomposition approach from Van Bulck and Goossens (2023). Moreover, we apply the symmetry-handling method orbitopal fixing to handle symmetries among teams. Whereas our framework is broadly applicable to many classes of problems, in our extended abstract we focus on one particular problem, for which we present effective preliminary results.

Download PDF

Shift design and rostering problems are often solved in a sequential manner to reduce the complexity of solving each phase, even though the results of shift design have a significant impact on the rostering phase. This impact is partially mitigated by adding additional constraints to shift design, e.g., on the average length of shifts. However, this approach does not work well in several scenarios, including high demand variation or the presence of multiple contracts. Therefore, this work proposes an integrated approach for shift design and rostering for a heterogenous workforce combining various full- and part-time contracts. Preliminary results show that the solution method based on Simulated Annealing can effectively solve the integrated problem and provide substantial benefits over the sequential approach in the presence of multiple contracts.

Download PDF

We present ASAS (Adaptive Structure-Aware Selector), a deterministic hyper-heuristic framework that distills large language model reasoning into transparent, explainable selection rules for examination timetabling. Using GPT-4 in an offline phase, we convert chain-of-thought reasoning into a seven-rule engine that maps five-dimensional structural features to candidate heuristic sets. Experiments on the Toronto bench- mark demonstrate that ASAS achieves a 92.3% perfect decision rate while providing an estimated 3.0× computational speedup. Independent validation on 18 generated instances confirms out-of-sample generalisa- tion with 100% accuracy, demonstrating the viability of offline LLM dis- tillation for combinatorial optimisation.

Download PDF

Extended Abstract Submission

Download PDF

Untis has provided scheduling software for schools worldwide for over 50 years. In recent years, the optimization team at Untis, in collaboration with IMC Krems University of Applied Sciences, has developed new approaches to course optimization. In this talk, we present one such approach: a course optimization for Finnish high schools. The solution is currently deployed and in operational use across multiple Finnish schools. Finnish high schools operate under a distinctive timetabling regime: a fixed master timetable, shared across all schools in a district, assigns time slots to clusters across multiple terms. Because time slots are aligned district-wide, students can attend courses at neighboring schools during the first and last periods of the day --- a feature rarely seen in other countries. These circumstances significantly shape the resulting optimization problem. The course optimization problem in this setting is a variant of student sectioning: given a set of students with their course choices, a set of courses, terms, and a fixed number of clusters, assign each student to course sections and each course to clusters and terms so as to minimize the total number of student conflicts, subject to constraints such as: - Each student is assigned to at most one cluster per time slot (no conflicts). - Each teacher is assigned to at most one cluster per time slot. - Each room type has a limited number of rooms available per time slot, and each course requires specific room types. - Each course must be assigned to exactly one cluster per term it takes place in. - A course spanning multiple terms must be assigned to clusters in consecutive terms. - Certain courses must be completed by a student in a prescribed order (prerequisite constraints). - Certain courses must be assigned to the same clusters. We formulate the problem as a mixed-integer program (MIP). However, real-world instances with up to 1500 students and 5-6 terms per academic year cannot be solved directly by state-of-the-art commercial and open-source MIP solvers (Gurobi, CPLEX, OR-Tools). The main difficulty is the lack of decomposable structure: in practice, student course choices always overlap across class levels and topic groups, preventing partitioning into independent subproblems. Furthermore, dependencies between terms restrict the decomposability. Our approach combines column generation with large neighborhood search (LNS). We select the initial set of representative students to cover the most constrained cases first, while ensuring that all course types and prerequisite course chain variants are represented. We solve the restricted MIP, analyze the solution to identify violated constraints, and iteratively add students. The LNS phase then improves the solution, considering all students simultaneously. For many real-world instances, this approach finds optimal or near-optimal solutions in under 60 minutes. This results in a significant reduction in planning time for the schedulers. We have also developed a validation layer that detects infeasibilities and conflicts before optimization. This component has proven essential in our deployed system, where schedulers need actionable feedback to adjust inputs when constraints cannot be satisfied. In the talk, we present the MIP formulation, discuss why standard decomposition strategies fail for this problem class, describe the validation layer, and show computational results and practical experiences from our deployment at Finnish schools.

Download PDF

Instructor scheduling is the problem of assigning instructors to classes subject to various constraints, such as instructor availability, qualifications, maximal load, teaching preferences, etc. In this abstract, we describe the university instructional scheduling problem (UISP) as modeled in the open-source educational scheduling system UniTime, and briefly explain the algorithm used to solve it.

Download PDF

Time Sensitive Networking (TSN), standardized as IEEE 802.1Q, is a collection of standards that extend the functionality of Ethernet. This technology can be used to guarantee high reliability and bounded latency, which is crucial when working with hard real-time systems, like avionics (the electronic systems in an aircraft). Our work is about joint routing and scheduling of time-triggered messages in TSN networks, a problem which is known to be computationally challenging. In practice, routing is therefore often done before the scheduling of traffic. However, in heavily loaded networks, particular routing decisions can render the resulting scheduling problem infeasible, even if the complete problem has a solution. Vlk, Hanzálek and Tang present a Logic-based Benders Decomposition (LBBD) approach for this problem, in which the master problem routes the traffic and the scheduling is handled by the subproblem. This approach can, however, fail at solving larger problem instances, since the resulting scheduling subproblem can become intractable. We therefore propose an extension to this approach, using a technique that is often applied in practice to reduce the complexity of the scheduling: no-wait scheduling. This extension allows us to solve a larger number of problem instances and is a first step towards designing a LBBD scheme that can solve even more challenging instances.

Download PDF

This paper presents an integrated software platform designed to automate the end-to-end coordination of undergraduate dissertations, including panel assignment, administrative data processing, conflict detection, and demo/presentation scheduling. The system combines a modern web-based architecture with tailored optimisation methods to address the complex scheduling constraints typically managed manually. A key component of the platform is the demonstration timetabling engine, capable of generating feasible, balanced schedules under staff, room, and time constraints. This work illustrates the proposed system’s easyto-use interactive interface, and compares the performance of the two hyper-heuristic approaches tested on realistic problem instances. Together, these components demonstrate how heuristic optimisation and workflow automation can significantly reduce administrative overhead while improving fairness and reliability in large-scale academic scheduling.

Download PDF

Omnichannel last-mile distribution requires vehicles to manage deliveries, returns, and inventory from multiple fulfillment sources. This study introduces the Vehicle Routing Problem in Omnichannel Distribution with Simultaneous Pickup and Delivery (VRPOSPD), covering delivery-only, pickup-only, and combined customers under store-only and hybrid store–depot scenarios.We propose a Bandit-Based Reinforcement Learning Simulated Annealing (BBRLSA) algorithm with adaptive neighborhood selection and reward-based learning. Results show BBRLSA outperforms conventional SA in solution quality, robustness, and scalability, particularly in hybrid fulfillment.

Download PDF

Curriculum-Based Course Timetabling (CB-CTT) is a long-standing benchmark problem in educational timetabling, yet obtaining robust performance across diverse datasets under strict time limits remains challenging. In this work, we revisit the role of local search for CB-CTT and present a Simulated Annealing (SA) method that uses the LectureKick neighborhood, a generalized version of the classic LectureMove neighborhood. The method combines moves preserving feasibility, sampling biases for soft constraints, efficient delta evaluation, and a cut-off mechanism for the cooling schedule. The algorithm is tuned on a large artificial training set and evaluated on the International Timetabling Competition 2007 instances and additional benchmark datasets. Experimental evidence shows that, under the original ITC 2007 time limits, the proposed approach clearly outperforms previously published local search methods and remains competitive with the state-of-the-art methods reported in the literature. These results indicate that a careful redesign of neighborhoods and move-selection biases can still significantly improve local search performance on a mature benchmark such as CB-CTT.

Download PDF

The Flexible Job Shop Scheduling Problem (FJSP) is a well-known NP-hard combinatorial optimization problem frequently encountered in modern manufacturing systems where operations can be processed on alternative machines. The routing flexibility and interaction between machine assignment and operation sequencing significantly enlarge the search space, making efficient scheduling particularly challenging for large-scale instances. This paper proposes an Adaptive Heterogeneous Sand Cat Swarm Algorithm (AH-SCSA) to enhance the optimization capability of the original Sand Cat Swarm Algorithm. The proposed method integrates heterogeneous population initialization and nonlinear hyperbolic search dynamics to improve population diversity and balance exploration and exploitation during the search process. Experimental evaluations were conducted on the widely used Brandimarte benchmark instances (Mk01--Mk10). The results demonstrate that the proposed algorithm achieves competitive makespan performance with stable convergence behavior across different problem scales.

Download PDF

Infeasibility in automated scheduling systems poses a significant challenge in many real-world applications, as conflicting constraints often prevent the generation of a feasible schedule. This paper focuses on the infeasibility of instances of Test Laboratory Scheduling Problem (TLSP), an extension of the Resource-Constrained Project Scheduling Problem (RCPSP). Specifically, it addresses challenges faced by industrial test laboratories where a large number of tests has to be performed by qualified personnel using specialized equipment, while respecting strict temporal requirements, intricate task dependencies and various other constraints. The infeasibility explainer described in this paper is already deployed in an industrial setting, where it effectively aids in resolving real-world scheduling infeasibilities.

Download PDF

Sports timetables are often judged by whether they satisfy logistical and commercial requirements, but they are also judged by whether they are fair. A common complaint from teams, fans, and the media is that some clubs face unusually difficult stretches of opponents within a short period, while others experience a smoother sequence of fixtures. This issue is especially important in leagues where short runs of difficult matches can strongly affect performance, momentum, and league position. In this extended abstract, we study a fairness-aware timetabling problem in which the dates of home games are treated as fixed, but the assignment of opponents to those dates is to be optimized as the season progresses. This setting is motivated by the fact that, in many real leagues, home dates need to be fixed long beforehand because of venue availability, city operations, broadcast planning, and other logistical constraints. We therefore focus on a more practical question: if the home calendar is fixed, how much can fairness still be improved by dynamically choosing the opponent assignment?

Download PDF

We discuss how to model efficiency and fairness for nurse rostering in terms of shift coverage and investigate the trade-off between both. Violations of shift coverage occur when either more or less nurses than necessary are assigned to a shift. While both cases should be avoided in order to obtain an efficient roster, shift understaffing in particular can have a significant impact on quality of care for patients as well as the wellbeing of nurses due to excessive workload. We formulate an efficiency objective taking into account that more shortages on a single shift exponentially increase the workload for the remaining nurses, and propose three objective functions to assess fairness in a shift coverage context.

Download PDF

In an incomplete round-robin schedule, all teams play the same number of games, but not necessarily against the same subset of opponents. The choice of what games to include is left to the timetable. The incomplete tournament format is rapidly gaining popularity, with a prominent example being the group stage of the UEFA Champions League. We introduce the incomplete Travelling Tournament Problem (iTTP), which is to minimize the overall travel distance in an incomplete round robin schedule. We present benchmark instances, along with lower bounding techniques and a heuristic solution approach. As the iTTP proves surprisingly difficult to solve, we encourage the development of new algorithms for this challenging problem.

Download PDF

Self‑rostering allows healthcare workers to propose their own work schedules, increasing autonomy and engagement, but often results in rosters that fail to meet operational requirements without substantial manual intervention. We present an optimization‑based method that supports planners by adjusting rosters within individual change limits. The approach incorporates shift blocks and a quantified system of change points to ensure fair and minimal modifications. To determine the smallest distance between the initial and modified rosters, we use a minimum-cost flow formulation. A pilot with a Dutch hospital will evaluate the ability of our optimizer to produce good quality rosters more efficiently.

Download PDF

This work compares online and offline selection hyper-heuristics in terms of adaptability and efficiency. As an offline approach, Conditional Markov Chain Search (CMCS) employs a fixed policy learned from training instances, enabling efficient decision-making with minimal runtime overhead. In contrast, the proposed online method leverages TD(0)-based Q-learning to adapt its selection policy during the search. Experiments on the Vehicle Routing Problem with Time Windows (VRPTW) show that while CMCS performs competitively under tight time constraints, the reinforcement learning-based approach achieves superior performance as runtime increases, demonstrating the benefits of online adaptation.

Download PDF

We discuss some issues that appear when implementing scheduling algorithms in practice.

Download PDF

Until recently, research on automated personnel rostering mostly focused on the complex mathematical problem solving perspective, while nowadays human aspects are starting to become more prominent. We identified an initial set of human centered objectives for train crew rostering algorithms. Netherlands Railways (NS) crew's working time preferences were assessed through revealed preferences. It showed feasible to include these in an developed integrated ILP model, which allowed the automatic generation of rosters meeting both CLA constraints and human preferences.

Download PDF

Nurse shortages become particularly severe during infectious disease outbreaks, and some hospitals operating under a three-shift system are forced to make a transition to a two-shift system in emergency situations. Focusing on this situation, this study proposes a scheduling method that enables smooth transitions between three-shift and two-shift duty rosters based on infection risk estimates derived from SEIR-based simulations. The proposed method suppresses undesirable shift sequences and simultaneously generates both three-shift and two-shift duty rosters. Through this approach, infection risk at shift handovers is reduced by decreasing the frequency of staff interactions and feasibility is maintained under uncertainty while preserving nurses’ quality of life. Compared with a conventional re-optimization approach, the proposed method improves the stability of duty rosters.

Download PDF

Upper secondary schools increasingly allow students to choose individualized combinations of elective subjects and introduce self-directed learning (SDL) sessions alongside traditional classroom instruction, which complicates timetable planning. This paper studies the resulting course planning and timetabling problem and proposes a three-phase optimization framework consisting of block building with student sectioning, timetabling of regular course sections, and scheduling of SDL sessions. Initial computational experiments indicate that representative instances can be solved within practical computation times. The framework aims to support schools in implementing flexible pedagogical concepts and enabling more individualized learning paths.

Download PDF

We introduce the Smart TV Scheduling in Public Venues problem, a new combinatorial optimization problem in which an intelligent system must select and schedule content from multiple TV channels on a single screen in a public venue to maximize aggregate viewer satisfaction, allowing gaps in the schedule, subject to operational constraints including genre diversity, minimum continuity, priority time blocks, and channel-switch and partial-broadcast penalties. We propose three solution approaches: a Beam Search Scheduler that constructs an initial high-quality feasible schedule, a Simulated Annealing metaheuristic that refines it through a destroy-and-rebuild neighborhood framework with adaptive operator selection, and a Segment-Based Deterministic Scheduler (SBDS) that independently solves the problem via dynamic programming over structured families of candidate segments. Experiments on 16 benchmark instances covering TV, IPTV, provider-based, and YouTube scenarios show that SBDS substantially outperforms an ILP baseline on large instances, while the Beam Search and Simulated Annealing pipeline achieves competitive results on smaller, well-constrained instances.

Download PDF

The long-term timetabling of railway renewal and maintenance is a complex and large-scale problem with significant economical and societal implications. We present a mixed-integer programming model for solving the Danish Rail Renewal and Maintenance Problem (DRRMP), considering the trade-offs between renewal, maintenance and their impact on traffic disturbance. We consider a time horizon of between 60 and 120 years and the entire Danish railway network. The proposed model incorporates realistic operational constraints provided by the Banedanmark, and is evaluated on data provided by Banedanmark, to test its applicability on large-scale infrastructure planning problems.

Download PDF

The Integrated Healthcare Timetable Competition 2024 introduced the Integrated Healthcare Timetabling Problem (IHTP), which combines patient admission scheduling, surgical case planning and nurse-to-room assignment into a single large-scale optimization problem. The competition attracted 32 teams from both industry and academia, who developed a diverse range of solution approaches, primarily based on mathematical programming, metaheuristics and hybrid methods. All approaches applied some form of decomposition and incorporated tailored strategies to cope with the problem's scale and combinatorial complexity. Notably, different methods performed best on different instances, and none was able to prove optimality for any instance. This work analyzes the competition design, benchmark instances and algorithmic trends, highlighting key methodological insights for integrated timetabling problems.

Download PDF

The One-Sided Crossing Minimization (OSCM) problem seeks a vertex ordering of the free layer in a bipartite graph that minimises edge crossings—a core subroutine in the Sugiyama framework for layered graph drawing. We propose an Iterated Local Search (ILS) metaheuristic that combines six lightweight, atomic local search operators within an Adaptive Large Neighborhood Search (ALNS) selection scheme. Unlike conventional steepest-descent moves requiring quadratic time per invocation, each atomic operator evaluates a single candidate move in constant or near-linear time, enabling several thousand improvement steps per second. Experimental evaluation on 30 instances from the PACE 2024 Challenge demonstrates that our solver matches the best known results on 16 of 30 instances within 60 seconds—one-fifth of the competition budget—achieving a mean gap of 0.24 % across all thirty instances.

Download PDF