# Identical Parallel Machine Scheduling Considering Workload Smoothness Index
## 4 Theoretical Analysis
### Upper and Lower Bounds  
**Theorem 3**: _Assume that job \(J_{k}\) (\(k\in[1,m]\)) has the longest processing time among the job set. For any feasible solution of a job input instance, the upper bound of the objective value is as follows._  
\[UB=\sqrt{m\cdot W_{\max}^{2}+(\frac{\sum_{j\in\mathcal{J}\setminus\{k\}}p_{j} }{m}+p_{k}-2\cdot W_{\max})\cdot\sum_{j\in\mathcal{J}}p_{j}}.\]  
**Proof.** In the optimal solution, we have \(W_{i}\leq\frac{\sum_{j\in\mathcal{J}\setminus\{k\}}p_{j}}{m}+p_{k}\) and \(\sum_{i\in\mathcal{M}}W_{i}=\sum_{j\in\mathcal{J}}p_{j}\). Thus, we can know that  
\[SI^{2}=\sum_{i\in\mathcal{M}}(W_{\max}-W_{i})^{2}\] \[=m\cdot W_{\max}^{2}-2\cdot\sum_{i\in\mathcal{M}}W_{\max}\cdot W _{i}+\sum_{i\in\mathcal{M}}W_{i}^{2}\] \[=m\cdot W_{\max}^{2}+\sum_{i\in\mathcal{M}}W_{i}\cdot(W_{i}-2 \cdot W_{\max})\] \[\leq m\cdot W_{\max}^{2}+(\frac{\sum_{j\in\mathcal{J}\setminus\{ k\}}p_{j}}{m}+p_{k}-2\cdot W_{\max})\cdot\sum_{j\in\mathcal{J}}p_{j}\] \[=UB^{2}.\]  
Hence, \(SI\leq UB\). The proof is completed.  
**Theorem 4**: \(LB=\sqrt{m\cdot(W_{\max}-\frac{\sum_{j\in\mathcal{J}}p_{j}}{m})^{2}}\) _is a lower bound of problem \(P_{m}||SI\)._  
Figure 3: Illustration of an optimal solution to problem \(P_{m}||SI\).  
Proof.: Let \(\Delta_{i}=W_{i}-\frac{\sum_{j\in\mathcal{J}}p_{j}}{m}\). As \(\sum_{i\in\mathcal{M}}\Delta_{i}=0\),  
\[SI^{2}=\sum_{i\in\mathcal{M}}\left(W_{\max}-\frac{\sum_{j\in \mathcal{J}}p_{j}}{m}-\Delta_{i}\right)^{2}\] \[=\sum_{i\in\mathcal{M}}\left[(W_{\max}-\frac{\sum_{j\in\mathcal{J }}p_{j}}{m})^{2}+\Delta_{i}^{2}-2\cdot\Delta_{i}\cdot(W_{\max}-\frac{\sum_{j \in\mathcal{J}}p_{j}}{m})\right]\] \[=\sum_{i\in\mathcal{M}}\left[(W_{\max}-\frac{\sum_{j\in\mathcal{J }}p_{j}}{m})^{2}+\Delta_{i}^{2}\right]-2\cdot(W_{\max}-\frac{\sum_{j\in \mathcal{J}}p_{j}}{m})\cdot\sum_{i\in\mathcal{M}}\Delta_{i}\] \[=\sum_{i\in\mathcal{M}}\left[(W_{\max}-\frac{\sum_{j\in\mathcal{J }}p_{j}}{m})^{2}+\Delta_{i}^{2}\right].\]  
Due to \(\sum_{i\in\mathcal{M}}\Delta_{i}^{2}\geq 0\), \(SI^{2}\geq m\cdot(W_{\max}-\frac{\sum_{i\in\mathcal{J}}p_{j}}{m})^{2}=LB^{2}\). Hence, \(SI\geq LB\). The proof is completed.  
Lemma 1: _In the optimal solution of problem \(P_{m}||S1\), the workload imbalance between any two machines is less than or equal to the processing time of the smallest job on the machine with a larger workload._  
Proof.: According to [PERSON] and [PERSON] [27], model **[P2]** and the following model **[P3]** share the common optimal solution.  
\[\textbf{[P3]}:\min f=\sum_{i\in\mathcal{M}}(W_{i})^{2}\]  
subject to Constraints (2)-(6).  
Let \(l\in\mathcal{J}\), \(i\) and \(i^{\prime}\) denote the smallest job on the machine with a larger workload, the machine with a larger workload and the machine with a smaller workload. We assume that \(W_{j}-W_{i^{\prime}}\geq p_{l}\). We only need to prove the following inequality.  
\[(W_{i})^{2}+(W_{i^{\prime}})^{2}\geq(W_{i}-p_{l})^{2}+(W_{i^{\prime}}+p_{l})^ {2}\]  
Due to \(W_{j}-W_{i^{\prime}}\geq p_{l}\), we have  
\[(W_{i}-p_{l})^{2}+(W_{i^{\prime}}+p_{l})^{2}\] \[=(W_{i})^{2}+(W_{i^{\prime}})^{2}+2\cdot(p_{l})^{2}-2\cdot p_{l} \cdot(W_{i}-W_{i^{\prime}})\] \[\leq(W_{i})^{2}+(W_{i^{\prime}})^{2}\]  
Therefore, Lemma 1 is proved. The proof is completed.  
Theorem 5: _If \(n>m\), there is no machine with a workload of 0 in the optimal solution of problem \(P_{m}||SI\)._  
Proof.: According to Lemma 1, it is evident that Theorem 5 holds. Therefore, the proof process is omitted for simplicity.