2
$\begingroup$

I have a system of $M$ machines and $U$ users. Each machine has a capacity in terms of number of resources.

Let, machine $m$ has $\zeta_m$ resources.

Each user has a service demand $d_u$ and there is a link between any user $u$ and any machine $m$ defined as $\theta_{u,m}$.

The link quality between the user $u$ and machine $m$ is defined as

$$l_{u}=\log_2\left(1+\frac{\theta_{u,m}}{\sum_{m'=1,m'\neq m}^{M}\theta_{u,m'}}\right),$$

$\sigma$ is constant value which is very small.

The amount of resources needed by user $u$ from machine $m$ depends on its link quality.

For example, if user $u$ with demand $d_u$ is connected to a single machine $m$ with link quality $l_{u}$, then the number of resources it needs from machine $m$ is $$\lambda_{u,m}=\frac{d_u}{l_{u}}$$

I want to do optimal/ best possible load balancing so that the machines have proportional load depending on the capacity/the of resources they have. At the same time, the overall link quality of all the user should also be maximised. This is because the lower the amount of resources used from the machines, the faster the users get their services attended.

Not that the each user has access to a given set of machines. For example, the accessible set of machines for user $u$ is defined as $\mathcal{S}_u$ (a non-empty set with at least one element) which is a subset of the set $\{1,2,\cdots,M\}$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Assuming $\theta_{u,m}$ is given for each user $u$ and machine $m \in\ S_u$
One way is to proportionally distribute quality with load balancing for each user
Objective1= Max $\sum_{u}\sum_{m \in\ S_u}(l(u,\theta_{u,m}) + \sum_{m \in\ M}\sum_u \frac{l(u,\theta_{u,m})}{d_u \zeta_m}$. Basically taking inverse of (load*capacity), thus min turns into max.

Or

If your solver allows solving multiobj lexicographically then
You may set obj1= max $\sum_{u}\sum_{m \in\ S_u}l(u,\theta_{u,m})$with higher priority.
And obj2= max$\sum_{m \in\ M}\sum_u \frac{l(u,\theta_{u,m})}{d_u \zeta_m}$ with lower priority.
Solver solves obj1 first then adds a constraint as obj1$\ge$solution and solves for obj2.

Constraints
$\sum_u x_{u,m}\frac{d_u}{l(u,\theta_{u,m})} \le \zeta_{m} \ \ \forall m \in\ $M
$1 \le \sum_{m \in\ S_u} x_{u,m} \le \vert S_u\vert \ \ \forall u$

$\sum_{m \in\ S_u} l(u,\theta_{u,m}) \ge d_u \ \ \forall u \in\ $users (Not required)

Where $l(u,\theta_{u,m}) = \log_2(\sum_m \theta_{u,m}) - \log_2 (\sum_m (1-x_{u,m})\theta_{u,m}+\sigma) \ \ \forall u \in\ $users
$x_{u,m} \in\ \{0,1\}: m \in\ S_u$

As suggested by OP for load balancing
$\underset{x_{u,m}}{\min} \sum_u x_{u,m}z$
Add a constraint
$z \ge \delta_m \ \ \forall m$

$\endgroup$
10
  • $\begingroup$ thanks. Would you please explain: $l(u,\theta_{u,m}) = \log_2(\sum_m \theta_{u,m}) - \log_2 \sum_m (1-x_{u,m})\theta_{u,m}= x_{u,m}\log_2 \theta_{u,m} \ \ \forall u \in\ $users $\endgroup$
    – KGM
    Commented Dec 28, 2022 at 8:01
  • $\begingroup$ What happens if the the system is overloaded? I mean no matter how we associate users with machines, the demand of the users cannot be satisfied. What happens then? The first and second constraint will make the solution infeasible. $\endgroup$
    – KGM
    Commented Dec 28, 2022 at 8:08
  • $\begingroup$ Also, how does your proposed solution allows some user to be connected to multiple machines simultaneously if needed? $\endgroup$
    – KGM
    Commented Dec 28, 2022 at 8:10
  • $\begingroup$ Added 3rd constraint even though I thought second constraint based on user demand would have ensure 1 or more machines to be assigned $\endgroup$ Commented Dec 28, 2022 at 8:15
  • $\begingroup$ Link quality: its log of all $\theta$ of (user, machines)/$\theta$ of machines not assigned. So it turns to log of $\theta$ of machines assigned. Binary x is the assignment $\endgroup$ Commented Dec 28, 2022 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.