When does a lower bound solve the distributed assembly flowshop? Optimality certificates, rates, a sharp threshold and 22 new optimality proofs

Abstract In the distributed assembly permutation flowshop, several identical flowshop factories make the jobs of a set of products, and a single machine then assembles each product. We explain when and why the optimal makespan equals a lower bound, and how fast failure becomes unlikely on random instances. The answer depends on the load ratio between assembly work and factory work. If the assembly machine is the bottleneck, the weakest assembly bound is exact with probability tending to one, and the failure probability is exponentially small when the processing-time distribution has an atom at its minimum. If the factories are the bottleneck, every product-decomposition bound fails by a linear amount, and the right bound is a new covering end-chain bound. For integer processing times and at least two factories we prove a sharp threshold: the failure probability is exponentially small if as many products of minimal assembly time as there are factories fit into one minimal processing time, and of exact order t^(-1/2) for t products otherwise, because machine-load ties then force idle assembly time. Without assembly, we prove that the factory bound of the distributed permutation flowshop is exact up to an exponentially small probability. The proofs yield polynomial optimality certificates, and two preregistered simulations confirm the main predictions. On the benchmark of Hatami et al., the certificates explain which instances are closed by bounds, prove optimality for 22 further large instances (two with new best values), and cut search time 5.5-fold when used as a stopping rule.