Thanks to the standards being developed by IEEE Time-Sensitive Networking (TSN) Task Group, the classical IEEE 802.1 Ethernet architecture is now enhanced to accommodate real-time and safety-critical requirements emerging in various cyber-physical systems. The deterministic nature of the communication is achieved through the time-triggered traffic, which requires introducing strict scheduling constraints that may be an obstacle in finding a feasible schedule. In this article, we propose a simple hardware enhancement of a switch along with a relaxed scheduling constraint that increases schedulability and throughput of the time-triggered traffic but maintains the deterministic nature and timeliness guarantees in a TSN network. We give a formal proof to justify the claims and an algorithm benchmarking and experimental validation to demonstrate the gains. The results show that the number of flows that can be scheduled in the model with the relaxed constraint is on average by 75.1 % larger than in the traditional model.

Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to a set of target destinations while avoiding collisions. In this work, we study the online version of MAPF where new agents appear over time. Several variants of online MAPF are defined and analyzed theoretically, showing that it is not possible to create an optimal online MAPF solver. Nevertheless, we propose effective online MAPF algorithms that balance solution quality, runtime, and the number of plan changes an agent makes during execution.

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.

Real-life scheduling has to face many difficulties such as dynamics of manufacturing environments with unforeseen events occurring during the execution of a schedule. Namely, in the case of a resource failure, it may be necessary to process a lot of work again, or a feasible schedule recovery may not exist at all. Moreover, the time window within which the ongoing schedule must be updated may be very short, and too timeconsuming computation of the schedule may lead to a failure of the scheduling mechanism and setback in production. Our approach in the area of predictive-reactive scheduling is to allow for substitution of tasks, which cannot be executed, with a set of alternative tasks. This paper makes use of the model of the hierarchical workflows and gives an SMT and a CSP models to recover an ongoing schedule from a resource failure with the objective to minimize the work processed in vain. The experimental analysis identified parameters for which the SMT model clearly outperforms the CSP model and vice versa.