Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 3 / c

Assume job sizes $t_i\ge 0$ and machine speeds $s_j>0$, with at least one machine. Let $y_{ij}\ge 0$ be the amount of job $T_i$ assigned to machine $M_j$, and let $T\ge 0$ be the proposed makespan. Use the linear programThe first family of constraints assigns every job completely. The second bounds each machine's completion time by $T$, since $L_j/s_j\le T$ is equivalent to $L_j\le s_{j}T$. It is a linear inequality because $s_j$ is an input constant. There is no integrality restriction: jobs are divisible as specified in this scheduling model.

To verify the formulation, any actual allocation defines the variables above, with $T$ equal to its largest completion time, and satisfies every constraint. Conversely, from a feasible solution, assign amount $y_{ij}$ to machine $M_j$ and process its assigned pieces consecutively. Its total time is at most $T$, so the linear program realizes the claimed makespan.

There is also a useful exact check. Put $W={\sum }_i{t}_i$ and $S={\sum }_j{s}_j$. Summing machine constraints gives $W\le ST$, so $T\ge W/S$. Assigningmakes every machine's completion time $W/S$, provingThis relies on the paper's divisible-work model, in which machine completion times depend only on total assigned size. If $W=0$, the optimum is $0$.