How to formulate and solve a variant of the Cutting Stock Problem

I should mention up front that I'm new to this forum and operations research in general. A problem has come up recently at work that I'm having a tough time solving.

Our machine shop acquires many long steel bars (typically 20 foot long, but could vary) that need to be cut to various sizes for further processing on a CNC lathe. I've been asked to minimize waste/trim from the process.

A couple special constraints are making it tough for me to formulate the problem. First, we can only feed ≤2 foot segments into the CNC at a time, so we cut the stock before cutting the final product. Additionally, each segment we cut must be fixed to the CNC (e.g. normally 2.5 inches of the segment are fixed and can't be cut), introducing a certain amount of inherent waste for each segment cut from the original bar. It is probably a naïve viewpoint, but this almost seems like two nested Cutting Stock Problems.

I will summarize briefly. We effectively have unlimited stock to cut from. In the usual case, we need to cut several hundred copies of two or more lengths from the stock. However, we can't feed the whole stock into the machine, so we must cut it into lengths of ≤2 feet. From each ≤2 foot segment, we can then cut the required lengths (i.e. the final product).

How would I go about formulating and solving this problem? As a mathematician, I always strive to find the most general solution. If it simplifies the solution, though, feel free to consider a more specific situation. Our normal use case (>50% of cases), we are using 20 foot stock and cutting 2 specific lengths.

Here is an expanded model for the two-stage version of the problem (cutting "bars" into "lengths" and then cutting "lengths" into final product). I'm going to change the terminology slightly. I will use “stock” to refer to the long bars, “parts” to refer to segments cut from the long bars, and “product” to refer to the products cut from the parts. $$I$$, $$J$$ and $$K$$ will be the index sets for different kinds of stock, part and product respectively. $$S_{i}>0$$ will be the supply of stock $$i\in I.$$ $$D_{k}>0$$ will be the demand for product $$k\in K.$$

$$P_{i}$$ will be the set of known patterns for cutting stock type $$i\in I,$$ and $$Q_{j}$$ will be the set of known patters for cutting part type $$j\in J.$$ For each $$i\in I$$ and $$p\in P_{i},$$ $$A_{pj}\ge 0$$ will be the number of parts of type $$j\in J$$ produced by cutting one unit of type $$i$$ stock using pattern $$p.$$ For each $$j\in J$$ and $$q\in Q_{j},$$ $$B_{qk}\ge 0$$ will be the number of units of product $$k\in K$$ produced by cutting one type $$j$$ part using pattern $$q.$$

For each combination of a stock type $$i\in I$$ and pattern $$p\in P_{i}$$ we have an integer variable $$x_{p}\ge 0$$ counting the number of units of that stock cut with that pattern. Similarly, for each part type $$j\in J$$ and pattern $$q\in Q_{j}$$ we have an integer variable $$y_{q} \ge 0$$ counting the number of parts of that type cut with that pattern. The objective function is$$\min_{x,y}\sum_{i\in I}\sum_{p\in P_{i}}c_{i}x_{p}$$where $$c_{i}$$ is the unit cost of a type $$i$$ piece of stock. The constraints are as follows.

• The number of pieces of stock you cut is limited to the available supply.$$\sum_{p\in P_{i}}x_{p}\le S_{i}\quad\forall i\in I.$$
• The number of parts cut is limited by the available supply.$$\sum_{q\in Q_{j}}y_{q}\le\sum_{i\in I}\sum_{p\in P_{i}}A_{pj}x_{p}\quad\forall j\in J.$$
• The amount of product produced must satisfy demand.$$\sum_{j\in J}\sum_{q\in Q_{j}}B_{qk}y_{q}\ge D_{k}\quad\forall k\in K.$$

If you begin with on-hand inventory of intermediate parts, you can add the on-hand inventory to the right side of the second set of constraints.

• Thank you Paul. That model looks like it will fit my use case perfectly. Mar 10, 2022 at 19:44

This sounds like a fairly standard one-dimensional cutting stock problem, which can be modeled with an integer linear program.

One approach is as follows. Let $$D_j$$ be the demand for pieces of length $$L_j$$, and let $$S_i$$ be the supply of bars of length $$B_i$$. I'm going to assume that $$L_j$$ includes not only the length of the final piece but also any required waste (the "fixed" portion in the problem description), and I'm also going to assume that there is no scrap value to any waste. Let $$c_i$$ be the cost of a length $$B_i$$ bar.

Start by enumerating possible cutting patterns for each type of bar. Pattern $$p$$ is described by the type $$i_p$$ of bar used and the number $$a_{pj}$$ of type $$j$$ pieces the pattern yields. (A pattern may produce pieces of one size or pieces of a mix of sizes.) Let $$P$$ be the index set for the patterns.

The model contains a nonnegative integer variable $$x_p$$ for each pattern, capturing how many rods are cut with that pattern. The objective is to minimize the cost of the bars used:$$\min_x \sum_{p\in P} c_{i_p}x_p.$$

The constraints are straightforward.

• You cannot cut more bars than you have. $$\sum_{p \in P:i_p = i} x_p \le S_i \quad \forall i.$$
• You need to produce enough pieces to meet demand. (I am assuming here that all pieces cut are usable, i.e., no "spoilage".) $$\sum_{p \in P} a_{pj} x_p \ge D_j \quad \forall j.$$

The one possible issue here is that if you have a lot of different piece sizes and bar sizes the number of patterns ($$\vert P \vert$$) can get out of hand. In that case, you can either try the branch-and-price (column generation) approach, which requires more sophisticated software, or the Gilmore-Gomory heuristic, which works well but does not guarantee an optimal solution. Both start with a handful of patterns and generate new patterns on the fly.

• Paul, thank you for your helpful comment. It is nice hearing from someone who is such an expert in this field. I have taken a while to respond as I've been working through the model that you explained. I was hoping to ask a follow up question if you don't mind. I modeled this using unlimited, fixed-2ft stock lengths (minus intrinsic waste) which are cut from a larger bar. However, 2ft is only the max for our CNC. Couldn't an optimal solution (i.e. minimal waste), use various stock lengths? Not sure if your model encapsulates that logic, as I mentioned I'm new to OR. Mar 7, 2022 at 18:54
• The model I wrote is for a one-stage process. It can be expanded to handle a two stage process, but requires extra variables and constraints ... and patterns. Basically, you need to identify a finite set of intermediate sizes you might use, then create two sets of patterns. One set of patterns is used to cut long bars into intermediate stock. The other is used to cut intermediate stock into final product.
– prubin
Mar 7, 2022 at 19:19
• In addition to supply constraints for the original stock and demand constraints for the final product, you have inventory constraints for each intermediate size, saying production of that size from initial stock cannot exceed consumption of that size producing end product.
– prubin
Mar 7, 2022 at 19:21
• Just to be clear, when you feed a "stock length" of 2ft or less into the CNC lathe, is the result a single unit of one end-item product, or can that one piece be cut into multiple end-items? Also, do you have a single final output (product), or are there multiple distinct products?
– prubin
Mar 8, 2022 at 18:31
• Paul, the 2 ft or less "stock lengths" that are fed into the CNC are then cut into multiple end-items, of which there can be multiple distinct products (end-items/products). Mar 9, 2022 at 13:48