Formulations and heuristics for the multi-item uncapacitated lot-sizing problem with inventory bounds

Abstract

We consider the multi-item uncapacitated lot-sizing problem with inventory bounds, in which a production plan for multiple items has to be determined considering that they share a storage capacity. We present (a) a shortest path formulation and (b) a formulation based on the a priori addition of valid inequalities, which are compared with a facility location formulation available in the literature. Two easy-to-implement mixed integer programming heuristic frameworks are also presented, (a) a rounding scheme and (b) a relax-and-fix approach performed in a time partitioning fashion. Computational experiments are performed to evaluate the different approaches. The numerical results show that the proposed relax-and-fix heuristic outperforms all other approaches. Its solutions are within 4.0% of optimality in less than 10 minutes of running time for all tested instances, with mean gaps in the order of 2.1 and 1.8% for instances with more relaxed and tighter capacities, respectively. The obtained solutions were always better than those obtained by a commercial MIP solver running for one hour using any of the available formulations.

Keywords:

• lot sizing
• production planning
• mixed integer linear programming
• matheuristics
• optimisation

Acknowledgements

The authors would like to thank the anonymous referees for their comments that helped improving this paper.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

Rafael A. Melo was partially supported by the Brazilian Coordination for the Improvement of Higher Education Personnel (CAPES) and by the Brazilian National Council for Scientific and Technological Development (CNPq). Celso C. Ribeiro was partially supported by CNPq research [grant number 303958/2015-4] and by FAPERJ research [grant number E-26/201.198/2014].