= Makespan
{title2=$C_{\max}=\max_jC_j$}
{wiki}
The time at which all work in a <scheduling> instance has finished, equivalently the largest completion time measured from a common start. For divisible job sizes $t_i\geq0$ and positive machine speeds $s_j$, when each machine's completion time is its total assigned size divided by its speed, the minimum <makespan> is $\sum_i t_i/\sum_j s_j$. The lower bound follows from total processing capacity; assigning the fraction $s_j/\sum_hs_h$ of each job to machine $j$ attains it.
Back to article page
