The problem is: suppose we have $p$ processes labeled $1, \ldots, p$, with runtimes $(t_1, \ldots, t_p) \in \mathbb{R}_{++}^p$. In what order should the processes be set up to minimize overall runtime if $n < p$ processes can run concurrently?
My first thought was that decreasing order is optimal, but there are simple counterexamples. After thinking about it, I think this problem is isomorphic to this problem: given a collection of $p$ straws of various length, how can you arrange the straws in $n < p$ lines to minimize the length of the largest line?
In that sense, if the lines all have the same length, you have a perfect ordering (where the process queues have 100% usage time). I've tried to google it, but I can't seem to find anything. So:
1) Is this a well-known problem? I would think it must be.
2) Does it have a known solution?
3) Is it underdetermined as written?
Any help would be appreciated. Thanks
This is an instance of the job shop scheduling problem. Specifically, with atomic jobs.