RESSALVA Atendendo solicitação da autora, o texto completo desta tese será disponibilizado somente a partir de 10/06/2022 Câmpus de São José do Rio Preto Caroline de Arruda Signorini One-dimensional cutting stock problems with multiple periods applied to the precast slab industry São José do Rio Preto 2022 Caroline de Arruda Signorini One-dimensional cutting stock problems with multiple periods applied to the precast slab industry Tese apresentada como parte dos requisi- tos para obtenção do título de Doutora em Matemática, junto ao Programa de Pós-Graduação em Matemática, do Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de São José do Rio Preto. Financiadora: FAPESP 2018/10284-0 Financiadora: CAPES Orientador: Prof. Dr. Silvio Alexandre de Araujo Co-orientadora: Profa. Dra. Gislaine Mara Melega São José do Rio Preto 2022 S578o Signorini, Caroline de Arruda One-dimensional cutting stock problems with multiple periods applied to the precast slab industry / Caroline de Arruda Signorini. -- São José do Rio Preto, 2022 134 p. : il., tabs. Tese (doutorado) - Universidade Estadual Paulista (Unesp), Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto Orientador: Silvio Alexandre de Araujo Coorientadora: Gislaine Mara Melega 1. Matemática. 2. Pesquisa Operacional. 3. Otimização Matemática. 4. Programação inteira-mista. 5. Problemas de corte de estoque multiperíodo. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Instituto de Biociências Letras e Ciências Exatas, São José do Rio Preto. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. Caroline de Arruda Signorini One-dimensional cutting stock problems with multiple periods applied to the precast slab industry Tese apresentada como parte dos requi- sitos para obtenção do título de Doutora em Matemática, junto ao Programa de Pós- Graduação em Matemática, do Instituto de Biociências, Letras e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de São José do Rio Preto. Financiadora: FAPESP 2018/10284-0 Financiadora: CAPES Comissão Examinadora Prof. Dr. Silvio Alexandre de Araujo Orientador Profa. Dra. Sônia Cristina Poltroniere Silva UNESP - Câmpus de Bauru Profa. Dra. Adriana Cristina Cherri Nicola UNESP - Câmpus de Bauru Prof. Dr. Reinaldo Morabito Neto UFSCar - Câmpus de São Carlos Prof. Dr. Bruno de Athayde Prata UFC - Fortaleza São José do Rio Preto 10 de dezembro de 2021 Ao Nenê AGRADECIMENTOS A conquista de elaborar esta tese de doutorado não seria possível sem a mo- tivação de meus pais e a priorização que eles deram em minha educação. A convivência entre gerações diferentes nem sempre é fácil, mas a aprendizagem é inevitável. Agradeço à minha mãe, Patricia, e meu pai, Antonio Carlos, por terem apoiado minhas decisões e possibilitado minha progressão acadêmica. Os anos de doutorado não foram fáceis: cobrança, ansiedade e comparação fizeram parte deste percurso e me confundiram, acrescentando mais barreiras a serem contornadas e até superadas. Uma grande parte da força para continuar obtive por cuidar do meu cachorrinho e irmão. Agradeço ao Nenê por ter me dado a oportunidade de amadurecer sendo sua irmã/mãe e ter me conduzido a valorizar as coisas simples que me trazem alegria. Ao meu parceiro-namorado Bruno, agradeço por ter me apoiado desde o primeiro dia de aula na graduação, tanto nas disciplinas quanto nas grandes decisões de vida e carreira. Seu apoio foi essencial para eu conseguir trilhar o caminho da graduação ao fim do doutorado. Agradeço a minhas amigas Ju, Bea, Flavinha, Isa, Mari, Amanda e Bia, e meus amigos Gui, Dan e Cebola pelo suporte emocional, pelos momentos e risos com- partilhados. A amizade de vocês faz minha vida ser mais leve. Fizeram parte dos últimos anos de meu doutorado meus amigos à distância, especialmente Igor, Markin e Tynho, que me acolheram no ambiente online, onde compartilhamos histórias, aprendizado e risadas por meio de conversas e partidas em nossas noites de jogatina. Sou muito grata aos meus amigos de Ibilce e de vida, em especial André Oak, Lucas Aracato, Jess, Kumon, Will, Ronísio, Luiz, Samuel, Eduardo, Jennifer, Helô, Junior, Ana, Otávio, Jarnin e Plínio. Pela companhia do dia-a-dia, estudos juntos, almoços no RU, cafés na salinha e rolês tão memoráveis. Muito importantes nessa jornada foram também os servidores do Ibilce. Agradeço em especial ao Getúlio e ao Thiago pelo suporte técnico e brincadeiras descontraí- das, à Michele, Eliani, Netinha e Eldes do Restaurante Universitário (RU) que tratam a todos com tanto carinho, à Eliane e ao André da STAEPE que me auxiliaram com paciência a encaminhar documentos para a FAPESP, e ao Mauro, Silvia e Alíria da Seção de Pós-Graduação pelo excelente atendimento. Prestativos, atenciosos e acolhedores, auxiliaram sempre que preciso e tornam o ambiente da universidade uma casa. Agradeço aos meus professores, que cumpriram papel essencial em minha for- mação. Em especial, Gorete, por ter me acolhido em meus três anos de PET, onde aprendi que a universidade é mais do que apenas cursar disciplinas. Hermínia, por ter acompanhado meus primeiros passos como pesquisadora. Hermes, que me inspira como pessoa e professora atenciosa. Valeriano e Socorro, que exigiram sempre meu melhor. Tim, pelas correções que me ensinaram matemática além do inglês. Ao Silvio e Gi, sou grata pelo amparo durante esses mais de quatro anos com tanta paciência e confiança em meu trabalho. Como meu orientador e co-orientadora no papel, atuaram como pais me guiando nessa aventura que é o doutorado. Agradeço aos membros da banca, Sônia, Bruno, Reinaldo, Adriana, Fernando, Valeriano e Kelly, por terem se disponibilizado a participarem de minha defesa. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoa- mento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001. Agradeço a FAPESP pela concessão da bolsa de pesquisa, sob o processo 2018/10284-0, Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP). ‘All we have to decide is what to do with the time that is given us’, John Ronald Reuel Tolkien RESUMO Este estudo analisa o planejamento da produção de lajes pré-moldadas decorrente de fábricas brasileiras especializadas. A primeira parte desta pesquisa considera o processo de produção de lajes alveolares, para o qual são propostos dois mode- los matemáticos baseados no problema de corte de estoque unidimensional mul- tiperíodo com aspectos inovadores relativos a múltiplos modos de manufatura que podem ser usados para produzir as lajes. Visando a minimização de custos de pro- dução e de estoque, os dois modelos são resolvidos por métodos heurísticos. Com base em dados fornecidos por uma fábrica, resultados computacionais indicam a relevância de tais modelos como ferramentas auxiliares na tomada de decisão. A segunda parte deste estudo trata o processo de produção de lajes treliçadas, o qual compreende dois estágios: corte de treliças de aço e concretagem nos moldes. O modelo matemático proposto consiste em um problema de corte de estoque uni- dimensional multiperíodo de dois estágios de modo a minimizar custos de setup, produção e estoque sob restrições de capacidade e balanceamento de estoque. Diferentes estratégias de solução baseadas no método de geração de colunas são aplicadas a este modelo para gerar os padrões de corte que serão utilizados na produção, e um pacote computacional é utilizado para identificar soluções inteiras. As instâncias são baseadas em informações obtidas da fábrica e os resultados computacionais ilustram a aplicação do modelo proposto em um contexto realista. Palavras-chave: Problemas de corte de estoque multiperíodo, Produção de laje alveolar, Produção de laje treliçada, Relax-and-fix, Geração de colunas. ABSTRACT This study looks at the production planning of precast slabs derived from specialized Brazilian factories. The first part of this research considers the production process of hollow-core slabs. For this, two mathematical models are proposed for the aris- ing problem, which consists of a multi-period one-dimensional cutting stock problem with innovative aspects regarding the multiple manufacturing modes that can be used to produce the slabs. These models are solved using heuristic methods, both models aiming at the minimization of production and inventory costs. Based on real data provided by a company, the computational results indicate the relevance of such models as auxiliary tools in decision-making. The second part of this study addresses the production of lattice slabs, which comprises a process in two stages: cutting steel trusses and concreting them in the molds. The proposed mathematical model is expressed by a two-stage multi-period one-dimensional cutting stock prob- lem and aims at the minimization of setup, production and inventory costs, subject to capacity and demand balance constraints. To solve this model, different strategies based on the column generation procedure are implemented to generate the cutting patterns used in the production and then different rounding strategies are applied to identify integer solutions. The instances are based on information obtained from the factory and computational results are used to evaluate the application of the proposed model in a realistic context. Keywords: Multi-period cutting stock problems, Hollow-core slab production, Lattice slab production, Relax-and-fix, Column generation. List of Figures 3.1 The production process of prestressed concrete structures. . . . . . . . 26 3.2 Steps of the column generation procedure with a rounding strategy ap- plied to the GGMPCSP. . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 Bar chart representing the MILP and RF solution status distribution. . 45 3.4 Bar chart representing the MILP and CG solution status distribution. . 47 4.1 Representation of a lattice joist. . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Representation of a mold used in the lattice joist production. . . . . . . 51 4.3 The production process of lattice joist. . . . . . . . . . . . . . . . . . . 52 4.4 Bar chart representing the solution status distribution of the ICG, ICG with two steps and SCG strategies. . . . . . . . . . . . . . . . . . . . . 63 4.5 Distribution of costs: overall averages between all results of ICG, ICG with two steps and SCG strategies. . . . . . . . . . . . . . . . . . . . . 66 A.1 Cutting patterns for the GGMPCSP numerical example. . . . . . . . . 86 D.1 Cutting patterns for the steel truss cutting problem. . . . . . . . . . . . 122 D.2 Cutting patterns for the concrete filling problem. . . . . . . . . . . . . 123 List of Tables 3.1 RF decomposition strategies per number of periods. . . . . . . . . . . . 39 3.2 Data set configuration. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Comparison between MILP and RF heuristic results: processing time and GAPs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.4 Comparison between KMPCSP MILP and GGMPCSP CG procedure results: linear relaxations, objective values and GAP. . . . . . . . . . . 48 4.1 Data set distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2 General analysis of the results: processing time and GAP. . . . . . . . . 64 4.3 General analysis of the results: lower and upper bounds. . . . . . . . . 64 4.4 Additional analysis of the results: distribution of costs. . . . . . . . . . 66 4.5 Additional analysis of the results: inventory level, use of steel truss, mold availability and usage. . . . . . . . . . . . . . . . . . . . . . . . . 67 A.1 Order form for the hollow-core slabs production planning numerical ex- ample. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 A.2 Numerical example for KMPCSP - variable conditions in each RF iteration. 84 A.3 Numerical example for KMPCSP - MILP and RF results: solution sta- tus, processing time, objective value and distribution of costs. . . . . . 85 A.4 Numerical example for KMPCSP - MILP and RF results: lower bounds and GAPs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 A.5 Numerical example for KMPCSP - MILP and RF results: mold usage. 85 A.6 Initial cutting patterns for the GGMPCSP numerical example. . . . . . 87 A.7 Cutting patterns for the GGMPCSP numerical example - end of the first iteration. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 A.8 Numerical example for GGMPCSP - CG results: solution status, pro- cessing time, objective value and distribution of costs. . . . . . . . . . . 103 A.9 Numerical example for GGMPCSP - CG results: lower bounds and GAPs.103 A.10 Numerical example for GGMPCSP - CG results: mold usage. . . . . . 103 B.1 Comparison between MILP and the RF heuristic results: objective values.105 B.2 Comparison between MILP and the RF heuristic results: distribution of costs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 B.3 GGMPCSP CG procedure results: total number of columns, processing time and distribution of costs. . . . . . . . . . . . . . . . . . . . . . . . 107 D.1 Primal problem: setup variable coefficients. . . . . . . . . . . . . . . . . 116 D.2 Primal problem: mold section production variable coefficients. . . . . . 117 D.3 Primal problem: steel truss production variable coefficients. . . . . . . . 118 D.4 Primal problem: inventory variable coefficients. . . . . . . . . . . . . . 119 D.5 Dual problem: variable coefficients. . . . . . . . . . . . . . . . . . . . . 120 D.6 Order form. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 D.7 Numerical example results: solution status, processing time, lower and upper-bound and GAP. . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 D.8 Numerical example results: distribution of costs. . . . . . . . . . . . . . 133 D.9 Numerical example results: mold and steel truss inventory level and usage.134 D.10 Numerical example results: mold availability and usage. . . . . . . . . . 134 List of Abbreviations KMPCSP Kantorovich-based multi-period cutting stock problem GGMPCSP Gilmore and Gomory-based multi-period cutting stock problem DWMPCSP Dantzig-Wolfe-based multi-period cutting stock problem MILP Mixed-integer linear programming RF Relax-and-fix CG Column generation RMP Restricted master problem O Optimal solution F Feasible solution NF Non-feasibility U Unknown solution status OF Objective function ICG Integrated column generation SCG Separated column generation 14 Contents 1 Introduction 17 2 Literature review 21 2.1 Multi-Period Cutting Stock Problems . . . . . . . . . . . . . . . . . . . 21 2.2 Cutting Stock Problems in the concrete industry . . . . . . . . . . . . . 22 2.3 Two-stage cutting processes . . . . . . . . . . . . . . . . . . . . . . . . 23 3 The multi-period cutting stock problem applied to hollow-core slab production 24 3.1 Production process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Mathematical models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.1 A Kantorovich-based multi-period cutting stock problem (KM- PCSP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.2 A Gilmore and Gomory-based multi-period cutting stock prob- lem (GGMPCSP) . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 A theoretical analysis of the formulations . . . . . . . . . . . . . . . . . 31 3.4 Solution methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4.1 Relax-and-fix procedure . . . . . . . . . . . . . . . . . . . . . . 37 3.4.2 Column generation procedure . . . . . . . . . . . . . . . . . . . 40 3.5 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.1 Data set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.2 KMPCSP: MILP and heuristic results . . . . . . . . . . . . . . 44 3.5.3 GGMPCSP: CG procedure results and a comparison with the KMPCSP results using the MILP . . . . . . . . . . . . . . . . . 46 3.6 Conclusion and future research . . . . . . . . . . . . . . . . . . . . . . 48 4 The multi-period cutting stock problem applied to lattice slab pro- duction 50 4.1 Production process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.2 Mathematical model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3 Solution methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.3.1 Integrated column generation procedure (ICG) . . . . . . . . . . 55 4.3.2 Integrated column generation with two steps (ICG with two steps) 57 4.3.3 Separated column generation procedure (SCG) . . . . . . . . . . 59 4.4 Computational results . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.1 Data set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.4.2 General analysis of the results . . . . . . . . . . . . . . . . . . . 62 4.4.3 Additional analysis of the results . . . . . . . . . . . . . . . . . 65 4.5 Conclusions and future research for this model . . . . . . . . . . . . . . 68 5 Conclusion and future research 69 References 71 Appendix A Numerical example for the hollow-core slab production planning 79 Appendix B Hollow-core slab production planning detailed results 104 Appendix C Variations of ICG with two steps and SCG strategies 108 C.1 Variant of the Integrated column generation with two steps (V-ICG) . . 108 C.2 Variant of the Separated column generation procedure (V-SCG) . . . . 109 C.3 Explanation of the non-applicability . . . . . . . . . . . . . . . . . . . . 109 Appendix D General and numerical example for the lattice slab produc- tion planning 111 D.1 General example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 D.2 Numerical example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 1 Introduction The advances in infrastructure conquered by humanity in the last two centuries are clear. In civil construction, industrial processes ease and speed up building while offering durability, sustainability and quality control. In the second industrial age, precast concrete combined with steel emerged as new technology to compose struc- tural elements of buildings, including joists, beams, columns, modular boxes, stairways and walls, among other components. The use of precast elements enhances techno- logical and social development since their application combines more sophisticated equipment, better working conditions and more efficient quality management. Conse- quently, an increasing use of precast concrete has been seen (Debs, 2000; Steinle et al., 2019). However, the construction industry in Brazil still has many challenges, since there is widescale waste of materials, low productivity, low quality, slow processes and an informal and low-skilled workforce. To face these challenges, this sector has been increasingly integrating innovative technologies and management tools into its produc- tion processes, aiming to increase productivity, quality, safety and client satisfaction (Debs, 2000; Barbosa and Viln̄ıtis, 2017). In the light of growing competitiveness, environmental responsibility and lack of resources, the industrial sector has had to develop decision-making tools intending to both design and produce materials economically and efficiently. As a scientific tool, mathematical modeling applied to industrial processes provides objective and measurable support for decision-making. In these circumstances, the cutting stock problem (CSP) can be a helpful approach to solve arising problems. The cutting stock problem arises in many industries as a fundamental subproblem of production planning and establishes the best way to cut standard length objects (material units such as aluminum or paper coils, metal or wood sheets, and steel bars, among others) into smaller items with specified dimensions, minimizing material waste while meeting the demand (Dyckhoff, 1990, Wang and Wäscher, 2002, Wäscher et al., 2007, Morabito et al., 2009, Gomes et al., 2016). There are many studies of the CSP from different perspectives. For example, the residual length of a cutting pattern can be stocked for future use, i.e. handling the usable leftovers (Cui et al., 2017). A multi-objective approach can also be considered, aiming, for example, to minimize the 17 18 Introduction frequency of different cutting patterns to be used and, simultaneously, to minimize the number of cut objects (Aliano Filho et al., 2018, İhsan Erozan and Çalışkan, 2020, Oliveira et al., 2021). Another perspective in production planning is the approach of multiple periods, where the decision can be made looking not only at the demand of a single period but considering the demand of future periods of a planning horizon (Aktin and Özdemir, 2009). The main objective of this thesis is to study mixed-integer linear programs applied to the production planning of hollow-core slabs and lattice slabs. According to the classification in Melega et al. (2018), the models presented here consist of a Multi- Period Cutting Stock Problems (MPCSP), also denoted by ( - /L2/ - /M), since they do not presuppose more than one production level and allow integration of periods by carrying inventory items from one period to another. Here, the one-dimensional case of the cutting process is considered. In Chapter 2, there is a literature review on the cutting stock problems, includ- ing papers with similar applications to those addressed in this research, along with a discussion of the mathematical formulations and papers that address mixed-integer mathematical models with cutting processes of two stages. The next two chapters of this work are based on the production planning of precast slabs derived from two differ- ent companies. Chapter 3 addresses the hollow-core slab production planning problem of a plant, and Chapter 4 is based on the production process of a factory specialized in lattice slabs. More specifically, Chapter 3 is based on the published paper by Signorini et al. (2021) that focuses on the production planning of hollow-core slabs at a specific plant, which is briefly described next. First, an order form is considered. It contains the client order specifications: prestressed wire configurations, the length of the slabs and the due date. Based on this information, the production manager plans weekly when, which and how many hollow-core slabs (items) should be made in each available mold. Following these instructions, the assembly sector conducts the preparation of the mold, pre- stressing, casting the concrete, curing, post-tensioning, wire release and item removal. A more detailed description of this process is presented in Section 3.1. Considering the previously-described production process and focusing on the weekly planning decision on which hollow-core slabs will be produced in each available mold, the main contri- bution of Chapter 3 is the proposal of two mathematical models based on the cutting stock problem literature, aiming at the minimization of inventory and production costs (mainly related to the use of steel wires) subject to demand balance and capacity con- straints, as presented in Section 3.2. There is one aspect of these models which, to the best of our knowledge, has not appeared in other studies in the literature about cutting Introduction 19 stock problems. In this study, the handling of wire configurations is more comprehen- sive, as it contemplates the combination of items with different wire configurations in the same production line (same mold) under an unusual restriction: to reduce the total costs, an item might be produced with a wire configuration whose load is equal to or higher than that required (multiple manufacturing modes). Moreover, a theoretical analysis of the compact and extended formulations is discussed in Section 3.3. The solution methods are described in Section 3.4. The first proposed model is solved by an exact method and heuristic methods, based on decomposition approaches, are used to solve both models. Considering a data set based on real information, Section 3.5 analyzes the computational results, which provides an interesting introspection for the industry. Section 3.6 summarizes the outcomes of Chapter 3 and some directions to amend this study. Looking upon the lattice slab production process of a Brazilian factory, the main contribution of Chapter 4 is the proposal of a mathematical model for the produc- tion planning of lattice joist based on the one-dimensional multi-period cutting stock problem with two stages. In the joists’ production process, a limited number of molds is used, which are divided into sections of equal length. The production planning of lattice slabs is also weekly and the production process starts with the preparation of the molds. Next, each mold is filled with concrete. The steel trusses previously cut into the length of the items are used as reinforcement, being inserted into the still liquid concrete base. Subsequently, the items are removed from the molds, resetting the production cycle. A more detailed description of the production process of lattice joists is presented in Section 4.1. The main concerns of the factory are the waste of steel trusses during the cutting process, the minimization of the setup and inventory costs and the increase in productivity. Considering a cutting process with two stages, Section 4.2 introduces a mathematical model based on the cutting pattern formulation that matches the factory objectives while meeting demand and satisfying capacity con- straints. The first stage is the cutting of steel trusses of standard length into pieces of specific lengths, and the second stage consists of dividing the molds with separators that will outline the allocation of each item. Different cutting patterns in the multiple sections of each mold are allowed, which entails a setup cost related to this use. To the best of our knowledge, this approach has not been handled by any other studies in the literature on cutting stock problems, since we optimize the multi-period cutting stock decisions in a two-stage scenario simultaneously. Another contribution of this research is the proposition of different column generation-based methods with inno- vative aspects arising from the two-stage problem, where two types of subproblems have to be solved. Exploring decomposition by stages, different rounding strategies are 20 Introduction also proposed. Details are specified in Section 4.3. To evaluate the application of the proposed model in a realistic context, Section 4.4 presents the computational results based on information collected from the factory. Conclusions and opportunities for further research are discussed in Section 4.5. Finally, Chapter 5 revises the contributions of this thesis and points out some perspectives for extending the research presented here. Other contributions of this thesis are presented in the appendices. Appendix A illustrate by a numerical example the application of the solution methods proposed in Chapter 3. Tables with more detailed computational results of Chapter 3 can be found in Appendix B. Variations of the solution strategies proposed in Chapter 4 are in Appendix C. Lastly, Appendix D contains a general example to illustrate the model proposed in Chapter 4 and the application of one of the proposed solution strategies to a numerical example. 5 Conclusion and future research The main objective of this research was to develop mathematical-computational tools that assist the decision making for the production planning of hollow-core slabs and lattice slabs motivated by partnership with precast concrete producers in Brazil. Considering the production planning of hollow-core slabs at a specific plant, two models based on compact and extended formulations of the one-dimensional multi- period cutting stock problems were proposed in the first part of this thesis. Both models aim at the minimization of inventory penalty and production costs (mainly related to the use of steel wires while satisfying demand balance and capacity con- straints). Also, both models handle with wire configurations more comprehensively, since they foresee the combination of items with different wire configurations in the same production line provided that the wire configuration of a produced item is equal or higher than that required. To the best of our knowledge, this feature has not ap- peared in other studies. To solve the compact model KMPCSP, the MILP approach and the Relax-and-fix heuristic were applied, while a strategy based on the column generation procedure was used to solve the extended model GGMPCSP. The compu- tational results used fictional instances generated based on real data from the plant. A better efficiency of the compact model compared to the extended model was observed. This unusual result arises from some particularities of this problem that produces a demand matrix and cutting pattern matrix of higher dimensions, which increases the complexity in generating interesting columns, forcing the hardware. It was also noted that bin-packing based models (compact formulation) are generally considered by stud- ies where the average demand for items is low and a weak lower bound to the integer problem is produced, along with symmetrical structures, decreasing the efficiency of branch-and-bound methods. On the other hand, models based on the cutting stock problems (extended formulation) perform better in cases where the average demand for items is high, granting a tight linear relaxation and stronger lower bounds through the elimination of some fractional solutions and removal of symmetries. In this study, the low demand rate in the instances tested caused a drawback in the performance of the column generation procedure used to solve the extended formulation, provoking its low efficiency. Furthermore, a theoretical analysis of the compact and extended 69 70 Conclusion and future research formulations was argued. Another widely used precast slab in Brazil is the lattice slab, the focus of the second part of this research. Considering the production planning of lattice joists (which com- pose the slab) and keeping in view the central interests of the factory (the minimization of setup and production costs and waste of steel trusses, while managing the inventory level and increasing productivity), a model based on the compact formulation for the multi-period cutting stock problem with two stages was proposed. The first stage comprehends the cutting of steel trusses of standard length into smaller pieces, while the second stage involve the division of the molds with separators, outlining the place- ment of each item. Since this model optimizes cutting stock decisions in a multi-period and two-stage scenario concomitantly, to the best of our knowledge, it provides an in- novative addition to the related literature. An additional contribution of this research is the proposal of three different solution strategies based on the column generation procedure that explore the two-stage feature, where two groups of subproblems are used to deal with the two cutting processes involved. The computational results used fictional instances based on existing orders from the factory in focus, and provide a very positive evaluation that supports the application of such research in the real-world problem. Opportunities for further research include the incorporation of other production pro- cesses, e.g., the acquisition of raw material, packing, and distribution of final products. Readjustments in the proposed models and the use of alternative mathematical models, such as the arc-flow formulation, might be necessary. Other possibilities to extend this research are improving the solution methods addressed here, while comparing their re- sults to others existent in the literature, implementing different techniques to generate interesting columns, and exploring combinations of different heuristic approaches. References K. Akartunalı and A. J. Miller. A heuristic approach for big bucket multi-level produc- tion planning problems. European Journal of Operational Research, 193(2):396–411, 2009. doi: 10.1016/j.ejor.2007.11.033. T. Aktin and R. G. Özdemir. An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing. European Journal of Operational Research, 196(2):737–743, 2009. doi: 10.1016/j.ejor.2008.04.005. A. Aliano Filho, A. C. Moretti, and M. V. Pato. A comparative study of exact methods for the bi-objective integer one-dimensional cutting stock problem. Journal of the Operational Research Society, 69:91–107, 2018. doi: 10.1057/s41274-017-0214-7. P. R. d. L. Andrade, S. A. de Araujo, A. C. Cherri, and F. K. Lemos. The in- tegrated lot sizing and cutting stock problem in an automotive spring factory. Applied Mathematical Modelling, 91:1023 – 1036, 2021. ISSN 0307-904X. doi: 10.1016/j.apm.2020.10.033. K. A. G. Araújo, T. O. Bonates, and B. A. Prata. The integrated cutting and packing heterogeneous precast beams multiperiod production planning problem. RAIRO- Oper. Res., 55(4):2491–2524, 2021a. doi: 10.1051/ro/2021107. K. A. G. Araújo, T. O. Bonates, B. A. Prata, and A. R. Pitombeira-Neto. Heteroge- neous prestressed precast beams multiperiod production planning problem: modeling and solution methods. TOP, 29:660–693, 2021b. doi: 10.1007/s11750-020-00589-4. T. A. Baldo, M. O. Santos, B. Almada-Lobo, and R. Morabito. An optimization ap- proach for the lot sizing and scheduling problem in the brewery industry. Computers & Industrial Engineering, 72:58–71, 2014. doi: 10.1016/j.cie.2014.02.008. A. A. R. Barbosa and M. Viln̄ıtis. Innovation and construction management in brazil: Challenges of companies in times of quality and productivity. In IOP Conference Se- ries: Materials Science and Engineering, volume 251, page 012040. IOP Publishing, 2017. doi: 10.1088/1757-899X/251/1/012040. 71 72 REFERENCES B. S. C. Campello, C. T. L. S. Ghidini, A. O. C. Ayres, and W. A. Oliveira. A multiobjective integrated model for lot sizing and cutting stock problems. Journal of the Operational Research Society, 71(9):1466–1478, 2020. doi: 10.1080/01605682. 2019.1619892. CBS Precast Limited/3D Warehouse. 150mm standard hol- lowcore plank, 2015. URL . M. M. Christofoletti, S. A. de Araujo, and A. C. Cherri. Integrated lot-sizing and cutting stock problem applied to the mattress industry. Journal of the Operational Research Society, 0(0):1–15, 2020. doi: 10.1080/01605682.2020.1718013. M. Correia, J. F. Oliveira, and J. Ferreira. Reel and sheet cutting at a paper mill. Computers Operations Research, 31(8):1223–1243, 2004. ISSN 0305-0548. doi: 10. 1016/S0305-0548(03)00076-5. Y. Cui, X. Song, Y. Chen, and Y.-P. Cui. New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers. Journal of the Operational Research Society, 68(3):269–280, 2017. doi: 10.1057/s41274-016-0098-y. S. A. de Araujo and A. Clark. A priori reformulations for joint rolling-horizon schedul- ing of materials processing and lot-sizing problem. Computers Industrial Engineer- ing, 65(4):577 – 585, 2013. ISSN 0360-8352. doi: 10.1016/j.cie.2013.04.003. M. K. Debs. Concreto Pré-Moldado: Fundamentos e Aplicações. Oficina de Textos. EESC-USP, 2000. Z. Degraeve and R. Jans. A new dantzig-wolfe reformulation and branch-and-price al- gorithm for the capacitated lot-sizing problem with setup times. Operations research, 55(5):909–920, 2007. doi: 10.1287/opre.1070.0404. G. Desaulniers, J. Desrosiers, and M. M. Solomon. Column Generation. Springer, Boston, MA, 2005. doi: 10.1007/b135457. H. Dyckhoff. A new linear programming approach to the cutting stock problem. Op- erations research, 29(6):1092–1104, 1981. doi: 10.1287/opre.29.6.1092. H. Dyckhoff. A typology of cutting and packing problems. European Journal of Op- erational Research, 44(2):145–159, 1990. ISSN 0377-2217. doi: https://doi.org/10. 1016/0377-2217(90)90350-K. Cutting and Packing. REFERENCES 73 Elecosoft PLC. Prestressed Concrete - Milbury Systems, 2010. URL . D. Ferreira, R. Morabito, and S. Rangel. Solution approaches for the soft drink inte- grated production lot sizing and scheduling problem. European Journal of Opera- tional Research, 196(2):697–706, 2009. doi: 10.1016/j.ejor.2008.03.035. D. Ferreira, R. Morabito, and S. Rangel. Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants. Computers & Operations Research, 37(4):684–691, 2010. doi: 10.1016/j.cor.2009.06.007. D. J. Fiorotto, R. Jans, and S. A. de Araujo. An analysis of formulations for the capac- itated lot sizing problem with setup crossover. Computers & Industrial Engineering, 106:338–350, 2017. doi: 10.1016/j.cie.2016.12.037. D. J. Fiorotto, J. d. C. Huaccha Neyra, and S. A. de Araujo. Impact analysis of setup carryover and crossover on lot sizing problems. International Journal of Production Research, 58(20):6350–6369, 2020. doi: 10.1080/00207543.2019.1680892. H. Foerster and G. Wascher. Pattern reduction in one-dimensional cutting stock prob- lems. International Journal of Production Research, 38(7):1657–1676, 2000. doi: 10.1080/002075400188780. P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting-stock problem. Operations research, 9(6):849–859, 1961. doi: 10.1287/opre.9.6.849. P. C. Gilmore and R. E. Gomory. A linear programming approach to the cutting stock problem – Part II. Operations research, 11(6):863–888, 1963. doi: 10.1287/opre.11. 6.863. P. C. Gilmore and R. E. Gomory. Multistage cutting stock problems of two and more dimensions. Operations research, 13(1):94–120, 1965. doi: 10.1287/opre.13.1.94. A. M. Gomes, J. F. Gonçalves, R. Alvarez-Valdés, and J. V. de Carvalho. Preface to the special issue on cutting and packing. International Transactions in Operational Research, 23(1-2):3–4, 2016. doi: https://doi.org/10.1111/itor.12208. M. C. N. Gramani and P. França. The combined cutting stock and lot sizing problem in industrial process. European Journal of Operational Research, 174(1):509–521, 2006. doi: 10.1016/j.ejor.2004.12.019. 74 REFERENCES O. Husein and E. Softić. Prestressed concrete beams production pro- cess. pages 351–356, 2013. URL https://pdfs.semanticscholar.org/deff/ e7fc3d65ad8ebc608686606741ac96edaf33.pdf. International Prestressed Hollowcore Association. Hollowcore slab production, 2020. URL . M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer Science & Business Media, 2009. doi: 10.1007/978-3-540-68279-0. L. V. Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6(4):366–422, 1960. doi: 10.1287/mnsc.6.4.366. B.-I. Kim, Y. Ki, D. Son, B. Bae, and J.-S. Park. An algorithm for a cutting problem in window frame production. International Journal of Production Research, 54(14): 4327–4339, 2016. doi: 10.1080/00207543.2016.1148279. E. S. Kokten and Ç. Sel. A cutting stock problem in the wood products industry: a two-stage solution approach. International Transactions in Operational Research, 00:1–29, 2020. doi: 10.1111/itor.12802. A. A. Leao, M. M. Furlan, and F. M. Toledo. Decomposition methods for the lot-sizing and cutting-stock problems in paper industries. Applied Mathematical Modelling, 48: 250–268, 2017. doi: 10.1016/j.apm.2017.04.010. F. K. Lemos, A. C. Cherri, and S. A. de Araujo. The cutting stock problem with multiple manufacturing modes applied to a construction industry. International Journal of Production Research, 59(4):1088–1106, 2021. doi: 10.1080/00207543. 2020.1720923. G. M. Melega, S. A. de Araujo, and R. Jans. Classification and literature review of integrated lot-sizing and cutting stock problems. European Journal of Operational Research, 271(1):1–19, 2018. doi: 10.1016/j.ejor.2018.01.002. G. M. Melega, S. A. de Araujo, and R. Morabito. Mathematical model and solution approaches for integrated lot-sizing, scheduling and cutting stock problems. Annals of Operations Research, 295:695–736, 2020. doi: 10.1007/s10479-020-03764-9. R. A. Melo and C. C. Ribeiro. Formulations and heuristics for the multi-item uncapaci- tated lot-sizing problem with inventory bounds. International Journal of Production Research, 55(2):576–592, 2017. doi: 10.1080/00207543.2016.1215567. https://pdfs.semanticscholar.org/deff/e7fc3d65ad8ebc608686606741ac96edaf33.pdf https://pdfs.semanticscholar.org/deff/e7fc3d65ad8ebc608686606741ac96edaf33.pdf REFERENCES 75 C. Mercé and G. Fontan. Mip-based heuristics for capacitated lotsizing problems. International Journal of Production Economics, 85(1):97–111, 2003. doi: 10.1016/ S0925-5273(03)00090-2. R. Morabito and M. Arenales. Optimizing the cutting of stock plates in a furniture company. International Journal of Production Research, 38(12):2725–2742, 2000. doi: 10.1080/002075400411457. R. Morabito, M. N. Arenales, and H. H. Yanasse. Special issue on cutting, packing and related problems. International Transactions in Operational Research, 16(6): 659–659, 2009. doi: 10.1111/j.1475-3995.2009.00739.x. I. Muter and Z. Sezer. Algorithms for the one-dimensional two-stage cutting stock problem. European Journal of Operational Research, 271(1):20–32, 2018. doi: 10. 1016/j.ejor.2018.04.04. D. N. Nascimento, A. N. Cherri, and S. A. de Araujo. Integrated lot sizing and one- dimensional cutting stock problem with usable leftovers. Annals of Operations Re- search (accepted), 2020. doi: 10.1007/s10479-020-03772-9. W. A. Oliveira, D. J. Fiorotto, X. Song, and D. F. Jones. An extended goal pro- gramming model for the multiobjective integrated lot-sizing and cutting stock prob- lem. European Journal of Operational Research, 2021. ISSN 0377-2217. doi: https://doi.org/10.1016/j.ejor.2021.03.049. K. C. Poldi and M. N. Arenales. O problema de corte de estoque unidimen- sional multiperíodo. Pesquisa Operacional, 30(1):153–174, 2010. doi: 10.1590/ S0101-74382010000100008. B. A. Prata, A. R. Pitombeira-Neto, and C. J. M. Sales. An integer linear programming model for the multiperiod production planning of precast concrete beams. Journal of Construction Engineering and Management, 141(10):04015029, 2015. doi: 10.1061/ (ASCE)CO.1943-7862.0000991. H. Reinertsen and T. W. Vossen. The one-dimensional cutting stock problem with due dates. European Journal of Operational Research, 201(3):701–711, 2010. ISSN 0377-2217. doi: 10.1016/j.ejor.2009.03.042. A. Respício and M. E. Captivo. Integrating the cutting stock problem in capacity planning. Department of Informatics and Centre of Operational Research, University of Lisbon, Portugal (2002), 2002. 76 REFERENCES J. L. Santos, J. Santos, M. J. Ferreira, N. Alves, and M. Guevara. Application of the two-stage one-dimensional cutting stock problem in the steel industry. In 2018 IEEE 27th International Symposium on Industrial Electronics (ISIE), pages 683–690, 2018. doi: 10.1109/ISIE.2018.8433734. M. W. P. Savelsbergh. Branch and price: Integer programming with column generation. Springer US, Boston, MA, 2008. doi: 10.1007/978-0-387-74759-0_58. M. Savsar and C. Cogun. Analysis and modelling of a production line in a corrugated box factory. International Journal of Production Research, 32(7):1571–1589, 1994. doi: 10.1080/00207549408957023. C. A. Signorini, S. A. de Araujo, and G. M. Melega. One-dimensional multi-period cutting stock problems in the concrete industry. International Journal of Production Research, 0(0):1–18, 2021. doi: 10.1080/00207543.2021.1890261. W. A. O. Soler, M. O. Santos, and K. Akartunalı. Mip approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products. Journal of the Operational Research Society, 0(0):1–16, 2019. doi: 10.1080/01605682.2019.1640588. H. Stadtler. Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows. Operations Research, 51(3): 487–502, 2003. doi: 10.1287/opre.51.3.487.14949. A. Steinle, H. Bachmann, and M. Tillmann. Precast concrete structures. Wiley Online Library, 2019. doi: 10.1002/9783433609064. The Prestressed Group. Prestressed and precast concrete, 2020. URL . E. A. Toso, R. Morabito, and A. R. Clark. Lot sizing and sequencing optimisation at an animal-feed plant. Computers & Industrial Engineering, 57(3):813–821, 2009. doi: 10.1016/j.cie.2009.02.011. P. Trkman and M. Gradisar. One-dimensional cutting stock optimization in consecutive time periods. European Journal of Operational Research, 179(2):291–301, 2007. doi: 10.1016/j.ejor.2006.03.027. J. M. V. Valério de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659, 1999. doi: 10.1023/A:1018952112615. REFERENCES 77 J. M. V. Valério de Carvalho. LP models for bin packing and cutting stock problems. European Journal of Operational Research, 41(2):253–273, 2002. doi: 10.1016/S0377-2217(02)00124-8. J. M. V. Valério de Carvalho. Using extra dual cuts to accelerate column generation. INFORMS Journal on Computing, 17(2):175–182, 2005. doi: 10.1287/ijoc.1030.0060. P. H. Vance. Branch-and-price algorithms for the one-dimensional cutting stock prob- lem. Computational Optimization and Applications, 9(3):211–228, 1998. ISSN 0926- 6003. doi: 10.1023/A:1018346107246. M. Vanzela, G. M. Melega, S. Rangel, and S. A. de Araujo. The integrated lot sizing and cutting stock problem with saw cycle constraints applied to furniture production. Computers Operations Research, 79:148 – 160, 2017. ISSN 0305-0548. doi: 10.1016/ j.cor.2016.10.015. A. H. D. Vassoler, S. C. Poltroniere, and S. A. de Araujo. Modelagem matemática para o problema de produção de vigotas na indústria de lajes treliçadas. C. Q. D. Revista Eletrônica Paulista de Matemática, 7:68–77, 2016. doi: 10.21167/ cqdvol7ermac201623169664ahdvscpsar6877. B. Verlinden, D. Cattrysse, and D. V. Oudheusden. Integrated sheet-metal production planning for laser cutting and bending. International Journal of Production Research, 45(2):369–383, 2007. doi: 10.1080/00207540600658062. P. Y. Wang and G. Wäscher. Editorial on cutting and packing. European Journal of Operational Research, 141(2):239–240, 2002. W. Wang, Z. Shi, L. Shi, and Q. Zhao. Integrated optimisation on flow-shop production with cutting stock. International Journal of Production Research, 57(19):5996–6012, 2019. doi: 10.1080/00207543.2018.1556823. G. Wäscher, H. Haußner, and H. Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3):1109–1130, 2007. doi: 10.1016/j.ejor.2005.12.047. L. A. Wolsey. Valid inequalities, covering problems and discrete dynamic programs. In P. Hammer, E. Johnson, B. Korte, and G. Nemhauser, editors, Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, pages 527–538. Elsevier, 1977. doi: 10.1016/S0167-5060(08)70758-1. 78 REFERENCES H. H. Yanasse and R. Morabito. Linear models for 1-group two-dimensional guillotine cutting problems. International Journal of Production Research, 44(17):3471–3491, 2006. doi: 10.1080/00207540500478603. İhsan Erozan and E. Çalışkan. A multi-objective genetic algorithm for a special type of 2d orthogonal packing problems. Applied Mathematical Modelling, 77:66–81, 2020. ISSN 0307-904X. doi: 10.1016/j.apm.2019.07.010. Introduction Literature review Multi-Period Cutting Stock Problems Cutting Stock Problems in the concrete industry Two-stage cutting processes The multi-period cutting stock problem applied to hollow-core slab production Production process Mathematical models A Kantorovich-based multi-period cutting stock problem (KMPCSP) A Gilmore and Gomory-based multi-period cutting stock problem (GGMPCSP) A theoretical analysis of the formulations Solution methods Relax-and-fix procedure Column generation procedure Computational results Data set KMPCSP: MILP and heuristic results GGMPCSP: CG procedure results and a comparison with the KMPCSP results using the MILP Conclusion and future research The multi-period cutting stock problem applied to lattice slab production Production process Mathematical model Solution methods Integrated column generation procedure (ICG) Integrated column generation with two steps (ICG with two steps) Separated column generation procedure (SCG) Computational results Data set General analysis of the results Additional analysis of the results Conclusions and future research for this model Conclusion and future research References Appendix Numerical example for the hollow-core slab production planning Appendix Hollow-core slab production planning detailed results Appendix Variations of ICG with two steps and SCG strategies Variant of the Integrated column generation with two steps (V-ICG) Variant of the Separated column generation procedure (V-SCG) Explanation of the non-applicability Appendix General and numerical example for the lattice slab production planning General example Numerical example