# A Novel Fast Parallel Batch Scheduling Algorithm for Solving the Independent Job Problem
## 4 5-Approximation Algorithm for \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\)
14:if\(p(b)>T/2\) then
15: append \(b\) to \(LongBS\)
16:else if \(T/4<p(b)\leq T/2\) then
17: append \(b\) to \(\textit{MedianBS}\)
18:else
19: append \(b\) to \(\textit{ShortBS}\)
20:endif
21:end if
22:end for
23:if\(LongBS\
eq\phi\) then
24:\(LongBS_{\max}=max(LongBS)\)// the longest processing time batch in \(LongBS\)
25: schedule \(LongBS_{\max}\) on \(M_{i}\); remove \(LongBS_{\max}\) from \(B_{i}^{\prime}\); remove jobs assigned to \(LongBS_{\max}\) from \(Q_{i}\) and add these jobs to \(\textit{Assigned}S\)
26:add these jobs to \(\textit{Assigned}S\)
27:\(RT=LongBS_{\max},p/\textit{LongBS}_{\max},p\) is the processing time of batch \(LongBS_{\max}\)
28:end if
29:for batch \(b\) in \(\textit{MedianBS}\) do
30:if\(RT+b\
eq 57/4\) then
31: schedule \(b\) on \(M_{i}\); remove \(b\) from \(\mathcal{B}_{i}^{\prime}\); remove jobs assigned to \(b\) from \(Q_{i}\) and add these jobs to \(\textit{Assigned}S\)
32:\(RT=RT+b.p\)// the processing time of batch \(b\)
33:endif
34:end for
35:for batch \(b\) in \(\textit{ShortBS}\) do
36:if\(RT+b.p\leq 57/4\) then
37: schedule \(b\) on \(M_{i}\); remove \(b\) from \(\mathcal{B}_{i}^{\prime}\); remove jobs assigned to \(b\) from \(Q_{i}\) and add these jobs to \(\textit{Assigned}S\)
38:\(RT=RT+b.p\)// the processing time of batch \(b\)
39:endif
40:end for
41:end for
42:for batch \(b\) in \(\textit{ShortBS}\) do
43:if\(RT+b.p\leq 57/4\) then
44:\(RT=RT+b.p\)// the processing time of batch \(b\)
45:endif
46:end for
47: Update \(C_{\max}\)// append the batches scheduled on \(M_{i}\) to \(C_{\max}\)
48:end for
49:return \(C_{\max}\), \(RT\)
```  
**Algorithm 1** SCMF-LPTJF (smallest capacity machine first processed and longest processing time job first processed)  
In \(\Sigma\), each machine can process up to three median batches or one long batch and one median batch. On the other hand, the SCMF-LPTJF program will allocate a long batch on the machine as much as possible. After it assigns a long batch on a machine, this machine still has enough time (at least \(5T/4\) time) to handle at least two median batches. Note that the SCMF-LPTJF procedure forms batches greedily. (It overfills each batch with the longest currently unassigned jobs.) Therefore, the SCMF-LPTJF procedure allocates more processing times for long jobs and median jobs on the machines with smaller capacities than \(\Sigma\) does. Equivalently, we claim that \(\sum_{j\in H\cap\bigcup_{i=1}^{m}B_{i}}p_{j}\) is the lower limit of the overall processing time in a long working state, and the median job arranged on machines \(M_{i},M_{i+1},\ldots,M_{m}\) in \(\Sigma\), \(i=1,2,\ldots,m\). Hence, if \(OPT\leq T\), then all long and median jobs will be allocated by SCMF-LPTJF. Therefore, if there is \(OPT\leq T\), but there is still a job \(j\) when executing to the end of the SCMF-LPTJF process, then job \(j\) must be a short job. When job \(j\) is assigned, all of machines \(M_{a_{j}},M_{a_{j}+1},\ldots,M_{m}\) have a load greater than \(2T\). Let \(i_{\max}<a_{j}\) be the largest index such that machine \(M_{i_{\max}}\) has a load less than or equal to \(2T\). If all of the machines have load greater than \(2T\), then set \(i_{\max}=0\). Therefore, all of machines \(M_{i_{\max}+1},M_{i_{\max}+2},\ldots,M_{m}\) have load greater than \(2T\). There is room on the machine \(M_{i_{\max}}\) for scheduling any short job. Hence, by the rule of the SCMF-LPTJF procedure, no short job from \(\bigcup\limits_{i=1}^{i_{\max}}\mathcal{T}_{i}\) can be assigned to machines \(M_{i_{\max}+1},M_{i_{\max}+2},\ldots,M_{m}\).