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.