This study investigates the performance of three dynamic scheduling approaches—proactive, reactive, and STNU-based—for solving the Multi-Mode Resource-Constrained Project Scheduling Problem with maximal time-lags and no-wait constraints (MMRCPSP/max) in uncertain environments. The performance of the approaches is validated on three key performance measures: solution quality (makespan), offline computation time, and online computation time. Drawing from the current work on stochastic RCPSP/max, this research introduces a more realistic formulation of the problem with multi-mode execution, generalised time lags, and no-wait constraints, under the PyJobShop library and stochastic duration modelling. Experimental results, based on altered PSPLIB instances, show that the three algorithms yield similar feasibility rates. However, they show distinct trade-offs in terms of solution quality, time offline, and time online. The proactive algorithm requires the shortest offline and online computational times, but provides slightly worse makespans. The STNU-based algorithm produces the best average solution quality, with significantly higher offline time. The reactive algorithm offers competitive offline times and solution quality, but has the largest online computational time. The findings provide insight into the trade-offs in solution quality and computational time in dynamic project scheduling and offer insight for using the strategies in the real world. ... Read more

Stochastic scheduling is a crucial and rapidly growing field that attracts significant interest across numerous domains, particularly in the development of digital factories. We evaluate and compare three algorithms for the stochastic Multi-Mode Resource Constrained Project Scheduling Problem with Hard Deadlines. We outline the proactive, reactive and hybrid approaches and compare their performance in terms of feasibility, execution time and makespan. We also experiment with higher variance, different instance sizes and duration distributions to understand the factors that affect performance. Our results highlight the potential of the hybrid approach and demonstrate the fundamental trade-off between robustness and schedule quality. ... Read more

This study investigates scheduling strategies for the stochastic duration flexible job-shop problem with no-wait and general time lags constraints (FJSP/NW-GTL). Progress in Constraint Programming (CP) and temporal-networks has renewed interest in assessing the strengths and limitations of different proactive and reactive scheduling approaches. This paper covers the application of a CP-based fully proactive method, a reactive method and STNU-based method on the FJSP/NW-GTL problem comparing results in terms of predetermined objectives and feasibility. In addition, the paper aims to answer how different distributions for task duration affect feasibility and performance. Our results show that strictly proactive methods are infeasible for no-wait constraints and very tight schedules, which lead to adding an online step in the proactive implementation to pursue the comparison between the approaches. With this change, plotting the average makespan across methods by distribution shows that there is not much fluctuation between distribution types in terms of makespan. Moreover, it appears that the proactive method performs the best, followed closely by the reactive method, while the STNU approach results in a notably higher makespan for the same instances. Notably, in terms of feasibility, the proactive and reactive approach have 100% rate of success compared to the STNU approach which is infeasible on 35% of the instances in the dataset. ... Read more

Modern manufacturing systems must meet hard delivery deadlines while coping with stochastic task durations caused by process noise, equipment variability, and human intervention. Traditional deterministic schedules break down when reality deviates from nominal plans, triggering costly last-minute repairs. This thesis combines offline constraint-programming (CP) optimisation with online temporal-network execution to create schedules that remain feasible under worst-case uncertainty.

First, we build a CP model of the flexible job-shop with per-job deadline tasks and insert an optimal buffer Δ* to obtain a fully pro-active baseline. We then translate the resulting plan into a Simple Temporal Network with Uncertainty (STNU) and verify dynamic controllability, which guarantees that a real-time dispatcher can retime activities for every bounded duration realisation without violating resource or deadline constraints. Extensive Monte-Carlo simulations on the open Kacem 1–4 benchmark suite show that our hybrid approach eliminates 100 % of deadline violations observed in state-of-the-art meta-heuristic schedules, while adding only 3 – 5 % makespan overhead. Scalability experiments confirm that CP solve-times and STNU checks remain sub-second on medium-size instances.

The work demonstrates how temporal-network reasoning can bridge the gap between proactive buffering and dynamic robustness, moving industry a step closer to truly digital, self-correcting factories. ... Read more

This report investigates the effectiveness of Simple Temporal Networks with Uncer- tainty (STNUs) for solving the Stochastic Flexible Job-Shop Scheduling Problem with Sequence-Dependent Setup Times (SFJSP-SDST), comparing it against proactive and reactive Constraint Programming (CP) approaches. Using a benchmark dataset with varying noise levels, the study evaluates solution quality, feasibility, and computational cost. Results show that the reactive method achieves the lowest makespan due to its dy- namic rescheduling capability but incurs high online computation time. The proactive method offers fast execution, while the STNU-based approach provides a dynamically controllable schedule, albeit with conservative makespans. ... Read more

Production planning in the biomanufacturing sector presents significant challenges due to uncertainties in job durations caused by biological variability, environmental conditions, and raw material quality. Traditional scheduling methods typically fail to adapt to these uncertainties, leading to suboptimal outcomes. This research addresses this issue at DSM-Firmenich, focusing on optimizing production planning while maximizing profit, adhering to deadlines, and efficiently utilizing resources. We propose an integrated approach using Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models, alongside Probabilistic Simple Temporal Networks (PSTNs) to handle uncertainty in real-time scheduling. The study introduces an offline optimization procedure for proactive scheduling decisions and a reactive real-time algorithm for adjustments of the planned schedule. This work showcases the potential of applying PSTNs in biomanufacturing and sets the stage for future research aimed at enhancing real-time execution strategies in factory environments. ... Read more

