The one-dimensional cutting stock problem with usable leftovers – A survey

In this article, we review published studies that consider the solution of the one-dimensional cutting stock problem (1DCSP) with the possibility of using leftovers to meet future demands, if long enough. The one-dimensional cutting stock problem with usable leftovers (1DCSPUL) is a problem frequently encountered in practical settings but often, it is not dealt with in an explicit manner. For each work reviewed, we present the application, the mathematical model if one is proposed and comments on the computational results obtained. The approaches are organized into three classes: heuristics, item-oriented, or cutting pattern-oriented.     

One-dimensional stock cutting: optimization of usable leftovers in consecutive orders

Central European Journal of Operations Research - This paper deals with usable leftovers (UL) in one-dimensional stock cutting in consecutive orders. UL are leftovers longer than a certain...     

A heuristic for the one-dimensional cutting stock problem with usable leftover

A heuristic algorithm for the one-dimensional cutting stock problem with usable leftover (residual length) is presented. The algorithm consists of two procedures. The first is a linear programming procedure that fulfills the major portion of the item demand. The second is a sequential heuristic procedure that fulfills the remaining portion of the item demand. The algorithm can balance the cost of the consumed bars, the profit from leftovers and the profit from shorter stocks reduction. The computational results show that the algorithm performs better than a recently published algorithm.     

MIP models for two-dimensional non-guillotine cutting problems with usable leftovers

In this study we deal with the two-dimensional non-guillotine cutting problem of how to cut a set of larger rectangular objects to a set of smaller rectangular items in exactly a demanded number of pieces. We are concerned with the special case of the problem in which the non-used material of the cutting patterns (objects leftovers) may be used in the future, for example if it is large enough to fulfill future item demands. Therefore, the problem is seen as a two-dimensional non-guillotine cutting/packing problem with usable leftovers, also known in the literature as a two-dimensional residual bin-packing problem. We use multilevel mathematical programming models to represent the problem appropriately, which basically consists of cutting the ordered items using a set of objects of minimum cost, among all possible solutions of minimum cost, choosing one that maximizes the value of the usable leftovers, and, among them, selecting one that minimizes the number of usable leftovers. Because of special characteristics of these multilevel models, they can be reformulated as one-level mixed integer programming (MIP) models. Illustrative numerical examples are presented and analysed.     

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.

     

A solution procedure for a pattern sequencing problem as part of a one-dimensional cutting stock problem in the steel industry

To cut reinforcing bars for concrete buildings, machines are used which have compartments to store the cut orders until the requirement is met. Number and size of these compartments restrict kind and processing sequence of possible cutting patterns. In this paper we present the so-called “Sequencing algorithm” that tackles the problem of finding a processing sequence for the cutting patterns starting from an integer solution of the cutting stock problem and using an interpretation of relations between orders in patterns as a graph. Computational results are reported.     

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.     

Solving a bi-criterion cutting stock problem with open-ended demand: a case study

We consider a real-life cutting stock problem with two types of orders. All orders have to be cut from a given number of raws (also known as stock unit, master reel or jumbo). For each order the width of the final (also known as reels or units) and the number of finals is given. An order is called an exact order when the given number of finals must be produced exactly. An order is called an open order when at least the given number of finals must be produced. There is a given maximum on the number of finals that can be produced from a single raw which is determined by the number of knives on the machine. A pattern specifies the number of finals of a given width that will be produced from one raw. A solution consists of specifying a pattern for each raw such that in total the number of finals of exact orders is produced exactly and at least the number of finals of open orders is produced. There are two criteria defined for a solution. One criterion is the cutting loss: the total width of the raws minus the total width of the produced finals. The second criterion is the number of different patterns used in the solution. We describe a branch-and-bound algorithm that produces all Pareto-optimal solutions.     

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.     

One-dimensional cutting stock optimization in consecutive time periods

The paper deals with the general one-dimensional cutting stock problem (G1D-CSP), where optimization is not limited to a single order. Stock cutting is treated as a permanent business process in a company in which consecutive order sets need to be fulfilled either for production needs or for its customers. Exact demand for future orders is not known in advance. The unutilized and partly utilized stock lengths left after fulfilling current order sets are stored and used later. The goal is the reduction of trim loss and costs over a broader time-span. A new approach is suggested where previously developed method for G1D-CSP is modified. Several practical examples of the cutting process for several consecutive order sets are presented. An extension to a currently used typology for cutting stock problems is proposed.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

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.     

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.     

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.     

The One Dimensional Cutting Stock Problem Using Two Objectives

This paper considers the cutting stock problem with two objectives. The primary objective is to minimize the trim loss in a given piece of metal work requiring metal sections of various lengths. The secondary objective is to organize the cutting so that the maximum quantity of leftovers is accumulated in the last bar(s). This leftover will then be of a length allowing it to be used in the future. An algorithm which provides an optimal solution is presented for this problem. However, it may not be efficient for large problems. Consequently, a heuristic approach is suggested, with the large problem being divided (decomposed) into smaller ones; the remainder of one problem being used in the next. This model was developed for a small metal workshop in a kibbutz.     

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.     

Roll cutting in the curtain industry,or: A well-solvable allocation problem

We study the problem of cutting a number of pieces of the same length from n rolls of different lengths so that the remaining part of each utilized roll is either sufficiently short or sufficiently long. A piece is ‘sufficiently short’, if it is shorter than a pre-specified threshold value δ_min, so that it can be thrown away as it cannot be used again for cutting future orders. And a piece is ‘sufficiently long’, if it is longer than a pre-specified threshold value δ_max (with δ_max > δ_min), so that it can reasonably be expected to be usable for cutting future orders of almost any length. We show that this problem, faced by a curtaining wholesaler, is solvable in O(nlogn) time by analyzing a non-trivial class of allocation problems.     

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.     

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.     

Alternative configurations for cutting machines in a tube cutting mill

In a steel tube mill where an endless stream of steel tube is supplied from a manufacturing facility, trim waste is never made regardless of cutting patterns used and the standard cutting stock problem seems meaningless. Therefore, the continuous stock cutting problem with setup is introduced to minimize the sum of cutting time and pattern changing time to meet the given demand. We propose a new configuration of cutting machines to achieve higher production efficiency, namely the open-ended configuration as opposed to the traditional closed-ended configuration, thereby two variants of the problem are defined. We propose linear formulations for both problems using binary expansion of the number of pieces of different types in a pattern. Furthermore, we define the time for pattern change as a linear function of the number of knives used in the pattern to be more realistic. Computational studies suggest that the open-ended cutting machine may improve the production time by up to 44% and that our linear formulations are more efficient than the existing ones.