We formuleren het probleem van load balancing als volgt. Gegeven een set van \(m\) machines \(M_1 ,... ,M_m\) en een set van \(n\) taken; elke taak \(j\) heeft een uitvoeringstijd \(t_j\). We willen elke taak aan een van de machines toekennen op zodanige manier dat de werklast op alle machines zo gebalanceerd als mogelijk is. Meer bepaald, in om het even welke toekenning van taken aan machines, zij \(A(i)\) de set van taken toegekend aan machine \(M_i\); door deze toekenning moet machine \(M_i\) in totaal tijd \(T_i\) werken; dit wordt de belasting van machine \(M_i\) genoemd. We definieren de makespan \(T\) als de maximum belasting van een machine uit de set, m.a.w. \(T = max_i T_i\). Gevraagd is een toekenning te vinden die \(T\) minimaliseert. Dit is een onhandelbaar probleem. Gevraagd is een 4/3-benaderingsalgoritme (of beter) voor dit probleem te implementeren.
Schrijf een Python-functie loadBalancing(jobs: list, m: int).
Deze functie krijgt een lijst van taken, evenals een geheel getal \(m\) dat het aantal gebruikte machines voorstelt.
De functie geeft een planning terug van de taken op de \(m\) verschillende machines, deze machines worden voorgesteld door een lijst.
>>> loadBalancing([2, 3, 4, 6, 2, 2], 3)
[[6, 2], [4, 2], [3, 2]]
>>> loadBalancing([3, 3, 3, 3, 3, 3], 2)
[[3, 3, 3], [3, 3, 3]]