5
$\begingroup$

A factory that manufactures clothing cuts multiple garments at once.

Sometimes a number of markers are used for a job. Each marker may have a single size or multiple sizes depending on what is needed. So the length of each is different.

To get the required number of garments a number of lays are laid out over each other to be cut at once. The number of lays can be different.

For example:


  • Marker1: 100 lays 10.5m each
  • Marker2: 80 lays 11m each
  • Marker3: 20 lays 5.2m each
  • Marker4: 20 lays 6.1m each
  • Marker5: 6 lays 2m each

So for Marker1 1050m of fabric is needed, for Marker2 another 880m of fabric is needed, and so on.

Some markers can be combined, such as Marker3 and Marker4, where the number of lays is the same, to form a marker of 11.3m.

Given the markers above, the total metres of fabric required would be 2168m.

However the fabric does not come in one big roll. And this is what causes the problem. Perhaps 11 rolls of 100m will be supplied. This causes wastage of fabric, one roll can be laid 9 times on Marker1, leaving 5.5m which can be used on the other markers.

The puzzle then is how do you find the best way of using the following rolls of fabric on the markers above.


  • 150m x 2
  • 120m x 4
  • 100m x 12
  • 50m x 5
  • 20m x 3


    (Disclaimer: I work in a factory where they manufacture clothing. And i wonder if there was some strategy to optimize cloth usage in general. Sorry if this question is not right for this site.)

  • $\endgroup$
    • 10
      $\begingroup$ Welcome to puzzling! You've discovered a famous (and difficult) problem known as the Cutting stock problem. $\endgroup$ – frodoskywalker Feb 13 '16 at 11:32
    • 1
      $\begingroup$ This is known to be a difficult problem even for computers to solve. $\endgroup$ – GentlePurpleRain Feb 14 '16 at 12:54
    4
    $\begingroup$

    One of the possible ways to solve such problem is to use integer programming. The idea is to transform your problem to a set of linear constraints on integer variables.

    For example, saying that a roll has a length of of 150m can be translated into a constraint that you cannot cut more than 150m out of the roll. So if the number of Marker1 you cut on this roll is $m_1$, the number of Marker2 you cut on this roll is $m_2$, and so on, the constraint will be

    $$10.5\times m_1 + 11\times m_2 + 5.2\times m_3 + 6.1\times m_4 + 2\times m_5 + leftover = 150$$

    Here, I added a variable $leftover$ to change the constraint to an equality. This way, it's easy to know how much you have left of each roll. Since we want to manipulate only integers, you can multiply the equation by 10.

    Now, we also need the constraints about the number of markers we want to cut. This follow the same principle: the sum of Marker1 we get from each roll should be equal to 100.

    As a final constraint, all the variables we use here should be positive integers.

    Once we have all the necessary constraints, we need a function to optimize the system. This is the metric that will tell you the quality of an answer. Since the amount of leftover will be always the same if you cut the same number of markers, we want to know the amount of leftover that cannot be reused to cut additional markers. To do this, we will change slightly the constraints about the number of markers to cut: instead of cutting exactly the required number of markers, we will cut at least the required number of markers. Then, the objective will be to reduce the amount of leftover.

    Now, for the application, the best way is still to use a computer. There are a lot of libraries to solve integer programming problems since it's something quite common. For this exemple, I used Google Optimization Tools or-tools mostly because I wanted to try it. To be honest, I never used any tool for this before, so I cannot give recommendation about which tool is the best. So I wrote this small python script:

    """Linear optimization example"""
    
    from __future__ import print_function
    from ortools.linear_solver import pywraplp
    
    def main():
      # Instantiate a Glop solver, naming it SolveSimpleSystem.
      solver = pywraplp.Solver('SolveSimpleSystem',
                               pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
    
      markers = [
        (100, 105),
        (80, 110),
        (20, 52),
        (20, 61),
        (6, 20)
      ]
    
      rolls = [
        (2, 1500),
        (4, 1200),
        (12, 1000),
        (5, 500),
        (3, 200)
      ]
    
      variables = []
      left_variables = []
    
      # Constraints for the size of the rolls
      for roll_num, roll_size in rolls:
        for roll_index in range(0, roll_num):
          roll_variables = []
          constraint = solver.Constraint(roll_size, roll_size)
          for _, marker_size in markers:
            variable = solver.IntVar(
              0, solver.infinity(),
              'r%d_%d m%d' % (roll_size, roll_index, marker_size))
            constraint.SetCoefficient(variable, marker_size)
            roll_variables.append(variable)
          left = solver.IntVar(0, solver.infinity(),
                               'r%d_%d left' % (roll_size, roll_index))
          constraint.SetCoefficient(left, 1)
          left_variables.append(left)
          variables.append(roll_variables)
    
      # Constraints for the number of markers
      for marker_index, (marker_num, _) in enumerate(markers):
        constraint = solver.Constraint(marker_num, solver.infinity())
        for roll_variables in variables:
          constraint.SetCoefficient(roll_variables[marker_index], 1)
    
      # Objective to maximize the size of leftover
      objective = solver.Objective()
      for left_variable in left_variables:
        objective.SetCoefficient(left_variable, 1)
      objective.SetMinimization()
    
      # Solve the system
      solver.set_time_limit(60*1000) # 1 min
      status = solver.Solve()
      status_dict = {
        pywraplp.Solver.OPTIMAL: 'Optimal',
        pywraplp.Solver.FEASIBLE: 'Feasible',
        pywraplp.Solver.INFEASIBLE: 'Infeasible',
        pywraplp.Solver.UNBOUNDED: 'Unbounded',
        pywraplp.Solver.ABNORMAL: 'Abnormal',
        pywraplp.Solver.NOT_SOLVED: 'Not solved'
      }
      print('Status =', status_dict[status])
      assert status in (pywraplp.Solver.OPTIMAL, pywraplp.Solver.FEASIBLE)
      assert solver.VerifySolution(1e-7, True)
      print('Number of variables =', solver.NumVariables())
      print('Number of constraints =', solver.NumConstraints())
    
      # The optimal solution
      opt_solution = sum(
              left_variable.solution_value() for left_variable in left_variables)
      print('Found solution =', opt_solution)
    
      # Number of additionnal markers
      for marker_index, (marker_target, marker_size) in enumerate(markers):
        num_marker = sum(roll_variables[marker_index].solution_value()
                         for roll_variables in variables)
        print('Marker %d has %d more.' % (marker_size, num_marker - marker_target))
    
      # Detail of cut
      for roll_variables in variables:
        for variable in roll_variables:
          if variable.solution_value() > 0:
            print('%s = %d' % (variable.name(), variable.solution_value()))
    
    
    if __name__ == '__main__':
      main()
    

    The result which has not been proven to be optimal (but might as well be) is the following:

    • 14.8m of leftover
    • 1 more Marker3
    • 51 more Marker5

    The full detail of the cut follows. r1500_0 m105 = 7 means that we should cut 7 Marker of size 10.5m from the first roll of size 150m.

    r1500_0 m105 = 7
    r1500_0 m110 = 6
    r1500_0 m61 = 1
    r1500_0 m20 = 2
    r1500_1 m105 = 11
    r1500_1 m110 = 2
    r1500_1 m61 = 2
    r1200_0 m105 = 5
    r1200_0 m110 = 5
    r1200_0 m61 = 2
    r1200_1 m105 = 1
    r1200_1 m110 = 7
    r1200_1 m61 = 5
    r1200_1 m20 = 1
    r1200_2 m105 = 6
    r1200_2 m110 = 3
    r1200_2 m20 = 12
    r1200_3 m105 = 7
    r1200_3 m52 = 3
    r1200_3 m61 = 3
    r1200_3 m20 = 6
    r1000_0 m105 = 8
    r1000_0 m110 = 1
    r1000_0 m20 = 2
    r1000_1 m110 = 7
    r1000_1 m52 = 4
    r1000_1 m20 = 1
    r1000_2 m110 = 7
    r1000_2 m52 = 4
    r1000_2 m20 = 1
    r1000_3 m105 = 7
    r1000_3 m52 = 1
    r1000_3 m61 = 3
    r1000_3 m20 = 1
    r1000_4 m105 = 8
    r1000_4 m52 = 3
    r1000_5 m105 = 8
    r1000_5 m110 = 1
    r1000_5 m20 = 2
    r1000_6 m110 = 9
    r1000_7 m105 = 9
    r1000_7 m52 = 1
    r1000_8 m105 = 9
    r1000_8 m20 = 2
    r1000_9 m110 = 7
    r1000_9 m52 = 2
    r1000_9 m61 = 1
    r1000_9 m20 = 3
    r1000_10 m105 = 2
    r1000_10 m110 = 7
    r1000_10 m20 = 1
    r1000_11 m110 = 9
    r500_0 m110 = 3
    r500_0 m52 = 2
    r500_0 m61 = 1
    r500_1 m110 = 4
    r500_1 m20 = 3
    r500_2 m105 = 4
    r500_2 m20 = 4
    r500_3 m105 = 2
    r500_3 m110 = 2
    r500_3 m61 = 1
    r500_4 m105 = 4
    r500_4 m61 = 1
    r200_0 m105 = 1
    r200_0 m52 = 1
    r200_0 m20 = 2
    r200_1 m105 = 1
    r200_1 m20 = 4
    r200_2 m20 = 10
    
    $\endgroup$

    Your Answer

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

    Not the answer you're looking for? Browse other questions tagged or ask your own question.