# 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}\)  
We denote the optimal makespan of the problem \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\) as \(OPT\). The main focus of the research is to develop a fast scheduling model to get a minimized makespan as close to \(OPT\) as possible. To solve the problem \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\), we used the MBLPT (modified longest processing time batch) rule [35], a modification of the BLPT (longest processing time batch) rule. For a given jobs set \(\mathcal{J}_{i}\) that can be assigned to machine \(M_{i}\), we apply the MBLPT rule, which sorts jobs to get \(\mathcal{J}_{i}^{\prime}\). We build a batch \(B_{i,1}\) on machine \(M_{i}\), and then the rule repeatedly pops the first job from \(\mathcal{J}_{i}^{\prime}\) and assigns it to \(B_{i,1}\) until the sum of all the jobs assigned to \(B_{i,1}\) just exceeds the capacity of \(M_{i}\). Batch \(B_{i,1}\) is called \begin{table}
\begin{tabular}{c c} \hline \hline
**Indices** & **Description** \\ \hline \(i\) & index of machine, \(i=\{1,2,\ldots,m\}\) \\ \(j\) & index of job, \(j=\{1,2,\ldots,n\}\) \\ \(l\) & index of batch, \(l=\{1,2,\ldots,n\}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Indices. \begin{table}
\begin{tabular}{c c} \hline \hline
**Decision Variables** & **Description** \\ \hline \(x_{jil}\) & 1, if job \(j\) is assigned to the \(l\)th batch processed on machine \(M_{i}\); 0, otherwise. \\ \(y_{il}\) & the processing time of \(l\)thbatch processed on machine \(M_{i}\). \\ \(C_{\max}\) & makespan. \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Decision variables. the one-job-overfull batch. Once the one-job-overfull batch exists, a new batch should be built on the same machine, unless the machine runs out of maximum completion time (maximum completion time is in the initialization parameters of the algorithm). We repeat the above job assignment procedure until the job list \(\mathcal{J}^{\prime}_{i}\) is empty. Let \(\mathcal{B}_{i}=\left\{B_{i,g}:g=1,2,\ldots,h_{i}\right\}\) denote the set of batches generated using the MBLPT rule to \(\mathcal{J}^{\prime}_{i}\) and machine \(M_{i}\), and \(h_{i}\) is the total number of batches scheduled on machine \(M_{i}\). Let \(p(B_{i,g})\) and \(p_{s}(B_{i,g})\) denote the longest processing time (the processing time of batch \(B_{i,g}\) is equal to the longest processing time of jobs on it) and the shortest processing time of the jobs in batch \(B_{i,g}\), respectively, such that \(p(B_{i,1})\geq p(B_{i,2})\geq\cdots\geq p(B_{i,h_{i}})\). The batches \(B_{i,1},B_{i,2},\ldots,B_{i,h_{i}-1}\) are one-job-overfull batches, while \(B_{i,h_{i}}\) can be one-job-overfull or not. We have \(p_{s}(B_{i,g})\geq p(B_{i,g+1})\) (\(g=1,2,\ldots,h_{i}-1\)). The Inequality (7) below (refer to [27]) is easy to prove. \[\sum\limits_{g=1}^{h_{i}-1}\left(p(B_{i,g})-p_{s}(B_{i,g})\right)+p(B_{i,h_{i} })\leq p(B_{i,1}). \tag{7}\]  
By the Inequality (7), we have  
**Lemma 1**. : \(\sum\limits_{g=1}^{h_{i}}p(B_{i,g})\leq\sum\limits_{g=1}^{h_{i}-1}p_{s}(B_{i,g })+p(B_{i,1})\)_._  
We now propose the 4.5-approximation algorithm for \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\). Similar frameworks have been used in [58; 59; 60; 61; 62]. In [58], [PERSON] et al. developed a 4/3 approximation algorithm to solve classical scheduling problems with minimized maximum completion time on parallel machines with processing set constraints. In [59], [PERSON] proposed a 9/4-approximation algorithm for \(P\big{|}s_{j}=1,p-batch,K_{i}\big{|}C_{\max}\) (the special case of \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\) where all \(s_{j}=1\)). The algorithm to be described extends the previous research by involving non-identical job sizes. We first run the 5-approximation algorithm for \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\). The algorithm generates a feasible schedule with a maximum completion time of \(UB\leq 5 OPT\) in \(O(n\log m+n^{2})\) time. Let the minimum completion time \(LB=UB/5\). We have \(LB\leq OPT\leq UB\).