The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.

• Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201. doi:10.1016/0167-6377(90)90018-Z

For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.

Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.

The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.

Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.

Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.

Edit: This report by Coffman and Whitt seems to consider the precise question you ask. They say that multiprocessor scheduling is the generic name for this class of problems, and state: "Because of the difficulty of exact analysis, the results take the form of limits". There is also a published version from 1996 which explicitly focuses on Markov chain approaches to study the asymptotic behaviour.

• E. G. Coffman, Jr. and Ward Whitt, Recent Asymptotic Results in the Probabilistic Analysis of Schedule Makespans. Unpublished, 1993.
• E. G. Coffman, Jr. and Ward Whitt, Stochastic limit laws for schedule makespans. Communications in Statistics. Stochastic Models 12, 215–243, 1996. doi:10.1080/15326349608807382

The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.

• Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201. doi:10.1016/0167-6377(90)90018-Z

For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.

Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.

The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.

Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.

Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.

Edit: This report by Coffman and Whitt seems to consider the precise question you ask. They say that multiprocessor scheduling is the generic name for this class of problems, and state: "Because of the difficulty of exact analysis, the results take the form of limits". There is also a published version from 1996 which explicitly focuses on Markov chain approaches to study the asymptotic behaviour.

• E. G. Coffman, Jr. and Ward Whitt, Recent Asymptotic Results in the Probabilistic Analysis of Schedule Makespans. Unpublished, 1993.
• E. G. Coffman, Jr. and Ward Whitt, Stochastic limit laws for schedule makespans. Communications in Statistics. Stochastic Models 12, 215–243, 1996. doi:10.1080/15326349608807382 (preprint)

The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.

• Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201. doi:10.1016/0167-6377(90)90018-Z

For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.

Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.

The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.

Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.

Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.

The case where $n > m$ is "easy": if $F$ is the distribution function of each of the $m$ iid random variables, then the distribution function of the maximum is $F^m$. Of course, $F^m$ may be difficult to compute, so even bounding the expectation of the makespan can be tricky.

• Peter J. Downey, Distribution-free bounds on the expectation of the maximum with scheduling applications, Operations Research Letters 9, 189–201. doi:10.1016/0167-6377(90)90018-Z

For the general case where $n \le m$ it seems difficult to obtain closed-form solutions.

Using Kendall's notation for queueing systems, this is a D/GI/n system, or in the extended notation D/GI/n/m/m/FIFO. Nothing is lost by requiring the tasks to form a queue. However, I do not know whether systems with such one-shot arrival distributions have been studied in the queueing theory literature.

The minimum of $n$ exponentially distributed random variables is also exponentially distributed. This does suggest a procedure to efficiently simulate the system, from which one can generate a numerical approximation to the distribution, but I don't immediately see how to obtain a closed form solution.

Suppose you choose a random partition of the tasks into $n$ blocks. This may fail to correspond to a valid schedule, since the block with the largest sum may still exceed the smallest block sum, even with a task removed. This suggests the following correction procedure. For the block with the largest sum, remove one of the tasks. If the sum without this task is no larger than the smallest block sum, then put the task back and stop. Otherwise put the task into the block with the smallest sum, and iterate. This procedure yields a valid schedule.

Now consider the maximum block sum. In the uncorrected case, this will be an upper bound for the makespan. As far as I can tell, it then seems feasible to find the distribution of the correction that is applied, as well as the distribution of the maximum block sum over all random partitions (though probably not in closed form). If $n \lt \lt m$ this might provide a reasonable way to go, perhaps in combination with bounding techniques for the distribution of the maximum.

Edit: This report by Coffman and Whitt seems to consider the precise question you ask. They say that multiprocessor scheduling is the generic name for this class of problems, and state: "Because of the difficulty of exact analysis, the results take the form of limits". There is also a published version from 1996 which explicitly focuses on Markov chain approaches to study the asymptotic behaviour.

• E. G. Coffman, Jr. and Ward Whitt, Recent Asymptotic Results in the Probabilistic Analysis of Schedule Makespans. Unpublished, 1993.
• E. G. Coffman, Jr. and Ward Whitt, Stochastic limit laws for schedule makespans. Communications in Statistics. Stochastic Models 12, 215–243, 1996. doi:10.1080/15326349608807382