How to iterate through all combinations within a FOR loop?

Hi,

I want to set up a loop where items in one array is subtracted from from elements in another array while minimising the leftovers.

A simplified example

Six rolls of three different lengths (10, 12, 15) are in one array roll_list. The first row is the lengths and the second row is the corresponding quantities.

Ten different parts of lengths (7, 6, 6, 5, 4, 7, 5, 4, 6, 5) need to be made from the six available rolls.

The parts need to be produced in the order as shown in the array part_list, but the rolls may be used in any order.

How can I set up a loop to iterate all the possible combination and find out the least amount of waste? I have managed to do one possible iteration sequential to the roll_list array, but I am struggling to figure out how to attempt all possible combinations.

Appreciate any suggestions.

----EDIT ----

• One part cannot be made using more than one roll. So Part A cannot include material from Roll X and Y.
• Once a roll enters production, it needs to be used straight away. It cannot be removed from production and brought back to be reused.

roll_list = [10 12 15; 3 1 2];
roll_tot=sum(roll_list(1,:).*roll_list(2,:));
part_list = [7 6 6 5 4 7 5 4 6 5];
parts_total_length = sum(part_list);

b=1;
c=1;
waste=0;

for a = 1:length(part_list)
    if roll_list(1,b) >= part_list(a) && roll_list(2,c) >= 1
        roll_list(1,b) = roll_list(1,b) - part_list(a);
    else
        waste = waste + roll_list(1,b);
        roll_list(2,c) = roll_list(2,c)-1;
        roll_list(1,:) = [10 12 15];
        if roll_list(2,c) == 0
            b=b+1;
            c=c+1;
        end
        roll_list(1,b) = roll_list(1,b) - part_list(a);
    end
end

[Matt J]

Six rolls of three different lengths (10, 12, 15) are in one array roll_list.

Don't you mean there are 3 rolls? If there are 6 rolls, why are there only 3 lengths and quantities listed?

[Abhi Ramesh]

There are three rolls of length 10(units), one roll of length 12(units), and two rolls of length 15(units). Total of six rolls, of three unique lengths.

[Matt J]

The parts need to be produced in the order as shown in the array part_list

I don't see how the order matters. The solution is a 10x6 table listing how much of each roll is allocated to each part correct? For any solution, you should be able to reorder the rows of the table any way you wish.

[Catalytic]

How can I set up a loop to iterate all the possible combination and find out the least amount of waste?

The amount of waste will always be the same. It has to be

waste = roll_tot - sum(part_list)

[Abhi Ramesh]

@Matt J

The program is for an actual (very large scale) production line with some constraints.

Once a roll is opened, we have to keep using it till it can no longer produce the next part.

The parts need to be made in the exact order as shown in the part_list array

The actual problem involves tens of roll lengths, hundreds of quantities, and thousands of parts. I am setting up a skeleton framework with this example so that it can be elaborated for the real problem.

[Matt J]

But what about @Catalytic's question? Why would the waste ever vary? Is the remainder of a previously used roll unusable?

[Abhi Ramesh]

@Catalytic

That is true for this particular problem, but not the same situation when the quantities and sizes change.

If the rolls were between 200 and 300 in length, and the part sizes were between 50 and 100 in length, there are some options that reduce waste more than others. It has been done manually in excel in the past but the system can be improved by optimising it and I am not sure how best to do it. We also cannot use a roll, for the first two parts, remove the used roll and then use it for the 5th part later. So the order in how the rolls are used need to be included.

[Abhi Ramesh]

@Matt J

Correct. Once the roll is removed from production and another roll is introduced, we cannot go back to the old roll.

[Stephen23]

"... but the system can be improved by optimising it and I am not sure how best to do it."

https://www.mathworks.com/help/optim/ug/mixed-integer-linear-programming-basics-problem-based.html

[Abhi Ramesh]

@Stephen

This looks like a promising approach. Thanks for sharing! I shall explore it further.

[Matt J]

