In realistic production scenarios, Advanced Planning and Scheduling (APS) tools often require manual intervention by production planners, as the system works with incomplete information, resulting in suboptimal schedules. Often, the preferable solution is not found just because of the too-restrictive constraints specifying the optimization problem, representing bottlenecks in the schedule. To provide computer-assisted support for decision-making, we aim to automatically identify bottlenecks in the given schedule while linking them to the particular constraints to be relaxed. In this work, we address the problem of reducing the tardiness of a particular project in an obtained schedule in the resource-constrained project scheduling problem by relaxing constraints related to identified bottlenecks. We develop two methods for this purpose. The first method adapts existing approaches from the job shop literature and utilizes them for so-called untargeted relaxations. The second method identifies potential improvements in relaxed versions of the problem and proposes targeted relaxations. Surprisingly, the untargeted relaxations result in improvements comparable to the targeted relaxations.

Modern industrial production with alternative process plans and the use of complex machine equipment increases requirements for its intralogistics operations in terms of efficiency, resilience, and flexibility. One of the most common solutions for transporting workpieces between the manufacturing stations is a system of conveyor belts where each conveyor rotates in a fixed direction at a constant speed. The movement of the individual workpieces can be controlled only indirectly via a set of gates connecting different carousels. In this paper, we aim to increase the flexibility of conveyor belt systems by carefully scheduling the gates to route the workpieces efficiently along the production line according to their process plans. The key component of our solution is the discretization of both the time and positions on the belts to represent the system by a directed graph with circular components. To find the routing of workpieces that minimizes the total flow time, we have reduced the problem to the integer multi-commodity flow on the time-expanded network with an extension for the vertex precedences. Despite the simplicity of the formulation, the results suggest that off-the-shelf solvers can find optimized routing for instances with tens of workpieces and more than hundreds of belt positions within a few minutes.

In every timed car race, the goal is to drive through the racing track as fast as possible. The total time depends on selection of the racing line. Following a better racing line often decides who wins. In this paper, we solve the optimal racing line problem using a genetic algorithm. We propose a novel racing line encoding based on a homeomorphic transformation called Matryoshka mapping. We evaluate the fitness of racing lines by lap time estimation using a vehicle model suitable for F1/10 autonomous racing competition. By comparing to the former state-of-the-art, we show that our method is able to find racing lines with lower lap times. Specifically, on one of the testing tracks, we achieve 2.5% improvement.

In this paper, we investigate the use of deep learning for solving a classical NP-Hard single machine scheduling problem where the criterion is to minimize the total tardiness. Instead of designing an end-to-end machine learning model, we utilize well known decomposition of the problem and we enhance it with a data-driven approach. We have designed a regressor containing a deep neural network that learns and predicts the criterion of a given set of jobs. The network acts as a polynomial-time estimator of the criterion that is used in a single-pass scheduling algorithm based on Lawler's decomposition theorem. Essentially, the regressor guides the algorithm to select the best position for each job. The experimental results show that our data-driven approach can efficiently generalize information from the training phase to significantly larger instances (up to 350 jobs) where it achieves an optimality gap of about 0.5%, which is four times less than the gap of the state-of-the-art NBR heuristic.

This paper deals with a scheduling problem that emerges in the production of water tubes of different sizes that require reconfiguration of the machines. The reconfiguration of the machines leads to the notion of sequence-dependent setup times between tasks. These setups are often performed by a single person who cannot serve more than one machine at the same moment, i.e., the setups must not overlap. Surprisingly, the problem with non-overlapping setups has received only a little attention so far. To solve this problem, we propose an Integer Linear Programming formulation, Constraint Programming models and a hybrid heuristic that leverages the strength of Integer Linear Programming in the shortest Hamiltonian path problem and the efficiency of Constraint Programming at sequencing problems with makespan minimization. The experimental evaluation shows that among the proposed exact approaches, the Constraint Programming is a superior method being able to solve instances with 3 machines and up to 11 tasks on each machine to optimality within a few seconds. The proposed hybrid heuristic attains high-quality solutions for instances with 50 machines and up to 116 tasks on each machine.

Many real-world scheduling problems are characterized by uncertain parameters. In this paper, we study a classical parallel machine scheduling problem where the processing time of jobs is given by a normal distribution. The objective is to maximize the probability that jobs are completed before a given common due date. This study focuses on the computational aspect of this problem, and it proposes a Branch-and-Price approach for solving it. The advantage of our method is that it scales very well with the increasing number of machines and is easy to implement. Furthermore, we propose an efficient lower bound heuristics. The experimental results show that our method outperforms the existing approaches.