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

We present a heuristic approach to solve a complex problem in production planning, the multistage lot-sizing problem with capacity constraints. It consists of determining the quantity to be produced in different periods in a planning horizon, such that an initially given demand forecast can be attained. We consider setup costs and setup times. Due the complexity to solve this problem, we developed methods based on evolutionary metaheuristics, more specifically a memetic algorithm. The proposed heuristics are evaluated using randomly generated instances and well-known examples in the literature.

Material Requirements Planning (MRP) is a procedure used in industry for planning the production of the end items, as well as the production (or purchase) of its components. By taking the anticipated build schedule from the Master Production Schedule (MPS) and “exploding” it through the Bill of Materials, the purchase and/or the production of the items and its components is established, in order to create a demand forecast. Although they are commonly used in practice, MRP systems suffer from some criticism. One of them is that in its basic form it does not take into account the limitations of the production resources (Tempelmeier, 1997). If the resources are exceeded, part of the production is transferred or capacity additions (overtime) are made to try to adjust the plan. However, such transfers can cause infeasible plans. In addition, in general, the plan generated by the MRP system does not provide an optimal production plan in the sense of its cost being the least possible (França et al., 1997). The multistage capacitated lot-sizing (MSCLS) problem that we consider in this paper takes into consideration all these issues. This means that its objective is to determine the lot-size production that minimizes the costs involved (production, inventory and setups) subject to a group of constraints (inventory balance with demand and capacity limitations). It determines the quantity and the period to produce each item in order to satisfy a given demand forecast in a planning horizon. In multistage production systems the planning of each item also depends on the planning of other items, lower in the product structure hierarchy. When capacity constraints and setup costs are considered the MSCLS problem is NP-Hard (Florian et al., 1980), even with equal demands, zero inventory costs and zero setup times. Bitran and Yanasse (1982) showed that several cases of a single item can be solved with a polynomial-time algorithm, and that the problem turns to be NP-Hard when a second item with an independent setup is introduced. When we consider non-zero setup times, the feasibility decision problem becomes NP-Complete (Maes et al., 1991). There is a vast literature on lot-sizing problems, which can be reviewed by Bahl et al. (1987) and Kuik et al. (1994). Due to the computational complexity of solving the MSCLS problem in an exact way, researchers have chosen to use heuristics (Katok et al., 1998; França et al., 1997; Tempelmeier and Derstroff, 1996; Ozdamar and Barbarosoglu, 2000). Katok et al. (1998) developed a heuristic based on the work of Harrison and Lewis (1996). Their results are compared with IBM's Optimization Subroutine Library (OSL, http://www.research.ibm.com/osl/) solution with limited time of execution. França et al. (1997) presented a heuristic composed of four procedures based on shifts of production between periods. The method starts with a solution given by the Wagner–Whitin (1958) heuristic, which returns a solution that is generally infeasible. After this, different procedures are used with the aim of finding a feasible solution or one with lower cost or even a new initial solution. We use this heuristic as one component of the memetic algorithm (MA) and we compare our results with it since it provides a good benchmark. Tempelmeier and Derstroff (1996) developed a Lagrangean heuristic. They also started with a Wagner–Within solution and then used a smoothing procedure to try to find a feasible solution. We also compare our results with theirs. Ozdamar and Barbarosoglu (2000) presented another heuristic using Lagrangean Relaxation and Simulated Annealing. They compared their results with the one proposed by Tempelmeier and Derstroff (1996). Unfortunately, the new heuristic did not get better results. The main objective of this paper is to present heuristic methods based on evolutionary algorithms to address the MSCLS problem, including setup costs and setup times. More specifically, we developed a MA, an evolutionary algorithm that makes use of local search techniques. This technique has been shown to be highly effective for several problems in production planning and scheduling (Moscato, 1999; França et al., 2001; Mendes et al., 2002; Moscato and Cotta, 2003). The local search techniques that we used are the procedures of the heuristic found in França et al. (1997). This paper is organized as follows. In Section 2 we present a mathematical model for the MSCLS problem. The heuristic found in França et al. (1997) is described in Section 3, due to the fact that it has been used in our MA. In Section 4 we describe the MA that we developed. Finally, in Section 5, we present the results we obtain and we compare it with the heuristics found in França et al. (1997) and Tempelmeier and Derstroff (1996).

We presented in this paper an MA to solve the multistage capacitated lot-sizing problem, considering setup time and setup cost. The MA that we developed uses procedures from the heuristic found in França et al. (1997). We tested two crossovers (XR and XWW) and a Restart strategy. We tested our MA in three groups of instances (G1, G2 and G3). In the G2 group we got 11.4% of gap against 14.3% obtained by H0 (heuristic in França et al. 1997). These gaps are calculated comparing the solution with a lower bound obtained using Lagrangean Relaxation. When we compare both crossovers, we concluded that the XWW, which was based on the Wagner–Within algorithm, was better for all types of instances in this study. Analyzing the feasibility, the MA was able to find feasible solutions in 71% of these instances and when it ended with an infeasible solution we observed that the overuse of resources was 1.9% on average. In G1, we have 160 instances of small dimension, for which we have the optimal solution. In this group we concluded two things. First of all, the good performance of the MA. It obtained a gap of the 0.2% from the optimal against 2.1% for H0. In addition, we noticed is the lower bound we used is poor. Comparing the MA result with the lower bound we have a gap of 12.1% against a 0.2% when comparing it with the optimal solution, i.e., almost 12% of the duality gap. This shows that the results presented for the G2 group may be even better than suggested. Finally, in G3 we tested a group of 600 instances found in Tempelmeier and Derstroff (1996). Our MA improved the results by 1.0%. It found solutions within a 0.3% from the optimal on average. Additionally, in 89% of the instances we found solutions 0.5% or less from the optimal, against the 53% by Tempelmeier and Derstroff heuristic. As a conclusion we can say that the MA provides a very useful strategy to obtain good results for the MCLSP, improving results obtained by other heuristics, like França et al. (1997) and Tempelmeier and Derstroff (1996).