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

Question

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.

Answer 1

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.

Answer 2

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.