# A Novel Fast Parallel Batch Scheduling Algorithm for Solving the Independent Job Problem
## 5 A 2-Approximation Algorithm for \(P\big{|}s_{j},p_{j}=p,p-batch,K_{i}\big{|}C_{\max}\)  
In this section, we study \(P\big{|}s_{j},p_{j}=p,p-batch,K_{i}\big{|}C_{\max}\), i.e., the problem of minimizing the makespan with equal processing times (\(p_{j}=p\)), arbitrary job sizes (may exceed the processing power of certain batches), and non-identical machine capacities.  
The 2-approximation algorithm is called LIM (largest index machine first consider). It groups the jobs in \(\mathcal{J}_{m},\mathcal{J}_{m-1},\ldots,\mathcal{J}_{1}\) (this ordering is crucial), respectively, into batches greedily. During the run of the algorithm, \(Load_{i}\) represents the load on machine \(M_{i}\), i.e., the overall processing time of the batches on \(M_{i}\), \(i=1,2,\ldots,m\). The algorithm dynamically maintains a variable \(x\), which represents the currently largest index such that \(Load_{x}<Load_{m}\). If there is no such index, then we can set \(x=m\). We can assign the next generated batch to machine \(M_{x}\).  
```
Input: \(\mathcal{J}=\cup_{i=1}^{m}\mathcal{J}_{i}\) Output: \(C_{\max}\)--best found solution, \(RT\)--running time
1:\(\textit{Assigned}S=\phi\)/the jobs have been assigned to any batch
2:for\(i=1\) to \(m\) do
3:\(Load_{i}=0\)// the load on machine \(M_{i}\), equals to the overall processing time of the batches on \(M_{i}\),
4:end for
5:x=m
6:for\(i=m\) to \(1\) do
7:if\(x==m\) and \(load_{m}>0\) then
8:\(x=i\)
9:endif
10:create new batch \(b\), \(\mathcal{J}_{i}=\mathcal{J}_{i}-\textit{Assigned}S\)
11:for job \(j\) in \(\mathcal{J}_{i}\) do
12:if\(b.size\leq K_{x}\) then
13:assign job \(j\) to batch \(b\)
14:\(b.size=b.size+j.size\)
15: remove job from \(\mathcal{J}_{i}\) and add it to \(\textit{Assigned}S\)
16:else
17: schedule \(b\) to \(M_{x}\)
18:\(Load_{x}=Load_{x}+b.p\)
19: initiate \(b\)
20:endif if
21:end for
22:if\(b\) is not empty and \(b.size\leq K_{x}\) then
23:while\(b.size\leq K_{x}\) and \(\mathcal{J}_{i-1}\big{|}\big{|}\mathcal{J}_{i-2}\big{|}\big{|}\cdots\big{|} \big{|}\mathcal{J}_{1}-\textit{Assigned}S\) is not empty do
24: get first job \(j\) from \(\mathcal{J}_{i-1}\big{|}\big{|}\mathcal{J}_{i-2}\big{|}\cdots\big{|}\big{|} \mathcal{J}_{1}-\textit{Assigned}S\)
25: assign job \(j\) to \(b\)
26:\(b.size=b.size+j.size\)
27: remove job \(j\) from \(\mathcal{J}_{i-1}\big{|}\mathcal{J}_{i-2}\big{|}\cdots\big{|}\big{|}\mathcal{J} _{1}\) and add it to \(\textit{Assigned}S\)
```  
**Algorithm 2** LIM (largest index machine first consider)
**Theorem 3**: _Algorithm LIM is a 2-approximation algorithm for \(P\big{|}s_{j},p_{j}=p,p-batch,K_{i}\big{|}C_{\max}\)._  
Let \(\Sigma_{1}\) be the schedule with makespan \(SOL_{1}\) generated by LIM after Step 2. In \(\Sigma_{1}\), all batches can be processed at the same time as they are assigned to a machine. During the running of the algorithm, the load on any machine is always less than or equal to the load on \(M_{m}\). Therefore, \(M_{m}\) finishes last in \(\Sigma_{1}\). Let \(B_{last}\) be the last batch assigned to \(M_{m}\). Let \([M_{l},M_{l+1},\ldots,M_{m}]\) be the processing set of \(B_{last}\), which can be defined as the largest size processing set of the job in \(B_{last}\). In \(\Sigma_{1}\), let \(S(B_{last})\) denote the start time of \(B_{last}\). We have: \(SOL_{1}=S(B_{last})+p\).  
Since we assigned \(B_{last}\) to \(M_{m}\), at that moment \(x=m\) must hold. Hence, machines \(M_{l},M_{l+1},\ldots,M_{m}\) are busy in the time interval \((0,S(B_{last}))\). All the batches allocated to machines \(M_{l},M_{l+1},\ldots,M_{m}\) before \(S(B_{last})\) are one-job-overfull batches. All jobs in these batches, together with the largest size job in \(B_{last}\), must be processed on machines \(M_{l},M_{l+1},\ldots,M_{m}\) in any feasible schedule. Hence, we get \(OPT\geq S(B_{last})+p\). So we can draw the conclusion that \(SOL_{1}\leq OPT\).  
For a feasible schedule with makespan \(SOL\) generated by LIM, we have \(SOL\leq 2 SOL_{1}\leq 2 OPT\).