A Dynamic Lot Size Problem with Multiple Customers : Customer-Specific Shipping and Backlogging Costs

This paper considers a dynamic lot sizing problem faced by a producer who supplies a single product to multiple customers. Characterized by their backorder costs as well as shipping costs, a customer with a high backorder cost has a greater need for the product than a customer with a low backorder cost. We show that the general problem with time-varying customer-dependent backlogging and shipping costs is NP-hard in the strong sense. We then develop an efficient dynamic programming algorithm for an important instance of the problem when there is no speculative motive for backlogging. We also establish forecast horizon results for the case of stationary production and shipping costs, which help the decision maker determine a proper forecast horizon in a rolling-horizon planning process