Answer to Question #187918 in Algorithms for tejaswini

Question

Consider the following preemptive variant of the Load Balancing problem: There are m identical machines, and n jobs with processing times t1, t2,...., tn respectively. Each machine can process at most one job at a time. Each job can run on more than one machines but must run on at most one machine at any time. Let T = max { max _(1<=j<=n) t_j , 1/ m $summation$ _(1<=j<=n) t_j }

Answer 1

Given:

Consider the following preemptive variant of the Load Balancing problem: There are m identical machines, and n jobs with processing times $t_1,t_2,...,t_n$ respectively. Each machine can process at most one job at a time. Each job can run on more than one machines but must run on at most one machine at any time. Let$T = \max \left\{ \max\limits_{(1<=j<=n)} t_j , \frac{1}{ m} \sum\limits_{(1<=j<=n)} t_j \right\}$

Solving:

$\forall i$ Plot in line section length $t_i$ ,that end i section=start i+1 section

in the result we give section with length= $\sum\limits_{(1<=j<=n)} t_j$.

this section divided by section length T.

Because T*m $\geq\sum\limits_{(1<=j<=n)} t_j$ we give m or less section.

 transform this graphic for machines

$p_i -process(job)\ with\ index\ i$

$m_i-machine\ with\ index\ i$

Because $\forall j T\geq t_j ,p_j$ -run on 1 or 2 machines . If $p_j$ run on 1 machines , we didn't problem ,$p_j$ - finished and  run on at most one machine at any time.if $p_j$ run on 2 mashines $p_j$ run on at most one machine at any time, because if exsist time ,that $p_j$  run on most than one machine in this time ,therefore $t_j>T$ ,but $t_j\leq T$