The lot sizing problem is frequently encountered in industrial production planning. How does a planner decide the lot size of each product produced on one or more machines in each demand period over a planning horizon? This problem has been extensively researched, as discussed in the reviews by Bahl et al., 1987, Drexl and Kimms, 1997, Brahimi et al., 2006, Karimi et al., 2003, Jans and Degraeve, 2007 and Jans and Degraeve, 2008.
In some industrial sectors, production setup costs and times are sequence-dependent, so that the decisions about the production of lots concern their sequence as well as their size. The two sets of decisions are mutually dependent and so should be modelled and decided simultaneously rather than separately. For example, Araujo, Arenales, and Clark (2007) consider the processing of key materials at an initial stage as well as the products that use the materials. In such a two-stage system, the sequencing decisions at the end stage must jointly consider products that use the same materials, so that material changeovers are minimised at the prior stage. In other words, the sequencing at both stages must be integrated. The model in Araujo et al. (2007) is based on a classical formulation of the lot sizing problem, but its complexity meant that an established industrial-grade optimisation solver was unable to find an optimal solution within acceptable computing time. As a result, the paper developed heuristic solution methods based on relax-and-fix within a rolling horizon approach and incorporating metaheuristics.
Since then, many other authors have also researched the integrated lot-sizing and sequencing problem with material preparation at a prior stage in a wide range of industrial settings. Examples include soft drink production (Ferreira et al., 2012, Ferreira et al., 2009, Ferreira et al., 2010 and Toledo et al., 2009), animal feed (Clark et al., 2010 and Toso et al., 2009), electrofused grains (Luche, Morabito, & Pureza, 2009), glass bottles (Almada Lobo et al., 2007 and Almada Lobo et al., 2008), foundries (Araujo et al., 2008, Camargo et al., 2012 and Tonaki and Toledo, 2010), yogurt packaging company (Marinelli, Nenni, & Sforza, 2007), pharmaceutical company (Stadtler, 2011) and sand casting operations (Hans & Van de Velde, 2011).
Most of this recent research, including Araujo et al. (2007), is based on the General Lot Sizing and Scheduling Problem (GLSP) model ( Fleischmann & Meyr, 1997) in which the planning horizon is subdivided into macro-periods, in each of which multiple products can be produced. To model the sequence of lots, each macro-period is in turn subdivided into micro-periods in which at most one product can be produced. This special structure involving subperiods within macro time periods is similar to a small-bucket framework ( Koçlar, 2005).
However, some papers, such as Clark et al., 2010 and Ferreira et al., 2012 take a different approach, using an asymmetric travelling salesman problem (ATSP) representation for sequencing lots rather than a GLSP-type model. The results presented in Ferreira et al. (2012) shown the superiority of their ATSP-type model over a GLSP-type model. One possible reason is the poor quality of the GLSP linear relaxation as a lower bound on the optimal solution.
Taking forward research initiated in Bernardes, Araujo, and Rangel (2010), the first contribution of this current paper is to demonstrate that certain reformulations applied to the GLSP-type model in Araujo et al. (2007) can provide improved solutions using established optimisation solvers, due mainly to their better quality of linear-relaxation lower-bounds, contributing to the growing research in this area. The second contribution is to show computationally that the use of metaheuristic methods can help solve the reformulations more quickly and better than established solvers, such as, Cplex 12.0.
This paper is structured as follows. In Section 2, the original model in Araujo et al. (2007) is presented. Section 3 develops extended formulations and proposes new constraints. In Section 4, a reformulated rolling horizon-based model is proposed while Section 5 presents the metaheuristics. Section 6 computationally compares the quality of the reformulations using the Branch-and-Cut search within the solver Cplex 12.0 and using the metaheuristics. Section 7 concludes and poses challenges for future research.
This paper considered a lot sizing model that sequences the preparation of a key material and decides the production lot sizes of the final products. This class of problem is very prevalent in the literature, using GLSP formulations. However, recent ATSP-inspired formulations have shown better performance. Aiming to tighten the linear relaxation of the GLSP-type model in Araujo et al. (2007), a reformulation as a facility location problem was extended with setup elimination constraints and flow equations, strengthening the link between setup and changeover variables. Three different metaheuristics and an industry-standard optimizer were then successfully applied to accelerate and improve the solution of both the original and extended formulations, particularly applying simulated annealing to the latter.
Computational tests showed that on the larger instances the metaheuristics outperformed Cplex and the reformulated model was more effective than the original model. Jointly applied, the metaheuristics and the extended formulation were effective on both small and large sized instances, particularly the latter where metaheuristics really show their advantage.
Future work will extend and adapt the metaheuristics to the case where multiple machines process the raw materials, the predominant case in many industrial processes. Considering the prevalence of this type of problem, future research should analyse and compare the GLSP and ATSP formulations, both theoretically and computationally.
