首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号