یک روش تمدد اعصاب لاگرانژی برای یک مشکل توأم تعیین اندازه دسته تولید و کاهش سهام

Industrial production processes involving both lot-sizing and cutting stock problems are common in many industrial settings. However, they are usually treated in a separate way, which could lead to costly production plans. In this paper, a coupled mathematical model is formulated and a heuristic method based on Lagrangian relaxation is proposed. Computational results prove its effectiveness.

This work focuses on decision-making problems associated with the production planning at tactical/operational levels. In this context, consider a production process in which the main activity is to manufacture final products assembled from parts which are to be cut from large objects in stock. More particularly, in furniture industries this cutting process consists of cutting wooden rectangular plates into smaller ordered parts, as shown in Fig. 1.Based on the known demand for final products per period, a lot-sizing problem (LSP) should be solved to decide the quantity of each final product which has to be manufactured in each period of the planning horizon. The objective is to minimize the production, inventory, and setup costs. However, it should be noted that the LSP does not optimize the material lost in the cutting process, since different lots require different amounts of parts that lead to a diverse material loss. In this paper we propose an integrated methodology to optimize the LSP and the imbedded cutting stock problem (CSP) simultaneously. The solution of this combined problem explores the trade-off when the CSP is solved by considering the trim loss, as well as the production, inventory and setup costs of final products for several periods. For example, if we consider the manufacturing anticipation of some final products, the storage costs increase, but probably the trim loss reduces due to better cutting patterns and setup costs are also expected to be lowered. This problem is called coupled lot-sizing and cutting stock problem or, for short, lot-cut problem (LCP). Typically, industries solve this problem separately by first solving the LSP, determining the production planning of final products for each period, and then solving the CSP, making decisions (for each period) on how to cut each plate in order to meet the quantity of parts necessary to fulfill the final product demand. However, when solving the problem in a decomposed fashion, possible infeasibilities can arise related to saw machine capacity, i.e., in some periods the planned saw capacity can be greater than the given capacity. These possible infeasibilities due to violated capacity constraints are overcome by transferring production among periods (this approach is reviewed in Section 3). Alternatively, difficulties in obtaining feasible solutions can be overcome with overtime work (considering one more work shift) or backlogging. This alternative can be modeled by considering new variables to increase the machine capacities, or by tackling with negative stocks, but this is not considered in this paper. The integration of the cutting stock and the production planning processes has not yet been much discussed in the literature, but its relevance, found in different industrial settings suggests that it is a very interesting and important problem to be researched. This type of problem is usually found in furniture industries, when wooden parts should be cut to assemble the final products (e.g., industrial/residential furniture), in fiber glass industries that cut fiber glass plates to manufacture printed circuit boards, in aluminum window frame manufacturing where aluminum profiles are cut to make several window types, in the packaging industry where carton plates are cut in order to fulfill a carton box demand, and so forth. In all mentioned problems, the lot-sizing and CSPs are economically relevant in the process. Drexl and Kimms (1997) suggest many coupled problems (coordination problems) for future research, for example the CSP integrated into the LSP, describing them as “probably the most crucial objective for future work”. Some work involving cutting stock decisions in production planning have been found in the literature (see Arbib and Marinelli, 2005; Hendry et al., 1996; Nonas and Thorstenson, 2000 and Nonas and Thorstenson, 2008; Poltroniere et al., 2008; Reinders, 1992) but, either they do not consider capacity constraints, or they consider the cutting patterns known as a priori, or they use a two-phase solution procedure. None of them solve both problems in conjunction considering capacity constraints, setup, storage, and trim loss costs. Gramani and França (2006) analyzed the trade-off that arises when solving the CSP 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 parts) and the setup costs. The authors formulated a mathematical model of the combined cutting stock and LSP 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 final products. Analogously, other problems at a tactical/operational level can be linked with a view to a better global solution. Recently, Toledo et al. (2008) have presented an optimization model for the integrated lot-sizing and scheduling problem in a soft drink industry. The challenge of this work was to determine simultaneously the minimum lot-sizing and scheduling costs of raw material in tanks and also in the bottling lines, where setup costs and setup times are sequence-dependent. Pileggi et al. (2005) also studied another combined problem. The authors presented three heuristic approaches to deal with the integrated cutting pattern generation and sequencing problem, taking into consideration the trade-off between trim loss and the number of open stacks. Although the investigation of combined problems is very relevant, the studies found in the literature are still not vast. This paper is organized as follows: in the next section, a mixed-integer mathematical model for the LCP is proposed. Then, in Section 3 a decomposition heuristic (DH) is presented, which reflects the industrial practice for solving the lot-sizing and CSPs separately. In Section 4, a heuristic based on Lagrangian relaxation is described, which is able to find good quality solutions in quite reasonable computational times. Finally, computational comparisons using four sets of randomly generated instances are presented.

In this paper a new mathematical model for the combined lot-sizing and cutting stock problem is presented. The model incorporates the conjecture that it is advantageous to anticipate the production of certain final product lots, which on the one hand will increase the inventory costs, but on the other hand will compensate with the reduction of the setup and cutting costs (using a better arrangement in cutting patterns and trim losses). For this model, a resolution method based on Lagrangian relaxation is proposed, using the sub-gradient method to update the Lagrange multiplier vectors. In order to compare the results of the proposed Lagrangian heuristic (LH), the decomposition heuristic (DH) was used. The DH heuristic reflects the industrial practice of treating the problem separately, first solving the lot-sizing problem and then, for each period of the planning horizon, solving a cutting stock problem. That solution is provided by the first iteration of the Lagrangian heuristic. The effectiveness of the proposal can be shown by the computational results obtained for 4 test sets by two different analyses: (1) the relative deviation of the setup, plates and storage quantities obtained by the DH and LH solutions and (2) the gain obtained by the LH solution when compared with the DH solution. The findings for large problems reveal that the approach that deals with the problems in a combined form (LH) presents a small increase in the storage costs, which is more than compensated by a substantial reduction in the setup costs and a small decrease in the number of cut plates. For smaller problems (represented by Table 1 and Table 2) the results were similar, in this case, even for the storage cost a reduction was observed (around 3%). It is worth noticing that for some instances, the LH was able to find optimal solutions. In short, in many manufacturing processes where cutting decisions have a great impact on production costs (such as furniture industries, leather product industries process, and packaging industries), storage, setup costs, and trim losses are relevant decisions that managers wish to achieve in the minimum cost plan. To make this decision more helpful, we show in this paper that instead of solving these problems in a separate way, the Lagrangian heuristic aggregates most of the relevant decisions, and leads to a lower total cost plan.