Load sharing problem

The load balancing problem deals with the theoretical aspects of load distribution . It is assumed that any job can be fulfilled by any machine and that all jobs and machines are known in advance. In this way, an optimal distribution of the jobs can be calculated, whereby the maximum runtime of all machines remains as short as possible.

Formal description

There are m machines available. On these machines are n jobs are distributed, with the length of a job j with is designated. The aim is to distribute the jobs to the machines so that the total runtime is as short as possible; the runtime of the machine that has been working the longest must therefore be minimized, because it is decisive for the total runtime. ${\ displaystyle M_ {1} \ ldots M_ {m}}$ ${\ displaystyle j_ {1} \ ldots j_ {n}}$ ${\ displaystyle t_ {j}}$

NP-completeness of the decision problem

The corresponding decision problem asks: Is there a load distribution such that the total running time is at most T ?

Formal:, where is a distribution of jobs. ${\ displaystyle L = \ {<t_ {1}, \ ldots t_ {n}, m, T> | \ exists A: T_ {A} \ leq T \}}$ ${\ displaystyle T_ {A}}$

In order to show that L is NP-complete , two points have to be proved:

L lies in NP . For this purpose, a witness (a solution) must be able to be given, which can be verified in polynomial time. This witness is the concrete distribution of jobs among the machines; it can then be verified in polynomial time that the specified maximum runtime is being observed.

L is at least as difficult as all other languages in NP. To do this, it suffices to trace L back to another problem from NP, here to the binary partition problem BINPART. It has to be shown that any input for BINPART can be converted into an input for the load sharing problem:

Let be an input set of numbers for BINPART. Then choose the input quantity for the load balancing problem .

{\ displaystyle <s_ {1}, \ ldots s_ {n}>}

{\ displaystyle <s_ {1}, \ ldots s_ {n}, 2, \ sum _ {j = 1} ^ {n} {\ frac {s_ {j}} {2}}>}

If BINPART has a solution (i.e. there is a division of into two partitions so that the sum of the numbers in both partitions is the same) then the load- sharing problem on the changed input also has a solution. For this purpose, the division found is applied directly to the two machines available so that both machines run for exactly the same time. Thus, each of the two machines receives exactly half of the total runtime of all jobs, so there actually is a solution . ${\ displaystyle S = s_ {1} \ ldots s_ {n}}$ ${\ displaystyle \ sum _ {j = 1} ^ {n} {\ frac {s_ {j}} {2}} = T}$
If BINPART has no solution (i.e. there is no division of into two partitions so that the sum of the numbers in both partitions is the same) then the load distribution problem on the changed input also has no solution. For this purpose, the division found is applied directly to the two available machines. Since no even distribution of the numbers could be found, one of the two machines has to run longer than the other. Thus, one of the two machines has a longer runtime than half of the total runtime of all jobs, so it was chosen to be sufficiently small to make a solution impossible. ${\ displaystyle S = s_ {1} \ ldots s_ {n}}$ ${\ displaystyle T}$

Approximation by greedy algorithm

Greedy balance

algorithm

Der nächste Job wird genau der Maschine zugewiesen, die bis jetzt die geringste Laufzeit hatte.

analysis

It is easy to find an example that this algorithm does not deliver the optimal solution - however, a 2-approximation is achieved: Let be the machine that received the last job j that was distributed . Then it was previously the case for this machine that it had the shortest running time to date, i.e. in particular that its running time was shorter than the average running time of all machines. This average can be specified as . ${\ displaystyle M_ {i}}$
${\ displaystyle {\ frac {1} {m}} \ cdot \ sum _ {x = 1} ^ {n} t_ {x}}$

With an optimal distribution of jobs, let T * be the best possible total runtime. Without knowing anything exactly about T *, you can still make the two estimates:

T * is at least as long as the longest job: . ${\ displaystyle T ^ {*} \ geq MAX (t_ {x})}$
T * is at least as long as the completely uniform distribution of jobs, if that were possible: . ${\ displaystyle T ^ {*} \ geq {\ frac {1} {m}} \ cdot \ sum _ {x = 1} ^ {n} t_ {x}}$

If you combine these estimates, you get for the greedy calculated solution T:

${\ displaystyle T = T_ {M_ {i}} = (T_ {M_ {i}} - t_ {j}) + (t_ {j}) \ leq \ left ({\ frac {1} {m}} \ cdot \ sum _ {x = 1} ^ {n} t_ {x} \ right) + (T ^ {*}) \ leq 2 \ cdot T ^ {*}}$ .

Sorted balance

If you sort the jobs in advance and distribute them to the machines in descending order of length, the following also applies to the last job j added :

${\ displaystyle t_ {j} \ leq T ^ {*} / 2}$ . The reason for this is that with a machine that processes at least two jobs, the next one is shorter than the previous one. The last job added can only account for half of the total time required for the longest running machine (it cannot be larger than an existing one).

In this case, the estimate can improve on:

${\ displaystyle T = T_ {M_ {i}} = (T_ {M_ {i}} - t_ {j}) + (t_ {j}) \ leq \ left ({\ frac {1} {m}} \ cdot \ sum _ {x = 1} ^ {n} t_ {x} \ right) + (T ^ {*} / 2) \ leq 1.5 \ cdot T ^ {*}}$ .

literature

Jon Kleinberg , Éva Tardos . Algorithm design. Pearson International Edition, 2006. ISBN 0-321-37291-3 . Pages 600ff.