Filed Under: C++

Today, we’ll learn to solve the load balancing problem using C++. It is an interesting greedy problem. This problem is also known as the life problem. Greedy problems are very important for interview preparation. There can be multiple solutions to the same problem but we aim to learn the most efficient one. So without wasting any time, let’s go through the problem statement.

Problem Statement for Load Balancing Problem Using C++

You own a super-fast computer server consisting of N-hyper-scalar amazingly fast processors Sigma 007. These processors are numbered from 1 to N. Each of these processors processes independent jobs. A new incoming job is assigned to an arbitrary processor. Sometimes, a computer gets assigned too many jobs and others even wait idly. This causes the whole system to undergo rebalancing.

Rebalancing process in rounds: During each round, a processor can transfer at most one job to each of its neighbors on the bus. The goal of the rebalancing is to achieve that all the processors have the same number of jobs.

Determine the balanced load after rebalancing. If rebalancing is not possible, return -1.

For example,

```processors_count: 3
max_transfers_needed: 34

processors_count: 2
max_transfers_needed: -1

processors_count: 8
load: [16, 17, 15, 0, 20, 1, 1, 2]
max_transfers_needed: 23

processors_count: 10
load: [0, 0, 100, 0, 0, 0, 0, 0, 0, 0 ]
max_transfers_needed: 70
```

Approach to Solving Load Balancing Problem Using C++

Note that, this is a minimization problem. We have to minimize the load on all the computers.

• Calculate the total load on the server.
• If the total load is not divisible by the total number of computers on the server, rebalancing is not possible. Return -1
• Otherwise, calculate the load on each computer after balancing the overall load.
• Declare min_diff and set its value to the minimum possible integer.
• int min_diff = INT_MIN;
• Now, we’ll start iterating over the loads. For each load, we’ll perform the following logic.
• Transfer the excess load to the next computer. This will make this computer balanced. Now we’re left with N – 1 computer left to balance.
• arr[i + 1] += arr[i] – balance_load;
• Update the difference if:
• max_diff = max(max_diff, abs(arr[i] – balance_load));
• Repeat the steps mentioned above for each value of i until i = N – 2.
• Finally, return the value of max_diff.

Algorithm

Below is the step by step process that we’ll follow to implement the algorithm.

```int job_scheduling(vector <int> arr,int n)
{
int sum = 0;

for(int i = 0;i < n; i++)
sum += arr[i];

if(sum % n != 0)
{
return -1;
}

int balance_load = (sum / n);

int max_diff = INT_MIN;

for(int i = 0;i < n - 1; i++)
{
arr[i + 1] += arr[i] - balance_load;
max_diff = max(max_diff, abs(arr[i] - balance_load));
}

return max_diff;
}
```

Load Balancing Problem Using C++ Program

```#include <iostream>
#include <climits>
#include <vector>

using namespace std;

int job_scheduling(vector <int> arr,int n)
{
int sum = 0;

for(int i = 0;i < n; i++)
sum += arr[i];

if(sum % n != 0)
{
return -1;
}

int balance_load = (sum / n);

int max_diff = INT_MIN;

for(int i = 0;i < n - 1; i++)
{
arr[i + 1] += arr[i] - balance_load;
max_diff = max(max_diff, abs(arr[i] - balance_load));
}

return max_diff;
}

int main()
{
// take the input
cout << "Enter the number of processors" << endl;
int N;
cin >> N;

// vector to store the load on each processor
vector <int> arr(N);

// take the loads as input
cout << "Enter the load on each processor" << endl;

for(int i = 0; i < N; i++)
cin >> arr[i];

int max_diff = job_scheduling(arr, N);

// print the output
if(max_diff == -1)
cout << "Load balancing is not possible for this configuration" << endl;
else
cout << "For perfect balance of loads, the max difference is: "<< max_diff << endl;

return 0;
}
```

Conclusion

In this article, we solved the load balancing problem using C++. Notice that, this was a mathematical problem overall. To check if the balancing is possible or not, we took the help of the modulus operator property. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.