pith. sign in

arxiv: 2604.17945 · v1 · submitted 2026-04-20 · 💻 cs.DS · cs.DM· math.OC

Flow Shop Scheduling with Stochastic Reentry

Maximilian von Aspern , Felix Buld , Michael Pinedo This is my paper

Pith reviewed 2026-05-10 03:57 UTC · model grok-4.3

classification 💻 cs.DS cs.DMmath.OC
keywords flow shop schedulingstochastic reentryparallel machine schedulingpriority policiesmakespan minimizationcompletion timeapproximation algorithms
0
0 comments X

The pith

A reduction to parallel machine scheduling with arrivals preserves expected objective values in stochastic reentry flow shops.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that flow shops where jobs randomly reenter for additional passes can be mapped exactly onto a parallel machine scheduling problem in which machines arrive over time. Because the mapping keeps the expected value of any performance measure identical for every possible policy, any optimality or approximation result proved for the parallel-machine side immediately carries over to the original reentry setting. This transfer yields the first known optimality guarantees for simple priority policies that minimize expected makespan or total completion time when the number of passes follows a geometric distribution or any monotone-hazard-rate distribution. The same reduction also supplies an approximation ratio for minimizing expected total weighted completion time that depends only on the squared coefficient of variation of the pass-count distribution.

Core claim

We reduce the stochastic reentry flow shop to a classical parallel machine scheduling problem augmented with machine arrivals. This reduction preserves expected objective values exactly for every policy. Consequently, structural results and performance guarantees from the auxiliary parallel-machine problem transfer directly to the reentrant flow shop. In particular, we prove optimality of priority policies for expected makespan and total completion time under geometric and monotone hazard rate distributions, and we obtain an approximation guarantee for total weighted completion time that depends only on the squared coefficient of variation.

What carries the argument

The exact reduction that maps each reentrant job into a sequence of machine arrivals on parallel machines while preserving expected objective values for every policy.

If this is right

  • Priority policies are optimal for minimizing expected makespan when pass counts are geometrically distributed.
  • Priority policies are optimal for minimizing expected total completion time under geometric or monotone hazard rate pass distributions.
  • A simple priority policy achieves an approximation ratio for expected total weighted completion time that depends solely on the squared coefficient of variation of the pass-count distribution.
  • These optimality and approximation results hold because the reduction preserves expectations for arbitrary policies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the reduction works for any policy, then simulation or dynamic programming algorithms developed for parallel machines with arrivals can be reused directly on reentrant instances.
  • The approach may extend to other stochastic shop models such as job shops or open shops by constructing analogous arrival mappings.
  • Testing the reduction on small deterministic instances where pass counts are fixed would verify that makespan values match exactly between the two models.

Load-bearing premise

The reduction to the parallel-machine problem with arrivals preserves expected objective values exactly for every policy.

What would settle it

Construct a small instance with two jobs, two machines, and a non-geometric pass distribution; compute the expected makespan under a given policy in the reentrant model and in the reduced parallel-machine model; any numerical difference would disprove the preservation claim.

Figures

Figures reproduced from arXiv: 2604.17945 by Felix Buld, Maximilian von Aspern, Michael Pinedo.