Correct. Once the roll is removed from production and another roll is introduced, we cannot go back to the old roll.

That's not what I asked, though. Suppose one part is made with 2.5 rolls, in other words one of the 3 rolls used to make the part is only partially expended. When you move onto the next part, can you continue to use what is left over from the partially-expended roll?

[Abhi Ramesh]

@Matt J

Suppose one part is made with 2.5 rolls, in other words one of the 3 rolls used to make the part is only partially expended. When you move onto the next part, can you continue to use what is left over from the partially-expended roll?

• One part cannot be made from more than one roll. So Part A cannot include material from Roll X and Y.
• Once a roll enters production, it needs to be used straight away. It cannot be removed from production and brought back to be reused.

I will edit the question to include the conditions. Apologies for the lack of clarity.

[Matt J]

So each part is to be made from exactly one roll? If so how can the 6 rolls in your example ever produce more than a total of 6 parts?

I suggest you demonstrate one possible solution to your 10 part example, not necessarily the optimal solution with the least waste.

[Abhi Ramesh]

One roll can produce more than one part as long as the parts are consecutive.

I have tried to show four options. Waste is only generated once a coil is used. If it is an unused coil, then it is not waste.

[Matt J]

The actual problem involves tens of roll lengths, hundreds of quantities, and thousands of parts.

I don't think you're going to be able to handle thousands of parts. The number of combinations grows exponentially with the number of parts, something like,

N=size(roll_list,2);
M=numel(part_list);

numberofCombinations=N.^M

So, if M is in the 1000s, I don't think there's any hope. As a compromise, you can decompose the parts list into sub-lists and optimize over each one sequentially.

[Abhi Ramesh]

The number of combinations grows exponentially with the number of parts

Yes, I just gave it a go with a list of just a few hundred parts and I am already having trouble. But this is a good start and an improvement from using intuition and simple spreadsheets and macros. It was not as simple a problem as it initially seemed.

Thank you for the help!

Answer 1

[Matt J]

Here's a dynamic programming approach:

roll_list = [10 12 15; 3 1 2];

part_list = [7 6 6 5 4 7 5 4 6 5];

roll_list=sortrows(roll_list.',1).'; %ensure sorted

[minwaste,schedule]=optimizeIt(roll_list(1,:),roll_list(2,:), part_list)

minwaste = 7

schedule = 1×5

10 10 15 12 15

function [minwaste,schedule]=optimizeIt(lengths,quantities, part_list)



  roll_tot=sum(lengths.*quantities);
  parts_total_length = sum(part_list);

   if roll_tot<parts_total_length  %problem is infeasible, bail out
     minwaste=Inf; schedule=[]; return 
  end


  n=find(lengths>=part_list(1) ,1 );
  
  if isempty(n) %problem is infeasible, bail out
     minwaste=Inf; schedule=[]; return 
  end


  M=numel(part_list);
  N=numel(lengths);

 
  C=cumsum(part_list);
 


  Wastes=inf(N,1);
  Schedules=cell(N,1);

  


  for i=n:N

      L=lengths(i); %pick a length

      j=find(L>=C,1,'last');

      if j==M % L covers all remaining parts
              % No need to consider longer rolls

        Wastes(i)=L-C(end);
        break

      else

        plist=part_list(j+1:end); 

        [llist,qlist]=deal(lengths,quantities);

        if quantities(i)==1  %shrink lists
          llist(i)=[];
          qlist(i)=[];
        else
          qlist(i)=quantities(i)-1;
        end

          if isempty(qlist) && ~isempty(plist)
              continue
          end

        Wastes(i)= (L-C(j));

        [cost_to_go,Schedules{i}]=optimizeIt(llist,qlist, plist); %RECURSE!!!

        Wastes(i)=Wastes(i)+cost_to_go;

      end



  end

 
  [minwaste,imin]=min(Wastes);

  schedule=[lengths(imin),Schedules{imin}];

end

[Abhi Ramesh]

Thank you! I would have never been able to figure out something so elegant.