پیش بینی تقاضا، تعیین اندازه دسته تولید و برنامه ریزی بر اساس فهرست افق برنامه ریزی

Lot sizing and scheduling problems arise when a variety of products are manufactured in a plant of finite capacity in which a single product variant at one time can be manufactured, and changeover costs (and/or times) depend on the products scheduling sequence. MIP models developed to solve these problems are hard to be optimally solved, essentially for the relevant number of integer variables required to represent all possible changeovers in the planning horizon. However, in many real applications, production is planned on a rolling horizon basis, that is, only decisions related to the first period of the planning horizon are usually implemented. Production decisions on later periods are often only represented, because these are obtained using data (forecasted demand) that will change in the next period. Thus, it is not worth spending a lot of time to exactly solve a problem whose input data are imprecise and unstable because to do so would be to exactly solve the wrong problem. This suggests the formulation of simplified models that do not consider the scheduling sequences in later periods. In this paper it is shown that if on one hand demand uncertainty due to forecasting justifies the model simplification (making it senseless to specify the exact future scheduling sequences) then on the other hand it introduces instability issues that can have a considerable impact on the performances of simplified MIP formulations. The study is conducted using data from a real case and simulating both the demand forecasting procedure and the production planning phase on a rolling horizon basis, and gives insights for deciding on the appropriate level of simplification of MIP formulations that can be successfully applied to these problems.