When addressing combinatorial optimization problems, the focus is predominantly on their computational complexity, and it is often forgotten to look at the bigger picture. As a result, it is common to miss critical details which could play a major role in the overall process. One such detail is the presence of uncertainty in the real world. A naive approach might directly predict values for the uncertain parameters, without taking into account that the ultimate goal is to obtain sound decisions. Consequently, in many cases, the resulting solutions are suboptimal. This challenge is precisely the premise behind Decision-Focused Learning (DFL) framework, which is a core of this work. This study pioneers the application of the DFL framework to scheduling problems with uncertain processing times, utilizing contextual features to predict these uncertainties. By employing the promising Score Function Gradient Estimation method, the research tackles the issue of non-differentiable regret loss functions in DFL. Key contributions include the development of techniques to enhance the performance of the Score Function, an in-depth analysis of DFL's applicability to complex scheduling scenarios, and a detailed evaluation of its strengths and weaknesses. This work not only demonstrates the potential of DFL in this new context but also lays the groundwork for future research and improvements in handling uncertainty in combinatorial optimization. ... Read more

The scheduling departments of batch manufacturing plants have to repeatedly solve a complex scheduling problem for the operation of their production lines. This problem can be modeled as a flexible job shop problem (FJSP) in which a set of operations has to be assigned to a set of machines and then the order of operations on each machine has to be determined. The main difference to the general FJSP is that there are changeover times that appear between two sequential operations on the same machine. To solve this extended problem, a hierarchical tabu search method has been chosen. This algorithm makes use of a global selection initialization procedure as well as two neighborhood functions for the assignment and sequencing sub-problems. The objective of this project is to show the effectiveness of tabu search on this version of FJSP compared to a mathematical model serving as a baseline. The initialization procedure performs well compared to the baseline on larger instances while the neighborhood functions worsen the initially found result. This is also the case for a random initialization method which leads to believe that these neighborhood functions are non-optimal and should be replaced which could not have been achieved due to time constraints. ... Read more

The aim of this research paper is to present two genetic algorithms targeted at solving the Flexible Job Shop Problem (FJSP). The first one only tackles a single objective - the schedule makespan, while the second one takes into account multiple objectives for the problem. Each schedule is represented by two integer vectors - one for the machine assignments and one for the operation sequence. Special care is taken to only produce valid schedules when generating the starting population and applying the mutation and crossover operations for further populations. A Mixed Integer Linear Programming (MILP) solution to the FJSP is presented and used as a benchmark for the feasibility of the genetic algorithms. The algorithms are tested on a set of 13 provided problem instances. The results showcase that genetic algorithms outperform the MILP implementation for large problem instances and produce solutions much faster. ... Read more

In this paper, a Simulated Annealing (SA) implementation for a Flexible Job Shop Problem (FJSP), with change-over time, is presented.
This implementation is compared to a Mixed Integer Linear Programming (MILP) optimization, to compare performances.
The SA algorithm starts with creating the first schedule with Global Selection.
The neighbourhood is created with an application of k-insertion.
Annealing is implemented with exponential cooling.
The SA implementation does not consistently outperform the provided MILP implementation. However, the run-time of the simulated annealing is shorter than the MILP.
The algorithm is then also used to discover bottlenecks in the production line presented with the FJSP instances. ... Read more

In this paper a heuristic algorithm is described that can constructively produce solutions to a variant of the Flexible Job Shop Problem (FJSP) that introduces changeover times between each pair of two operations consecutively performed on a machine. The performance of the heuristic algorithm is compared to the performance of an exact solver. Seven heuristics are compared for the FJSP variant with changeovers. The main objective function used is the makespan of the created schedules. The difference that occurs in the quality of the seven heuristics is examined also when instead the total lateness across all jobs is chosen as objective function. It concludes that a heuristic algorithm allows for the creation of good feasible solutions to complex problem instances for the FJSP variation with changeover times in under 30 seconds and that it outperforms an exact algorithm for the FJSP with changeover for use cases where efficiency is important and runtime is limited. ... Read more

This papers examines an ant colony optimization approach for solving a specific variant of the Flexible Job Shop Problem faced by the Dutch chemistry company DSM. Jobs consisting of operations on a specific enzyme need to be scheduled as efficiently as possible on groups of available machines. The most interesting requirement upon the general FJSP are the sequence-dependent cleaning times a machine needs when it processes two different enzyme types consecutively. This can all be intuitively represented using a weighted disjunctive graph, which ACO uses as its input. The algorithm consists of a number of epochs for which multiple ants create a feasible schedule one operation at the time. Scheduling choices are made using pheromones and an heuristic visibility function based on earliest starting times. Pheromone amounts are updated using both a negative local updating rule and a positive global update for the best ant per epoch. Two hyperparameters, the initial pheromone amount τ₀ and the cutting exploration parameter q₀ are experimentally evaluated. Varying τ₀ does not consistently impact the solution quality nor runtime, while the higher the value of q₀, the better both measures. Performance evaluation of ACO is done using a provided MILP solver as baseline and the makespan as objective function for a range of different time limits. For the tested instances, ACO shows to significantly outperform MILP, finding good solutions exceptionally fast. Based on this, ACO is an efficient method to solve the production scheduling problem of DSM. ... Read more