In a cross-docking terminal, an outbound truck can start loading only after every inbound truck that carries its goods has been unloaded. We study the makespan of this problem with several identical doors on each side. Earlier lower bounds reason about one truck at a time. We propose the union-of-predecessors bound (UPB). For each time t, it bounds the outbound work that can have started by t. This bound is a knapsack problem over the union of the trucks’ inbound predecessors. We prove that the bound is valid and give an exact finite form. On the 10,500 benchmark instances it is on average 15.8% above the best earlier bound, and 3.4% above it on preregistered sparse and block-structured instances. The bound is not tight: on 165 proven optima it lies 3.6–6.6% below the optimum. A second bound, which infers time windows, reduces this distance from 5.5% to 1.4% on 98 optima. Written as cuts in a constraint-programming solver, the knapsack argument proves optimality on 137 of 300 new instances within 300 s, against 47 without the cuts, in a preregistered test. Certified schedules come from a forward–backward iterated local search. In a preregistered test it improves on a published evolutionary algorithm by 0.63% at equal numbers of schedule evaluations, and by 1.09% at equal computing time; this second comparison pits our compiled code against the rival’s interpreted code. Code and data: https://doi.org/10.5281/zenodo.23933868