A lot sizing and scheduling problem from a company in the wood floors sector is presented. In these types of companies, a variety of products characterized by different wood types, sizes, surface finishings and colors are manufactured. In particular, the last stage of production, consisting of the customization of the final product, can be modeled as a single plant of finite capacity, in which a single product variant at one time can be manufactured. Changing the type of product that is manufactured is expensive in terms of costs, and changeover costs depend on the products scheduling sequence. The scheduling of production lots, as well as their sizing, is an area of increasing research attention within the wider field of production planning and scheduling (Clark et al., 2011). The single-level lot-sizing problem for multiple items that compete for finite resource (machine or plant) capacity is known as the Capacitated Lot-Sizing Problem (CLSP). The CLSP is a large-bucket model (i.e. more than one product can be produced in each period) that, in its pure version, does not consider the sequencing of products in each period. Quadt and Kuhn (2008) performed a literary review that extends the standard CLSP formulation by back-orders, setup carry-over, sequencing, parallel machines. Sequence-dependent setup costs in CLSP have been introduced by Haase (1996), while Haase and Kimms (2000) proposed a model for CLSP with sequence-dependent setup times and costs in which efficient product sequences are pre-determined. Sequence dependent setups have been also approached through small-buckets models, like the Discrete Lotsizing and Scheduling Problem (DLSP), in which the planning horizon is divided in small time periods such that at most one product can be manufactured in a single period (All-or-Nothing assumption). Fleischmann (1994) extended the DLSP to sequence dependent setup costs. He determines upper and lower bounds by Lagrangian relaxation and reformulates the problem as a Traveling Salesman Problem with Time Windows (TSPTW) to propose a heuristic solution. Salomon et al. (1997) used the same approach, considering also sequence-dependent setup times and using a dynamic programming approach to solve small problems exactly. Another formulation that provides a natural way to model sequence dependent setup costs is the Generalized Lotsizing and Scheduling Problem, introduced by Fleischmann and Meyr (1997). GLSP makes use of a two-level time structure that divides the planning horizon into large buckets, which are then divided into a number of small time slots. Deterministic and dynamic demands over a finite planning horizon are to be met without back-logging so as to minimize inventory holding and sequence-dependent setup costs. The term ‘General’ is based on the fact that several models for lot-sizing (including CLSP and DLSP) differ from the GLSP only by additional constraints that restrict the time structure of the solutions. Meyr (2000) extended the GLSP to the GLSPST (which considers both sequence-dependent setup costs and setup times) and developed an algorithm that uses local search for lot sequencing with linear programming and dual reoptimization for lot-sizing. In recent years, lot sizing models with sequence dependent setups are receiving an increasing attention by researchers. From the review by Karimi et al. (2003) that outlined the scarcity of literature till then devoted to lot sizing problems with sequence-dependent setups, a few works considering this issue appeared. Gupta and Magnusson (2005) considered CLSP with sequence dependent setup costs and non-zero (but fixed) setup times, with the feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. They developed a heuristic for solving large problem instances and a procedure for obtaining a lower bound on the optimal solution. Almada-Lobo et al. (2007) presented two exact formulations for modeling setup carryover in the CLSP, described a five-step heuristic that finds solutions to these problems, and measured the goodness of solutions by the gap between the lower and upper bounds. Almada-Lobo and James (2010) employed a tabu search and a variable neighborhood search meta-heuristic to solve (not optimally) CLSP medium to large sized problems with sequence-dependent times and costs. Recently, they proposed a new iterative MIP-based neighborhood search heuristics to solve the same problem in a most efficient way (James and Almada-Lobo, 2011). Mohammadi et al. (2010) provided five MIP-based heuristics based on iterative procedures for solving the CLSP with the introduction of serially arranged machines and sequence-dependent setups. Kovacs et al. (2009) introduced a new mixed-integer programming model for CLSP with sequence dependent costs, derived from that presented in Haase and Kimms (2000). In their formulation all the efficient product sequences are represented using item-related binary variables. The setup costs for each time period are then bounded from below adding new constraints based on the efficient sequences, and an heuristic algorithm generates coefficients of these constraints which give tight LP relaxations. In this way they succeeded in solving larger problems with respect to the MIP of Haase and Kimms (2000). Clark (2003) developed an approximate static MIP models and heuristic methods for sequence dependent setup times problems. Clark (2005) proposed a model that includes product-group set-up and time backlogs, but does not consider sequence dependent setup-costs. Araujo et al. (2007) presented a model, derived from the GLSP, that schedules machines with sequence-dependent setup costs and times to produce key materials which are then used to manufacture final products. Three local search variants are used to approximately solve the problem: descent heuristic, diminishing neighborhood search and simulated annealing. Gicquel et al. (2009) considered the DLSP with sequence-dependent changeover costs and times, and proposed an approach based on the extension of an existing tight formulation (Wolsey, 2002) for the case without changeover times. Shim et al. (2011) improved the algorithm of Haase (1996) for the CLSP with sequence-dependent setup costs, by suggesting a two stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method with various priority rules to select the items to be moved among periods. Kwak and Jeong (2011) consider CLSP with a special form of sequence-dependent setup times, where the larger is the product produced again the more is the setup time needed. The problem is solved utilizing the characteristic of the special structure of setup times through a two-level hierarchical method. What arises from all the above-mentioned studies is the difficulty to optimally solve this type of lot sizing problem (that considers both capacity constraints and sequence dependent setup costs), essentially for the relevant number of integer variables involved in its formulation. However, in real applications, only decisions related to the first period of the planning horizon are usually implemented. Production decisions on later periods are often only represented, because these are obtained using data (forecasted demand) that will change in the next period. Araujo et al. (2007) outlined that is not worth spending a lot of time to exactly solve a problem whose input data are imprecise and unstable because to do so would be to exactly solve the wrong problem. For that reason, they proposed a simplified formulation of the GLSP that is applicable on a rolling horizon basis, implementing the immediate decisions relating to the next one period, after which the planning horizon is rolled forward and the model is applied once more with updated forecasts and inventory information. Another possible approach to deal with demand uncertainty is to consider the stochastic version of the lot sizing and scheduling problem (Sox et al., 1999). There is a growing literature on stochastic and robust lot sizing. Many models developed to solve this problem are variants of statistical inventory management strategies, which may be used to address supply chain management within a decentralized framework; however, they are not so useful for capacity constrained master production scheduling (Brandimarte, 2006). Among the possible approaches to tackle the problem, multistage stochastic programming (Birge and Louveaux, 1997) is potentially interesting. However, multi-stage stochastic programming is computationally intensive, even in the continuous case; adding the complexity of mixed-integer programming models such as multi-item CLSP with sequence-dependent setups makes this approach difficult to apply to the case study. The rolling horizon assumption fits well to the case studied, and suggests the application of simplified models such as the one proposed by Araujo et al. (2007). However, as it will be described in more detail in 4 and 5.3, the application of this model to the case study presented herein provides myopic solutions, due to the neglect of setup costs related to periods after the first one in the objective function. Furthermore, although Araujo et al. tested their model on a rolling horizon basis, they did not consider forecasted demand data, but exactly known demand data. In this paper simplified formulations that take into account, in an approximate way, future setup costs are proposed and tested on a rolling horizon basis, and the impact of using forecasted demand data instead of real ones is considered. In fact, as it will be described, if on one hand demand uncertainty justifies the model simplification (making it senseless to specify the exact future scheduling sequences) then on the other hand it introduces instability issues that have to be considered when generating production plans. In the following, the production environment of the case studied is described, and a MIP formulation to solve the complete problem, derived from the GLSP, is given. Then, three simplified models with some variants, applicable on a rolling horizon basis, are formulated. The appropriateness of these three simplified models is then evaluated by simulating the forecasting process and the generation of production plans (through each one of the three models) during one year, using historical demand data from the company.

