An integer programming model for two- and three-stage two-dimensional cutting stock problems

In this paper, an integer programming model for two-dimensional cutting stock problems is proposed. In the problems addressed, it is intended to cut a set of small rectangular items of given sizes from a set of larger rectangular plates in such a way that the total number of used plates is minimized.     

Multi-job Cutting Stock Problem with Due Dates and Release Dates

The common feature of cutting stock problems is to cut some form of stock materials to produce smaller pieces of materials in quantities matching orders received. Most research on cutting stock problems focuses on either generating cutting patterns to minimize wastage or determining the required number of stock materials to meet orders. In this paper, we examine a variation of cutting stock problems that arises in some industries where meeting orders' due dates is more important than minimizing wastage of materials. We develop two two-dimensional cutting stock models with due date and release date constraints. Since adding due dates and release dates makes the traditional cutting stock problem even more difficult to solve, we develop both LP-based and non-LP-based heuristics to obtain good solutions. The computational results show that the solution procedures are easy to implement and work very well.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Reducing the number of cuts in generating three-staged cutting patterns

Three-staged guillotine patterns are widely used in the manufacturing industry to cut stock plates into rectangular items. The cutting cost often increases with the number of cuts required. This paper focuses on the rectangular two-dimensional cutting stock problem, where three-staged guillotine patterns are used, and the objective is to minimize the sum of plate and cutting costs. The column generation framework is used to solve the problem. It uses a pattern-generation procedure to obtain the patterns. The cutting cost is considered in both the pattern-generation procedure and the objective of the linear programming formulation. The computational results indicate that the approach can reduce the number of cuts, without increasing the plate cost.     

A matching approach for replenishing rectangular stock sizes

Consider a replenishment problem in which several different rectangular sizes of material are stocked. Customers order rectangles of the material, but the rectangles ordered have a range on specified width as well as on specified length. To satisfy the customer requirements, the stock material can be cut once longitudinally in order to satisfy two customer requirements or not cut at all, that is, an entire stock piece of material is used to satisfy one customer requirement. If an exact match is impossible in the current planning period, the unused material must be returned to stock— an expensive and undesirable situation. In this paper, a nonbipartite weighted matching problem formulation will be given for determining the replenishment requirements of rectangular stock sizes. Then, a hybrid solution approach, capable of solving real applications (typically up to 3000 nodes) efficiently, will be discussed. This solution was implemented in September 1998 and has operated successfully since then.     

Integrated lot-sizing and one-dimensional cutting stock problem with usable leftovers

This paper addresses the integration of the lot-sizing problem and the one-dimensional cutting stock problem with usable leftovers (LSP-CSPUL). This integration aims to minimize the cost of cutting items from objects available in stock, allowing the bringing forward production of items that have known demands in a future planning horizon. The generation of leftovers, that will be used to cut future items, is also allowed and these leftovers are not considered waste in the current period. Inventory costs for items and leftovers are also considered. A mathematical model for the LSP-CSPUL is proposed to represent this problem and an approach, using the simplex method with column generation, is proposed to solve the linear relaxation of this model. A heuristic procedure, based on a relax-and-fix strategy, was also proposed to find integer solutions. Computational tests were performed and the results show the contributions of the proposed mathematical model, as well as, the quality of the solutions obtained using the proposed method.

     

Multi-Item Single-Level Capacitated Dynamic Lot-Sizing Heuristics: A General Review

The multi-item single-level capacitated lot-sizing problem consists of scheduling N different items over a horizon of T periods. The objective is to minimize the sum of set-up and inventory-holding costs over the horizon, subject to a capacity restriction in each period. Different heuristic approaches have been suggested to solve this difficult mathematical problem. So far, only a few limited attempts have been made to analyse and compare these approaches. The paper can be divided into two main parts. The first part shows that current heuristics can be classified in two different categories: single-resource heuristics, which are special-purpose methods, and mathematical-programming-based heuristics, which can usually deal with more general problem environments. The second part is devoted to an extensive computational review. The general idea is to find relationships between the performance of the heuristic and the computational burden involved in finding the solution. Based on these computational results, suggestions can be given with respect to the usefulness of the various heuristics in different industrial settings.     

Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem

