- #1

mentil

- 6

- 0

## Homework Statement

You want to process x units of a product (at y processing plants), minimizing the total time spent processing all the units. Each place y_i has a queue of q_i units ahead of you and a processing rate of r_i units/minute. If you can simultaneously process units at the same time at different places, what is the minimum amount of time you can spend?

## Homework Equations

## The Attempt at a Solution

I solved the problem by formulating it like the following:

min(max((x>0)*(x+q)/m))

where x,q,m are vectors representing how quantities sent/queues/rates at each processing plant.

and with constraints

sum(x)=total units

x_i>=0

The (x>0) is just an indicator variable saying that if we go to processing plant y_i, then we will have to add in the time we have to wait in the queue.

I get what I think is the correct solution by using an evolutionary search algorithm, but I was wondering if anyone has any suggestions on how I might restructure the problem to be a linear programming problem or what algorithm is the right one to use (otherwise it seems like an np hard problem?). Does anyone know any similar types of problems or methods?

I hope this is the right area to post this...thanks!