رویکرد بهینه سازی برای مشکل تعیین اندازه دسته تولید و برنامه ریزی در صنعت آبجوسازی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|22886||2014||14 صفحه PDF||سفارش دهید||محاسبه نشده|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Industrial Engineering, Volume 72, June 2014, Pages 58–71
This study considers a production lot sizing and scheduling problem in the brewery industry. The underlying manufacturing process can be basically divided into two main production stages: preparing the liquids including fermentation and maturation inside the fermentation tanks; and bottling the liquids on the filling lines, making products of different liquids and sizes. This problem differs from other problems in beverage industries due to the relatively long lead times required for the fermentation and maturation processes and because the “ready” liquid can remain in the tanks for some time before being bottled. The main planning challenge is to synchronize the two stages (considering the possibility of a “ready” liquid staying in the tank until bottling), as the production bottlenecks may alternate between these stages during the planning horizon. This study presents a novel mixed integer programming model that represents the problem appropriately and integrates both stages. In order to solve real-world problem instances, MIP-based heuristics are developed, which explore the model structure. The results show that the model is able to comprise the problem requirements and the heuristics produce relatively good-quality solutions.
Recently the Kirin Institute of Food and Lifestyle (Kirin, 2012) published a survey on the global beer production per country. The production went up 3.7% from 2010 to 2011, marking its 27th consecutive year of growth. China has been the largest beer-producing country in the world for the tenth year in a row, while United States is the second-largest producer. China produced 10.7% more beer in 2011 than in 2010. Brazil achieved a 3.4% growth in 2011, after reporting a 18.2% annual increase in the previous year, and now it is the third largest beer producing country (overtaking Russia in 2010). It has had the highest percentual growth in the past 11 years. This increase has made industries seek for more efficient and effective production planning and control methods. The production lot sizing and scheduling in a brewery needs to consider various pieces of information in the planning time horizon simultaneously, such as several machines with different capacities and specificities, multiple items to be produced with different demands, more than one production stage involving sequence-dependent setup times and costs, multitanks for preparation and fermentation of different liquids, production synchronization of the stages, storing “ready” liquid waiting for the bottling, among others. Even with all the data variables, it is still hard to devise good production plans. In practice, many companies determine the production planning manually, which can take hours until a satisfactory plan is achieved. Moreover, during the planning horizon, it is often necessary to reschedule the production due to the occurrence of unforeseen events and changes of information, for example, extra client requests, machine shutdowns and unexpected shortages of raw material. Lot sizing problems can be difficult to solve in practice, depending on the features of the problem. In general, they are NP-hard problems (Bitran and Yanasse, 1982 and Meyr, 2002). Models and algorithms for the single-level lot sizing problem with incapacitated and capacitated constraints are discussed by Karimi et al., 2003 and Jans and Degraeve, 2007. When there is fragmentation of production by stages, a final item has precedent items that should be programmed for production and/or procurement. The different stages have to be coordinated, which introduces an additional dimension of complexity to the lot sizing, referred to as a multi-stage problem (Billington, McClain, & Thomas, 1986). For example, in brewery industries, bottling at a filling line can only start after the liquid gets ready in a tank. Fig. 1 illustrates three feasible situations regarding the interdependencies between tanks and lines. In each case, the production of the tanks (above) and the filling lines (below) are depicted as Gantt charts. In Fig. 1A, an ideal scenario is illustrated where the liquid gets ready after the fermentation/maturation process in the tank at the same instant as the bottling starts on the line. In situation Fig. 1B, the line waits for the fermentation/maturation of the liquid in the tank. Finally, in Fig. 1C the “ready” liquid in the tank waits until the line becomes available for bottling. Full-size image (38 K) Fig. 1. Synchronization between tanks and filling lines with the possibility to stock “ready” liquid in the tank. Figure options Lot sizing problems can consider the sequence-dependent production, i.e., sequence-dependent setup times and costs between the production of different items (Araujo and Clark, 2013, Clark and Clark, 2000, Fleischmann, 1994, Haase and Kimms, 2000, Meyr, 2000, Meyr and Mann, 2013 and Shim et al., 2011). The underlying lot sizing and scheduling problem can be found in different industrial settings, for example in packaging (Marinelli, Nenni, & Sforza, 2007), foundries (Araujo et al., 2007 and Santos-Meza et al., 2002), textile (Silva & Magalhaes, 2006), in the production of glass containers (Almada-Lobo, Oliveira, & Carravilla, 2008), electro fused grains (Luche, Morabito, & Pureza, 2009), animal nutrition (Clark et al., 2010 and Toso et al., 2009), soft drinks (Ferreira et al., 2012, Ferreira et al., 2009, Toledo et al., 2012 and Toledo et al., 2009) and pulp and paper (Santos & Almada-Lobo, 2012). Reviews on lot sizing and scheduling with sequence independent/dependent setups can be found in, e.g., Drexl and Kimms, 1997 and Jans and Degraeve, 2007. The hardness of solving these problems is linked to the features to be met and the model sizes, thus most of the literature focuses on heuristics and metaheuristics methods to solve the integrated lot sizing and scheduling problem. A few mixed integer production planning models of beverages have been proposed, for instance Toledo et al., 2009, Toledo et al., 2012, Ferreira et al., 2009 and Ferreira et al., 2012, for the soft drink industry. Similarly to soft-drinks, beer production can also be considered as a two stage production process: preparation and bottling (or kegging) of the liquids. However, there are some differences between these problems, mainly regarding the first stage. Generally, the preparation times of the liquids in soft drinks and other beverage industries only take a few minutes and, in some cases, a few hours. On the other hand, in brewing, fermentation and maturation times last several days (from 3 up to 41 days, depending on the type of beer), which affect the beer production plans in an important way. Another difference is that in brewing, after the fermentation and maturation processes, the “ready” liquid can be stored in the preparation tanks for several days while waiting for being bottled in the filling lines, differently to the soft-drink production processes. Few attempts regarding beer production planning are presented in the literature and some issues remain to be addressed, such as effective optimization approaches dealing with the integrated lot sizing and scheduling in breweries to support operational decisions in the short term, which is the objective of this study. In Guimarães, Klabjan, and Almada-Lobo (2012), the authors consider the assignment and sizing of production lots in a multi-plant environment (each plant has a set of filling lines that bottle and pack beverages – beer and soft drinks), including the transfers of the final products between plants. It relates to the tactical level of the beer industry production planning and, therefore, it does not consider the necessary level of detail to perform a short-term plan (issues such as the fermentation and maturation tanks are disregarded there) as in the present study. As mentioned before, the aim of this study is to address a production lot sizing and scheduling problem appearing at a standard brewery industry and to present optimization approaches based on mixed integer programming (MIP) formulation of the problem and MIP-based heuristics to deal with it, namely the relax-and-fix and fix-and-optimize (Pochet & Wolsey, 2006). A novel MIP model is presented to integrate the two main production stages, preparing the liquids including fermentation and maturation inside the fermentation tanks and bottling the liquids on the filling lines, making products of different liquids and sizes. Moreover, the planning horizon is discretized into periods (days). In addition, each period of the first part of the horizon is subdivided into a number of slots of variable widths, allowing for the scheduling and sequences of production lots. The second part (end) of the planning horizon is focused on lot sizing decision, disregarding few scheduling details. This two-dimensional time matrix allows for different granularities along the planning horizon, more accurate scheduling decisions are considered in the first part, contrarily to the rough lot sizing decisions in the second. This model can be used on a rolling-horizon approach. To the best of our knowledge, this is the first work to address the brewery production planning problem in this line of research. The MIP model solution provides feasible production plans to the lot sizing and scheduling problem. However, for large problem instances as the ones found in practice, the model becomes difficult to solve, motivating the development of MIP-based heuristics. MIP-heuristics consider several novel partition schemes, which are developed based on the specific features of the beer manufacturing process. For instance, the fermentation time significantly influences the size of the time-decomposition strategy. Due to significant and variable fermentation/maturation times, synchronization of the liquid preparation and bottling stages can be properly addressed in the novel approaches. Depending on the liquid type, these times may take up to 41 days, triggering shifting bottlenecks between both stages. In addition, the “ready” liquid may be held in tanks for some time before feeding the lines. Summing up, the major contributions of this study are the MIP model formulated for the brewery problem based on a practical case and the MIP-heuristics developed to solve it. The remainder of this paper is organized as follows. The next section briefly describes the beer production process. In Section 3, an MIP formulation is presented and in Section 4 solution approaches based on different relax-and-fix and fix-and-optimize heuristics are proposed. The problem instances used and the results of the computational tests are reported and analyzed in Section 5. Section 6 concludes this study and discusses possible future research directions.
نتیجه گیری انگلیسی
In this paper, we consider the lot sizing and scheduling problem in the brewery industry. This problem differs from other problems in the beverage industries mainly due to the time required for the fermentation and maturation processes during the liquid preparation in the tanks. Moreover, the “ready” liquid can be stored in the tanks for several days while waiting for bottling in the filling lines. To the best of our knowledge, there are no other studies in the literature addressing this problem at the brewery companies. The main planning challenge is the synchronization of the two stages, as the production bottlenecks alternate between them. We propose a novel model that integrates both stages, as well as MIP-based heuristics that explore the model structure. Two solution methods are proposed using a constructive method based on the relax-and-fix heuristic and several improvement procedures based on fix-and-optimize strategies. The results are better than those obtained by solving the overall model with the CPLEX 12.4 solver in terms of applicability of the solutions and computational performance (average Ratio and CPU time). An interesting line of research would be to explore alternative formulations for the problem based on ATSP (Asymmetric Travelling Salesman Problem) constraints, as well as problem decomposition using the structure of stages. These formulations could provide tighter lower bounds than the aggregate formulation. Another potential future research would be to develop heuristics and metaheuristics which could be more effective to solve the problem rather than the present MIP-heuristics.