The (1+√37)/6 lower bound for semi-online scheduling with decreasing processing times: a first proof for all m ≥ 4

This preprint proves, for the first time, the lower bound c = (1+sqrt(37))/6 ≈ 1.18046 on the competitive ratio of deterministic algorithms for semi-online scheduling with decreasing processing times, for all numbers of machines m ≥ 4. Background: Seiden, Sgall and Woeginger (Operations Research Letters, 2000) proved the bound for m = 3. Cheng, Kellerer and Kotov (Operations Research Letters, 2012) gave a 5/4-competitive algorithm for m ≥ 3 and stated in their introduction that the lower bound c holds for all m ≥ 3, attributing it to the 2000 paper, which proved only the case m = 3. No proof for m ≥ 4 has appeared since. Epstein's survey (Journal of Scheduling, 2018) explicitly records the optimal competitive ratio for m ≥ 4 as an open problem. This paper gives two independent proofs. The first is a padding lemma: an adversarial instance on m machines satisfying four natural invariants can be lifted to m+1 machines by prefixing a single job of size 1/c, preserving all invariants with the same constants; applied to the three-machine instance of Seiden et al., induction yields the bound for all m ≥ 3. The feasible interval for the padding constant collapses to the single point G = 1/c, which is equivalent to the defining equation 3c^2 - c - 3 = 0 of the SSW constant. The second proof is an explicit adversarial family, valid uniformly for all m ≥ 4, which after scaling embeds the three-machine instance of Seiden et al. verbatim. The paper is fully self-contained, cites only three references (all verifiable), and uses pencil-and-paper arguments only. The gap between the lower bound c and the 5/4 upper bound remains open on the algorithmic side.