Similar to cutting stock problem but not quite

Question

I have read about cutting stock problem, but this is a bit different.

We have orders in different variants, and a maximum sized machine to produce it.

Variants would be, X,S,XL,L and ordered quantities, 100,40,40,80

X > 100

S > 40

XL > 40

L > 80

Say, machine width is 6

This means, we can put 6 different variants together and produce it.

We can put 2 X,1 S,1 XL,2 L , this means if we produce it 50 times , output is :

X > 100 (0 waste)

S > 50 (10 waste)

XL > 50 (10 waste)

L > 100 (20 waste)

Total of 40 waste in 300 produced.

---

Another aproach to reduce waste would be creating 2 different variation. We can put 4 X,2 S and produce it 25 times, with 10 waste and make another setup and put 2 XL,4 L and produce it 20 times with no waste. With total 10 waste we handled this production in 2 setups.

Since setup has a price, we would prefer first setup, or depending on quantities, we may choose the second one.

I have read about cutting stock and it looks similar to this one, but ability to divide quantities between different setups, this has more potential to optimize and therefore more complex.

I have thought about it, and couldn't come with a reliable solution, If this problem has any place in literature, could you at least tell me the keywords so I can search for it?

thanks.

Note : I know basic mathematics and good python programming language.

Answer 1

One idea would be to formulate this as an mathematical optimization problem. We want to simultaneously solve for (1) the patterns used in each run, (2) the length of each run and (3) the number of runs (which results in setup cost). An example can look like:

$$\begin{align} \min \>&TotalCost\\ &TotalCost=WasteCost+SetupCost\\ &SetupCost = CostSetup \cdot \sum_r Run_r\\ &WasteCost = \sum_v CostWaste_v \cdot Waste_v\\ &\sum_r RunLen_r \cdot Pattern_{v,r} = Demand_v + Waste_v\\ &RunLen_r \le MaxRunLen \cdot Run_r\\ &\sum_v Pattern_{v,r} \le Capacity\cdot Run_r\\ &Run_r \in \{0,1\} &&\text{do a run}\\ &RunLen_r \in \{0,1,...\}&&\text{length of a run}\\ &Pattern_{v,r} \in \{0,1,...\}&&\text{variant pattern used in run}\\ &Waste_v \in \{0,1,...\}&&\text{waste of each variant} \end{align}$$

This is a non-convex, non-linear (quadratic) mixed-integer programming model which can be solved using standard available software. The non-linearity results from multiplying the pattern by the runlength.

My inputs are as follows:

----     97 PARAMETER costwaste  input data

X  1.000,    S  2.000,    XL 3.000,    L  4.000


----     97 PARAMETER costsetup            =      100.000  input data

----     97 PARAMETER demand  

X  100,    S   40,    XL  40,    L   80

This gives the optimal solution shown below. Note that the optimal solutions are not unique, so a different solver may give a different solution with the same optimal total cost.

----     97 VARIABLE runlen.L  

run1 20,    run2 40


----     97 VARIABLE pattern.L  

          run1        run2

X            1           2
S                        1
XL                       1
L            4


----     97 VARIABLE waste.L  

                      ( ALL          0. )


----     97 VARIABLE wastecost.L           =        0.000  
            VARIABLE setupcost.L           =      200.000  
            VARIABLE cost.L                =      200.000  

If we increase the setup cost the model will automatically reduce the number of runs. For large instances one would probably reformulate this a bit (e.g. linearizing things, or may be trying a constraint programming solver).

Note that the problem description does not talk about minimizing the total run length. Probably a cost for this should be added to the total cost, so we prefer shorter runs above longer ones.