This study examines a deterministic material requirements planning (MRP) problem where lead times at subsequent ordering moments differ. Adequate replenishment methods that can cope with lead time differences are lacking because of the order crossover phenomenon, that is, replenishment orders are not received in the sequence they are ordered. This study specifies how to handle order crossovers and recalculate planned order releases after an update of gross requirements. The optimal (s, S) policy is based on dynamic programing. The state space is kept to a minimum due to three fundamental insights. The performance of the optimal solution approach is compared with two heuristics based on relaxations and a benchmark approach in which order crossovers are ignored. A numerical analysis reveals that average cost savings up to 25% are possible if the optimal policy is used instead of the benchmark approach. The contribution of this study is threefold: (1) it generalizes theory on MRP ordering, allowing for lead time differences and order crossovers; (2) it develops new fundamental insights and an optimal solution procedure, leading to substantial cost saving; and (3) it provides good‐performing heuristics for a general and realistic replenishment problem that can replace the current replenishment methods within MRP.