# Identical Parallel Machine Scheduling Considering Workload Smoothness Index
## 2 Literature Review
### Parallel Machine Workload Balancing Problem  
For the parallel machine workload balancing problem, [PERSON] et al. [11] introduce the index of total relative percentage of workload imbalances, i.e., \(RPI=\sum_{i\in\mathcal{M}}\frac{W_{\max}-W_{i}}{W_{\max}}\).  
Figure 2: Illustration of two optimal solutions to Example 2 for problem \(P_{m}||MWD\).  
100%, where \(W_{i}\) is the workload of machine \(i\), and \(W_{\max}=\max\{W_{1},W_{2},\ldots W_{i},\ldots,W_{m}\}\). They propose three list scheduling algorithms based on the following rules: Random, SPT (shortest processing time first), and LPT (longest processing time first). Experimental results show that the list scheduling algorithm based on the LPT rule outperforms the other two algorithms. [PERSON] et al. [13] study the workload balancing problem in a semi-automatic parallel machine shop in which two types of machines are operated by several operators. The objective is to minimize the imbalance of the workloads among the operators, i.e., to minimize \(TB=\sum_{i\in\mathcal{M}}|\frac{\sum_{i\in\mathcal{M}}W_{i}}{m}-W_{i}|\). [PERSON] et al. [16] investigate the parallel machine workload balancing problem with the objective of minimizing the maximum workload difference between machines, i.e., minimizing \(MWD=\max_{i\in\mathcal{M}}\frac{W_{\max}-W_{i}}{W_{\max}}\).  
[PERSON] et al. [17] study the parallel machine workload balancing problem with sequence-dependent setup times and define the maximum allowable level \(\alpha\) of imbalance. That is, the sum of the processing times and setup times of jobs assigned to machine \(i\), denoted by \(W^{\prime}_{i}\), has to be within some tolerance. More precisely, \(W^{\prime}_{i}\leq\frac{1}{m}\cdot W^{\prime}_{total}(1+\alpha)\) and \(W^{\prime}_{i}\geq\frac{1}{m}\cdot W^{\prime}_{total}(1-\alpha)\), where \(W^{\prime}_{total}\) is sum of the total processing time and the total setup time of all the jobs. [PERSON] et al. [12] also address the parallel problem scheduling problem with sequence-dependent setup times, in which the objective is to minimize the average relative percentage of imbalance (\(ARPI\)), i.e., to minimize \(ARPI=\frac{1}{m}\cdot(\sum_{i\in\mathcal{M}}\frac{W_{\max}-W_{i}}{W_{\max}}) \times 100\%\).  
[PERSON] et al. [18] introduce a criterion named the normalized sum of squared workload deviations (NSSWD) to minimize the workload imbalance. They prove that an NSSWD-optimal schedule is necessarily a makespan-optimal one. [PERSON] and [PERSON] [19] explain such a proof is incorrect under the case of \(m\geq 3\). For solving the problem under the case of \(m\geq 3\), [PERSON] and [PERSON] [20] propose an algorithm based on a local search procedure. Theoretically, an NSSWD-optimal schedule is necessarily an SI-optimal one. However, relatively few studies apply NSWWD to achieve the workload imbalance minimization. Consequently, the linearization process of NSSWD is relatively unexplored, which makes the problem difficult to be directly solved by calling commercial solvers. Moreover, few studies on problem \(P_{m}||NSSWD\) consider the given maximum workload constraint of machines. Besides, some works consider controllable processing in order to achieve balanced workloads (i.e., smooth processes) on (neighbor) machines [21; 22].  
In the above studies, various indices have been proposed to deal with the parallel machine workload balancing problem. As shown in Example 1 and Example 2, however, the indices may not guarantee a solution with the best possible balance between the parallel machines. Therefore, we adopt the smoothness index rather than any of the above indices as the optimization objective of the considered problem in this study.