The research addressing two-dimensional (2D) irregular shape packing has largely focused on the strip packing variant of the problem. However, it can be argued that this is a simplification. The materials from which pieces are required to be cut will ultimately have a fixed length either due to the physical dimensions of the material or through constraints on the cutting machinery. Hence, in order to cut all the pieces, multiple sheets may be required. From this scenario arises the 2D irregular shape cutting stock problem. In this paper, we will present implementations of cutting stock approaches adapted to handle irregular shapes, including two approaches based on column generation (CG) and a sequential heuristic procedure. In many applications, setup costs can be reduced if the same pattern layout is cut from multiple sheets; hence there is a trade-off between material waste and number of patterns. Therefore, we describe the formulation and implementation of an adaptation of the CG method to control the number of different patterns. CG is a common method for the cutting stock problem; however, when the pieces are irregular the sub-problem cannot be solved optimally. Hence we implement CG and solve the sub-problem using the beam search heuristic. Further, we introduce a version of CG for instances where the number of rows is less than the number of columns.     

Solving real-world cutting stock-problems in the paper industry: Mathematical approaches,experience and challenges

We discuss cutting stock problems (CSPs) from the perspective of the paper industry and the financial impact they make. Exact solution approaches and heuristics have been used for decades to support cutting stock decisions in that industry. We have developed polylithic solution techniques integrated in our ERP system to solve a variety of cutting stock problems occurring in real world problems. Among them is the simultaneous minimization of the number of rolls and the number of patterns while not allowing any overproduction. For two cases, CSPs minimizing underproduction and CSPs with master rolls of different widths and availability, we have developed new column generation approaches. The methods are numerically tested using real world data instances. An assembly of current solved and unsolved standard and non-standard CSPs at the forefront of research are put in perspective.     

Heuristics for Multistage Production Planning Problems

Several heuristics for the capacitated multistage production planning problem with concave production costs, based on traditional production planning techniques and linear programming, are stated and empirically evaluated using a new capacity relaxation of the problem to furnish lower bounds on cost.     

Trim-loss minimization in a crepe-rubber mill; optimal solution versus heuristic in the 2 (3) - dimensional case

The efficiency—waste minimization—of a production planning system (PPS), solving the 3-dimensional cutting problem in a crepe rubber mills, has had to be provedSection 1 points out the problem caused by material and production. Section 2 demonstrates an algorithms solving these problems optimally but with comparatively high CPU-time. Section 3 points out how a good heuristic for the same problem works. Section 4 compares the heuristic with the optimal solution. Section 5 compares the presently employed system with the heuristic.     

A genetic algorithm solution for one-dimensional bundled stock cutting

This paper discusses a one-dimensional cutting stock problem in which lumber is cut in bundles. The nature of this problem is such that the traditional approaches of linear programming with an integer round-up procedure or sequential heuristics are not effective. A good solution to this problem must consider trim loss, stock usage and ending inventory levels. A genetic search algorithm is proposed and results compared to optimal solutions for an integer programming formulation of the problem.     

Competitive travelling salesmen problem: A hyper-heuristic approach

We introduce a novel variant of the travelling salesmen problem and propose a hyper-heuristic methodology in order to solve it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen are to visit n cities and the relationship between the travelling salesmen is non-cooperative. The salesmen will receive a payoff if they are the first one to visit a city and they pay a cost for any distance travelled. The objective of each salesman is to visit as many unvisited cities as possible, with a minimum travelling distance. Due to the competitive element, each salesman needs to consider the tours of other salesman when planning their own tour. Since equilibrium analysis is difficult in the CTSP, a hyper-heuristic methodology is developed. The model assumes that each agent adopts a heuristic (or set of heuristics) to choose their moves (or tour) and each agent knows that the moves/tours of all agents are not necessarily optimal. The hyper-heuristic consists of a number of low-level heuristics, each of which can be used to create a move/tour given the heuristics of the other agents, together with a high-level heuristic that is used to select from the low-level heuristics at each decision point. Several computational examples are given to illustrate the effectiveness of the proposed approach.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

An algorithm for a cutting stock problem on a strip

A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In our problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems we have developed a fast heuristic based on partial enumeration of all feasible patterns. We then tested the effectiveness on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

Heuristic and exact methods for the cutting sequencing problem

Cutting stock problems deal with the generation of a set of cutting patterns that minimizes waste. Sometimes it is also important to find the processing sequence of this set of patterns to minimize the maximum queue of partially cut orders. In such instances a cutting sequencing problem has to be solved. This paper presents a new mathematical model and a three-phase approach for the cutting sequencing problem. In the first phase, a greedy algorithm produces a good starting solution that is improved in the second phase by a tabu search, or a generalized local search procedure, while, in the last phase, the problem is optimally solved by an implicit enumeration procedure that uses the best solution previously found as an upper bound. Computing experience, based on 300 randomly generated problems, shows the good performance of the heuristic methods presented.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.