The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases |
| |
Authors: | Ayse Akbalik Christophe Rapine |
| |
Affiliation: | Université de Lorraine, Laboratoire LGIPM, Ile du Saulcy, Metz F-57045, France |
| |
Abstract: | This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T3), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T3 logT). |
| |
Keywords: | Inventory Uncapacitated lot sizing Batch delivery Stepwise cost Polynomial time algorithm Complexity |
本文献已被 ScienceDirect 等数据库收录! |
|