5
$\begingroup$

I already asked this on stack overflow but just found this forum instead and figured it was more suited here. If this isn't allowed please feel free to tell me and I'll delete the post.

I am doing some work for a local factory of where they cut out small metal sheets from larger metal sheets. All are rectangles.

Today they try to fit many small sheets on one large. And only order and keep stock of one size of large sheets before cutting them into smaller. They try to minimize the metal waste by fitting as many small sheets on the large one, and because of this the order of the production of the small sheets can be quite hard to predict some days. To combat this, they instead want to start ordering large sheets of varying sizes, maybe 8-16 different sizes. And instead produce only ONE small sheet from each LARGE sheet. This might increase the waste, but also make it easier to plan ahead which small sheets to produce. But we now face another optimization problem: What 8(just an example number, could be 10 later, but quite small number) sizes of LARGE should we keep in stock?

The SMALL sheets can be 50mm - 2000mm in width and 50mm - 1500mm in height. So one SMALL sheet could for example be 50mm wide and 1000mm high. Using a 1000x1000mm LARGE sheet would then create a lot of waste. They know what the sizes and the number of each of the SMALL sheets they are going to produce each month before, so that is part of the input. It could be many different sizes, maybe 100. And different number of each.

So the question is essentially: If our input is some sizes and the number of each, maybe : (50mm,200mm,50pcs), (100mm,200mm,50pcs) .... and the number of different LARGE sheets to order (maybe 8). What 8 sizes of LARGE sheets should we order (and how many of each?).

So far I have programmed a python script to calculate the waste for a specific set of LARGE sheets and for a data set of needed SMALL sheets, always using the best LARGE sheet for a specific SMALL sheet. But now I struggle to come up with a smart way to choose the large sheets. I am guessing the sizes can be discretized to steps of 25mm or 50mm to make it easier. I have only been thinking of randomly trying different sets of large sheets and choosing the best set found, but I guess some greedy heuristic could be developed?

Would greatly appreciate some guidance on how to move forward with this.

Improve this question
$\endgroup$
2
  • $\begingroup$ You wan to get the sizes of large sheet to consider, right? What abt surface area type calculation since you are dealing with rectangles, like what you need is $50\times200\times50+ 100\times200\times50$. For a large sheet, width should be $100$. Then for $n=8$ what's the length? $\endgroup$
    – Sutanu
    Jan 30 at 14:36
  • $\begingroup$ My idea is to first define a set of possible large rectangles to choose from. What I call Height is what you call Length I suppose. In my first attempts I will use rectangles ranging from $50mm \times 50mm$ up to $2000mm \times 1500mm$, with steps of $50mm$ in each direction. I am not interested in the thickness/depth of the sheets. Price will be per unit of surface area. $\endgroup$
    – guso141
    Jan 30 at 14:55

1 Answer 1

Reset to default
4
$\begingroup$

If I understand well your problem, a good way to tackle it is to model it as an integer linear program and solve it with a mixed-integer linear programming solver, such as CBC, SCIP or Highs for the free ones.

Data:

  • $n$ small sheets with demand $d_j$, $j = 1, \dots, n$
  • $m$ large sheets with cost $c_i$, $i = 1, \dots, m$
  • For all $j = 1, \dots, n$, for all $i = 1, \dots, m$, $a_{i, j} = 1$ iff small sheet $j$ fits in large sheet $i$, otherwise $0$
  • $U$: maximum number of types of large sheets to use

Variables:

  • $y_i \in \{ 0, \sum_j d_j \}$, $i = 1, \dots, m$. $y_i = k$ iff $k$ copies of large sheets $i$ are used
  • $z_i \in \{ 0, 1 \}$, $i = 1, \dots, m$. $z_i = 1$ iff large sheets $i$ are used
  • $x_{i, j} \in \{ 0, d_j \}$, $j = 1, \dots, n$: number of small sheets $j$ assigned to large sheets $i$

Objective: minimize the cost of the selected large sheets $$ \min \sum_{i = 1}^m c_i y_i $$

Constraints 1: all small sheet is assigned to a large sheet $$ \forall j = 1, \dots, n, \qquad \sum_{i, a_{i, j} = 1} x_{i, j} = d_j$$

Constraints 2: link between $y$ and $x$ $$ \forall i = 1, \dots, m, \qquad \sum_{j, a_{i, j} = 1} x_{i, j} = y_i $$

Constraints 3: link between $z$ and $x$ $$ \forall i = 1, \dots, m, \quad \forall j = 1, \dots, n, \quad a_{i, j} = 1, \qquad d_j z_i \ge x_{i, j} $$

Constraints 4: maximum number of types of large sheets to order: $$ \forall i = 1, \dots, m, \qquad \sum_i z_i \le U $$

Note that if you don't impose to use only one small sheet in a large sheet, then the problem is known as the Variable-sized Bin Packing Problem. It's the kind of problem that a library I wrote can solve.

Improve this answer
$\endgroup$
9
  • $\begingroup$ My thought was to have a cost for each pair of small-large depending on the waste. But your way of thinking is way more intuitive. Thank you for such a detailed answer! I will look in to how to use one of the solvers in Python and give it a try with this problem description. $\endgroup$
    – guso141
    Jan 30 at 12:48
  • $\begingroup$ The easiest way is to use them through pulp or pyomo. Here is a close example $\endgroup$
    – fontanf
    Jan 30 at 13:04
  • $\begingroup$ Okay thank you, will look into that example and try something similar. $\endgroup$
    – guso141
    Jan 30 at 13:16
  • $\begingroup$ Could you maybe just clarify constraint #3? you say that z_i greater or equal to x_(i,j). But z is max 1 and x can be from 0 to d_j. Am i missing something? $\endgroup$
    – guso141
    Jan 30 at 13:29
  • $\begingroup$ Don't want to spam this comment section but: Maybe what you mean with constraint #3 that IF $x_{i,j} >0$ then $z_i>0$? In that case I don't think this is right? $\endgroup$
    – guso141
    Jan 30 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy