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$$ α > 0 is given in advance. Each job $$J_{j}$$ J j has a normal processing time $$p_j$$ p j . Two jobs $$J_i$$ J i and $$J_j$$ J j are compatible if $$\max \{p_i, p_j\} \le (1+\alpha )\cdot \min \{p_i, p_j\}$$ max { p i , p j } ≤ ( 1 + α ) · 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 $$ 1 + β α , where $$\beta _\alpha $$ β α is the positive root of the equation $$(1+\alpha )x^{2}+\alpha x=1+\alpha $$ ( 1 + α ) x 2 + α x = 1 + α .