Question

In Exercises 42-46 we will study the problem of load balancing. The input to the problem is a collection of p processors and n jobs, $t_j$is the time required to run job j, jobs run without interruption on a single machine until finished, and a processor can run only one job at a time. The load $L_k$of processor k is the sum over all jobs assigned to processor k of the times required to run these jobs. The make span is the maximum load over all the p processors. The load balancing problem asks for an assignment of jobs to processors to minimize the make span.

Run the algorithm from Exercise 44 on the input given in Exercise 42 .

Short answer

$L_1=10,L_2=5,L_3=12$

Make span 12 .

Step-by-step solution

Step 1

We call the algorithm “minimal make span”, while the input to the algorithm are the non-negative numbers $t_1,t_2,...,t_n$and positive integers n and p.

Procedure-minimal make span

$(t_1,t_2,...,t_n:non-negative\mathrm{realnumbers};\mathrm{n},\mathrm{p}:\mathrm{positiveinteger})$. Initially, we set the load of each processors ${\mathrm{L}}_{\mathrm{k}}$equal to . We move through the jobs in the order that they were given $(job1,job2,...,jobn)$. We add the time required to run job j to the processors with the smallest load role="math" localid="1668673672486" ${\mathrm{L}}_{\mathrm{k}}$and j to the set of jobs $J_k$to processor k. After we ran through all jobs, we return the assignments of the jobs along with the make span M.

for $\mathrm{i}:=1\mathrm{to}\mathrm{p}$

$$\begin{gathered} L_i:=0 \\ {J}_i:=\varphi \end{gathered}$$

for $j:=1ton$

$k:=1$

for $\mathrm{i}:=2\mathrm{to}\mathrm{p}$

if $L_i<L_k$then

$$\begin{gathered} \mathrm{k}:=\mathrm{i} \\ {\mathrm{L}}_{\mathrm{i}}:={\mathrm{L}}_{\mathrm{k}}+{\mathrm{t}}_{\mathrm{j}} \\ {\mathrm{J}}_{\mathrm{k}}:={\mathrm{J}}_{\mathrm{k}}\cup \left\{\mathrm{j}\right\} \\ \mathrm{M}:=0\mathrm{for}\mathrm{i}:=1\mathrm{to}\mathrm{p} \\ \mathrm{M}=\mathrm{M}+{\mathrm{L}}_{\mathrm{i}} \end{gathered}$$

return $J_1,J_2,...,J_p,M$.

Step 2

SOLUTION

Given:

Collection of p processors and n jobs

$t_j=$time required to run job j

Load $L_k$of processors ksum of times required to run all jobs assigned to processor k.

Make span maximum load over all p processors.

We are interested in minimizing the make span.

$\begin{array}{r}{t}_1=3\\ t_2=5\\ t_3=4\\ t_4=7\\ t_5=8\\ p=3\end{array}$

Let us first assign job 1 to processor 1 .

$L_1=t_1=3$

Let us next assign job 2 to processor 2 .

$L_2=t_2=5$

Let us next assign job 3 to processor 3 .

$L_3=t_3=4$

Next, we assign job 4 to the processor with the lowest load, which is processor 1.

$L_1=3+t_4=3+7=10$

Next, we assign job 5 to the processor with the lowest load, which is processor 3.

$L_3=4+t_5=4+8=12$

The loads are then $L_1=10,L_2=5,L_3=12$. The maximum load is 12 and thus the make span is then 12 as well.