Lot sizing problem with multi-mode replenishment and batch delivery

We study the single-item uncapacitated lot sizing problem with multi-mode replenishment and batch deliveries (ULS-MMB). Specifically, we consider that each replenishment mode has a Full Truck Load (FTL) cost structure and incurs a fixed ordering cost plus a fixed cost per batch. This problem arises in practice when a retailer places the order with different suppliers in each period. We show that this problem is NP-hard even for a single period and under very restricted cost parameters. We then show that ULS-MMB can be transformed into a lot sizing problem with only one replenishment mode per period, that is, ULS-MMB is a special case of lot-sizing with time-varying batch sizes. This simple observation allows us to improve some results already known in the literature of multi-mode replenishment. We propose a very efficient 2-approximation algorithm and establish that the problem admits an FPTAS. Finally, we show that the problem restricted to two modes with divisible batch sizes can be solved in polynomial time. (C) 2017 Elsevier Ltd. All rights reserved.