Formulations and heuristics for the multi-item uncapacitated lot-sizing problem with inventory bounds |
| |
Authors: | Rafael A. Melo Celso C. Ribeiro |
| |
Affiliation: | 1. Departamento de Ciência da Computa??o, Universidade Federal da Bahia, Salvador, Brazil.melo@dcc.ufba.br;3. Instituto de Computa??o, Universidade Federal Fluminense, Niterói, Brazil. |
| |
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 |
|
|