A polynomially-solvable case of the single-item lotsizing problem with continuous start-up costs and uniform production capacity

ESCALANTE, MARIANA SILVINA; MARENCO, JAVIER; VARALDO, MARIA DEL CARMEN

ANNALS OF OPERATIONS RESEARCH

SPRINGER

Lugar: Berlin; Año: 2015 vol. 235 p. 233 - 258

0254-5330

In this work we consider the uniform capacitated single-item single-machine lotsizingproblem with continuous start-up costs. A continuous start-up cost is generated in aperiod whenever there is a nonzero production in the period and the production capacity in theprevious period is not saturated. This concept of start-up does not correspond to the standard(discrete) start-up considered in previous models, thus motivating a polyhedral study of thisproblem. In thisworkwe explore a natural integer programming formulation for this problem.We consider the polytope obtained as convex hull of the feasible points in this problem. Westate some general properties, study whether the model constraints define facets, and presentan exponentially-sized family of valid inequalities for it. We analyze the structure of theextreme points of this convex hull, their adjacency and bounds for the polytope diameter.Finally, we study the particular case when the demands are high enough in order to requireproduction in all the periods.We provide a complete description of the convex hull of feasiblesolutions in this case and show that all the inequalities in this description are separable inpolynomial time, thus proving its polynomial time solvability.