In this paper, a single-item lot sizing problem with backordering is discussed. The time horizon is divided into planning periods, characterized by fixed and variable production costs, and future delivery periods with specified demands, where inventory holding and backordering costs may occur. For each planning period, a common nominal lead time is given. The true lead times can deviate to some extent from the nominal one, and their exact values are unknown at the planning step. We assume that lead times take only integer values and splitting production orders is not allowed. Furthermore, order crossovers are prohibited; thus, an order placed earlier cannot arrive after one placed later. A budgeted uncertainty set of possible lead-time scenarios is defined, where a budget allows us to control the amount of uncertainty of lead times. It is shown how to construct a family of production plans varying from the most optimistic (a best lead-time scenario occurs) to the most pessimistic (a worst lead-time scenario occurs). In order to compute these plans the R* criterion is applied which generalizes the conservative robust min-max criterion, commonly used in robust optimization. The computational complexity of the problem is investigated. Polynomial, pseudopolynomial time algorithms, and mixed integer programming formulations are proposed to solve the general problem and its special cases. The results of computational tests are provided that demonstrate that using the R* criterion can significantly enlarge the set of candidate production plans.