In this paper three simplified MIP models, derived from the Generalized Lotsizing and Scheduling Problem, have been presented and applied to a real case of a company in the wood floors sector, in which setup costs depend on items' scheduling sequence, future requirements are forecasted and production planning is performed on a rolling horizon basis. The simplifications introduced by the MIP models (namely SM, CSM and FCSM) are, respectively, to ignore future setup costs in the objective function (SM); to estimate future setup costs in the objective function without specifying the exact scheduling sequence for future periods (CSM); to introduce, with respect to the CSM model, a freezing mechanism for the first period of the planning horizon in order to limit instability issues caused by demand uncertainty. Different variants of these basic models have also been tested, including the consideration of valid inequalities, the reformulation of changeover variables, and a different way of estimating future setup costs in the objective function. We did not focus our attention on the development of new algorithms to optimally solve these simplified problems. In this study we want rather to outline the concept that when applying MIP formulations to real cases, it is of primary importance to find the appropriate level of simplification of the MIP formulation. The simulation study that has been performed using historical data from the company allows to draw some general consideration. Simplifying the complete MIP model reducing the number of integer variables cannot be done by neglecting future setup costs. In fact, the SM (proposed by Araujo et al., 2007) demonstrates a myopic behavior that brings, when capacity is not tight, just to reproduce a lot for lot production planning. The CSM allows overcoming this limit by estimating future changeover costs, trying in this way to anticipate productions and accumulate inventories in order to avoid an excessive number of setups. However, due to demand uncertainty, CSM fails to reduce total costs because of the frequent adjustments needed to adjust inventories (accumulated on the basis of forecasts) to real demands. In fact, the difficulty to estimate future setup costs through a single parameter for each product causes a tendency to perform (unnecessary) changeovers in the first period of the rolling horizon rather than in later periods, bringing higher total setup costs. The use of a weighted sum of setup costs in the objective function provides a more unbiased estimate of future setup-cost, limiting in this way an excessive anticipation of production and providing better solution in terms of decreasing total costs. By introducing a freezing mechanism on the first period of the rolling horizon, the FCSM demonstrates its effectiveness in bringing down total costs, by considerably reducing the total number of changeovers with respect to the CSM. This result is obtained through the introduction of a conditional constraint that preserves the ability to avoid future capacity shortages if big quantities of products are ordered in later periods. This model allows extending the planning horizon to many periods, without suffering the typical instability effects due to demand uncertainty.