Single-item lot sizing problem is studied under a capacity reservation contract.
Batch deliveries are allowed and the overall replenishment cost is stepwise.
Four NP-hard cases are identified and an efficient FPTAS is proposed.
Pseudo-polynomial time dynamic programming algorithm is given for the general case.
Polynomial time algorithms are proposed under restricted parameters.