Wash clothes as quickly as possible

Question

It's laundry day, and you have lots of clothes that need to be washed. Wanting to have as much time left over for code golf as possible, you hope to optimize how quickly you wash and dry them all.

You have three types of appliances:

• Washing machines: Take dirty clothes and turn them into wet clothes
• Dryers: Take wet clothes and turn them into dry clothes
• Dishwashers: Take dirty and/or wet clothes and turn them into dry clothes

You'll be given a list of appliances, including a capacity (the number of items of clothing, as a nonnegative integer, that can be washed in it at once) and a run time (the time in minutes, as a nonnegative integer, that it takes to finish its job). Additionally, you'll be given a nonnegative integer describing how many items of clothing you have.

Task

Given a list of appliances and a number of items of clothing, you'll return the minimum number of minutes it would take to wash and dry them all. You don't need to return the actual set of operations it would take to do so.

At any time, you can perform any of the following operations:

• Take up to \$n\$ dirty clothes, and put them in an available washing machine (where \$n\$ is less than or equal to its capacity)
• Take up to \$n\$ wet clothes, and put them in an available dryer (where \$n\$ is less than or equal to its capacity)
• Take up to \$n\$ dirty or wet clothes, or some combination, and put them in an available dishwasher (where \$n\$ is less than or equal to its capacity)
• If it has been \$x\$ minutes since a washing machine was loaded, the clothes in it can be removed. They are now wet, and the washing machine is now available again.
• If it has been \$x\$ minutes since a dryer or dishwasher was loaded, the clothes in it can be removed. They are now dry, and the appliance is now available again. (Don't worry, you clean the lint trap like a responsible code golfer)

Clothes are "fungible", so you can keep track of all of the clothes not in a running appliance using three nonnegative integers (one for dirty, one for wet, and one for dry).

Example

Let's say you have 120 articles of clothing, and the following appliances:

• A washing machine, with a capacity of 10, that takes 40 minutes
• A washing machine, with a capacity of 40, that takes 180 minutes
• A dryer, with a capacity of 40, that takes 120 minutes
• Two dishwashers, each with a capacity of 15, which take 100 minutes

An example solution would be (red/dark red indicating dirty clothes in, blue indicating wet clothes in, purple indicating a mix, units of 20 minutes):

This takes a total of 300 minutes. The second pair of dishwasher cycles contain a total of 10 dirty clothes, and 20 wet clothes, and the final two dishwasher cycles aren't completely full. To optimize this any further we'd need to remove two dishwasher cycles and start the dryer earlier (or not at all), which would not result in all clothes being washed.

Test cases

Formatted as num_clothing, washing_machines, dryers, dishwashers, with appliances formatted as [capacity, mins_to_finish]:

1, [], [], [[1, 10]]                            10
10, [], [], [[1, 10]]                           100
1, [[2, 2]], [[1, 4]], [[1, 10]]                6
2, [[2, 2]], [[1, 4]], [[1, 10]]                10
2, [[2, 2]], [[2, 4]], [[1, 10]]                6
16, [[2, 2]], [[1, 4]], [[1, 10]]               50
16, [[2, 2]], [[1, 4]], [[1, 10], [10, 20]]     20
10, [[1, 10]], [], [[3, 10]]                    40
4, [[1, 1]], [[1, 2], [2, 4]], []               7
4, [[1, 1], [1, 2]], [[1, 2], [2, 4]], []       6
6, [[1, 1], [1, 2]], [[1, 2], [2, 4]], [[1, 4]] 4

I'm not entirely sure these are correct; my reference implementation is buggy.

Other

This is code-golf, so shortest answer in bytes (per language) wins.

Answer 1

Python3, 1091 bytes:

import itertools as I
g=lambda x:[[a,[0,b]]for a,b in x]
E=enumerate
def p(m,o):
 k=0
 for i,a in E(m):
  if a[1][1]==1:k+=a[1][0];m[i][1][1]=o[i][1];m[i][1][0]=0
  elif a[1][0]:m[i][1][1]-=1
 return k
C=lambda x:eval(str(x))
def P(d):
 a,b=zip(*[(a[0],range(0,[0,a[0]][a[1][0]==0]+1))for i,a in E(d)])
 return[[a,i]for i in I.product(*b)]
def U(b,d):
 for x,y in P(d):
  if(s:=sum(y))<=b:
   D=C(d)
   for i,(j,k)in E(zip(x,y)):D[i][1][0]+=k
   yield b-s,D
def K(N,r,Q,s=[]):
 if[]==Q:yield(N,r,s);return
 if Q[0][1]:
  if Q[0][0]in[0,2]:
   for a,b in U([N,0,r][Q[0][0]],Q[0][1]):yield from K([a,0,N][Q[0][0]],[r,0,a][Q[0][0]],Q[1:],s+[b])
  else:
   for x in[{0:N,1:r},{1:r,0:N}]:
    b=Q[0][1]
    for i in[*x]:
     for a,b in U(x[i],b):x[i]=a;yield from K(x[0],x[1],Q[1:],s+[b])
 else:yield from K(N,r,Q[1:],s+[Q[0][1]])
def f(n,w,d,s):
 q=[(n,*map(g,[w,d,s]),0,0,0)];O=[]
 while q:
  N,*U,r,c,t=q.pop(0)
  W,D,S=map(C,U)
  if c==n:return t-1
  r+=p(W,w);c+=p(D,d)+p(S,s)
  for _n,_r,[_w,_s,_d]in K(N,r,[(0,W),(1,S),(2,D)]):
   if(M:=(_n,_w,_d,_s,_r,c,t+1)) not in O:
    q+=[M];O+=[M]

Try it online!

Very brute force solution and as such, it times out on the larger test cases. I will come back to those later.