Flow Shop Scheduling with Stochastic Reentry
This work provides the first optimality and approximation guarantees for flow shops with stochastic reentry, extending established scheduling policies to this setting.
The paper addresses flow shop scheduling with stochastic reentry, where jobs require a random number of passes. It reduces the problem to a parallel machine scheduling problem with machine arrivals, proving optimality of simple priority policies for makespan and total completion time under geometric and monotone hazard rate distributions, and deriving an approximation guarantee for total weighted completion time.
We study flow shop scheduling with stochastic reentry, where jobs must complete multiple passes through the entire shop, and the number of passes that a job requires for completion is drawn from a discrete probability distribution. The goal is to find policies that minimize performance measures in expectation. Our main contribution is a reduction to a classical parallel machine scheduling problem augmented with machine arrivals. This reduction preserves expected objective values and enables transferring structural results and performance guarantees from the auxiliary problems to the reentrant flow shop setting. We demonstrate the usefulness of this reduction by proving the optimality of simple priority policies for minimizing the makespan and the total completion time in expectation under geometric and, more generally, monotone hazard rate distributions. For minimizing the total weighted completion time, we derive an approximation guarantee that depends only on the squared coefficient of variation of the underlying distributions for a simple priority policy. Our results constitute the first optimality and approximation guarantees for flow shops with stochastic reentry and demonstrate that established scheduling policies naturally extend to this setting through the proposed reduction.