In the multiprocessor scheduling problem the input consists of n jobs, J$1,...,$ Jn$.$ Job

Ji has a corresponding runtime pi $($a rational number$).$ The jobs are to be distributed

between m identical machines. The finish$-$time is the maximum, over machines M$,$ of

the total runtime of jobs assigned to M$.$ The goal is to minimise the finish$-$time. In the

following greedy approximation algorithm we consider the n jobs one$-$by$-$one:

When a job is considered, pick the currently least$-$loaded machine, and assign the

job to that machine.

What is the $$relative performance of this algorithm$$ and why? Construct two instances

of the problem on which the algorithm will have the worst performance and the best

performance