Formulações e heurísticas para o problema integrado de dimensionamento de lotes e de empacotamento de produtos

Abstract

In the Integrated Uncapacitated Lot Sizing and Bin Packing problem we have to couple lot sizing decisions of replenishment from single products suppliers with bin packing decisions in the delivering of client orders. A client order is composed by quantities of each product, and the quantities of such order must be delivered all together no later than a given period. The quantities of an order must all be packed in a same bin, and may be delivered in advance if its advantageous in terms of costs. We assume a large enough set of homogeneous bins available at each period. The costs involved are setup and inventory holding costs and the cost to use a bin as well. All costs are variable in the planing horizon, and the objective is to minimize the total cost incurred. We propose mixed integer linear programming formulations, and a combinatorial relaxation where it is no longer necessary to keep track of the specific bin where each order is packed. An aggregate delivering capacity is computed instead. We also propose heuristics using different strategies to couple the lot sizing and the bin packing subproblems. Computational experiments on instances with different configurations show that the proposed methods are efficient ways to obtain small optimality gaps in reduced computational times.