Recall the following NP$-$hard job scheduling problem $($aka the "load balancing" problem$).$ There are $m$ machines, all identical. There are $n$ jobs, and job $j$ has processing time $($or "size"$)t_j.$ Each job must be assigned to exactly one machine. The load of a machine is the sum of the sizes of the jobs that get assigned to it$.$ The makespan of an assignment of jobs is the maximum load over all the machines; this is the quantity that we want to minimize.

$($a$)(8$ points$)$ Suppose we have an instance where there are $m=2$ machines and $n=4$ jobs, with job sizes $8,9,5,$ and $7.$

i$.$ If we assign the first two jobs to the first machine and the last two jobs to the second machine, what will the load be on each machine?

ii$.$ What will the makespan be$?$

iii. How can the assignment for this input be modified to yield the optimal makespan?