One-Dimensional Cutting Stock Problem with a Given Number of Setups: A Hybrid Approach of Metaheuristics and Linear Programming

One-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems, which arises in many industrial applications. Since the setup costs for switching different cutting patterns become more dominant in recent cutting industry, we consider a variant of 1D-CSP, called the pattern restricted problem (PRP), to minimize the number of stock rolls while constraining the number of different cutting patterns within a bound given by users. For this problem, we propose a local search algorithm that alternately uses two types of local search processes with the 1-add neighborhood and the shift neighborhood, respectively. To improve the performance of local search, we incorporate it with linear programming (LP) techniques, to reduce the number of solutions in each neighborhood. A sensitivity analysis technique is introduced to solve a large number of associated LP problems quickly. Through computational experiments, we observe that the new algorithm obtains solutions of better quality than those obtained by other existing approaches.     

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.     

A two-objective mathematical model without cutting patterns for one-dimensional assortment problems

This paper considers a one-dimensional cutting stock and assortment problem. One of the main difficulties in formulating and solving these kinds of problems is the use of the set of cutting patterns as a parameter set in the mathematical model. Since the total number of cutting patterns to be generated may be very huge, both the generation and the use of such a set lead to computational difficulties in solution process. The purpose of this paper is therefore to develop a mathematical model without the use of cutting patterns as model parameters. We propose a new, two-objective linear integer programming model in the form of simultaneous minimization of two contradicting objectives related to the total trim loss amount and the total number of different lengths of stock rolls to be maintained as inventory, in order to fulfill a given set of cutting orders. The model does not require pre-specification of cutting patterns. We suggest a special heuristic algorithm for solving the presented model. The superiority of both the mathematical model and the solution approach is demonstrated on test problems.     

An effective solution for a real cutting stock problem in manufacturing plastic rolls

We confront a practical cutting stock problem from a production plant of plastic rolls. The problem is a variant of the well-known one dimensional cutting stock, with particular constraints and optimization criteria defined by the experts of the company. We start by giving a problem formulation in which optimization criteria have been considered in linear hierarchy according to expert preferences, and then propose a heuristic solution based on a GRASP algorithm. The generation phase of this algorithm solves a simplified version which is rather similar to the conventional one dimensional cutting stock. To do that, we propose a Sequential Heuristic Randomized Procedure (SHRP). Then in the repairing phase, the solution of the simplified problem is transformed into a solution to the real problem. For experimental study we have chosen a set of problem instances of com-mon use to compare SHRP with another recent approach. Also, we show by means of examples, how our approach works over instances taken from the real production process. All authors are supported by MEC-FEDER Grant TIN2007-67466-C02-01 and by contract CN-05-127 of the University of Oviedo and the company ERVISA, and by FICYT under grant BP04-021.     

The Application of Preprocessing and Cutting Plane Techniques for a Class of Production Planning Problems

This paper investigates properties of integer programming models for a class of production planning problems. The models are developed within a decision support system to advise a sales team of the products on which to focus their efforts in gaining new orders in the short term. The products generally require processing on several manufacturing cells and involve precedence relationships. The cells are already (partially) committed with products for stock and to satisfy existing orders and therefore only the residual capacities of each cell in each time period of the planning horizon are considered. The determination of production recommendations to the sales team that make use of residual capacities is a nontrivial optimization problem. Solving such models is computationally demanding and techniques for speeding up solution times are highly desirable. An integer programming model is developed and various preprocessing techniques are investigated and evaluated. In addition, a number of cutting plane approaches have been applied. The performance of these approaches which are both general and application specific is examined.     

Modeling multistage cutting stock problems

