Abstract
A prestressed precast beam is a type of beam that is stretched with traction elements. A common task in a factory of prestressed precast beams involves fulfilling, within a time horizon, the demand ordered by clients. A typical order includes beams of different lengths and types, with distinct beams potentially requiring different curing periods. We refer to the problem of planning such production as heterogeneous prestressed precast beams multiperiod production planning (HPPBMPP). We formally define the HPPBMPP, argue its NP-hardness, and introduce four novel integer programming models for its solution and a size reduction heuristic (SRH). We perform computational tests on a set of synthetic instances that are based on data from a real-world scenario and discuss a case study. Our experiments suggest that the models can optimally solve small instances, while the SRH can produce high-quality solutions for most instances.
Similar content being viewed by others
References
Arbib C, Marinelli F (2014) On cutting stock with due dates. Omega 46:11–20
Arenales MN, Cherri AC, Nascimento DNd, Vianna A (2015) A new mathematical model for the cutting stock/leftover problem. Pesquisa Operacional 35(3):509–522
Augusto T, Mounir K, Melo AM (2012) A cost optimization-based design of precast concrete floors using genetic algorithms. Autom Constr 22:348–356
Benjaoran V, Bhokha S (2014) Three-step solutions for cutting stock problem of construction steel bars. KSCE J Civ Eng 18(5):1239–1247
Benjaoran V, Dawood N, Hobbs B (2005) Flowshop scheduling model for bespoke precast concrete production planning. Constr Manag Econ 23(1):93–105
Braga N, Alves C, de Carvalho JV (2016) Exact solution of combined cutting stock and scheduling problems. In: Computational management science. Springer, pp 131–139
Castilho V, Lima M (2012) Comparative costs of the production, transport and assembly stages of prestressed precast slabs using genetic algorithms. Iran Univ Sci Technol 2(3):407–422
Chen JH, Yan S, Tai HW, Chang CY (2017) Optimizing profit and logistics for precast concrete production. Can J Civ Eng 44(999):393–406
Fanjul-Peyro L, Ruiz R (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput Oper Res 38(1):301–309
Fanjul-Peyro L, Perea F, Ruiz R (2017) Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. Eur J Oper Res 260(2):482–493
Garey M, Johnson D, Collection MSM (1979) Computers and intractability: a guide to the theory of NP-completeness. Books in mathematical series, W. H. Freeman. https://books.google.com.br/books?id=fjxGAQAAIAAJ. Accessed 1 Oct 2020
Gramani MCN, França PM (2006) The combined cutting stock and lot-sizing problem in industrial processes. Eur J Oper Res 174(1):509–521
Khalili A, Chua D (2013) Integrated prefabrication configuration and component grouping for resource optimization of precast production. J Constr Eng Manag 140(2):1–12
Ko CH, Wang SF (2011) Precast production scheduling using multi-objective genetic algorithms. Expert Syst Appl 38(7):8293–8302
Li S (1996) Multi-job cutting stock problem with due dates and release dates. J Oper Res Soc 47(4):490–510
Martí JV, Yepes V, González-Vidosa F (2014) Memetic algorithm approach to designing precast-prestressed concrete road bridges with steel fiber reinforcement. J Struct Eng 141(2):04014114
Mokotoff E (2001) Parallel machine scheduling problems: a survey. Asia Pac J Oper Res 18(2):193
Nonås SL, Thorstenson A (2000) A combined cutting-stock and lot-sizing problem. Eur J Oper Res 120(2):327–342
Nonas SL, Thorstenson A (2008) Solving a combined cutting-stock and lot-sizing problem with a column generating procedure. Comput Oper Res 35(10):3371–3392
Ozer EA, Sarac T (2019) Mip models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints. Top 27(1):94–124
Pileggi GC, Morabito R, Arenales MN (2005) Abordagens para otimização integrada dos problemas de geração e seqüenciamento de padrões de corte: caso unidimensional. Pesquisa Operacional 25(3):417–447
Pitombeira-Neto A, Prata B (2019) A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders. Top 28:178–192
Prata BA, Neto Pitombeira AR, Sales CJM (2015) An integer linear programming model for the multiperiod production planning of precast concrete beams. J Constr Eng Manag 141(10):1–4
Reinertsen H, Vossen TW (2010) The one-dimensional cutting stock problem with due dates. Eur J Oper Res 201(3):701–711
Salem O, Shahin A, Khalifa Y (2007) Minimizing cutting wastes of reinforcement steel bars using genetic algorithms and integer programming models. J Constr Eng Manag 133(12):982–992
Shahin AA, Salem OM (2004) Using genetic algorithms in solving the one-dimensional cutting stock problem in the construction industry. Can J Civ Eng 31(2):321–332
Shih KC, Liu SS (2010) An optimization model for precast project planning using group concepts. J Oper Res Soc Jpn 53(3):189–206
Wang D, Liu G, Li K, Wang T, Shrestha A, Martek I, Tao X (2018) Layout optimization model for the production planning of precast concrete building components. Sustainability 10:1807
Wäscher G, Gau T (1996) Heuristics for the integer one-dimensional cutting stock problem: a computational study. Oper Res Spektr 18(3):131–144. https://doi.org/10.1007/BF01539705
Yanasse HH, Lamosa MJP (2007) An integrated cutting stock and sequencing problem. Eur J Oper Res 183(3):1353–1370
Yang Z, Ma Z, Wu S (2016) Optimized flowshop scheduling of multiple production lines for precast production. Autom Constr 72:321–329
Yepes V, Martí JV, García-Segura T (2015) Cost and CO2 emission optimization of precast-prestressed concrete u-beam road bridges by a hybrid glowworm swarm algorithm. Autom Constr 49:123–134
Yuen BJ (1991) Heuristics for sequencing cutting patterns. Eur J Oper Res 55(2):183–190
Acknowledgements
This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior—Brasil (CAPES)—Finance Code 001. This work was partially funded by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) through grants 404232/2016-7 and 303594/2018-7.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix 1: Symmetry breaking constraints
Appendix 1: Symmetry breaking constraints
As we can see from the solutions of all proposed models, there may be many symmetric solutions. For example, if we change the order of production of the patterns in mold 13 of the solution shown in Fig. 2 we would get the same solution with a different representation. We call this a period-based symmetry. The same occurs when we move the patterns produced in a mold to another one, for example, if we move the produced patterns on mold 14 to mold 15 and vice versa of the solution shown in Fig. 2 we would get the same solution with a different representation. We call this a mold-based symmetry. In order to circumvent this problem and, consequently, improve the running times of the models we define two sets of constraints for breaking both period and mold-based symmetries:
Constraints (21) state that patterns will be fabricated in a crescent order of indexes in the molds. Constraints (22) define that molds will be used for patterns production in a crescent order defined by the value of \(\sum _{t = 1}^T \sum _{i \in Q^*(m)} i\;t\;x_i^{m,t}\) for each mold m. Thus, it is easy to see that Proposition 2 is true.
Proposition 2
Addition of symmetry breaking constraints does not modify the optimal solution value of any of the proposed models.
Although considering symmetric solutions increases drastically the problem’s search space and symmetry breaking constraints reduce the number of solutions greatly, we noted, during preliminary computational tests, that the usage of these constraints made the models much bigger and hard to solve. The models required greatly more memory and execution time than before and their insufficient solution performance led us to not consider such constraints in our larger computational tests.
Rights and permissions
About this article
Cite this article
Araújo, K.A.G., Bonates, T.O., Prata, B.A. et al. Heterogeneous prestressed precast beams multiperiod production planning problem: modeling and solution methods. TOP 29, 660–693 (2021). https://doi.org/10.1007/s11750-020-00589-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00589-4
Keywords
- Prestressed concrete
- Precast beams
- Modular construction
- Integer linear programming
- Size reduction heuristics