رویکرد بهینه سازی خطی برای ترکیب مدل برنامه ریزی تولید

Two fundamental processes usually arise in the production planning of many industries. The first one consists of deciding how many final products of each type have to be produced in each period of a planning horizon, the well-known lot sizing problem. The other process consists of cutting raw materials in stock in order to produce smaller parts used in the assembly of final products, the well-studied cutting stock problem. In this paper the decision variables of these two problems are dependent of each other in order to obtain a global optimum solution. Setups that are typically present in lot sizing problems are relaxed together with integer frequencies of cutting patterns in the cutting problem. Therefore, a large scale linear optimizations problem arises, which is exactly solved by a column generated technique. It is worth noting that this new combined problem still takes the trade-off between storage costs (for final products and the parts) and trim losses (in the cutting process). We present some sets of computational tests, analyzed over three different scenarios. These results show that, by combining the problems and using an exact method, it is possible to obtain significant gains when compared to the usual industrial practice, which solve them in sequence.

Due to economical aspects and computational advances, the complexity of optimization models in industrial processes has been increasing considerably. It is still common that most research is focused on solving isolated industrial problems. But with the growth and general dissemination of computer and optimization-based planning, industries have been looking for more advanced global methods. Instead of determining optimal solutions of isolated problems, people of industries are looking for integrated solutions that represent the industrial activities more accurately. For instance, managers that have tools to solve separately logistics and production planning, now are interested in treating both problems in conjunction, to obtain a global cost minimization. Obviously, by joining various problems of high complexity, one is faced with a problem much more difficult to solve, since there are additional coupling constraints, and a global optimum solution to the combined problem is not in general a straight composition of each optimal solution of the isolated problems. In this paper we focus on the case of furniture industries, but extensions to many others industrial settings are straightforward. Given a demand of final products (Fig. 1(c)) over a planning horizon, the issue addressed consists of deciding what to produce in each period over the planning horizon and how to arrange the parts (Fig. 1(b)) in plates (Fig. 1(a)) in order to minimize the trim loss during the cutting process. Therefore, two problems of high complexity arise in this production planning. The first one, the lot sizing problem, which consists of planning the quantity of each type of final product to be produced in each period. Setup costs may be associated with production decision for each final product in any given period. The second problem that arises in the case of furniture industries consists of cutting rectangular plates in order to produce smaller rectangular parts used in the assembly of final products, the well-known rectangular guillotineable two-dimensional cutting stock problem (see [22]). In this way, combining these two problems, the issue consists of the trade-off analysis existent when we solve the cutting stock problem taking into account the production planning for various periods. Probably it would be worth of anticipating the production of lots of parts or final products, increasing the storage costs, but reducing losses in cutting process as well as decreasing the quantity of setups. Thus, three economical factors have influence on the combined problem: the trim loss, storage and setup costs.Both problems considered separately have been well studied in literature. Previous research on the lot sizing problem has focused on single and multi-levels, as well as capacitated and uncapacitated resources. There are a number of studies in the literature (see for example, [1], [11], [12], [13], [20] and [21]). Also, the cutting stock problem has been greatly studied since the seminal paper of Gilmore and Gomory [5] (see for example [3], [5], [6], [10], [14], [15] and [22]). Even though the cutting stock problem coupled in the production planning problem arises in many industries, only a few papers have been published to find good mathematical models and, hopefully, efficient solution methods. Drexl and Kimms [4] remarked that this combined problem (they called coordination problem) as a “most crucial goal for future research”. Nonas and Thorstenson [17] studied the combined cutting stock and lot sizing problem to a company of off-roads trucks. Reinders [19] studied the process of cutting tree trunks to assortments and boards for various markets. Hendry et al. [9] proposed a two-stage solution to solve the combined problem for a copper industry; first they found the best cutting patterns minimizing the waste, and then these patterns are given as input to the second stage, which provides the daily production planning. This decomposition approach was also used by Poltroniere et al. [18] to solve a combined problem in the paper industry. However, none of them studied the assembly of final products. Only few papers in the literature approach directly the combined lot sizing and cutting stock problem. Gramani and França [7] analyzed the trade-off that arises when solving the cutting stock problem by taking into account the production planning for various periods. The goal was to minimize the trim loss costs in the cutting process, the inventory costs (for the parts) and the setup costs. The authors formulated a mathematical model of the combined cutting stock and lot-sizing problem and proposed a solution method based on an analogy with the network shortest path problem, comparing its results with the ones simulated in the industrial practice. However, this paper does not consider the production and inventory costs of final products. Gramani et al. [8] proposed a heuristic method based on Lagrangian relaxation to the coupled lot sizing and cutting stock problem. The difficulty faced by the Lagrangian solution approach is that the resulting Lagrangian subproblems are NP-hard capacitated lot sizing problems. In this paper, we address the model as Gramani et al. [8] by relaxing setups but including the storage of parts. The aims with this new approach are, on the one hand, a simpler model solvable by available solvers, and, on the other hand, the incorporation of part inventories, a practical and relevant issue, which can be seen as usable leftovers (see [2] for other approaches). We solve this combined model to optimality by using the CPLEX package with the column generation technique. It is worth of noting that even relaxing setups the trade-off between storage and trim losses still remains. This paper is organized as follows: Next section presents the mathematical model proposed in Gramani et al. [8] by relaxing setups but including the storage of parts. Then a decomposition approach is presented to solve the problem in two steps, first solving the lot sizing problem and then the cutting stock problem. In Section 4 we present a column generation method to solve the combined model. In Section 5 we take two sets of instances analyzed over three different aspects to be used in computational tests, which support the advantage of the combined model, and finally some concluding remarks are given in Section 6.

This paper provides a new methodology to solve in conjunction two complex problems that arise in furniture companies. The first one is the problem of cutting rectangular plates in order to produce smaller rectangular parts, the well-known cutting stock problem. The other is the problem of planning the quantity of final products to be produced in each period of the planning horizon, while satisfying all demand requirements and optimizing the production and storage costs, the lot sizing problem. Our approach is inspired in a combined model proposed in [8] which showed to be successful in capturing the trade-off between the setup and plate costs. In the new model the final product setup cost is disregarded but the part inventory cost is now considered, which maintains a trade-off between the storage and plate’s cost. As stated previously, the aim with this new approach is two-fold: the simpler model permits the use of a commercial solver to achieve optimal solutions while it allows for the incorporation of parts inventories, a practical and relevant issue in most industries. Toward this, we proposed an exact approach to solve the combined model using the simplex method with the column generation technique. We show that, when solving these problems in conjunction, even disregarding the setup constraints, it could be beneficial to anticipate the production of some lots of parts or final products, increasing the storage costs, but obtaining an advantageous cost decrease in the trim loss through a better composition of the cutting patterns. Computational results obtained when the new method is executed over a set of generated instances clearly show its applicability. We present two sets of computational tests, analyzed over three different aspects. In one case, the results of the exact method compared with the solutions obtained by the method used in usual practice (separated method) show that we were able to obtain gains up to 12.7%. Another aspect concerned the saw capacity shows that when the capacity is considered tight, the solutions use more plates in comparison when we use a normal capacity, leading to costly global solutions. The third aspect considered is that, if the plate’s costs increases, the quantity of plates used decreases considerably, using better cutting patterns.