# Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis
## 3 Theoretical Analysis of Different Criteria
### Case with More Than Two Machines  
**Proposition 4**. : _The normalized sum of the square for Workload Deviations criterion \(NSSWD\) can be bounded as follows: \(\frac{M}{\sqrt{2}\times\sum\limits_{j=1}^{N}{P_{j}}}\times C_{\Delta}\leq\)\(NSSWD\leq\frac{M^{\frac{3}{2}}}{2\times\sum\limits_{j=1}^{N}{P_{j}}}\times C_{\Delta}\)._  
**Proof of Proposition 4. ** As first step, we deal with the upper bound. Before dealing with the demonstration, we remind the reader of the following result (see [20] for details) concerning the maximum value of the standard deviation measure. It is shown that if \(a\leq c_{m}\leq b,\forall m\), then the maximum possible value of standard deviation occurs when half of the values are equal ta \(a\) and half of them are equal to \(b\). That means:  
\[C_{max}=\max\{C_{1},C_{2}\}=\frac{C_{1}+C_{2}}{2}+\frac{1}{2}\times(|C_{2}-C_ {1}|)=\mu+\frac{1}{2}\times C_{\Delta} \tag{11}\]  
\[\max_{a\leq c_{m}\leq b}\left\{\frac{1}{M}\times\left[\sum\limits_{m=1}^{M}{(C _{m}-\mu)^{2}}\right]\right\}=\frac{{(b-a)^{2}}}{4} \tag{12}\]  
Based on the proposition cited above, we can establish that:  
\[ \begin{array}{ll}NSSWD=\frac{1}{\mu}\times\left[\sum\limits_{m=1}^{M}{(C_{ m}-\mu)^{2}}\right]^{\frac{1}{2}}=\frac{M^{\frac{1}{2}}}{\mu}\times\left[ \frac{1}{M}\sum\limits_{m=1}^{M}{(C_{m}-\mu)^{2}}\right]^{\frac{1}{2}}\\ \implies\max NSSWD=\max\frac{M^{\frac{1}{2}}}{\mu}\times\left[\frac{1}{M}\sum \limits_{m=1}^{M}{(C_{m}-\mu)^{2}}\right]^{\frac{1}{2}}=\frac{M^{\frac{1}{2}} }{\mu}\times\left[\max\frac{1}{M}\sum\limits_{m=1}^{M}{(C_{m}-\mu)^{2}}\right] ^{\frac{1}{2}}\\ \implies\max NSSWD=\frac{M^{\frac{1}{2}}}{\mu}\times\left[\frac{{(C_{max}-C_ {min})^{2}}}{4}\right]^{\frac{1}{2}}=\frac{M^{\frac{1}{2}}}{\mu}\times\left[ \frac{{(C_{max}-C_{min})}}{2}\right.\\ \left.\implies\max NSSWD=\frac{M^{\frac{3}{2}}}{2\times\sum\limits_{j=1}^{N}{P_ {j}}}\times(C_{max}-C_{min})\\ \left.\implies NSSWD\leq\frac{M^{\frac{3}{2}}}{2\times\sum\limits_{j=1}^{N}{P_ {j}}}\times C_{\Delta}\end{array}  \tag{13}\]  
The second step of demonstration deals with the lower bound. \[ \begin{array}{ll}NSSWD=\frac{1}{\mu}\times\left[\sum\limits_{m=1}^{M}{(C_{ m}-\mu)^{2}}\right]^{\frac{1}{2}}=\frac{1}{\mu}\times\left[{(C_{1}-\mu)^{2}+(C_{M}- \mu)^{2}+\sum\limits_{m=2}^{M-1}{(C_{m}-\mu)^{2}}}\right]^{\frac{1}{2}}\\ NSSWD\geq\frac{1}{\mu}\times\left[{(C_{1}-\mu)^{2}+(C_{M}-\mu)^{2}}\right]^{ \frac{1}{2}}\end{array}  \tag{14}\]Or by considering the relationship: \(a^{2}+b^{2}=\frac{1}{2}(a+b)^{2}+\frac{1}{2}(a-b)^{2}\), we can conclude that:  
\[ \begin{array}{ll}NSSWD&\geq\frac{1}{\mu}\times\left[\left(C_{1}-\mu\right)^{2 }+\left(C_{M}-\mu\right)^{2}\right]^{\frac{1}{2}}\\ &\geq\frac{1}{\mu}\times\left[\frac{1}{2}\times\left(C_{1}+C_{M}-2\times\mu \right)^{2}+\frac{1}{2}\times\left(C_{M}-C_{1}\right)^{2}\right]^{\frac{1}{2} }\geq\frac{1}{\mu}\times\left[\frac{1}{2}\times\left(C_{M}-C_{1}\right)^{2} \right]^{\frac{1}{2}}\\ &\geq\frac{1}{\sqrt{2}\times\mu}\times\left(C_{max}-C_{min}\right)\\ NSSWD&\geq\frac{M}{\sqrt{2}\times\sum_{j=1}^{N}p_{j}}\times C_{\Delta}\\ \end{array}  \tag{15}\]  
\(\square\)  
**Remark 1**. : _In the case of \(M=2\), \(NSSWD\) and \(C_{\Delta}\) criteria are linearly dependent. This confirms the equivalence between the \(P2||NSSWD\) and \(P2||C_{\Delta}\) problems established in the previous section. This relationship is given below._  
\[ \begin{array}{ll}\frac{2}{\sqrt{2}\times\sum_{j=1}^{N}p_{j}}\times C_{\Delta }\leq\ NSSWD\leq\frac{2\frac{3}{2}}{2\times\sum_{j=1}^{N}p_{j}}\times C_{ \Delta}\\ \implies\frac{\sqrt{2}}{\sum_{j=1}^{N}p_{j}}\times C_{\Delta}\leq\ NSSWD\leq \frac{\sqrt{2}}{\sum_{j=1}^{N}p_{j}}\times C_{\Delta}\\ \implies NSSWD=\frac{\sqrt{2}}{\sum_{j=1}^{N}p_{j}}\times C_{\Delta}\\ \end{array}  \tag{16}\]  
**Remark 2**. : _Based on Proposition 3, we can introduce \(\frac{NSSWD}{C_{\Delta}}\) as a new criterion to deal with the workload imbalance minimization in an identical parallel machine problem.