In the integrated uncapacitated lot sizing and bin packing problem, we have to couple lot sizing decisions of replenishment from single product suppliers with bin packing decisions in the delivery of client orders. A client order is composed of quantities of each product, and the quantities of such an order must be delivered all together no later than a given period. The quantities of an order must all be packed in the same bin, and may be delivered in advance if it is 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 planning 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 showed that the proposed methods are efficient ways to obtain small optimality gaps in reduced computational times.
Keywords: Integrated production-delivering problems, lot sizing, bin packing, Heuristics
@article{RO_2021__55_3_1197_0,
author = {Goulart, Nat\~a and Noronha, Thiago F. and Ravetti, Martin G. and de Souza, Mauricio C.},
title = {The integrated uncapacitated lot sizing and bin packing problem},
journal = {RAIRO. Operations Research},
pages = {1197--1212},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {3},
doi = {10.1051/ro/2021049},
mrnumber = {4256082},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021049/}
}
TY - JOUR AU - Goulart, Natã AU - Noronha, Thiago F. AU - Ravetti, Martin G. AU - de Souza, Mauricio C. TI - The integrated uncapacitated lot sizing and bin packing problem JO - RAIRO. Operations Research PY - 2021 SP - 1197 EP - 1212 VL - 55 IS - 3 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021049/ DO - 10.1051/ro/2021049 LA - en ID - RO_2021__55_3_1197_0 ER -
%0 Journal Article %A Goulart, Natã %A Noronha, Thiago F. %A Ravetti, Martin G. %A de Souza, Mauricio C. %T The integrated uncapacitated lot sizing and bin packing problem %J RAIRO. Operations Research %D 2021 %P 1197-1212 %V 55 %N 3 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021049/ %R 10.1051/ro/2021049 %G en %F RO_2021__55_3_1197_0
Goulart, Natã; Noronha, Thiago F.; Ravetti, Martin G.; de Souza, Mauricio C. The integrated uncapacitated lot sizing and bin packing problem. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1197-1212. doi: 10.1051/ro/2021049
[1] , and , The production routing problem: a review of formulations and solution algorithms. Comput. Oper. Res. 55 (2015) 141–152. | MR | Zbl | DOI
[2] , , and , A genetic algorithm-taguchi based approach to inventory routing problem of a single perishable product with transshipment. Comput. Ind. Eng. 104 (2017) 124–133. | DOI
[3] and , The integrated production-inventory-distribution-routing problem. J. Scheduling 12 (2009) 257–280. | MR | Zbl | DOI
[4] and , The multi-item joint replenishment problem with transportation and container effects. Transp. Sci. 28 (1994) 37–54. | Zbl | DOI
[5] and , Bin packing and related problems: General arc-flow formulation with graph compression. Comput. Oper. Res. 69 (2016) 56–67. | MR | Zbl | DOI
[6] , and , Thirty years of inventory routing. Transp. Sci. 48 (2014) 1–19. | DOI
[7] , , and , Simultaneous lotsizing and scheduling problems: a classification and review of models. OR Spectr. 39 (2017) 1–64. | MR | Zbl | DOI
[8] , A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2 (1996) 5–30. | DOI
[9] , and , A heuristic algorithm for a multi-product dynamic lot-sizing and shipping problem. Int. J. Prod. Econ. 98 (2005) 204–214. | DOI
[10] and , Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8 (1998) 3–30. | Zbl | DOI
[11] , and , Classification and literature review of integrated lot-sizing and cutting stock problems. Eur. J. Oper. Res. 271 (2018) 1–19. | MR | Zbl | DOI
[12] , and , MIP models for production lot sizing problems with distribution costs and cargo arrangement. J. Oper. Res. Soc. 67 (2016) 1395–1407. | DOI
[13] and , Multi-product lot-sizing with a transportation capacity reservation contract. Eur. J. Oper. Res. 165 (2005) 127–138. | MR | Zbl | DOI
[14] , Mathematical programming models and formulations for deterministic production planning problems. Computational Combinatorial Optimization, edited by and . In: Vol. 2241 of Lecture Notes in Computer Science. Springer, Berlin Heidelberg (2001) 57–111. | MR | Zbl | DOI
[15] and , Multi-item dynamic lot-sizing with delayed transportation policy. Int. J. Prod. Econ. 131 (2011) 595–603. | DOI
[16] , and , Rich routing problems arising in supply chain management. Eur. J. Oper. Res. 224 (2013) 435–448. | MR | Zbl | DOI
[17] and , Production and transportation integration for a make-to-order manufacturing company with a commit-to-delivery business mode. Manuf. Serv. Oper. Manage. 9 (2007) 123–224. | DOI
[18] , , and , Solving binary cutting stock problems by column generation and branch-and-bound. Comput. Optim. App. 3 (1994) 111–130. | MR | Zbl | DOI
[19] and , Dynamic version of the economic lot size model. Manage. Sci. 5 (1958) 89–96. | MR | Zbl | DOI
Cité par Sources :
