# A Novel Fast Parallel Batch Scheduling Algorithm for Solving the Independent Job Problem
## 2 Literature Review  
Since the 1980s, scholars have studied the job scheduling problem of parallel batch machines extensively [1]. In this section, we review the results of research dealing with different job sizes and minimization of the maximum completion time [14; 15; 16; 17; 18; 19; 20]. \begin{table}
\begin{tabular}{c c} \hline
**Notation** & **Description** \\ \hline \(\mathcal{J}\) & set of jobs, \(\mathcal{J}=\{J_{1},J_{2},\ldots,J_{n}\}\) \\ \(J_{j}\) & \(j\)th job \\ \(p_{j}\) & processing time of job \(J_{j}\) \\ \(s_{j}\) & size of job \(J_{j}\) \\ \(\mathcal{M}\) & set of machines, \(\mathcal{M}=\{M_{1},M_{2},\ldots,M_{m}\}\) \\ \(M_{i}\) & \(i\)th machine \\ \(K_{i}\) & capacities of \(M_{i}\) \\ \(B_{i,g}\) & \(g\)th batch scheduled on \(i\)th machine \\ \(UB\) & upper bound of makespan \\ \(LB\) & lower bound of makespan \\ \(C_{\max}\) & makespan \\ \hline \end{tabular}
\end{table} 
Table 1: Notations. In the one-machine case of problem \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\), we denote \(1\big{|}s_{j},p-batch,B\big{|}C_{\max}\). [PERSON] [21] proved that \(1\big{|}s_{j},p-batch,B\big{|}C_{\max}\)  is a strong NP-hard (non-deterministic polynomial) problem, and presented four heuristics. [PERSON] et al. [22] also proposed a 1.75-approximation algorithm for \(1\big{|}s_{j},p-batch,B\big{|}C_{\max}\). [PERSON] and [PERSON] presented a branch and bound method for \(1\big{|}s_{j},p-batch,B\big{|}C_{\max}\). [PERSON] et al. [23] presented a 1.7-approximation algorithm for \(1\big{|}s_{j},p-batch,B\big{|}C_{\max}\). [PERSON] et al. [24] presented a \((2+\varepsilon)\)-approximation algorithm for \(1\big{|}r_{j},s_{j},p-batch,B\big{|}C_{\max}\) (the more general case where jobs have different release times), where \(\varepsilon\) is a number greater than 0 and is arbitrarily small. The special case of \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\)  is where all \(K_{i}=B\) (\(B<n\)) is represented as \(P\big{|}s_{j},p-batch,B\big{|}C_{\max}\). [PERSON] et al. [25] studied \(P\big{|}s_{j},p-batch,B\big{|}C_{\max}\)  and provided an algorithm that is based on the simulated annealing approach. [PERSON] et al. [23] demonstrated that although the processing time for all jobs is the same (unless P = NP), \(P\big{|}s_{j},p-batch,B\big{|}C_{\max}\)  cannot be approximated to a ratio less than 2. [PERSON] et al. presented a \((2+\varepsilon)\)-approximation algorithm. [PERSON] et al. [26] presented a 8/3-approximation algorithm for \(P\big{|}s_{j},p-batch,B\big{|}C_{\max}\)  with running time \(O(n\log n)\). [PERSON] et al. [27] developed a mixed integer programming model and some heuristic algorithms for \(P\big{|}r_{j},s_{j},p-batch,B\big{|}C_{\max}\) (the problem where jobs have different release times). A 2-approximation algorithm for \(P\big{|}r_{j},s_{j},p_{j}=p,p-batch,B\big{|}C_{\max}\)  (the special case of \(P\big{|}r_{j},s_{j},p-batch,B\big{|}C_{\max}\)  where all jobs have the same processing times) was given by [PERSON] et al. [28]. [PERSON] [29] obtained a \((2+\varepsilon)\)-approximation algorithm for \(P\big{|}r_{j},s_{j},p-batch,B\big{|}C_{\max}\). More recently, several research groups have focused on the scheduling problems on parallel batch machines with different capacities and applications in many fields [30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41]. The special case of \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\), where all \(s_{j}\leq K_{1}\) (i.e., all jobs can be assigned to any machine), is denoted as \(P\big{|}s_{j}\leq K_{1},p-batch,K_{i}\big{|}C_{\max}\). [PERSON] et al. [30] studied \(P\big{|}s_{j}\leq K_{1},p-batch,K_{i}\big{|}C_{\max}\)  and developed a genetic algorithm for it. [PERSON] and [PERSON] [31] proposed a metaheuristic for \(P\big{|}r_{j},s_{j}\leq K_{1},p-batch,K_{i}\big{|}C_{\max}\)  (the problem where jobs have different release times). [PERSON] et al. [32] proposed a PSO method for \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\). [PERSON] et al. [33] presented a heuristic and a metaheuristic for \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\).