Critical constraints in re-entrant flexible manufacturing systems(FMSs) schedules are those constraints that for some change to their weight (and only the weight), could make the sequence of operation in the schedule infeasible. This paper describes how to find critical constraints by representing the benchmark as a graph and finding its strongly connected components and by exploiting the properties of FMSs.
We also find we can force the schedule to have non-participating constraints at some points in the sequence. Finally, we see two possible relationships between critical constraints and describe how these can be found.
We conclude that the points in the sequence where non-critical edges lay, have infinite temporal flexibility.

Delays and complications in different schedules are a common and widely applicable issue in modern society. These problems, if severe enough can cause a preexisting schedule to become infeasible, thus creating additional problems with varying levels of severity. The focus of this work is to showcase a systematic method for modelling potential disturbances in the execution of a schedule, and to provide algorithms which can help analyze the maximum bounds in which each constraint of the schedule is allowed to change without making the schedule infeasible. Presented is a method that is proven to provide results for the entire schedule with cubic complexity with regard to the number of jobs, as well as a heuristic method with results that approximate the correct ones, but runs considerably faster.

Scheduling is required in almost every industry and when done well it can bring a lot of revenue. Flexibility is often forgotten when creating the initial schedules. Therefore, in case of an unexpected delay, the whole schedule has to suffer. In this paper, we consider a re-entrant flow shop with sequence-dependent setup times and relative due dates for our industrial partner, which specialises in industrial printers. Then, we perform a robustness analysis on real schedules from the industry, which can be extended to any system represented as a flow shop with relative due dates. We find how much time a schedule with relative due dates has before it becomes infeasible. We continue by empirically creating a new robustness measure and comparing it with state-of-the-art techniques. The experiments confirm that this measure can be useful in creating robust initial schedules for re-entrant flow shops with added idle time that has a minimal effect on the total duration of the solution.

Flexible manufacturing systems (FMS) such as large industrial printers can be modeled as re-entrant flow-shops with a set of constraints of processing times, setup times and relative due dates. This is a non-deterministic system in which the actual values for these constraints can be different from the ones originally estimated. Therefore, a way to quickly determine the ranges of constraint values for which a given schedule becomes feasible or infeasible can become highly useful. In this paper, a heuristic algorithm is proposed that can efficiently split the zones of feasibility for a given schedule. With the right settings, an accuracy of 99.9% can be achieved with relatively few queries on 2-dimensional examples.