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.     

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 new dynamic programming procedure for three-staged cutting patterns

Three-staged patterns are often used to solve the 2D cutting stock problem of rectangular items. They can be divided into items in three stages: Vertical cuts divide the plate into segments; then horizontal cuts divide the segments into strips, and finally vertical cuts divide the strips into items. An algorithm for unconstrained three-staged patterns is presented, where a set of rectangular item types are packed into the plate so as to maximize the pattern value, and there is no constraint on the frequencies of each item type. It can be used jointly with the linear programming approach to solve the cutting stock problem. The algorithm solves three large knapsack problems to obtain the optimal pattern: One for the item layout on the widest strip, one for the strip layout on the longest segment, and the third for the segment layout on the plate. The computational results indicate that the algorithm is efficient.     

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

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.     

Integrating two-dimensional cutting stock and lot-sizing problems

The two-dimensional cutting stock problem (2DCSP) consists in the minimization of the number of plates used to cut a set of items. In industry, typically, an instance of this problem is considered at the beginning of each planning time period, what may result in solutions of poor quality, that is, excessive waste, when a set of planning periods is considered. To deal with this issue, we consider an integrated problem, in which the 2DCSP is extended from the solution in only a single production planning period to a solution in a set of production planning periods. The main difference of the approach in this work and the ones in the literature is to allow sufficiently large residual plates (leftovers) to be stored and cut in a subsequent period of the planning horizon, which may further help in the minimization of the waste. We propose two integrated integer programming models to optimize the combined two-dimensional cutting stock and lot-sizing problems, minimizing the total cost, which includes material, waste and storage costs. Two heuristics based on the industrial practice to solve the problem were also presented. Computational results for the proposed models and for the heuristics are presented and discussed.     

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 heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

In this paper we present a heuristic method to generate constrained two-dimensional guillotine cutting patterns. This problem appears in different industrial processes of cutting rectangular plates to produce ordered items, such as in the glass, furniture and circuit board business. The method uses a state space relaxation of a dynamic programming formulation of the problem and a state space ascent procedure of subgradient optimization type. We propose the combination of this existing approach with an and/or-graph search and an inner heuristic that turns infeasible solutions provided in each step of the ascent procedure into feasible solutions. Results for benchmark and randomly generated instances indicate that the method’s performance is competitive compared to other methods proposed in the literature. One of its advantages is that it often produces a relatively tight upper bound to the optimal value. Moreover, in most cases for which an optimal solution is obtained, it also provides a certificate of optimality.     

BPPLIB: a library for bin packing and cutting stock problems

The bin packing problem (and its variant, the cutting stock problem) is among the most intensively studied combinatorial optimization problems. We present a library of computer codes, benchmark instances, and pointers to relevant articles for these two problems. The library is available at http://or.dei.unibo.it/library/bpplib. The computer code section includes twelve programs: seven are directly downloadable from the library page, while for the remaining five we provide addresses where they can be obtained or downloaded. Some of the codes for which we provide an original C++ implementation need an integer linear programming solver. For such cases, the library provides two versions: one that uses the commercial solver CPLEX, and one that uses the freeware solver SCIP. The benchmark section provides over six thousands instances (partly coming from the literature and partly randomly generated), together with the corresponding solutions. Instances that are difficult to solve to proven optimality are included. The library also includes a BibTeX file of more than 150 references on this topic and an interactive visual tool to manually solve bin packing and cutting stock instances. We conclude this work by reporting the results of new computational experiments on a number of computer codes and benchmark instances.     

An application of simulated annealing to the cutting stock problem

We solve a two-dimensional cutting stock problem by applying a general global optimization algorithm, the simulated annealing. Our algorithms applied to the cutting problems involving both the guillotine and non-guillotine constraints, underlying that the latter is to be preferred for a big number of items. Several tests prove the validity of the algorithms.     

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.     

New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.     

考虑生产计划的多周期切割问题优化研究

切割生产广泛存在于工业企业,是原材料加工的重要环节。已有文献主要关注单周期切割问题,但是切割计划也是生产计划的一部分,切割计划和生产计划应该协调优化,达到全局最优。本文研究考虑生产计划的多周期切割问题,目标是最小化运营成本,包括准备成本、切割成本、库存成本以及母材消耗成本。首先建立混合整数规划模型;提出动态规划启发式算法;最后对算例在多种情境下测试,分析成本因子变化对最优结果的影响。算法结果与CPLEX最优结果比较,平均误差为1.85%,表明算法是有效的。     

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.     

An efficient approach for large-scale two-dimensional guillotine cutting stock problems

We present an efficient method for solving approximately both constrained and unconstrained two-dimensional cutting stock problems. The algorithm guarantees a constant approximation ratio for some versions of the problem. The performance of the proposed algorithm is evaluated on several large-scale randomly generated problem instances and on many instances of the literature. Computational results show that our algorithm produces high-quality solutions within reasonable computational times.     

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.     

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.

     

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.     

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.