فرمولاسیون های تک مرحله ای برای تعیین اندازه دسته تولید دو مرحله ای همگام و برنامه ریزی در تولید نوشابه

This study deals with industrial processes that produce soft drink bottles in different flavours and sizes, carried out in two synchronised production stages: liquid preparation and bottling. Four single-stage formulations are proposed to solve the synchronised two-stage lot sizing and scheduling problem in soft drink production synchronising the first stage's syrup lots in tanks with the second stage's soft drink lots on bottling lines. The first two formulations are variants of the General Lot Sizing and Scheduling Problem (GLSP) with sequence-dependent setup times and costs, while the other two are based on the Asymmetric Travelling Salesman Problem (ATSP) with different subtour elimination constraints. All models are computationally tested and compared to the original two-stage formulation introduced in Ferreira et al. (2009), using data based on a real-world bottling plant. The results show not only the superiority of the single-stage models if compared to the two-stage formulation, but also the much faster solution times of the ATSP-based models.

This paper considers a production lot sizing and scheduling problem encountered in a soft drink bottling plant. Although the models developed are based on that plant, its production processes are sufficiently similar to those in many other bottling plants worldwide and even in other industries for the models proposed in this paper to be widely applicable. Integrated lot sizing and scheduling models have been researched in the context of real-word problems (Clark et al., 2011), for example, packaging company production yogurt (Marinelli et al., 2007), foundries (Araujo et al., 2008), electro-fused grains (Luche et al., 2009), glass container industry (Almada-Lobo et al., 2008), animal feed production (Toso et al., 2009), soft drink production (Ferreira et al., 2010), pharmaceutical company (Stadtler, 2011), sand casting operations (Hans and Van de Velde, 2011). Besides the real problem theoretical models have been extensively studied in the last years (Fleischmann, 1990, Haase, 1994, Drexl and Haase, 1995, Fleischmann and Meyr, 1997, Drexl and Kimms, 1997, Kang et al., 1999, Haase and Kimms, 2000, Meyr, 2000, Meyr, 2002, Gupta and Magnusson, 2005, Fandel and Stammen-Hegene, 2006, Tempelmeier and Buschkühl, 2008, Gicquel et al., 2009 and Kaczmarczyk, 2011). Production lot sizing and scheduling problems can be very difficult depending on the restrictions which have to be met and on the combinatorial structure (classified in general as NP-hard optimization problems, e.g., Meyr, 2002 and Bitran and Yanasse, 1982). In general the integrated lot sizing and scheduling problems are based on lot sizing models (Karimi et al., 2003, Toledo and Armentano, 2006 and Helber and Sahling, 2010) adapted to incorporate the lot sequences. The sequence of lots involves the determination of when each lot is produced. Different characteristics have been considered in the lotsizing and scheduling models. For example, the sequence dependent setup times and costs was studied by Fleischmann and Meyr (1997), Haase and Kimms (2000), Meyr (2000), Beraldi et al. (2008), and Kovàcs et al. (2009). The sequence-dependent setup costs and setup times with setup carryover problem was studied in Gupta and Magnusson (2005) and Menezes et al. (2011); Almeder and Almada-Lobo (2011) study the synchronisation in lot sizing and scheduling problems; Supithak et al. (2010) treat lot sizing and scheduling problems with earliness tardiness and setup penalties; Mateus et al. (2010) apply decomposition methods and an iterative approach for the integration of the problems; Stadtler (2011) studies multilevel lot sizing and scheduling problems with zero lead times. For reviews in lot sizing and scheduling problems the reader is referred to, e.g., Drexl and Kimms (1997), Koçlar (2005), Zhu and Wilhelm (2006), Jans and Degraeve (2008), and Robinson et al. (2009). The formulations for lot sizing and scheduling problems can be mainly classified into two groups: small bucket and big bucket models. In small bucket models, such as the DLSP (Discrete Lot Sizing Problem, Fleischmann, 1990 and Gicquel et al., 2009), the planning horizon is broken down into relatively small intervals in which at most one item can be produced. The sequence in small bucket formulations is inherent of the model. In situation in which there are many lots (periods), the total number of variables and constraints can increase significantly. In big bucket models, on the other hand, multiple items can be produced in each period. The strategy to incorporate the sequence in the model can be, for example, adding ATSP constraints (Menezes et al., 2011). An advantage is that the total number of variables and constraints is smaller. An interesting formulation is the GLSP (General Lot Sizing and Scheduling Problem, Fleischmann and Meyr, 1997), in which the planning horizon is broken down into macro-periods and multiple items can be produced in each macro-period. However, to incorporate the sequence, each macro-period is divided into micro-periods in which at most one item can be produced, so its special structure involving subperiods within time periods may be associated with a small bucket framework (Koçlar, 2005). Clark et al. (2010) take a different approach using an asymmetric travelling salesman problem (ATSP) representation for sequencing lots rather than a GLSP-type model, obtaining good results. Although their formulation was inspired by the animal feed production case, the same idea is applicable to soft drinks production. An important characteristic of soft drink production processes is the synchronisation between its two stages. This is necessary in case the start of production of lots at the second stage (drink bottling) depends on the lots at the first stage (syrup preparation). Toledo et al., 2007 and Toledo et al., 2009 propose a general model that synchronises the schedules of the soft drink plant's two production stages. Nevertheless, the mathematical model is rather complex, which has motivated the authors to develop approximate methods. An alternative model to represent a synchronised two-stage multi-machine problem is formulated in Ferreira et al. (2009). The authors simplify the overall problem by dedicating bottling lines to tanks. This paper introduces alternative formulations for the lot sizing and scheduling problem in which the synchronised two-stage problem is formulated as a single-stage model. The first two formulations (models R1 and R2) are based on the single-stage GLSP model with sequence-dependent setup times and costs, while the other two are ATSP-based formulations (models F1 and F2) with different subtour elimination constraints. In Section 2, we briefly explain the soft drink production process and summarize the synchronised two-stage formulation presented in Ferreira et al. (2009). In Section 3, the single-stage models R1 and R2 are presented, then Section 4 formulates the two models F1 and F2. Section 5 develops the solution procedures to solve the models. In particular, two strategies are detailed for solving model F2, based on the generation of subtour elimination inequalities and patching procedures. The models are computationally tested and analysed in Section 6. Concluding remarks and perspectives for future research are discussed in Section 7.

This paper proposes single-stage strategies (the R1, R2 and F1 models, and the SF2 and PS strategies to solve model F2) to solve a two-stage lot sizing and scheduling problem with sequence-dependent setup times and costs at each stage and with synchronisation between the two stages. The solutions were compared to those in Ferreira et al. (2009). The R1 and R2 models are based on small-bucket formulations, which divide each period into subperiods, thus increasing the total number of variables and constraints. In contrast, F1, SF2 and PS rely on the big-bucket structure of an ATSP-formulation. Computational tests show that F1 and PS provide the best solutions of all the instances analyzed. The results also indicate that in the soft drink production context, strategies based on ATSP have a better performance than the ones based on small-bucket formulations. Future research could explore alternative solution methods to incorporate subtour elimination constraints and patching within the linear programmes at nodes in a single branch-and-cut tree search (Kang et al., 1999), instead of solving the relaxed problem without subtour-elimination constraints to integer optimality and then prohibiting the specific subtours that arise. It would also be interesting to test different methods to solve the sub-MIPS present in the PS strategy.