# Identical Parallel Machine Scheduling Considering Workload Smoothness Index
## 5 Heuristic Algorithms
### An Improved List Scheduling Algorithm  
Previous studies show that the list scheduling algorithm based on the LPT rule has better performance in solving workload balancing problems (e.g., [32]). Inspired by Lemma 1, we propose an improved list scheduling algorithm based on the LPT rule, which is denoted by \(ILSA_{LPT}\). The main idea of \(ILSA_{LPT}\) algorithm is to minimize the difference between the maximum workload and the minimum workload. A detailed description of the main idea of the \(ILSA_{LPT}\) algorithm is shown in Figure 5.  
For example, suppose there are seven jobs to be processed on two machines. The corresponding processing times of the jobs are (8, 9, 8, 6, 8, 7, 6). Let the maximum workload constraint be 29. The solution of the \(LSA_{LPT}\) algorithm is shown in Figure 6a. The working time of machine 1 is 6 longer than that of machine 2. If we can remove 3 (6/2) units' processing times from machine 1 to machine 2, the optimal solution can be obtained. However, it is not difficult to find that this method is not feasible for this case. Nevertheless, we can reduce the working time on machine 1 by 3 units as much as possible by exchanging the positions of job \(J_{2}\) and job \(J_{6}\); the detail is shown in Figure 6b. After the above operations, we can obtain a better feasible solution. To keep our algorithm more understandable, the pseudo-code of the \(ILSA_{LPT}\) algorithm is described in Algorithm 3.  
Figure 5: The framework of the \(ILSA_{LPT}\) algorithm.  
```
0:\(m,n,\{p_{1},p_{2},\ldots,p_{n}\}\)
1: Find a feasible solution by \(LST_{LPT}\)
2: Calculate the difference between the maximum workload and the minimum workload, denoted by \(\Delta_{\max}\)
3: Determine the longest job \(k\) which is processed on the machine with the maximum workload
4: Determine the set, denoted by \(\eta\), of jobs that are processed on the machine with the minimum workload
5:\(\alpha=\{j|j\in\eta\ \&\ 0<p_{k}-p_{j}<\Delta_{\max}\}\) % _Find the job \(j\) in set \(\eta\) satisfying \(0<p_{k}-p_{j}<\Delta_{\max}\)_
6:while\(\alpha\
eq\phi\)do
7: Assign job \(J_{k}\) to the machine with the minimum workload
8: Seek the job denoted by \(j^{\prime}\) in set \(\alpha\) whose absolute value of the difference between its processing time and \(p_{k}\) is the closest to \(\Delta_{\max}/2\), then assign the job to the machine with the maximum workload
9:\(\alpha=\alpha\setminus\{j^{\prime}\}\)
10: Update set \(\alpha\) and \(\Delta_{\max}\)
11:endwhile
12:\(\beta=\{j|j\in\eta\ \&\ p_{j}<\Delta_{\max}\}\) % _Find the job \(j\) processed on the machine with the maximum workload satisfying \(p_{j}<\Delta_{\max}\)_
13:while\(\beta\
eq\phi\)do
14: Assign the job denoted by \(j^{\prime\prime}\) in set \(\beta\) whose processing time is closest to \(\Delta_{\max}/2\) to the machine with the minimum workload
15:\(\beta=\beta\setminus\{j^{\prime\prime}\}\)
16: Update set \(\beta\) and \(\Delta_{\max}\)
17:endwhile
18: Calculate the objective value
19:return The objective value and the feasible solution
```  
**Algorithm 3**\(ILSA_{LPT}\) algorithm