This paper considers a dynamic lot-sizing problem with backlogging under a minimum replenishment policy. For general concave production costs, we propose an O(T^5^) dynamic programming algorithm. If speculative motive is not allowed, in this case, a more efficient O(T⁴) algorithm is developed.