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.     

An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing

This paper presents a two-stage approach for pattern generation and cutting plan determination of the one-dimensional cutting stock problem. Calculation of the total number of patterns that will be cut and generation of the cutting patterns are performed in the first stage. On the other hand, the second stage determines the cutting plan. The proposed approach makes use of two separate integer linear programming models. One of these models is employed by the first stage to generate the cutting patterns through a heuristic procedure with the objective of minimizing trim loss. The cutting patterns obtained from Stage 1 are then fed into the second stage. In this stage, another integer linear programming model is solved to form a cutting plan. The objective of this model is to minimize a generalized total cost function consisting of material inputs, number of setups, labor hours and overdue time; subject to demand requirements, material availability, regular and overtime availability, and due date constraints. The study also demonstrates an implementation of the proposed approach in a coronary stent manufacturer. The case study focuses on the cutting phase of the manufacturing process followed by manual cleaning and quality control activities. The experiments show that the proposed approach is suitable to the conditions and requirements of the company.     

Generating optimal cutting patterns for rectangular blanks of a single size

This paper deals with the problem of minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts. First we prove that we can obtain the unconstrained optimal layout by searching among normal multi-section layouts. Next we present an unconstrained algorithm to search for it. The unconstrained algorithm uses a branch-and-bound method with a tight upper bound. Later we discuss the algorithm for the constrained problem where the blank demand must be met exactly. Finally, the unconstrained algorithm is extended to cope with the blade length constraint. Experimental computations show that the algorithms are extremely efficient.     

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.     

The Cutting Stock Problem in the Flat Glass Industry -- Selection of Stock Sizes

In the glass industry holding good stock sizes appears to have at least as big an impact on trim loss as cutting up the stock plates efficiently. In this paper two tech niques are described for determining "optimal" stock sizes, one a heuristic method and the other an integer programming algorithm. Several actual applications within the glass industry are described, and illustrative results of the improvements in wastage that have been achieved are given.     

Setup minimising conditions in the trim loss problem

The one-dimensional cutting stock, trim or deckling problem arises in cutting short units from long ones. The long units could be pipes, rods or reels of paper. The objectives are to fill demand with as little stock as possible, to reduce trim waste and to keep the number of setups to a minimum.We examine a formal approach to setup minimization and show that, at best, it provides necessary conditions for solving this task. Sufficient conditions also require the generation of all possible patterns, in principle at least.     

A fractional algorithm for optimal cutting of lumber into dimension parts

A fractional algorithm is described which optimizes the cutting of boards or lumber into dimension parts. The model is an extension of previously developed models and is purposely designed for cutting scenarios where the customer order for the dimension parts can be satisfied within a given range, i.e., flexible rather than exact demand. An illustrative example is presented simply to describe the model and compare results between the standard procedure and the modified procedure proposed in this paper.     

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.     

Enforcing minimum run length in the cutting stock problem

Deckling, cutting stock or trim loss problems arise when small units are to be fitted into large ones. One aims to reduce stock usage and setups, then favors long runs, surplus over waste, similar loss per pattern and prompt delivery. One may also want to enforce exact solutions, with zero tolerance for surplus, or those with a narrow limit on pattern loss.Among secondary objectives, setups affect run length: on the average, fewer setups mean longer runs. Yet this relation is erratic. As setups decrease, some runs become longer, but others may stay as short as they are or become even shorter. We first show that this is so.We then examine the feasibility and the cost of making the shortest run longer in one-dimensional deckling problems. We show that conditional constraints do not formally enforce long runs, yet help to prove that they add at least one stock unit to an otherwise optimal plan. In turn, a relaxed stock constraint may improve runs, setups and surplus.     

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.     

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.     

A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems

This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.     

A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.     

A model for heuristic coordination of real life distribution inventory systems with lumpy demand

This paper presents an approximation model for optimizing reorder points in one-warehouse N-retailer inventory systems subject to highly variable lumpy demand. The motivation for this work stems from close cooperation with a supply chain management software company, Syncron International, and one of their customers, a global spare parts provider. The model heuristically coordinates the inventory system using a near optimal induced backorder cost at the central warehouse. This induced backorder cost captures the impact that a reorder point decision at the warehouse has on the retailers’ costs, and decomposes the multi-echelon problem into solving N + 1 single-echelon problems. The decomposition framework renders a flexible model that is computationally and conceptually simple enough to be implemented in practice.     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.     

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.     

A two-echelon inventory model with lost sales

This paper considers a single-item, two-echelon, continuous-review inventory model. A number of retailers have their stock replenished from a central warehouse. The warehouse in turn replenishes stock from an external supplier. The demand processes on the retailers are independent Poisson. Demand not met at a retailer is lost. The order quantity from each retailer on the warehouse and from the warehouse on the supplier takes the same fixed value Q, an exogenous variable determined by packaging and handling constraints. Retailer i follows a (Q, R_i) control policy. The warehouse operates an (SQ, (S − 1)Q) policy, with non-negative integer S. If the warehouse is in stock then the lead time for retailer i is the fixed transportation time L_i from the warehouse to that retailer. Otherwise retailer orders are met, after a delay, on a first-come first-served basis. The lead time on a warehouse order is fixed. Two further assumptions are made: that each retailer may only have one order outstanding at any time and that the transportation time from the warehouse to a retailer is not less than the warehouse lead time. The performance measures of interest are the average total stock in the system and the fraction of demand met in the retailers. Procedures for determining these performance measures and optimising the behaviour of the system are developed.     

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.     

Allocation of warehouse inventory with electronic data interchange and fixed order intervals

This paper considers the problem of allocating warehouse inventory to retailers where retailer orders and the replenishment of warehouse inventory occur periodically on a fixed schedule. We assume that the warehouse and the retailers have the opportunity to exchange demand information through Electronic Data Interchange (EDI). At the warehouse level, for instance, the available information on the retailer's demand may be utilized in determining the shipment quantities needed to meet the desired service level to the retailers. Unlike similar models focusing primarily on optimizing systems wide performance measures, in this paper we focus on the service level furnished to the retailers by the warehouse. To this end, three different allocation policies are considered: static, myopic, and dynamic rules characterizing the impact of available demand information on the resulting service levels. Numerical illustrations exemplify the allocation rules considered. An interesting though counter intuitive observation is that the existence of additional demand information cannot, a prior, be assumed superior.