# Workload Balancing on Identical Parallel Machines: Theoretical and Computational Analysis
## 3 Theoretical Analysis of Different Criteria  
### Case with Identical Jobs  
This section introduces some of the properties of the different workload balancing performance measures and establishes equivalence between the following problems: \(P\big{|}p_{j}=p\big{|}C_{max}\), \(P\big{|}p_{j}=p\big{|}C_{\Delta}\) and \(P\big{|}p_{j}=p\big{|}NSSWD\).  
**Proposition 1**: _If any schedule of a parallel machines problem with \(N\) identical jobs and \(M\) machines, the problems \(P\big{|}p_{j}=p\big{|}C_{max}\), \(P\big{|}p_{j}=p\big{|}C_{\Delta}\) and \(P\big{|}p_{j}=p\big{|}NSSWD\) are equivalent and trivial._  
\begin{table}
\begin{tabular}{c c} \hline \(N\) & Total number of jobs \\ \hline \(M\) & Total number of machine \\ \hline \(m\) & Machine index \\ \hline \(j\) & Job index \\ \hline \(p_{j}\) & Processing time of job \(j\) \\ \hline \(S_{m}\) & Set of jobs scheduled on the machine \(m\) \\ \hline \(C_{m}=\sum\limits_{j\in S_{m}}p_{j}\) & Completion time or workload of machine \(m\) \\ \hline \(C_{max}\) & Maximum of workloads \\ \hline \(C_{min}\) & Minimum of workloads \\ \hline \(C_{\Delta}=C_{max}-C_{min}\) & Difference between maximum and minimum workloads \\ \hline \(\mu=\frac{1}{M}\times\sum\limits_{m=1}^{(M)}C_{m}=\frac{1}{M}\times\sum\limits_{ j=1}^{N}p_{j}\) & Average workload \\ \hline \(NSSWD=\frac{1}{\mu}\times\sqrt{\sum\limits_{m=1}^{M}\left(C_{m}-\mu\right)^{2}}\) & Normalized Sum of Square for Workload Deviations \\ \hline \end{tabular}
\end{table}
Table 1: Nomenclature.  
**Proof of Proposition 1.** In any schedule of a parallel machines problem with \(N\) identical jobs and \(M\) machines, there is a set of \(l\) machines (\(1\ \leq l\ \leq M\)) which have the same workload load \(C_{max}=\left(\left\lfloor\frac{N}{M}\right\rfloor+1\right)\times p\) and \((M-l)\) other machines which must have the same workload \(C_{max}=\left\lfloor\frac{N}{M}\right\rfloor\times p\), where \(l=N-M\times\left\lfloor N/M\right\rfloor\).  
We consider that all jobs have the same processing time: \(\forall j=1\ldots N,p_{j}=p\), then we obtain the following cases.  
Case 1: \(\frac{N}{M}\equiv 0\ (modM)\)  
Then, the different workload measures can be expressed as follows.  
\[\left\{\begin{array}{c}C_{max}=\frac{N}{M}\times p\\ C_{min  
Considering that \(l=N-M\times\left\lfloor\frac{N}{M}\right\rfloor\), the Normalized Sum of Square for Workload Deviations can be expressed as follows:  
\[\begin{array}{ll}NSSWD&=\frac{[M\times(M-I)\times l]^{\frac{1}{2}}}{N}=\frac{ \left[M\times\left(M-N+M\times\left\lfloor\frac{N}{M}\right\rfloor\right)\times \left(N-M\times\left\lfloor\frac{N}{M}\right\rfloor\right)\right]^{\frac{1}{2}}} {N}\\ &=\frac{\left[M\times\left(M\times\left(1+\left\lfloor\frac{N}{M}\right\rfloor \right)-N\right)\times\left(N-M\times\left\lfloor\frac{N}{M}\right\rfloor \right)\right]^{\frac{1}{2}}}{N}\\ \end{array} \tag{5}\]  
Based on the demonstration detailed above, we can also conclude that in any parallel machine scheduling problem with \(N\) identical jobs and \(M\) machines, the Normalized Sum of Square for Workload Deviations \((NSSWD)\)-criterion is constant and completely independent of the job processing times (rather, it depends only on the number of jobs and the number of machines). \(\square\)