購(gòu)買設(shè)計(jì)請(qǐng)充值后下載，，資源目錄下的文件所見即所得，都可以點(diǎn)開預(yù)覽，，資料完整，充值下載可得到資源目錄里的所有文件。。?！咀ⅰ浚篸wg后綴為CAD圖紙，doc,docx為WORD文檔，原稿無水印，可編輯。。。具體請(qǐng)見文件預(yù)覽，有不明白之處，可咨詢QQ:12401814
Reel and sheet cutting at a paper mill
M. Helena Correia, Jose F. Oliveira, J. Soeiro Ferreira
INESC Porto, Instituto de Engenharia de Sistemas e Computadores do Porto, 4200-465 Porto, Portugal
Faculdade de Economia e Gestao, Universidade Catolica Portuguesa, 4169-005 Porto, Portugal
Faculdade de Engenharia, Universidade do Porto, 4200-465 Porto, Portugal
Abstract
This work describes a real-world industrial problem of production planning and cutting optimization of reels and sheets, occurring at a Portuguese paper mill. It will focus on a particular module of the global problem which is concerned with the determination of the width combinations of the items involved in the planning process: the main goal consists in satisfying an order set of reels and sheets that must be cut from master reels. The width combination process will determine the quantity/weight of the master reels to be produced and their cutting patterns, in order to minimize waste, while satisfying production orders.
A two-phase approach has been devised, naturally dependent on the technological process involved.Details of the models and solution methods are presented. Moreover some illustrative computational results are included.
2003 Elsevier Ltd. All rights reserved.
Keywords: Combinatorial optimization; Cutting-stock; Heuristics
1. Introduction
Planning the paper production at a paper mill assumes several essentially distinct forms, each of which has its own particular characteristics, requiring different mathematical formulation and solution methods [1–3]. However, trim loss minimization is usually a component of the objective function. Other components take account of factors such as setup processing time, number and characteristics of cutting patterns. Additionally, there are usually several constraints involved, concerning customers specifications, strategic decisions and technological characteristics of the production process.
This paper describes a system developed by request of a Portuguese paper mill, Companhia dePapel do Prado (CPP), to support its production planning, focusing on the production and cutting of paper reels. This work is part of a broader system, named COOL (COOL stands for the Portuguese words meaning optimized combination of widths), which is intended to support the implementation of an optimizing policy for paper production and stock management.
The problem tackled in this paper concerns the definition of cutting patterns and quantity of paper to produce in order to satisfy a set of ordered reels and sheets, grouped by type of paper and grade.
It basically deals with the problem of planning the paper production and cutting of the master reels in order to satisfy a set of orders. The cutting plans to associate to the master reels must be defined considering minimization of waste while satisfying the ordered quantities. Varieties of technological and operational constraints are involved in the planning process, causing an interesting and dig cult trim problem.
From this perspective, this problem can be included in the broad family of Cutting-Stock Problems [4–6]. The problem formulation adopted disregards trim loss at the end of the reels (as it was considered irrelevant when compared with that occurring at the edges of the paper reels, which runs all along the paper length) and so, a 1D approach has been devised. The need of a two-phase methodology was determined by the technological characteristics of the cutting process. Other 1D two-phase cutting-stock problems can be found in published literature. Besides paper industry, similar approaches are also applied in other industries, such as the steel industry [7,8] and the plastic Flm industry [9].
We propose an original solution method for the problem described above, which leads to considerable improvements in terms of paper savings when compared with those solutions obtained manually, as confirmed by the paper mill. The procedure developed is based on two distinct linear programming models, which are solved by a Simplex algorithm. Then, the solutions obtained are rounded in a post-optimization procedure, in order to satisfy integer constraints previously ignored. The quality of the solutions obtained are also validated by the resolution of an integer programming model of the problem, solved using the commercial optimization software CPLEX v.6.0.
The paper is organized as follows. Section 2 introduces the production problem and its industrial background. Particular emphasis will be given to those features of the industrial environment, which were relevant for the solution approach developed. Sections 3 and 4 will describe the problem and the methodology developed to solve it, respectively. A small example is considered throughout Section 4 in order to illustrate the solution procedure. In Section 5 some results will be presented and discussed.
2. Industrial environment
This case study takes place at a Portuguese paper mill, which can be considered as a vertical industry, since it produces paper products from pulp. The products are supplied both in reels and sheets. This industry operates in two types of markets: one in which the paper products have standard dimensions and other where paper products have make-to-order dimensions. The production cycle is of 6 weeks and, for technological reasons, there is a pre-defend production sequence in which paper is produced in ascending or descending rates.
Fig. 1 shows the production Jow of the paper products through out the production line. The paper is produced at the paper machine from pulp and is wound into a master reel of fixed width. Then, the master reel follows to the winder where it is cut into smaller reels. These reels either go straight to the customer or to the Intermediate Stock, or are cut into sheets at the cutters. These cut-to-sizes sheets either go to the customer or to the Standard Stock.
Both at the winder and cutters there is a small shred of fixed width cut-o8 all along the paper length. This scrap has been quite determinant for the solution process adopted.
Fig. 2 illustrates the relative perspectives of planning and production processes, emphasizing the products and sub-products involved. Planning and Production follow opposite directions. Planning’s based on the customers specifications of ordered products. Ordered reels and sheets of the same type of paper and grade, and belonging to the same Production Order, are combined into auxiliary reels. These auxiliary reels may include either reels or sheets, but never both. So, two types of auxiliary reels will be distinguished: auxiliary reels of sheets and auxiliary reels of reels. Auxiliary reels are then combined into cutting patterns that are associated to master reels.
The concept of auxiliary reel has been introduced for a better understanding of both the production procedure and the solution approach adopted. It is strictly related to the technological process involved, which requires the consideration of additional scrap width whenever the cutters are used. The definition of sub-patterns inside the main cutting patterns to be cut from the master reels has determined the two-phase solution approach considered.
There is a set of constraints that must be considered in the generation of the auxiliary reels and cutting patterns and which will be described later in Section 3. These constraints determine pattern feasibility.
The order system is schematized in Fig. 3. An order can be placed by the national market or by the international market (as this company also operates outside Portugal) and is processed by the Marketing Department. The Marketing Department can also generate an internal order, similar to the external orders, if it is considered appropriated. These orders can originate a Production Requisition, a Cutting Order or an Expedition Order. A Production Requisition is grouped with other existing Production Requisitions of the same type of paper and grade, resulting in a Production Order, which then follows to production. A Cutting Order occurs when a customer order of reels can be satisfied by existing reels (stocked at the Intermediate Stock) and an Expedition Order occurs when a customer order of sheets can be satisfied by existing sheets (stocked at the Standard Stock).
3. Problem description
The work presented in this paper is mainly concerned with the cutting patterns generation process, which will determine the quantity/weight of the master reels to produce and the associated cutting patterns, in order to minimize waste while satisfying a production order. The system developed will support the cutting planning of a Production Order, not interfering with decisions related to the orders to satisfy and the type of paper to produce in each production cycle. These are previous decisions made by the Marketing Department, eventually supported by a simulation using the system COOL.
Some constraints must be considered during the definition of the cutting patterns to associate to a master reel. These constraints can be grouped in two sub-sets: ?Operational constraints (imposed by management and customers specifications):
? Only reels of identical weight per width unit (reels with the same length of paper) can be combined.
? Only reels of identical internal and external diameters can be combined.
? Customer specifications of internal and external diameters must be satisfied.
? Assignment of the auxiliary reels to the cutters must be considered, since cutters have different characteristics.
? Minimum width is imposed to cutting patterns, in order to optimize the use of the machinery available.
? Technological constraints (mainly due to machinery characteristics):
? Maximum and minimum widths of the master reel at the winder (input).
? Limited number of winder slitting knives.
? Maximum and minimum sheet lengths at the cutters.
? Maximum and minimum sheet widths at the cutters.
? Limited number of slitting knives at the cutters.
? Maximum diameter of input reels at the cutters.
? Edge trims loss both at the winder and cutters.
There are European Standard Tolerances in use at the paper industry, which must be taken into account when fulfilling order (see Table 1). The client is obliged to accept deviations of the quantity ordered in these ranges. When over-production above maximum tolerances occurs, the Marketing Department can try to negotiate the acceptance of this extra quantity with the client. Due to losses inherent to production, negative tolerances are never considered during the planning phase.
4. Solution procedure
The solution procedure adopted is clearly injected by the production Jow. It is divided into three main stages, which are represented in Fig. 4.
The First stage consists in enumerating all the auxiliary reels and cutting patterns, based on a fixed width for the master reel and on the widths of the ordered items. The resultant set of cutting patterns is then submitted to a selection process through which undesirable auxiliary reels/cutting patterns are eliminated. All the remaining cutting patterns must be feasible in terms of the technological and operational constraints imposed to the production process.
In the second stage, the cutting patterns generated and accepted during the First stage are used as columns in a linear programming model of the optimization problem. Two linear programming models were developed. These models are solved by a Simplex algorithm [10].
In the following sections each one of these stages will be presented in detail.
A small real industrial example is introduced to illustrate the solution procedure and will be followed through out its description. It concerns the production planning of paper in master reels of 2520 mm width. The paper grade is 250 g=m2 and its thickness is 345 _m. The Production Requisitions involved are described in Table 2.
Rounding heuristic
The rounding procedure is applied to the solution of both LP models and is intended to fulfill those constraints of integer nature previously ignored, such as:
(1) Fixed 7nished reels diameters imposed by the customer must be satisfied, meaning that the paper length of cutting patterns including such reels must always be multiple of the requested diameter. In order to minimize the impact of this heuristic procedure, the quantities ordered of reels of Fixed diameter are adjusted to the closest multiple of the length of one reel before building the LP model.
Table 3
(2) The minimum weight for combination of sheets constraint, equivalent to a minimum paper length, intends to avoid inefficient use of the cutters.
(3) Alike the previous item, the minimum weight for cutting pattern constraint is intended to prevent inefficient use of the winder, while establishing a minimum quantity of paper to cut with each cutting pattern used.
The rounding heuristic starts with the Final solution of the LP model (non-zero length patterns) and tries to adjust those pattern lengths in order to satisfy the referred constraints. The new solution is kept as close as possible to the LP one and must satisfy the ordered quantities. First, the rounding procedure tries to eliminate those patterns which do not respect the minimum weight conditions (constraints 2 and 3 above). Precaution must be taken not to eliminate the unique pattern containing some ordered item. Then, the remaining patterns must be rounded up in order to compensate the e8ect of the destroyed ones.
This procedure consists basically in successively sorting the cutting patterns by the number of items not satisfied in each pattern, and augmenting the quantity to be cut with the First cutting pattern of the list until, at least, one unsatisfied item becomes satisfied. This procedure is repeated until all the items in all cutting patterns are satisfied.
This rounding procedure can lead to over-production above standard tolerances, even when Model(1) is used.
In the solution presented in Table 3, only the constraint concerning the minimum weight for combination of sheets is not being satisfied by the length of FP 16(x12) since it is smaller than the minimum weight for combination of sheets determined for that pattern (2730:00 mm). As the only order in that pattern is PR 1002 and it also exists in FP 21 (x14), pattern FP 16 can be eliminated and the length of FP 21 must be adjusted to include the quantity of PR 1002 that was being cut from FP 16. The Final solution is presented in Table 4.
Fig.5.shows the output of COOL for the data in Table 2.
Table 4
Fig.5.Computational results for large-scale instances
5. Computational results
The main purpose of the computational tests was to validate the solution procedure adopted and to establish a comparative analysis between the two linear programming models developed (Model(1) and Model(2)). The data used in this First set of computational runs was provided by the Marketing Department of the company and corresponds to real problems solved at the paper mill. The number of ordered items involved range from 3 to 16 and the maximum and minimum width of the ordered items are 1392 and 238 mm, respectively, being the average width 690 mm, approximately. These are relative small instances but, by doing this, the company intends to allow the system user to easily evaluate the performance of COOL in the initial phase of usage.
Data used in the computational tests is available at www.apdio/sicup.
The algorithms were implemented using the C programming language. The computational results were obtained with a Pentium III at 450 MHz.
In order to evaluate the quality of the solutions obtained with the linear models and rounding heuristic described above, an IP model was implemented. This IP model minimizes the amount of paper produced while strictly satisfying the ordered quantities. In order to consider those integer constraints mentioned above, several integer variables are included: ? Minimum weight for combination of sheets (Min Weight Sheets): The IP model was solved using the Mixed Integer Programming module of the optimization software CPLEX v.6.0.
In Fig.6, the performance of each solution procedure developed (based on the two LP models, Model(1) and Model(2)) is evaluated in terms of objective function value. In Fig.6(a), for each model, the ratio of the results obtained with the IP model and those obtained with the linear procedure followed by the rounding heuristic are depicted for each test instance: the value of 1.00 in the y-axis corresponds to the IP model solution. From this chart it can be observed that the results of the linear based procedure are, in most cases, coincident with those obtained with the IP model: Model(1) attains the same objective function values of IP in 70% of the test instances while only approximately 50% of the results obtained with Model(2) are coincident with the IP results. Though, with only one exception, the IP results are never exceeded in more than 22%.
The chart in Fig.6(b) intends to prove the adequacy of the linear approach adopted and, so, the ratio of the results before and after the rounding procedure is computed. The value of 1.00 in the y-axis corresponds to the LP model solution before the rounding procedure. In most cases, the results of the LP routine are coincident with the Final result, which means that, in those cases, the constraints of integer nature considered in the rounding procedure do not change the linear programming result.
Both charts show that the results obtained with Model(1), which minimizes the paper length produced and does not allow over production above tolerances, are never worse than those obtained with Model(2), which does not produce to the Intermediate Stock. Moreover, these results suggest the need to improve the rounding procedure in case of Model(2).
Table 5
Table 5 compares the results obtained with the two linear programming models in terms of the three exceeding components: quantity produced to the Intermediate Stock (QuantStock), overproduction above standard tolerances (QuantTolExc) and quantity of paper that cannot be re-used in any way (Waste). All the values are expressed in terms of a percentage of the total weight of paper produced and reject the objective function adopted in each model: Model(2) does not produce to the Intermediate Stock while Model(1) tries not to exceed standard tolerances. The amounts in which, sometimes, these tolerances are exceeded in Model(1) are a consequence of the rounding procedure. However, they are quite small when compared to those obtained with Model(2).
Since waste is the only component which can not be re-used, Fig.7draws attention to the comparison between the values obtained with the two LP based procedures: Final solutions based on Model(1) are seldom significantly worse than those attained with Model(2), in terms of paper waste minimization.
According to the comparative tests performed with this set of instances, Model(1) seems to perform better than Model(2) in all of them. Nevertheless, Model(2) was kept available in the Final version of COOL, as each model may generate solutions more adequate to, or even required by, different industrial situations: when production to the Intermediate Stock is allowed or even recommended, Model(1) can be used; situations in which Intermediate Stock levels are high enough to forbid stock enlargement, Model(2) solutions may be required. In terms of efficiency, the LP approach lead to a reduction of the processing time of approximately 75% of the time used by the IP approach. Although the average resolution time of the IP approach for the instances tested was of 18 s, situations may occur which would preclude the use of the IP approach in practice.
A set of larger instances was generated and tested in order to evaluate the performance in terms of efficiency of the develo