In multistage cutting stock problems (CSP) the cutting process is distributed over several successive stages. Every stage except the last one produces intermediate products. The list of intermediate products may be given or arbitrary. The goal is to minimize the total amount of material taken out of stock to cut finished products sufficient to meet customer demands. If the intermediate sizes are given, the column generation technique can be applied to multistage cutting problems. If the intermediate sizes are not given then another dimension is added to the problem complexity. We propose a special procedure for this case that dynamically generates both rows (intermediate sizes) and columns (patterns). We refer to this method as row-and-column generation. The method uses an auxiliary problem embedded into the frame of the revised simplex algorithm. It is a non-linear knapsack problem that can be solved efficiently. In contrast to the column generation method the developed technique cannot guarantee the optimal solution. However, the results of computational experiments are very promising and prove that the method is a valuable addition to the set of tools for modeling and solving multistage CSPs.     

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.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

A multi-objective programming approach to 1.5-dimensional assortment problem

In this paper we study a 1.5-dimensional cutting stock and assortment problem which includes determination of the number of different widths of roll stocks to be maintained as inventory and determination of how these roll stocks should be cut by choosing the optimal cutting pattern combinations. We propose a new multi-objective mixed integer linear programming (MILP) model in the form of simultaneously minimization two contradicting objectives related to the trim loss cost and the combined inventory cost in order to fulfill a given set of cutting orders. An equivalent nonlinear version and a particular case related to the situation when a producer is interested in choosing only a few number of types among all possible roll sizes, have also been considered. A new method called the conic scalarization is proposed for scalarizing non-convex multi-objective problems and several experimental tests are reported in order to demonstrate the validity of the developed modeling and solving approaches.     

Solving a two-dimensional trim-loss problem with MILP

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.     

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.     

Complete and robust no-fit polygon generation for the irregular stock cutting problem

The no-fit polygon is a construct that can be used between pairs of shapes for fast and efficient handling of geometry within irregular two-dimensional stock cutting problems. Previously, the no-fit polygon (NFP) has not been widely applied because of the perception that it is difficult to implement and because of the lack of generic approaches that can cope with all problem cases without specific case-by-case handling. This paper introduces a robust orbital method for the creation of no-fit polygons which does not suffer from the typical problem cases found in the other approaches from the literature. Furthermore, the algorithm only involves two simple geometric stages so it is easily understood and implemented. We demonstrate how the approach handles known degenerate cases such as holes, interlocking concavities and jigsaw type pieces and we give generation times for 32 irregular packing benchmark problems from the literature, including real world datasets, to allow further comparison with existing and future approaches.     

Controlling distribution inventory systems with shipment consolidation and compound Poisson demand

We consider a one-warehouse-multiple-retailer inventory system where the retailers face stochastic customer demand, modelled as compound Poisson processes. Deliveries from the central warehouse to groups of retailers are consolidated using a time based shipment consolidation policy. This means that replenishment orders have to wait until a vehicle departures, which increases the lead time for the retailers and therefore also the safety stock. Thus, a trade-off exists between expected shipment costs and holding costs. Our aim is to determine the shipment intervals and the required amount of safety stock for each retailer and the warehouse to minimize total cost, both for backorder costs and fill rate constraints. Previous work has focused on exact solutions which are computationally demanding and not applicable for larger real world problems. The focus of our present work is on the development of computationally attractive heuristics that can be applied in practice. A numerical study shows that the proposed heuristics perform well compared to the exact cost minimizing solutions. We also illustrate that the approaches are appropriate for solving real world problems using data from a large European company.     

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem

This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are 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.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

Variable neighbourhood search for the minimum labelling Steiner tree problem

We present a study on heuristic solution approaches to the minimum labelling Steiner tree problem, an NP-hard graph problem related to the minimum labelling spanning tree problem. Given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes of the graph, whose edges have the smallest number of distinct labels. Such a model may be used to represent many real world problems in telecommunications and multimodal transportation networks. Several metaheuristics are proposed and evaluated. The approaches are compared to the widely adopted Pilot Method and it is shown that the Variable Neighbourhood Search that we propose is the most effective metaheuristic for the problem, obtaining high quality solutions in short computational running times.