Figure 1
Figure 1. Figure 1: Illustration of machine arrivals in the auxiliary problems (shaded); [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of a worst-case and an optimal WSPT ordering. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A counter-example for α = 1/2. 1. There exist ν functions f1, . . . , fν : N0 → [0, 1] that are either all non-increasing or all non-decreasing such that: fi(k1) < fi+1(k2) for all i ∈ [ν − 1], k1, k2 ∈ N. 2. For all j ∈ N, there exists an i ∈ [ν] and and xj ∈ N such that: hj (k) = fi(xj + k) for all k ∈ N. Weber (1979) shows that the preemptive LEPT and SEPT policies minimize the expected makespan and exp… view at source ↗
Figure 4
Figure 4. Figure 4: LVF policy vs. MERL policy under different realizations of [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies flow shop scheduling with stochastic reentry, where the number of passes each job requires is drawn from a discrete probability distribution. The main contribution is a reduction to a classical parallel-machine scheduling problem augmented with machine arrivals; this reduction is asserted to preserve expected objective values for every policy. The authors use the reduction to prove optimality of simple priority policies for expected makespan and total completion time under geometric and monotone hazard rate distributions, and to obtain a squared-coefficient-of-variation approximation guarantee for expected total weighted completion time.

Significance. If the reduction is valid, the work supplies the first optimality and approximation guarantees for stochastic-reentry flow shops. By mapping the problem onto an auxiliary parallel-machine instance whose structural results transfer directly, the paper shows that classical priority policies extend to this setting without modification. The monotone-hazard-rate and CV-based results are concrete and falsifiable, strengthening the contribution.

major comments (1)
  1. [Main contribution (reduction)] The central claim (abstract and main contribution paragraph) is that the reduction to parallel-machine scheduling with arrivals preserves expected objective values exactly for every policy. This preservation is load-bearing for all subsequent optimality and approximation transfers. The explicit construction of the mapping and the proof that expectations are identical for arbitrary policies must be examined for any implicit independence or support assumptions on the reentry distribution that could invalidate the transfer.
minor comments (2)
  1. [Abstract] The abstract states optimality holds for geometric and, more generally, monotone hazard rate distributions; the precise definition of the monotone-hazard-rate class and whether it includes all distributions used in the approximation result should be stated explicitly in the introduction or preliminaries.
  2. [Preliminaries] Notation for policies, reentry random variables, and the auxiliary machine-arrival process should be introduced once in a dedicated preliminaries section and used consistently thereafter.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and for identifying the critical role of the reduction in our results. We provide a detailed response to the major comment below.

read point-by-point responses

  1. Referee: The central claim (abstract and main contribution paragraph) is that the reduction to parallel-machine scheduling with arrivals preserves expected objective values exactly for every policy. This preservation is load-bearing for all subsequent optimality and approximation transfers. The explicit construction of the mapping and the proof that expectations are identical for arbitrary policies must be examined for any implicit independence or support assumptions on the reentry distribution that could invalidate the transfer.

    Authors: We appreciate the referee's emphasis on verifying the foundational reduction. The explicit construction is detailed in Section 3, where each job's reentries are mapped to arrivals of new jobs on parallel machines, with the number of arrivals for each original job drawn from the given distribution. The proof that the expected objective value is identical for any policy in the original and auxiliary problems relies on the law of total expectation, applied recursively over the sequence of passes. This argument holds for any discrete probability distribution on the number of reentries (including those with infinite support) and assumes only the independence of processing times and reentry counts across jobs, which is standard in the model. There are no hidden assumptions on the support or independence that would invalidate the transfer. To address the referee's request for examination, we will expand the proof in the revision with an additional lemma explicitly stating the generality. revision: partial

Circularity Check

0 steps flagged

No significant circularity; reduction is an independent mapping

full rationale

The paper's load-bearing step is a reduction from stochastic reentrant flow shop to a parallel-machine problem with arrivals that exactly preserves expected objective values for every policy. This is presented as a direct equivalence (not a fit or redefinition), allowing transfer of known optimality and approximation results from the classical setting. No equations reduce the preservation claim or subsequent guarantees (optimality of priority policies under geometric/monotone hazard rates, or the C^2-based approximation) back to the original inputs by construction. No self-citations are load-bearing for uniqueness or ansatz, and no renaming of known empirical patterns occurs. The derivation chain is self-contained against external benchmarks in classical scheduling theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the modeling assumption that reentry counts are drawn from discrete distributions (geometric or monotone hazard rate) and on the unverified correctness of the reduction mapping.

axioms (1)
  • domain assumption Number of passes for each job is drawn independently from a discrete probability distribution
    Core modeling choice that enables the reduction and the subsequent optimality statements under geometric and monotone hazard rate cases.

pith-pipeline@v0.9.0 · 5475 in / 1155 out tokens · 48662 ms · 2026-05-10T03:57:45.371620+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Scheduling:

    Pinedo, Michael , year=. Scheduling:

    work page

  2. [2]

    European Journal of Operational Research , volume=

    Flow shops with reentry: Reversibility properties and makespan optimal schedules , author=. European Journal of Operational Research , volume=. 2020 , publisher=

    work page 2020

  3. [3]

    Journal of Scheduling , volume=

    Flow shops with reentry: The total weighted completion time objective , author=. Journal of Scheduling , volume=. 2025 , publisher=

    work page 2025

  4. [4]

    Generalizing the

    J\". Generalizing the. 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) , pages =. 2018 , volume =. doi:10.4230/LIPIcs.STACS.2018.43 , annote =

    work page doi:10.4230/lipics.stacs.2018.43 2018

  5. [5]

    Worst case bound of an

    Kawaguchi, Tsuyoshi and Kyan, Seiki , journal=. Worst case bound of an. 1986 , publisher=

    work page 1986

  6. [6]

    Weber , title =

    Richard R. Weber , title =

    work page

  7. [7]

    Journal of Applied Probability , volume=

    Scheduling tasks with exponential service times on parallel processors , author=. Journal of Applied Probability , volume=. 1979 , publisher=

    work page 1979

  8. [8]

    1983 , issn =

    Scheduling of re-entrant flow shops , journal =. 1983 , issn =. doi:10.1016/0272-6963(83)90004-9 , author =

    work page doi:10.1016/0272-6963(83)90004-9 1983

  9. [9]

    Scheduling of stochastic tasks on two parallel processors , year =

    Pinedo, Michael and Weiss, Gideon , journal =. Scheduling of stochastic tasks on two parallel processors , year =. doi:10.1002/nav.3800260314 , publisher =

    work page doi:10.1002/nav.3800260314

  10. [10]

    and Downey, P

    Bruno, J. and Downey, P. and Frederickson, G. N. , title =. 1981 , issue_date =. doi:10.1145/322234.322242 , journal =

    work page doi:10.1145/322234.322242 1981

  11. [11]

    Gittins, J. C. , journal =. Multiserver scheduling of jobs with increasing completion rates , year =. doi:10.2307/3213196 , publisher =

    work page doi:10.2307/3213196

  12. [12]

    Scheduling two classes of exponential jobs on parallel processors: structural results and worst-case analysis , year =

    Chang, Cheng-Shang and Nelson, Randolph and Pinedo, Michael , journal =. Scheduling two classes of exponential jobs on parallel processors: structural results and worst-case analysis , year =. doi:10.2307/1427684 , publisher =

    work page doi:10.2307/1427684

  13. [13]

    1981 , issn =

    Mathematics of Operations Research , title =. 1981 , issn =. doi:10.1287/moor.6.2.305 , publisher =

    work page doi:10.1287/moor.6.2.305 1981

  14. [14]

    , journal =

    Weber, Richard R. , journal =. Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime , year =. doi:10.2307/3213926 , publisher =

    work page doi:10.2307/3213926

  15. [15]

    Approximation in stochastic scheduling: the power of

    M\". Approximation in stochastic scheduling: the power of. 1999 , issue_date =. doi:10.1145/331524.331530 , journal =

    work page doi:10.1145/331524.331530 1999

  16. [16]

    On the optimality of static priority policies in stochastic scheduling on parallel machines , year =

    Kämpke, Thomas , journal =. On the optimality of static priority policies in stochastic scheduling on parallel machines , year =. doi:10.2307/3214267 , publisher =

    work page doi:10.2307/3214267

  17. [17]

    2008 , issn =

    Minimizing makespan on an m-machine re-entrant flowshop , journal =. 2008 , issn =. doi:10.1016/j.cor.2006.09.028 , author =

    work page doi:10.1016/j.cor.2006.09.028 2008

  18. [18]

    2011 , issn =

    Minimizing total completion time for re-entrant flow shop scheduling problems , journal =. 2011 , issn =. doi:10.1016/j.tcs.2011.08.030 , author =

    work page doi:10.1016/j.tcs.2011.08.030 2011

  19. [19]

    2012 , doi=

    Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications , author=. 2012 , doi=

    work page 2012

  20. [20]

    , title =

    Middendorf, Martin and Timkovsky, Vadim G. , title =. Journal of Scheduling , volume =. doi:10.1002/jos.95 , year =

    work page doi:10.1002/jos.95

  21. [21]

    Computing , volume=

    Complexity Results for Single-Machine Problems with Positive Finish-Start Time-Lags , author=. Computing , volume=. 1999 , publisher=

    work page 1999

  22. [22]

    2003 , issn =

    Identical parallel machines vs.\ unit-time shops and preemptions vs.\ chains in scheduling complexity , journal =. 2003 , issn =. doi:10.1016/S0377-2217(02)00767-1 , author =

    work page doi:10.1016/s0377-2217(02)00767-1 2003

  23. [23]

    Operations Research Letters , volume =

    An alternative proof of the. Operations Research Letters , volume =. 2011 , issn =. doi:10.1016/j.orl.2011.06.007 , author =

    work page doi:10.1016/j.orl.2011.06.007 2011

  24. [24]

    Statistics & Probability Letters , volume=

    A generalized geometric distribution and some of its properties , author=. Statistics & Probability Letters , volume=. 1983 , publisher=

    work page 1983

  25. [25]

    Hall, W. J. and Wellner, Jon A. , title =. Proceedings of the International Symposium on Statistics and Related Topics (Ottawa, Ont., Canada) , pages =. 1981 , publisher =

    work page 1981

  26. [26]

    and Dauzère-Pérès, Stéphane and Mason, Scott J

    Mönch, Lars and Fowler, John W. and Dauzère-Pérès, Stéphane and Mason, Scott J. and Rose, Oliver , journal =. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations , year =. doi:10.1007/s10951-010-0222-9 , publisher =

    work page doi:10.1007/s10951-010-0222-9

  27. [27]

    Journal of the Operational Research Society , volume =

    S-W Choi and Y-D Kim , title =. Journal of the Operational Research Society , volume =. 2007 , publisher =

    work page 2007

  28. [28]

    and Mason, Scott J

    Pfund, Michele E. and Mason, Scott J. and Fowler, John W. Semiconductor Manufacturing Scheduling and Dispatching. Handbook of P roduction S cheduling. 2006

    work page 2006

  29. [29]

    and Fowler, John W

    Mason, Scott J. and Fowler, John W. and Matthew Carlyle, W. , journal =. A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops , year =. doi:10.1002/jos.102 , publisher =

    work page doi:10.1002/jos.102