# Identical Parallel Machine Scheduling Considering Workload Smoothness Index
## 1 Introduction  
Parallel machine scheduling systems have been extensively applied in various production and manufacturing industries [1]. In parallel machine scheduling, it generally contains two decision issues, i.e., sequencing and job assignment [2; 3]. Various optimization objectives, including the makespan and the total completion time, have been well addressed in previous studies [4; 5; 6; 7]. In addition to the above classical objectives, workload balance between the machines together with the corresponding operators is also a major aspect of decision making in manufacturing industry [8; 9; 10]. It contributes to reducing the idleness and work-in-process and removing bottlenecks [8; 11]. Minimum imbalance is actually beneficial for minimizing the inventory of finished goods [12]. The solutions with the classical minimum objective of the makespan or the total completion time may induce the workload balance between the parallel machines to a large extent. However, the above solutions cannot guarantee their optimality when we aim to minimize the imbalance of workloads between the machines. Therefore, some previous works have investigated other specific criteria to measure the workload imbalance, such as the Average Relative Percentage of Imbalance (\(ARPI\)) [12], Total Imbalance (\(TB\)) [13] and even Total Workload [14]. In this work, we introduce the workload smoothness index (\(SI\)) to the identical parallel machine scheduling problem. The index of \(SI\) was introduced by [PERSON] and [PERSON] [15] to measure the balance level of workloads between the neighboring workstations in an assembly line environment. To our best knowledge, this is the first study to introduce \(SI\) as an optimization objective into parallel machine scheduling problems. We observe that \(SI\) may generate a better solution in terms of the workload balance between the parallel machines, comparing with \(ARPI\), \(TB\) and some other measurements. We first present the formulae of the above indices and then give two examples to illustrate theirperformance difference. The indices are given by \(SI=\sqrt{\sum_{i\in\mathcal{M}}(W_{\max}-W_{i})^{2}}\), \(ARPI=\frac{1}{m}\cdot(\sum_{i\in\mathcal{M}}\frac{W_{\max}-W_{i}}{W_{\max}})\) and \(TB=\sum_{i\in\mathcal{M}}|\frac{\sum_{i\in\mathcal{M}}W_{i}}{m}-W_{i}|\), where \(W_{\max}\) is the maximum workload or the makespan, \(W_{i}\) is the workload of machine \(i\), and \(\mathcal{M}\) is the set of machines. In Example 1, there are \(five\) jobs \(J_{1},J_{2},J_{3},J_{4},J_{5}\) to be processed on \(four\) parallel machines. The corresponding processing times of the jobs are 1, 2, 3, 6 and 8, respectively. For both problems \(P_{m}||C_{\max}\) and \(P_{m}||ARPI\), all the three solutions shown in Figure 1a-c are optimal with the minimum objective value of \(C_{\max}=W_{\max}=8\) and \(ARPI=\frac{1}{4}\cdot(\sum_{i=1}^{4}\frac{8-W_{i}}{8})=3/8\), respectively. For problem \(P_{m}||TB\), however, only the two solutions in Figure 1b,c are optimal with the minimum objective value of \(TB=\sum_{i=1}^{4}|\frac{\sum_{i\in\mathcal{M}}W_{i}}{4}-W_{i}|=8\). For the considered problem \(P_{m}||SI\) in this work, we observe that only solution Figure 1b is optimal with the corresponding objective value of \(SI=\sqrt{\sum_{i=1}^{4}(8-W_{i})^{2}}=\sqrt{54}\), while the other two solutions in Figure 1a,c are of the objective values of \(SI=\sqrt{74}\) and \(SI=\sqrt{62}\), respectively. That is, the job assignment in Figure 1b has the best workload balance among the three solutions. In the above example, we find that the solution in Figure 1b is also the only optimal schedule for problem \(P_{m}||MWD\) where \(MWD=\max_{i\in\mathcal{M}}\frac{W_{\max}-W_{i}}{W_{\max}}\). The following Example 2, however, reveals that index \(SI\) also better guarantees workload balance than \(MWD\). In Example 2, there are \(six\) jobs with processing times 15, 9, 9, 7, 6, and 5 to be processed on \(four\) machines.