We investigate flow shop scheduling with stochastic reentry, where each job must traverse the entire shop multiple times and the number of required passes follows a discrete probability distribution. The objective is to design policies that minimize performance measures in expectation. The main contribution is a reduction that maps the problem to stochastic scheduling on identical parallel machines augmented with machine arrivals. This reduction preserves objective values, allowing structural results and performance guarantees from the auxiliary problem to be transferred to the reentrant flow shop. Using the reduction, we prove that simple priority policies are optimal for minimizing the expected makespan and total completion time under geometric and, more generally, monotone hazard‑rate distributions. For minimizing total weighted completion time, we provide an approximation guarantee that depends only on the squared coefficient of variation of the underlying distributions. Our results constitute the first optimality and approximation guarantees for flow shops with stochastic reentry, showing that established scheduling policies naturally extend to this setting via the proposed reduction.
Blogger's Review: By converting a notoriously hard stochastic reentry flow shop into a well‑understood parallel‑machine framework, the paper unlocks existing scheduling theory for a new class of problems, offering both rigorous guarantees and practical insights.