An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities

We consider the online (over time) scheduling on a single unbounded parallel-batch machine with job processing time compatibilities to minimize makespan. In the problem, a constant \(\alpha >0\) is given in advance. Each job \(J_{j}\) has a normal processing time \(p_j\). Two jobs \(J_i\) and \(J_j\) are compatible if \(\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}\). In the problem, mutually compatible jobs can form a batch being processed on the machine. The processing time of a batch is equal to the maximum normal processing time of the jobs in this batch. For this problem, we provide an optimal online algorithm with a competitive ratio of \(1+\beta _\alpha \), where \(\beta _\alpha \) is the positive root of the equation \((1+\alpha )x^{2}+\alpha x=1+\alpha \).