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.

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.

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.

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.

In this work, it is investigated whether the predict+optimize framework could be utilized for combinatorial optimization problems with a linear objective that have uncertainty in the constraint parameters, such that it outperforms prediction-error-based training. To this end, a predict+optimize formulation of the 0-1 knapsack problem is used, which is an NP-hard combinatorial optimization problem. This formulation was chosen because it has many real-world applications where the constraint parameters are uncertain. In this instance, the challenge is to predict the weights of knapsack items based on feature data and then use these predictions to solve the knapsack problem. The key is that the item weights are uncertain
and thus must be estimated, but the quality of the solution is evaluated with respect to the true weights. This uncertainty in the weights can lead to infeasible solutions when evaluated on the true weights. Standard predict+optimize techniques do not account for such infeasibility of candidate solutions, which makes them mostly inapplicable for solving problems with uncertainty in the constraint parameters. To
overcome this shortcoming of standard predict+optimize techniques, several correction methods for the evaluation of infeasible solutions during training are compared. Crucially these correction methods can be varied between training and evaluation. By penalizing infeasible solutions linear in the weight of the overweight items during training, predict+optimize is able to outperform standard prediction-error-based techniques. This performance increases to an extent with increased penalization factors, leading to more stable, more optimal results on the validation set.

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.

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.